Codeforces Round #712 (Div. 2) 题解

题目链接https://codeforces.com/contest/1504

这一场打的又很差，我是fw，C想不出来。

A题

题意：给你一个字符串，问你有没有办法往里添一个‘a‘，使得它不是一个回文串。

思路：显然只有整个字符串全是‘a‘才无解，否则对字符串进行扫描，对称位置不是‘a‘的地方放‘a‘即可。
代码如下

char s[N];
 
int main()
{
	IOS;
	int T;
	cin >> T;
	while(T --)
	{
		cin >> s;
		int len = strlen(s);
		bool flag = false;
		for(int i = 0 ; i < len ; i ++)
			if(s[i] != ‘a‘) flag = true;
		int d;
		if(!flag) cout << "NO\n";
		else
		{
			cout << "YES\n";
			int d;
			for(int i = 0 ; i < len ; i ++)
				if(s[len - i - 1] != ‘a‘)
				{
					d = i;
					break;
				}
			for(int i = 0 ; i < len ; i ++)
			{
				if(i == d) cout << ‘a‘;
				cout << s[i]; 
			}
			cout << "\n";
		}
	}	
	
	return 0;
}

B题

题意：给你一个01初始序列和目标序列，每次可以选择前 \(2*x\)个位置异或1（前提是选择区域的0和1个数相等），问你有没有办法变成目标序列。

思路：直接找到最长的需要变换的地方，l[i]，r[i]分别表示0~i中0和1的个数，每操作一次，都应该使得要操作的区间长度减小，模拟这个过程即可。
代码如下

char s[N];
char mb[N];
int l[N], r[N];
 
int main()
{
	IOS;
	int T;
	cin >> T;
	while(T --)
	{
		int n;
		cin >> n;
		cin >> s; 
		cin >> mb;
		if(s[0] == ‘0‘) l[0] ++;
		else r[0] ++;
		for(int i = 1 ; i < n ; i ++)
		{
			l[i] = l[i - 1];
			r[i] = r[i - 1];
			if(s[i] == ‘0‘) l[i] ++;
			else r[i] ++;
		}
		int len = -1;
		for(int i = 0 ; i < n ; i ++)
			if(s[i] != mb[i])	len = i;
		
		bool flag = true;
		int time = 1;
		while(len >= 0)
		{
			int pre = len;
			if(l[len] != r[len])
			{
				flag = false;
				break;
			}
			if(time & 1)
				for( ; len >= 0 && s[len] != mb[len] ; len --);
			else 
				for( ; len >= 0 && s[len] == mb[len] ; len --);
			time ++;
		}
		if(flag) cout << "YES\n";
		else cout << "NO\n";
		for(int i = 0 ; i < n ; i ++)	l[i] = r[i] = 0; 
	}	
	
	return 0;
}

C题

题意：给你一个01序列，问你能不能构造两个合法的括号序列a，b，使得当\(s[i] = 1时，a[i] = b[i], 当s[i] = 0时，a[i] \neq b[i]\)。

思路：首先，两个括号序列的开头一定是‘(‘，结尾一定是‘)‘，其次，由于两个左右括号之和都是n，而n是偶数，因此01序列中0的个数必须是偶数。必须满足上述条件才有解，然后构造序列的方式为，先双指针扫描左右两端的‘1‘，左边放左括号，右边放右括号，然后从头开始扫描0，轮流放左右括号，另一个序列反之即可。
代码如下

int n;
char s[N];
char ans[N];
 
 
int main()
{
	IOS;
	int T;
	cin >> T;
	while(T --)
	{
		cin >> n;
		cin >> s + 1;
		bool flag = true;
		int cnt = 0;
		if(s[1] != ‘1‘ || s[n] != ‘1‘) flag = false;
		for(int i = 2 ; i < n ; i ++)
			if(s[i] == ‘0‘) cnt ++;
		
		if(cnt & 1) flag = false;
		if(!flag) cout << "NO\n";
		else
		{
			cout << "YES\n";
			int l = 1, r = n;
			while(l < r)
			{
				while(s[l] != ‘1‘) l ++;
				while(s[r] != ‘1‘) r --;
				if(l >= r) break;
				ans[l ++] = ‘(‘, ans[r --] = ‘)‘;				
			}
			int cnt = 0;
			for(int i = 1 ; i <= n ; i ++)
				if(s[i] == ‘0‘)
				{
					cnt ++;
					if(cnt & 1) ans[i] = ‘(‘;
					else ans[i] = ‘)‘;
				}
			for(int i = 1 ; i <= n ; i ++)	cout << ans[i];
			cout << "\n";
			
			cnt = 0;
			for(int i = 1 ; i <= n ; i ++)
				if(s[i] == ‘0‘)
				{
					cnt ++;
					if(cnt & 1) ans[i] = ‘)‘;
					else ans[i] = ‘(‘;
				}
			for(int i = 1 ; i <= n ; i ++)	cout << ans[i];
			cout << "\n";	
		}
	}	
	
	return 0;
}

Codeforces Round #712 (Div. 2) 题解

原文：https://www.cnblogs.com/luoyicong/p/14615541.html