A. Déjà Vu
A palindrome is a string that reads the same backward as forward. For example, the strings “z”, “aaa”, “aba”, and “abccba” are palindromes, but “codeforces” and “ab” are not. You hate palindromes because they give you déjà vu.

There is a string s
. You must insert exactly one character ‘a’ somewhere in s

. If it is possible to create a string that is not a palindrome, you should find one example. Otherwise, you should report that it is impossible.

For example, suppose s=

“cbabc”. By inserting an ‘a’, you can create “acbabc”, “cababc”, “cbaabc”, “cbabac”, or “cbabca”. However “cbaabc” is a palindrome, so you must output one of the other options.
Input

The first line contains a single integer t
(1≤t≤104

) — the number of test cases.

The only line of each test case contains a string s

consisting of lowercase English letters.

The total length of all strings does not exceed 3⋅105

.
Output

For each test case, if there is no solution, output “NO”.

Otherwise, output “YES” followed by your constructed string of length |s|+1

on the next line. If there are multiple solutions, you may print any.

You can print each letter of “YES” and “NO” in any case (upper or lower).
Example
Input
Copy

6
cbabc
ab
zza
ba
a
nutforajaroftuna

Output
Copy

YES
cbabac
YES
aab
YES
zaza
YES
baa
NO
YES
nutforajarofatuna

Note

The first test case is described in the statement.

In the second test case, we can make either “aab” or “aba”. But “aba” is a palindrome, so “aab” is the only correct answer.

In the third test case, “zaza” and “zzaa” are correct answers, but not “azza”.

In the fourth test case, “baa” is the only correct answer.

In the fifth test case, we can only make “aa”, which is a palindrome. So the answer is “NO”.

In the sixth test case, “anutforajaroftuna” is a palindrome, but inserting ‘a’ elsewhere is valid.
题意：
给你一个字符串，然后你可以通过在任意位置上+‘a’，然后让这个字符串不是回文字符串，如果实在无法让字符串变成非回文，则输出NO。
思路：
我们可以判断出只有全为a的回文字符串才会+‘a’后无法变成非回文串，其他的都可以在任意位置上“a”，使字符串变成非回文串，那我们可以直接在首或者尾“a”，然后循环判断是否为回文，输出非回文的那一种就可以了。
代码：

#include<bits/stdc++.h>
using namespace std;
bool judge(string p)
{for(int i=0,j=p.size()-1;i<j;i++,j--){if(p[i]!=p[j])return true;}return false;
}
int main ()
{int t;cin>>t;while(t--){string ch;cin>>ch;int f=0;for(int i=0;i<ch.size();i++){if(ch[i]!='a'){f=1;break;}}if(f==0){cout<<"NO"<<endl;}else{string ch1,ch2;ch1="a"+ch;ch2=ch+"a";if(judge(ch1)){cout<<"YES"<<endl;cout<<'a';for(int i=0;i<ch.size();i++) cout<<ch[i];cout<<endl;}else{if(judge(ch2)) {cout<<"YES"<<endl;for(int i=0;i<ch.size();i++) cout<<ch[i];cout<<'a';cout<<endl;}elsecout<<"NO"<<endl;}}}return 0;
}

B. Flip the Bits
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There is a binary string a
of length n. In one operation, you can select any prefix of a with an equal number of 0 and 1 symbols. Then all symbols in the prefix are inverted: each 0 becomes 1 and each 1 becomes 0
For example, suppose a=0111010000
since it has four 0’s and four 1’s: [01110100]00→[10001011]00
In the second operation, we can select the prefix of length 2
since it has one 0 and one 1: [10]00101100→[01]00101100
It is illegal to select the prefix of length 4
for the third operation, because it has three 0’s and one
Can you transform the string a
into the string b
using some finite number of operations (possibly, none)?
Input
The first line contains a single integer t
(1≤t≤104) — the number of test cases.
The first line of each test case contains a single integer n
(1≤n≤3⋅105) — the length of the strings a and b
The following two lines contain strings a
and b of length n, consisting of symbols 0 and 1
The sum of n
across all test cases does not exceed 3⋅105
Output
For each test case, output “YES” if it is possible to transform ainto b, or “NO” if it is impossible. You can print each letter in any case (upper or lower).
Example
Input
Copy
5
10
0111010000
0100101100
4
0000
0000
3
001
000
12
010101010101
100110011010
6
000111
110100

Output
Copy

YES
YES
NO
YES
NO

Note

The first test case is shown in the statement.

In the second test case, we transform a
into b

by using zero operations.

In the third test case, there is no legal operation, so it is impossible to transform a
into b

.

In the fourth test case, here is one such transformation:

Select the length 2

prefix to get 100101010101
.
Select the length 12
prefix to get 011010101010
.
Select the length 8
prefix to get 100101011010
.
Select the length 4
prefix to get 011001011010
.
Select the length 6
prefix to get 100110011010

In the fifth test case, the only legal operation is to transform a
into 111000. From there, the only legal operation is to return to the string we started with, so we cannot transform a into b
题意：
给你一个字符串a，b，由0,1组成，然后只有在字符串下标i前面的0,1个数相同时，你可以进行把0->1,1->0,然后看是否能进行一些操作把字符串a变成b。
思路：
这题思路有点难想，你看，它每次个数相同时，都可以进行操作，所以我们从后往前进行操作，因为如果从前往后，小区间会影响大区间的，所以从大区间向小区间进行，然后遍历字符串，将每一位的0,1的个数进行计算，然后将a，b不相同的下标进行标记为1，代表需要改变。

从后遍历，cnt进行次数，因为如果是奇数的话，才会变成不一样的数字，偶数的话，区间变化会使它变回去了，在判断当前位之前，我们先看之前的大区间的变化将当前第i位变成了什么，因为只有0,1，跟标记的0,1是代表他是否需要变化，假如说：原先为0，他后面的区间将它变化了奇数次，那么它就现在是需要变化的才能变成吧b。原先为1，它后面的区间将它变化了偶数次，就还是1。如果这个下标的标记为1，代表需要被变化，我们就判断当前位的0,1个数是否相同，相同的话就代表了一次变化cnt++，否则就退出无法变成b了，因为之后没有区间将它再次变化了。然后我们就可以判断了
代码：

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+7;
int s0[N],s1[N];
int a[N],b[N],p[N];
int main ()
{int t;cin>>t;while(t--){int n;cin>>n;string a,b;cin>>a>>b;memset(p,0,sizeof p);for(int i=0;i<n;i++){if(a[i]=='0'){s0[i]=s0[i-1]+1;s1[i]=s1[i-1];}else{s1[i]=s1[i-1]+1;s0[i]=s0[i-1];}if(a[i]!=b[i]){p[i]=1;//是否相同的标记}}int cnt=0;int f=0;for(int i=n-1;i>=0;i--){if(cnt%2==1){//奇数次才会被变化p[i]=1-p[i];}//而且必须在前面判这一步，因为你得先看后面的区间将这一位变成了什么if(p[i]){if(s0[i]==s1[i]) cnt++;//0,1相同时才可以进行一次变化else {f=1;break;}}}if(f==1){cout<<"NO"<<endl;}else{cout<<"YES"<<endl;}}return 0;
}//这个就利用了一个标记来判断当前为被影响成了什么
/*
01 01 01 01 01 01
10 01 10 01 10 10100101010101
011010101010
100101011010
011001011010
100110011010
Select the length 12
prefix to get
.
Select the length 8
prefix to get
.
Select the length 4
prefix to get
.
Select the length 6
prefix to get01 110100 00
01 001011 00
*/

C. Balance the Bits
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A sequence of brackets is called balanced if one can turn it into a valid math expression by adding characters ‘+’ and ‘1’. For example, sequences ‘(())()’, ‘()’, and ‘(()(()))’ are balanced, while ‘)(’, ‘(()’, and ‘(()))(’ are not.

You are given a binary string s
of length n. Construct two balanced bracket sequences a and b of length n such that for all 1≤i≤n if si=1, then ai=bi
if si=0, then ai≠bi
If it is impossible, you should report about it.
Input
The first line contains a single integer t
(1≤t≤104) — the number of test cases.
The first line of each test case contains a single integer n
(2≤n≤2⋅105, nis even).
The next line contains a string sof length n, consisting of characters 0 and 1.The sum of nacross all test cases does not exceed 2⋅105.
Output
If such two balanced bracked sequences exist, output “YES” on the first line, otherwise output “NO”. You can print each letter in any case (upper or lower).
If the answer is “YES”, output the balanced bracket sequences a and b satisfying the conditions on the next two lines.If there are multiple solutions, you may print any.
Example
Input
Copy
3
6
101101
10
1001101101
4
1100
Output
Copy
YES
()()()
((()))
YES
()()((()))
(())()()()
NO
Note
In the first test case, a=
“()()()” and b="((()))". The characters are equal in positions 1, 3, 4, and 6, which are the exact same positions where si=1
.In the second test case, a=
“()()((()))” and b="(())()()()". The characters are equal in positions 1, 4, 5, 7, 8, 10, which are the exact same positions where si=1
In the third test case, there is no solution.
题意：
一个n代表01串的长度，构造两个长度为n的括号序列，给你一个01串，代表着a，b两个序列串字符不相同。然后你来判断是否有合理的a，b串。有的话输出。
思路：
这题想了很久想不明白，看了大佬的题解，迷迷糊糊差不多理解吧。这题是这样的，就是：
（1）第一步得合法的字符串，所以首尾得是相同的且都为1
（2）第二步，因为01串长度为偶数，所以如果合法的话，得（ 的个数= ) 的个数，然后你想呀，假如为 ()()()()吧，然后你有一个0破坏了一个括号，但如果合法的话，是不是得还有一个0再破坏一个括号，然后被破坏的这俩个进行分配才能合理，所以如果合法的话，01串得0的个数为偶数，1的个数自然而然为偶数吧。
（3）最后一步构造，既然1的个数为偶数，首尾又都为1，所以1的个数前sum1/2个1构造为‘（ ’，后sum1/2个构造为‘）’，然后我们1的所有的目前是合法的，然后剩下的0也是偶数的，然后如果让他们合法进行分配就（ ）间接进行就可以了，然后我们根据01串将b构造出来。合法的核心就是当前位的（个数大于等于），所以我们在循环进行判断一下a，b串是否都满足，（其实我觉得这么构造出来，a必然合理呀，其实就判b就行了，我保险起见都判了）。
代码：

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+7;
char a[N],b[N];
int main ()
{int t;cin>>t;while(t--){int n;cin>>n;string s;cin>>s;if(s[0]!=s[n-1]&&s[0]!='1'){cout<<"NO"<<endl;}else{int sum1=0,sum0=0;for(int i=0;i<s.size();i++){if(s[i]=='1') sum1++;else sum0++;}if(sum1%2!=0||sum0%2!=0){cout<<"NO"<<endl;}else{int cnt1=0,cnt0=1;for(int i=0;i<n;i++){if(s[i]=='1'&&cnt1<sum1/2){a[i]='(';cnt1++;}else if(s[i]=='1'&&cnt1>=sum1/2){a[i]=')';cnt1++;}else if(s[i]=='0'&&cnt0%2==1){a[i]='(';cnt0++;}else if(s[i]=='0'&&cnt0%2==0){a[i]=')';cnt0++;}//cout<<a[i]<<endl;}for(int i=0;i<n;i++){if(s[i]=='0'){if(a[i]=='(') b[i]=')';else b[i]='(';}else{b[i]=a[i];}//cout<<b[i]<<endl;}// cout<<"YES"<<endl;int f=0;int s0=0,s1=0;for(int i=0;i<n;i++){if(a[i]=='(') s0++;else if(a[i]==')') s1++;if(s0<s1) {f=1;break;}}s0=0,s1=0;for(int i=0;i<n;i++){if(b[i]=='(') s0++;else if(b[i]==')') s1++;if(s0<s1) {f=1;break;}}if(f==0){cout<<"YES"<<endl;for(int i=0;i<n;i++) cout<<a[i];cout<<endl;for(int i=0;i<n;i++) cout<<b[i];cout<<endl;}else{cout<<"NO"<<endl;}}}}return 0;
}
/*
01 01 01 01 01 01
10 01 10 01 10 10100101010101
011010101010
100101011010
011001011010
100110011010
Select the length 12
prefix to get
.
Select the length 8
prefix to get
.
Select the length 4
prefix to get
.
Select the length 6
prefix to get01 110100 00
01 001011 00
*/