A. Déjà Vu
题意：有n个字符串，有一次操作在字符串任意位置填一个字符‘a’，求是否能构成一个非回文串，如果不能则输出NO能则输出添加一个’a’之后形成的非回文串。
思路：不难想到如果全是由字符a构成的字符串是NO，其他都有对应解，然后加在首尾的两种情况肯定是顶多只有一种会构成回文串，特判一下就好=。=判断的时候脑子短了。
#include<bits/stdc++.h> using namespace std; int main () { int n,i,j,t; string s1; cin>>t; while(t--){ cin>>s1; int f=0; for(i=0;i<s1.length();i++){ if(s1[i]!='a') f=1; } if(f==0){ cout<<"NO"<<endl; } else { cout<<"YES"<<endl; string s2; int d1=0; while(1){ for(i=0;i<s1.length();i++){ if(i==d1) s2+='a'; s2+=s1[i]; } string s3=s2; reverse(s2.begin(),s2.end()); if(s3!=s2){ cout<<s3<<endl; break; } d1=s1.length()-1; s2=""; } } } }
B. Flip the Bits
题意：给你两个字符串a、b，可以修改无限次，每次修改可以使得前缀的0和1相同的字符串的0变成1,1变成0。
思路：直接模拟就好，不会t，因为能操作的时候一定是0和1相同的时候，如果操作完会生成两种字符串，一种是反转一种是原串，如果其中有一种串能和答案串匹配那么就继续，然后指针从下一位开始。
总结：哎，又被这么简单的题卡了那么久= =，下次一定从b开始就仔细读题，由于上场没读明白被卡了一晚上x，这次猛冲完发现只能改前缀并且0和1相同。
#include<bits/stdc++.h> using namespace std; int main() { std::ios::sync_with_stdio(false); cin.tie(NULL); string s1,s2; int n,i,j,t; cin>>t; while(t--){ cin>>n>>s1>>s2; int m1=0,c0=0,c1=0,flag=0; for(i=0;i<n;i++){ if(s1[i]=='0') c0++; else c1++; if(c1==c0){ string s3; for(j=m1;j<=i;j++){ if(s1[j]=='0') s3+='1'; else s3+='0'; } if(s3!=s2.substr(m1,i-m1+1)&&s1.substr(m1,i-m1+1)!=s2.substr(m1,i-m1+1)){ flag=1; break; } else { m1=i+1; } } } string s3; if(s1.substr(m1,i-m1+1)!=s2.substr(m1,i-m1+1)){ flag=1; } if(flag==1){ cout<<"NO"<<endl; } else { cout<<"YES"<<endl; } } }
C. Balance the Bits
题意：给你个01串，求两个字符串ab，看是否能使得ab左右括号匹配，当01串其中某一位的位置为0，则ab串的括号必须相反，如果为1，则a和b串的括号必须相同
思路：将前半部分的1全部改成“（”,后半部分的1全部改成‘）’，再把0按照括号匹配做一下即可。
#include<bits/stdc++.h> using namespace std; int main() { string s1; int t,n,i,j; cin>>t; while(t--){ cin>>n>>s1; string s2,s3; int cnt1=0,flag=0,cnt0=0; for(i=0;i<s1.length();i++){ if(s1[i]=='1') cnt1++; } if(s1[i]=='0'||s1[n-1]=='0') flag=1; int a=0,b=0; for(i=0;i<s1.length();i++){ if(s1[i]=='1'){ cnt0++; if(s1[i]=='1'&&cnt0<=cnt1/2){ s2+='('; a++; s3+='('; b++; } else if(s1[i]=='1'&&cnt0>cnt1/2) { s2+=')'; a--; s3+=')'; b--; } } else { if(a>0&&b>0){ if(a>=b){ s2+=')';a--; s3+='(';b++; } else { s2+='(';a++; s3+=')';b--; } } else if(a>0){ s2+=')';a--; s3+='(';b++; } else if(b>0){ s2+='(';a++; s3+=')';b--; } else { flag=1; } } if(a<0||b<0){ flag=1; // cout<<s2<<endl<<s3<<endl; } } if(flag==1){ cout<<"NO"<<endl; } else { cout<<"YES"<<endl; cout<<s2<<endl<<s3<<endl; } } }
