5月9日贪心考试总结
5月9日贪心考试总结
自制考试链接：https://www.luogu.org/contestnew/show/16837
这次考试没有经过任何复习，我就想知道考出来是啥样子。
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。游记部分
考前inf小时：
我：“你是复习贪心还是背地生？”
GSC大佬：“当然是复习贪心了啊！”说罢，拿出了生物书。
JMR大佬：“肯定是背地生了啊！我明天肯定会爆（A）零（K）。”
文化课大佬QHY：“JMR你肯定爆（A）零（K）”
CXY大佬：“那你呢？”说罢，拿出了生物书。
果然是神仙啊%%%。
考前0.1小时：
我：“这次绝对不会考加工生产调度问题。”
YYQ大佬：“？？？”
我：“这次肯定要考种树（区间选点）。”
YYQ大佬：“？？？”
我：“这次可能要考喷水装置。”
YYQ大佬：“？？？”
果然是神仙啊%%%。
考试时：
经过我某条以脚趾为神经中枢的反射弧做出的反应，我要按顺序开题。
看到T1（diet）：我的天哪！不是说好考贪心的吗？？？这是 ······ 什么毒瘤东西？？？
境泽曰：“甚香！”
于是我去看了T2（fruit）。这不是我做过的原题吗？使用STL几分钟切掉
然后我又回去看了T1。
境泽曰：“甚香！”
这不是道红题吗？真是尴尬。两分钟切了。
于是我去看了T3。
这是 ······ 喷水？？？完了。然后就去看了T4。
woc不是说好贪心的吗？？？这是 ······ 注明了的暴搜？？？这题我之前好像是打表过的啊？
于是我就打了个暴搜。
数据范围：n≤200，2≤k≤6。
于是我输入了200 6
2.7e-4 小时过去了......
没有输出！！！
心态崩了，要爆零了！！！
这时，CXY说过的一句话在我脑海中闪现——
"记搜不就是有技巧的搜索吗？"
于是我剪了个枝，好像没有超时。于是我又去刚T3（仿佛不叫刚）
"这次肯定要考种树（区间选点）"。
还真考到了。这不就是个种雷达吗？于是我就切了它。
这时，GSC大佬：“我觉得T3比T4难。”
%%%果然是大佬
剩下半小时，没有查错，没有对拍，而是——
和YYQ大佬颓太空弹珠？？？
考后：
于是 ...... 我就这样AK了。
题解部分
T1：
这是道签到题（至少写完后的我是这么认为的）。只需要把所有食物按脂肪从大到小排序，取最多脂肪的食物，然后把当前种类的可选个数的限制减一，当然，如果可选的个数为0，那就直接continue;。这样就可以获得最优解了。证明略。第一题真没什么好说的。
代码：
#include<iostream>
#include<cstdio>
#include<fstream>
#include<algorithm>
#include<cstring>
using namespace std;
const int MaxN=505;
int n,m,k;
int num[MaxN];
struct food {
int col,fat;
}a[MaxN];
void init()
{
freopen("diet.in","r",stdin);
freopen("diet.out","w",stdout);
}
bool cmp(food a,food b)
{
return a.fat>b.fat;
}
int main()
{
init();
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=k;i++) scanf("%d",&num[i]);
for(int i=1;i<=n;i++) scanf("%d%d",&a[i].fat,&a[i].col);
sort(a+1,a+1+n,cmp);
int cnt=0,ans=0;
for(register int i=1;i<=n;i++) {
int col=a[i].col,fat=a[i].fat;
if(num[col]>0) {
ans+=fat;
num[col]--;
cnt++;
}
if(cnt==m) break;
}
printf("%d",ans);
}T2：
要求用优先队列，那我们就用。这道题的策略肯定是每次选出最小的两堆果子，合并后再排序。当然快排很浪费，是会超时的。我们使用小根堆来实现。这种水题也没什么好说的。
我的代码：
#include<iostream>
#include<cstdio>
#include<queue>
#include<fstream>
using namespace std;
priority_queue<int,vector<int>,greater<int> >q;
int n;
inline void init()
{
freopen("fruit.in","r",stdin);
freopen("fruit.out","w",stdout);
}
int main()
{
init();
scanf("%d",&n);
for(int i=1;i<=n;i++) {
int x;
scanf("%d",&x);
q.push(x);
}
int ans=0;
while(q.size()>1) {
int x=q.top();q.pop();
int y=q.top();q.pop();
ans+=x+y;
q.push(x+y);
}
printf("%d",ans);
}T3：
这题引入了平面直角坐标系，看起来比较复杂，但实际上就是板子。我们先预处理出每个岛可被观察的区间，也就是说每个区间内要求有一个雷达。这就是区间选点的板子了。板子就没什么好说的了。
#include<iostream>
#include<cstdio>
#include<fstream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int MaxN=1005;
struct segment {
double l,r;
}a[MaxN];
int n;
double d;
int num[MaxN];
inline double calc(double y)
{
return sqrt(d*d-y*y);
}
inline void init()
{
scanf("%d%lf",&n,&d);
for(register int i=1;i<=n;i++) {
double x,y;
scanf("%lf%lf",&x,&y);
if(y>d) {
printf("-1");
exit(0);
}
double len=calc(y);
a[i].l=x-len;
a[i].r=x+len;
num[i]=1;
}
}
bool cmp(segment x,segment y)
{
return x.r<y.r;
}
inline void work()
{
int ans=0;
sort(a+1,a+1+n,cmp);
int now=0;
for(int i=1;i<=n;i++) {
double nowr=a[i].r;
if(num[i]<=0) continue;
num[i]--;
for(register int j=i+1;j<=n;j++) {
if(a[j].l<=nowr) {
num[j]--;
}
}
ans++;
}
printf("%d",ans);
}
int main()
{
init();
work();
}T4：
这道是老师故意出的超纲题。肯定不带脑子暴搜是会 T 掉的（如果傻到一种境界还会WA）。首先需要判重。在暴搜剪枝中，记last是一种常见的策略。所以我们就记一个last，每次下一个数必定大于last，这样我们搜出的组合就是单调不降的，就不会重了。然后考虑T的问题。我们发现，当下一个数过大时，就没有保持序列单调不降的可能了。所以我们再加一个可行性剪枝，枚举量就会大大减少了。
代码：
#include<iostream>
#include<cstdio>
#include<fstream>
using namespace std;
int n,k;
int ans=0;
int sum=0;
inline void init()
{
freopen("divide.in","r",stdin);
freopen("divide.out","w",stdout);
}
inline void dfs(int l,int a)
{
sum++;
if(sum==k+1) {
if(a==0)
ans++;
}
else {
for(register int i=l;i<=a-i*(k-sum);i++) {
dfs(i,a-i);
}
}
sum--;
}
int main()
{
init();
scanf("%d%d",&n,&k);
dfs(1,n);
printf("%d",ans);
}总结部分
虽然这次AK了，但仍有很多不足：
1、眼瞎。看错了多少题意？红题都能看成毒瘤？幸好我心态不差，不然就爆零了。
2、颓废。写完就颓，万一文件错了怎么办？幸好脸好，不然就爆零了。
3、急躁。写题的时候手忙脚乱的。这样容易写炸。幸好我脸好，没有炸。
1: 焦鸣睿还真爆零了
2: YYQ怎么回事？我不是说了要考种树吗？
3: GSC和CXY把T3弄成了大模拟海星
