Codeforces Round #516 (Div. 2, by Moscow Team Olympiad) 划水题解

由于博主水平较低，只有A到E题的题解。

A
题面大意是，给出三条边长度，每分钟能够使其中一条边的长度加一。求最短多长时间能使三条边组成三角形。

题解：
考虑贪心，由于比较简单，就直接放代码了。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int a[4];
int main()
{
	cin>>a[1]>>a[2]>>a[3];
	sort(a+1,a+4);
	if(a[1]+a[2]>a[3]){
		puts("0");
		return 0;
	}
	cout<<a[3]-a[2]-a[1]+1;
	return 0;
}

B
题目大意 ： 求 a−(a xor x)−x = 0 有多少组解

题解 ：我们可以把a写成二进制，显然当a−(a xor x)−x = 0时 ，a-(a xor x) = x。所以 x即a的二进制位组成的子集。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int n;
int a,cnt;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a);
		cnt=0;
		while(a)
		{
			if(a&1) cnt++;
			a>>=1;
		}	
		int ans=1<<cnt;
		if(cnt){
			cout<<ans<<endl;
		}
		else puts("1");
	}
	return 0;
}

C
题目大意 给定一个字符串，可随意变换字符位置，使变换后的字符串 的回文子串的数量最大。

这算是一道脑筋急转弯题吗 QAQ 代码在这里 你可以看一看 然后想想为什么

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 1e5+100;
int n;
char s[maxn];
int main()
{
	scanf("%d",&n);
	scanf("%s",s+1);
	sort(s+1,s+1+n);
	cout<<s+1<<endl;
	return 0;
}

D
题目大意 规定左右行走步数的bfs 问最终能覆盖几个格。

多传几个参数的BFS 我的代码有一丝混乱

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
const int maxn = 2010;
int n,m,r,c,x,y,ans;
char s[2010][2010];
queue<int> Q;
struct node
{
	int x,y,X,Y;
	bool vis;
}T[maxn][maxn];
int xx[4]={0,1,-1,0},yy[4]={1,0,0,-1};
void bfs(int r,int c)
{
	Q.push(r);Q.push(c);Q.push(x);Q.push(y);
	T[r][c]=(node){r,c,x,y,1};
	while(!Q.empty())
	{
		int x1=Q.front();Q.pop();
		int y1=Q.front();Q.pop();
		int X=Q.front();Q.pop();
		int Y=Q.front();Q.pop();
		for(int i=0;i<4;i++)
		{
			if(i==3&&!X) continue;
			if(i==0&&!Y) continue;
			int XX=x1+xx[i],YY=y1+yy[i];
			if(XX<=0||XX>n||YY<=0||YY>m||s[XX][YY]=='*') continue;
			int X_n=X,Y_n=Y;
			if(i==3) X_n--;
			if(i==0) Y_n--;
			if(!T[XX][YY].vis)
			{
				T[XX][YY]=(node){XX,YY,X_n,Y_n,true};
				Q.push(XX);Q.push(YY);Q.push(X_n);Q.push(Y_n);
			}else if(X_n>T[XX][YY].X||Y_n>T[XX][YY].Y){
				T[XX][YY]=(node){XX,YY,X_n,Y_n,true};
				Q.push(XX);Q.push(YY);Q.push(X_n);Q.push(Y_n);
			}
		}
	}
}
int main()
{
	scanf("%d%d%d%d%d%d",&n,&m,&r,&c,&x,&y);
	for(int i=1;i<=n;i++)
	{
		scanf("%s",s[i]+1);
	}
	bfs(r,c);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(T[i][j].vis) ans++;
		}
	}
	printf("%d",ans);
	return 0;
}

E
E题是一个交互题。意思是在一个棋盘上，你输出n个点 机器会告诉你它的颜色是黑还是白。
你需要使一条线分割整个棋盘，使棋盘一边全是黑色点，棋盘另一边全是白色点。最终还要输出这条直线上的两个点（两点确定一条直线）

本人考虑的是二分，即在里的最近的黑色点和白色点之间二分（棋盘足够大1e9 够放） 之后根据中间点的颜色更新可二分的区间。注意处理一下前两个点的颜色就行。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define LL long long
using namespace std;
LL l=0,r=1e9,mid;
int n,B,W;
char op[5];
int cur;
int main()
{
	scanf("%d",&n);
	cout<<"0 1"<<endl;
	scanf("\n%s",op);
	if(op[0]=='b') cur=1;
	else cur=0;
	for(int i=2;i<=n;i++)
	{
		if(cur)
		{
			mid=(l+r)>>1;
			cout<<mid<<" 1"<<endl;
			scanf("\n%s",op);
			if(op[0]=='b') l=mid;
			else r=mid;
		}else{
			mid=(l+r)>>1;
			cout<<mid<<" 1"<<endl;
			scanf("\n%s",op);
			if(op[0]=='b') r=mid;
			else l=mid;
		}
	}
	cout<<r<<" 2 "<<l<<" 0";
	return 0;
}