Buttons(Problem - A - Codeforces)
题目大意：有三排按钮数量分别为a,b,c，第一排只能由A按下，第二排只能由B按下，第三排可以被任意一个人按下，问两人轮流游戏，谁没有可以按的谁输，问如果都发挥最佳状态，谁会胜利。A先开始。
思路：显然是个简单的博弈论问题，为了保证对方没有按钮可以按，那么两者都先去按公共部分的按钮，然后再去按自己的。
如果公共按钮的个数为奇数，那么A按下最后一个公共按钮，B按一下自己的按钮后，又转换成A先手问题，那么就看谁的多，谁赢，如果一样那么就是B胜利。
如果为偶数，那么B按下最后一个公共按钮。直接看两者谁多谁赢，如果相等那么就是B赢。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
if(c%2) b--;
if(a>b) printf("First\n");
else printf("Second\n");
}
}The Walkway（Problem - B - Codeforces）
题目大意：一条路上有n个长凳和m个卖饼干的商家，小p带了无限块饼干，她将在满足以下条件的时候吃饼干：
1.从来没吃过
2.已经走过d个长凳还没吃
3.遇到卖饼干的商家
问如果删除一个卖饼干的商家，她最少吃多少块，在她吃的块数最少的情况下，最多有几个商家可以作为被删除的那一个。
思路：一排商家，删除某个，显然是贪心问题，贪心问题的核心就是找到不被影响的局部最优解。那么我们就要看看一个商家被删除带来的影响最多能延伸到哪里：
如图，显然c被删除后，a,b之间吃饼干的位置会发生改变，但是a之前和b之后的情况是不变的，因为只能删除一个，所以a,b是正常要吃饼干的，并不会影响这个区间之外的地方。那么c对这个区间内部的影响，我们可以先不考虑a,b位置，只看中间如果删除c的话会吃多少饼干。那么显然就是(b-a)/d-((b-a)%d==0),因为如果(b-a)%d==0,那么就说明b被算进去了，此时我们是不计算b的，只考虑中间部分。然后再看加上c之后会吃多少饼干:(c-a)/d-((c-a)%d)+(b-c)/d-((b-c)%d)+1,这里在算ac段的时候先把c去掉，最后再加起来，防止算重。那么如果去掉后要吃的饼干变少了，很显然就可以去掉。最后一个点再单独讨论一下即可，因为最后一个点后面没有了，而n位置可能会因为它的去掉要加1个，所以要单独讨论清楚。
现在还有一个地方需要证明，就是我们去掉后，如果能减少，那么不管去掉哪里减少的是一样的，这个我是有个地方没写完善，交了通过了才知道，但实际上用map统计一下也不麻烦。既然写题解，那么咱们还是不水，就用map统计一下就是。
#include<bits/stdc++.h>
using namespace std;
int s[200010];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,m,d;
scanf("%d%d%d",&n,&m,&d);
s[0]=1;
for(int i=1;i<=m;i++) scanf("%d",&s[i]);
int cnt=0,mx=0;
map<int,int>mp;
for(int i=1;i<m;i++)//先不看最后一个
{
int a=s[i-1],b=s[i+1],c=s[i];
int q=(b-a)/d- ((b-a)%d==0?1:0);
int nq=(c-a)/d- ((c-a)%d==0?1:0) +(b-c)/d- ((b-c)%d==0?1:0) +1;
if(nq>q) cnt++,mx=max(mx,nq-q),mp[nq-q]++;
}
//
int q=(n-s[m-1])/d;
int nq=(s[m]-s[m-1])/d-((s[m]-s[m-1])%d==0)+(n-s[m])/d+1;
if(nq>q) cnt++,mx=max(mx,nq-q),mp[nq-q]++;
int ans=0,tmp=1;//tmp标记左端点有没有被计算过
for(int i=1;i<=m;i++)
{
ans += (s[i]-s[i-1])/d+tmp;
if((s[i]-s[i-1])%d) tmp=1;//当前的右端点会变成下一个区间的左端点，所以要看这里有没有被计入
else tmp=0;
}
//s[m]-n
ans += (n-s[m])/d+tmp;//先统计出一个都不删的情况
if(mp[mx]==0) cnt=m;//有可能去掉任何一块都不能产生改变
else cnt=mp[mx];
printf("%d %d\n",ans-mx,cnt);
}
}Yet Another Permutation Problem（Problem - C - Codeforces）
题目大意：现在有一个排列a[],我们以此来构造一个数组d[],使d[i]=gcd(a[i],a[i%n+1]),要使d[]中不同的种类数最多，输出排列的顺序。
思路：这里实际上就是a[i]和它后面那个数取最大公因数，a[n]和a[1]取最大公因数。我们如果按顺序排列，那么所有的d[i]都是1，显然是不合适的。那么如何才能使种类数尽可能的多呢，显然就是需要将有倍数关系的放在一块儿。那么具体该怎么排呢，我们先把样例中的输出的d[]算出来，那么我们后续构造的时候，就可以用构造结果与之比较了。我们尝试直接把每个数的二倍放在它后面，剩下的随便放，发现构造出来的d[]和样例的d[]相同，一交果然ac。
#include<bits/stdc++.h>
using namespace std;
int st[100010];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
vector<int>p;
memset(st,0,sizeof st);
for(int i=1;i<=n;i++)
{
if(!st[i])
{
int d=i;
while(d<=n)
{
if(!st[d])p.push_back(d);
st[d]=1;
d *= 2;
}
}
}
for(auto it:p) printf("%d ",it);
printf("\n");
}
}Trees and Segments （Problem - D - Codeforces）
题目大意：现在有一排树，其中只有橡树和冷杉两种树，橡树用0表示，冷杉用1表示，现在我们可以进行k次反转操作，质检员来检查的标准是a*l0+l1,a是质检员喜欢的数，l0是0的个数，l1是1的个数。a是在1-n之间的数，我么想要知道a在取不同的值的情况下，a*l0+l1的最大值是多少。
思路：我们可以去枚举连续0的区间[l,r]，假设这段区间要符合要求需要修改c次，那么还剩下k-c次修改操作，我们如果能找出在这么多次操作的情况下[1,l-1],[r+1,n]中可以获得的连续1的最大长度，那么问题就解决了。
所以现在的问题就转变成获得在不超过任意操作次数下，[1,l-1]和[r+1,n]中连续1的最大长度，这个可以用dp来处理。
我们一段一段来看：
先看前半段，定义dp[i][j]表示前i个中，操作次数不超过j次的情况下连续1的最大长度。
那么我们来看状态转移如何计算：
首先按照最后一个划分，那么就是第i个选不选的问题：
如果第i个不选，那么就是前i-1个，操作次数不超过j的情况下连续1的最大长度
如果第i个选，那么就是从i往前延伸，在操作不超过j的情况下最多能延伸到的位置。
我们先暴力实现一下再考虑优化：
for(int i=1;i<=n;i++)//以i为结尾
{
for(int j=0;j<=k;j++)
{
dp[i][j]=dp[i-1][j];//第i个不选
int c=0,z;
for(z=i;z>=1;z--)
{
if(a[z]=='0') c++;
if(c==j) break;
}
dp[i][j]=max(dp[i][j],i-z+1);
}
}显然这里的三重循环时间复杂度有点高。
我们很容易发现，在第三层循环中有一些位置虽然没有到j，但是却可以用来更新操作不超过c的情况下的值，那么我们不如就来实时更新一下。另外第i个不选，无论是对哪个j来说，都是从前一个转移而来，我们可以把它独立出来。
另外这里我们可以先不限制操作次数，最后调用的时候限制一下即可。
for(int i=1;i<=n;i++)//以i为结尾
{
for(int j=0;j<=n;j++) p[i][j]=p[i-1][j];//第i个不选
int c=0;
for(int z=i;z>=1;z--)
{
if(a[z]=='0') c++;
p[i][c]=max(p[i][c],i-z+1);
}
for(int j=c;j<=k;j++) p[i][j]=max(p[i][j],p[i][c]);//这里不超过c的，自然也不超过大于c的情况，所以我们还是一并更新一下
}ps：为了与后缀区分，改成p
那么这里的时间复杂度就变成O(n^2)了。我们想要的也都更新出来了。
对于后缀的更新和这个同理：
for(int i=n;i>=1;i--)//以i为开头
{
for(int j=0;j<=n;j++) q[i][j]=q[i+1][j];
int c=0;
for(int j=i;j<=n;j++)
{
if(a[j]=='0') c++;
q[i][c]=max(q[i][c],j-i+1);
}
for(int j=c;j<=k;j++) q[i][j]=max(q[i][j],q[i][c]);
}至此我们前缀后缀都处理出来了，那么现在实际上可以直接嵌套循环去枚举区间了，但是有一点要注意，我们最后要的只是不同a时的结果，枚举区间的时间复杂度是O(n^2),如果再嵌套一层a，那么就是O(n^3)，显然时间复杂度高了。但是我们注意到，讨论a的时候，我们只关心l0和l1的值，对于它们是哪段区间的并不关心，那么我们就可以先枚举区间找出不同的l0对应的l1的值，然后在遍历a的时候只用遍历l0的值即可。
for(int i=1;i<=n;i++)
{
int c=0;
for(int j=i;j<=n;j++)
{
if(a[j]=='1') c++;
int d=j-i+1;
f[d]=max(f[d],max(p[i-1][k-c],q[j+1][k-c]));
}
}注意到，这里我们没有f[0]的情况，f[0]的话，那么就是全为1，不一定能得到这种情况，因为最多只能操作k次，但是如果能得到，那么1的个数应该是p[n][k],如果不能得到的话，也会有另一个值大于f[0]的情况，不会取到，所以，我们可以就令f[0]=p[n][k],至此就差不多解决了，最后再枚举一下a即可。
#include<bits/stdc++.h>
using namespace std;
int p[3010][3010],q[3010][3010],f[4000],ans[4000];
char a[4000];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,k;
scanf("%d%d",&n,&k);
memset(f,-0x3f,sizeof f);
memset(ans,-0x3f,sizeof ans);
scanf("%s",a+1);
for(int i=0;i<=n+1;i++)//前缀用到i-1,后缀用到i+1
for(int j=0;j<=n;j++)
p[i][j]=q[i][j]=0;
for(int i=1;i<=n;i++)//以i为结尾
{
for(int j=0;j<=n;j++) p[i][j]=p[i-1][j];//第i个不选
int c=0;
for(int z=i;z>=1;z--)
{
if(a[z]=='0') c++;
p[i][c]=max(p[i][c],i-z+1);
}
}
for(int i=n;i>=1;i--)//以i为开头
{
for(int j=0;j<=n;j++) q[i][j]=q[i+1][j];
int c=0;
for(int j=i;j<=n;j++)
{
if(a[j]=='0') c++;
q[i][c]=max(q[i][c],j-i+1);
}
}
for(int i=1;i<=n;i++)
{
int c=0;
for(int j=i;j<=n;j++)
{
if(a[j]=='1') c++;
if(c>k) break;
int d=j-i+1;
f[d]=max(f[d],max(p[i-1][k-c],q[j+1][k-c]));
}
}
f[0]=p[n][k];
for(int i=1;i<=n;i++)
{
for(int j=0;j<=n;j++)
{
ans[i]=max(ans[i],i*j+f[j]);
}
}
for(int i=1;i<=n;i++) printf("%d ",ans[i]);
printf("\n");
}
}这道题的核心点在于它要求在有条件限制下两个连续区间的最大长度，其实和(问题 H: 再会，谢谢所有的鱼 - BUCTOJ)这道题有点像，都是要找到两个不相交的连续区间，不过一个是要找区间的最长长度，一个是要找区间中的最大和，本质上都是要处理出以某个点为端点的一段区间的某个值，这里的这道题涉及到一个很妙的优化思路，就是上面所写的将三层循环降至两层循环的过程，因为很显然在查找的过程中，j是单增的关系，那么我们就可以在遍历的时候实时更新，进而降低时间复杂度。
