Gift Carpet（Problem - A - Codeforces）
题目大意：有一块儿地毯，上面有n行m列的字符，如果从左往右一列一列的读，可以读到“vika”，那么就输出yes，否则输出no。
思路：这里显然有个顺序，那么就很简单，不用考虑分配的问题了，直接一列一列地找就可以了。 mm
#include<bits/stdc++.h>
using namespace std;
char s[30][30];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
int flag=1;
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
if(flag==1&&s[j][i]=='v')
{
flag=2;
break;
}
if(flag==2&&s[j][i]=='i')
{
flag=3;
break;
}
if(flag==3&&s[j][i]=='k')
{
flag=4;
break;
}
if(flag==4&&s[j][i]=='a')
{
flag=5;
break;
}
}
}
if(flag==5) printf("YES\n");
else printf("NO\n");
}
}Sequence Game（Problem - B - Codeforces）
题目大意：对于一个序列a[]，我们用如下地方式生成一个序列b[]:
挑选a[1]
挑选a[i],并使a[i]满足a[i-1]<=a[i],
现给出b[],需要输出一个可能的a[]
思路：很显然如果b[]中的数第一个一定是a[]中的数，如果后一个大于前一个，那么就不用插入别的数，否则在不满足的位置前插入一个相同的数即可。
#include<bits/stdc++.h>
using namespace std;
int a[200010];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
vector<int>b;
b.push_back(a[1]);
for(int i=2;i<=n;i++)
{
if(a[i]>=b.back())b.push_back(a[i]);
else
{
b.push_back(a[i]);
b.push_back(a[i]);
}
}
printf("%d\n",b.size());
for(auto i:b) cout<<i<<" ";
printf("\n");
}
}Flower City Fence（Problem - C - Codeforces）
题目大意：给定一些木板，它们原本是从高到低竖着排列的，现在要求它们横着摆放，问得到的围栏是否和之前的相同。
另外[3,1,1]也是可以的。
思路：我们来看，竖着摆放的时候显然用的就是木板的高度，而横着摆放的时候的高度实际是木板的数量。如上图，竖着摆放时的最高为5，那么相当于有且仅有5个能够同时减1，[3,1,1]则是有且仅有3个能够同时减3.原本的高度就变成了能够横着延伸多远。横着放的时候，最初的高度是n，最短的那个长度是几，那么就是有多少个n，最短的那个有d个，那么下一个高度就是n-d，我们可以用vector<pair<int,int>>将两者产生的围墙记录下来，然后排序判断是否相等。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
map<int,int>mp;
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
mp[x]++;
}
int l=n;
vector<pair<int,int>>p1,p2;
int c=0;
for(auto it:mp)
{
int h=it.first,v=it.second;
p1.push_back({h,v});
p2.push_back({l,h-c});//这里的数量是要把之前已经访问过的减掉
l -= v;
c += h-c;
}
sort(p1.begin(),p1.end());
sort(p2.begin(),p2.end());
if(p1==p2) printf("YES\n");
else printf("NO\n");
}
}Ice Cream Balls（Problem - D - Codeforces）
题目大意：现在需要制作n个不同类型的双球冰淇淋，已知{1，1，2}可以制作{1，1}和{1,2},两种类型的冰淇淋，{1,2}可以制作{1,2}一种类型的冰淇淋，{1}什么都不可以，{1,1}可以制作{1,1}一种类型的冰淇淋。问如果恰好制作n种不同类型的冰淇淋，至少需要购买多少冰淇淋球。
思路：这题最关键的一点在于恰好，k种不同类型的冰淇淋球可以制作k*(k-1)/2种不同类型的冰淇淋，那么我们可以找出制作数小于等于n的最大的k，然后不够的补一下即可。
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
int check(int mid)
{
int ans=mid*(mid-1)/2;
if(ans<=n) return 1;
else return 0;
}
signed main()
{
int t;
scanf("%lld",&t);
while(t--)
{
scanf("%lld",&n);
int l=1,r=2e9;
while(l<r)
{
int mid=(l+r+1)/2;
if(check(mid)) l=mid;
else r=mid-1;
}
r += n-r*(r-1)/2;
printf("%lld\n",r);
}
}Kolya and Movie Theatre(Problem - E - Codeforces)
题目大意：现在新开了一家电影院，一共有n部电影，每天上映一部，小k每天可以看一部，最多看m天，每部电影有一个娱乐值，而小k隔得越久去电影院，实际获得的娱乐值越小。举个例子，d=2，a=[3,2,5,4,6],那么如果选择看第一部电影，实际的获取的娱乐值就是3-(1-0)*2,如果看完第一部电影后再去看第三部电影，那么从第三部电影中获取的娱乐值就是5-(3-1)*d,如果只看这两部电影，那么总的娱乐值就是两者的和。
思路：这里娱乐值要改变显然很麻烦，我们看看实际减少的量是什么，如上例子中实际减少的是（1-0+3-1）*d=3*d，多看几个样例就会发现，这个减少的值就是选择的天数中，最后一天的下标乘d。那么我们可以来讨论以谁作为最后一天，进而找出最大值。这里还需要维护第i天之前最多选m-1天得到的娱乐值最大，那么显然就是当之前选择的超过m天后，将娱乐值小的弹出来，那么用优先队列维护就行。另外注意可能会爆int
#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[200010];
signed main()
{
int t;
scanf("%lld",&t);
while(t--)
{
int n,m,d;
scanf("%lld%lld%lld",&n,&m,&d);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
int sum=0,mx=0;
priority_queue<int,vector<int>, greater<int>>p;
for(int i=1;i<=n;i++)
{
if(a[i]<0) continue;
while(p.size()>m-1)
{
sum-=p.top();
p.pop();
}
sum += a[i];
mx=max(mx,sum-i*d);
p.push(a[i]);
}
cout<<mx<<endl;
}
}Magic Will Save the World（Problem - F - Codeforces）
题目大意：现在有n个怪兽，小v每秒可以积攒w单位水能量和f单位火能量，每个怪兽有一个生命值，小v杀死一只怪兽只能用一种能量，问小v想要杀死所有的怪兽最少需要多少秒。
思路：显然，对于小v来说，她可以不断积攒能量然后在最后一秒再发动攻击。和她在过程中发动攻击是等价的。那么实际上就是将这些怪兽分成两堆，一堆的生命值总和小于总的火能量，一堆生命值的总和小于总的水能量，要求最少，那么二分即可。我们该如何实现check函数呢，首先可以利用01背包预处理出来从n个数中任选可以组成哪些数，sum-c(c为可以组出来的数)则为另一堆，只需要判断在当前情况下是否存在两堆生命值一堆小于火能量总和，一堆小于水能量总和即可。
#include<bits/stdc++.h>
using namespace std;
using namespace std;
#define int long long
int dp[1000010],a[100010];
int w,f,sum;
int check(int mid)
{
int ax=w*mid,bx=f*mid;
for(int i=min(sum,ax);i>=1;i--)//这里sum可能小于ax，但是也可能大于，所以我们在两者中取小
{
if(dp[i])
{
if((i<=ax&&sum-i<=bx)||(i<=bx&&sum-i<=ax)) return 1;
}
}
return 0;
}
signed main()
{
int t;
scanf("%lld",&t);
while(t--)
{
scanf("%lld%lld",&w,&f);
int n;
scanf("%lld",&n);
sum=0;
for(int i=1;i<=n;i++) scanf("%lld",&a[i]),sum+=a[i];
memset(dp,0,sizeof dp);
dp[0]=1;
for(int i=1;i<=n;i++)
{
for(int j=sum;j>=a[i];j--)
{
dp[j]+=dp[j-a[i]];
}
}
int ti=(sum/w+1,sum/f+1);
int l=1,r=ti;
while(l<r)
{
int mid=(l+r)/2;
if(check(mid)) r=mid;
else l=mid+1;
}
cout<<l<<endl;
}
}ps：这题差不多是先由最小联系到二分，再由二分的条件联系到分堆，再由分堆联系到通过01背包找所有合法的情况进而分堆，至此题目解决。剩下的就是一些细节上的问题了。
