Codeforces Round #516 (Div. 2, by Moscow Team Olympiad) A，B，C，D，E

题目链接

A Make a triangle!

题意：给定三条线段，问怎么延长最少并能构成一个三角形。

题解：看两条小边是否大于最长的那条边，大于输出0，不大于则输出最长边长度加1减去两条最小边的和，这样保证答案最小。

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a,b,c;
	cin>>a>>b>>c;
	if(a+b<=c||a+c<=b||b+c<=a){
		if(a>b&&a>c){
			cout<<a-b-c+1<<endl;
		}
		else 
		if(b>a&&b>c){
			cout<<b-a-c+1<<endl;
		}
		else 
		if(c>b&&c>a){
			cout<<c-b-a+1<<endl;
		}
	}
	else cout<<0<<endl;
}

 

 

B. Equations of Mathematical Magic

题意：给定a，给定公式：a−(a⊕x)−x=0；问有多少个x满足条件。

题解：根据公式可以得出：(a⊕x)=a−x，然后就能发现当a二进制某一位为0时，只要x那一位满足为0就能满足条件，最后就变成求a在二进制下1的个数，然后求pow(2,sum);

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		int n;
		cin>>n;
		int ans=0;
		while(n){
			if(n&1) ans++;
			n>>=1;
		}
		cout<<pow(2,ans)<<endl;
	}
 } 

 

 

C. Oh Those Palindromes

题意：给定一个字符串，可以进行重新排列，问怎么构造能使得它的子串为回文串的个数最多。

题解：不难发现(其实一开始我也没发现qwq)ololo的子串为9，而oooll的子串也为9。所以排序就完事了。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+100;
char s[maxn];
int main()
{
	int n;
	cin>>n>>s+1;
	sort(s+1,s+1+n);
	cout<<s+1;
}

 

 

D. Labyrinth

题意：给定一个迷宫，给定初始位置，给定可以向左走的次数以及向右走的次数，上下走没有限制，' . '表示可以走，' * '表示不能走。问最多可以走到多少个点。

题解1：使用bfs模拟行走的路程，记录到达每个点的向左走的次数以及向右走的次数。为了保证到达每个点的向左走和向右走的次数最少，每次优先上下走。能上下走就先上下走，然后再左右走。使用双向队列，如果是上下行走就放到队首，如果是左右行走就放到队尾。

#include<bits/stdc++.h>
using namespace std;
char s[2010][2010];
int n,m,sx,sy,l,r,ans,vis[2010][2010];
int d[5][3] = {{1,0},{-1,0},{0,-1},{0,1}};
struct node{
	int x,y,l,r;
};
int check(int nx,int ny){
	if(nx<1||ny<1||nx>n||ny>m||vis[nx][ny]||s[nx][ny]=='*')
	return 0;
	return 1;
}
void bfs()
{
	deque<node>q;//双向队列 
	vis[sx][sy]=1;ans++;
	q.push_back(node{sx,sy,l,r});
	while(!q.empty())
	{
		node t = q.front();q.pop_front();
		for(int i=0;i<4;i++){
			int nx = t.x + d[i][0];
			int ny = t.y + d[i][1];
			if(check(nx,ny)){
				if(i<2){//上下走 
					q.push_front(node{nx,ny,t.l,t.r});//将上下走优先放进队列队首 
					vis[nx][ny]=1;
					ans++;
				}
				if(i==2&&t.l>=1){//向左走 
					q.push_back(node{nx,ny,t.l-1,t.r});//放进队尾 
					vis[nx][ny]=1;
					ans++;
				}
				if(i==3&&t.r>=1){//向右走 
					q.push_back(node{nx,ny,t.l,t.r-1});//放进队尾 
					vis[nx][ny]=1;
					ans++;
				}
			}
		} 
	}
}
int main()
{
	
	cin>>n>>m>>sx>>sy>>l>>r;
	for(int i=1;i<=n;i++) cin>>s[i]+1;
	bfs();
	cout<<ans<<endl;
}

题解2：使用普通队列，以及记忆化搜索。如果发现这个点已经入过队列了，那么当前这个点还能入队的唯一要求就是我能向左走或者向右走的次数大于之前的结点，这样才能保证答案最优。

#include<bits/stdc++.h>
using namespace std;
int n,m,sx,sy,l,r,ans;
char s[2010][2010];
int vis[2010][2010][3];
int d[5][3] = {{1,0},{-1,0},{0,-1},{0,1}};
struct node{
	int x,y,l,r;
};
int check(int nx,int ny,int L,int R){
	if(nx<1||ny<1||nx>n||ny>m||s[nx][ny]=='*'||L<0||R<0)
	return 0;
	if(L<=vis[nx][ny][1]&&R<=vis[nx][ny][2]) //如果L以及R没有1个满足要求。 
	return 0;
	return 1;
}

void bfs()
{
	queue<node>q;
	q.push(node{sx,sy,l,r});vis[sx][sy][0]=1;ans++;
	while(!q.empty())
    {
    	node t=q.front();q.pop();
    	for(int i=0;i<4;i++){
    		int nx = t.x + d[i][0];
			int ny = t.y + d[i][1];
			int L = t.l , R = t.r; 
			if(i==2) L--;
			if(i==3) R--;
    		if(check(nx,ny,L,R)){
    			if(vis[nx][ny][0]==-1) ans++;//如果这个结点没有走过 
    			q.push(node{nx,ny,L,R});
    			vis[nx][ny][0]=1;
				vis[nx][ny][1]=L;//保存nx，ny这个点能向左走的距离 
				vis[nx][ny][2]=R;//能向右走的距离 
			}
		}
	}
}
int main()
{
	cin>>n>>m>>sx>>sy>>l>>r;
	memset(vis,-1,sizeof vis);
	for(int i=1;i<=n;i++) cin>>s[i]+1;
	bfs();
	cout<<ans<<endl;
}

 

 

 

E. Dwarves, Hats and Extrasensory Abilities

题意：交互题，看到交互就用二分orz。在直角坐标系第一象限上(范围0到1e9)，你可以询问n个点，对于每个点都有一个颜色（黑或白）。要你输出一条直线使得同色的点在这条直线的一侧。

题解：直接二分一条直线就行了，首先询问(0,0)这个点定为白色，然后二分(0，1e9)，每次询问mid这个点，如果是白色就l=mid；否则就r=mid；但是因为要将两个平面分开，所以我们要从y=1开始二分。具体题解：题解

#include<bits/stdc++.h>
using namespace std;
string sa,s;
int main()
{
	int n;
	cin>>n;
	int l=0,r=1e9;
	printf("0 1\n");
	cin>>sa;
	for(int i=1;i<n;i++){
		int mid = (l+r)>>1;
		printf("%d 1\n",mid);
		cin>>s;
		if(s==sa) l = mid;
		else r = mid;
	}
	printf("%d 0 %d 2\n",l,r);
 }