Codeforces Round #516 (Div. 2, by Moscow Team Olympiad)ABCD总结
这场比赛发挥比较稳，在比赛开始45分钟后 ABCD全是1A，并且最终过了终测。rating还没出来，终测完rank146，希望能多上一点分吧。（这次代码放后面）E题互动题，依然不会做，待补。
A：给你三根木棒的长度，问你至少增加（任意一根木棒）多长长度才能使这三根木棒能够成三角形。签到题，排序后答案就是
max(0,c-b-a+1)。
B：给你a(0<=a<2e30) 求满足a−(a⊕x)−x=0的x有多少个。打表很容易发现答案就是2的(a的二进制中1的数量)次方。
C：给一个长度为n的字符串，你把这些字符串中的字符重新排序，使得排序后串的本质不同回文串数量最多。之前做过一道构造题，自己在纸上画画也不难发现，只需要对每一个字符相同的连起来就可以了。
（补：长度为n的字符串的本质不同回文串数量最多为n。最少要看串中有几个字母。）
D：这题可谓终测挂了一大片，就是给你一个n*m的地图，'*'表示墙，不能走，'.'表示空地，可以走。给你你的起点坐标(nn,mm)，你可以上下左右移动，每次移动一个单位，但是你左往左移动的次数不超过x，往右移动的次数不超过y。问你有多少格子是你能到达的。
其实不难发现到达一个格子所消耗的往左、往右步数的最小值是唯一的。所以只需要记录到达这个点往左往右的最小步数即可。如果有更小的方案才加入队列。我的代码跑了186ms，还是比较快的。
放上一张D题终测的截图：（侵删）
真是壮观！
代码：
A：
#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=200010;
int n,m,k;
int a[maxn],sum[maxn];
int c[maxn];
int ans,ct,cnt,tmp,flag;
char s[maxn];
int main()
{
int T,cas=1;
while(scanf("%d%d%d",&n,&m,&k)!=EOF)
{
if(n+m>k&&n+k>m&&m+k>n) ans=0;
else
{
ans=min(abs(k-(n+m)+1),abs(n-(k+m)+1));
ans=min(ans,abs(m-(n+k)+1));
}
printf("%d\n",ans);
// if(flag) puts("Yes"); else puts("No");
}
return 0;
}B：
#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=200010;
int n,m,k;
int a[maxn],sum[maxn];
int c[maxn];
int ans,ct,cnt,tmp,flag;
char s[maxn];
int fcount(int x) //求数x二进制下所含1的个数
{
int s=0;
while(x){
s++;
x&=(x-1);
}
return s;
}
int main()
{
int T,cas=1;
n=20;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
ll ii=pow(2,fcount(n));
cout<<ii<<endl;
//printf("%d\n",ans);
// if(flag) puts("Yes"); else puts("No");
}
return 0;
}C：
#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=200010;
int n,m,k;
int a[maxn],sum[maxn];
int c[maxn];
int ans,ct,cnt,tmp,flag;
char s[maxn];
int main()
{
int T,cas=1;
scanf("%d",&n);
scanf("%s",s);
memset(c,0,sizeof(c));
for(int i=0;i<n;i++)
{
c[s[i]-'a']++;
}
for(int i=0;i<26;i++)
{
while(c[i]--)
{
char ch=i+'a';
cout<<ch;
}
}
cout<<endl;
//printf("%d\n",ans);
// if(flag) puts("Yes"); else puts("No");
return 0;
}D：
#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=2010;
int n,m,k,nn,mm;
int a[maxn],sum[maxn];
int c[maxn][maxn],cc[maxn][maxn];
int ans,ct,cnt,tmp,flag;
char s[maxn][maxn];
int X,Y;
struct node
{
int x,y;
int zuo,you;
node(){zuo=0;you=0;}
node(int a,int b){x=a;y=b;zuo=0;you=0;}
};
int dxy[]={1,0,-1,0,0,1,0,-1};
bool jud(int x,int y)
{
if(x<0||x>=n||y<0||y>=m) return 0;
return 1;
}
void bfs(int ii,int jj)
{
ans=0;
memset(c,-1,sizeof(c));
memset(cc,-1,sizeof(cc));
queue<node>q;
q.push(node(ii,jj));
c[ii][jj]=cc[ii][jj]=0;ans++;
while(!q.empty())
{
node kk,k=q.front();
q.pop();
for(int i=0;i<4;i++)
{
kk=k;
int x=k.x+dxy[i],y=k.y+dxy[i+4];
if(!jud(x,y)) continue;
if(s[x][y]=='*') continue;
if(i==1) kk.you=k.you+1;
if(kk.you>Y) continue;
if(i==3) kk.zuo=k.zuo+1;
if(kk.zuo>X) continue;
if(c[x][y]!=-1&&cc[x][y]!=-1&&c[x][y]<=kk.zuo&&cc[x][y]<=kk.you)
continue;
if(c[x][y]==-1||cc[x][y]==-1) ans++;
//cout<<x<<" "<<y<<endl;
if(c[x][y]==-1||c[x][y]>kk.zuo)
c[x][y]=kk.zuo;
if(cc[x][y]==-1||cc[x][y]>kk.you)
cc[x][y]=kk.you;
kk.x=x;kk.y=y;
q.push(kk);
}
}
printf("%d\n",ans);
}
int main()
{
int T,cas=1;
scanf("%d%d",&n,&m);
scanf("%d%d",&nn,&mm);
scanf("%d%d",&X,&Y);
for(int i=0;i<n;i++)scanf("%s",s[i]);
bfs(nn-1,mm-1);
//printf("%d\n",ans);
// if(flag) puts("Yes"); else puts("No");
return 0;
}