Codeforces Round #712 (Div. 2)
A. Déjà Vu
暴力瞎搞即可，只有全a是不满足的，否则挑选a更多的一端加上a，当然也可以分别加a进行判断。
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while(t--) {
string s;
cin >> s;
string s1 = s + "a", ss1 = s1;
reverse(ss1.begin(), ss1.end());
string s2 = "a" + s, ss2 = s2;
reverse(ss2.begin(), ss2.end());
if(s1 != ss1) {
cout << "YES" << endl;
cout << s1 << endl;
} else if(s2 != ss2) {
cout << "YES" << endl;
cout << s2 << endl;
} else cout << "NO" << endl;
}
return 0;
}
B. Flip the Bits
注意到操作前面的不会影响到后面位置的可操作性，因此要从后往前判断。设置一个标记表示变了多少次，奇数次的话01互换，偶数次不变。从后往前遍历，如果a[i]（此时是变换了奇数或者偶数次的a[i]）和b[i]不一样且a的长为i的前缀里（也是变换了奇数或者偶数次的）01数量相等则进行变换，否则输出NO结束。统计前缀01数量其实可以维护两个变量，从后往前遍历的时候更新其值即可。
#include <bits/stdc++.h>
using namespace std;
int n;
string a, b;
int sum0[300005], sum1[300005];
int main() {
int t;
cin >> t;
while(t--) {
sum0[0] = sum1[0] = 0;
cin >> n;
cin >> a;
cin >> b;
a = " " + a;
b = " " + b;
int aa[2];
aa[0] = aa[1] = 0;
for(int i = 1; i <= n; i++) {
if(a[i] == '0') aa[0]++;
else aa[1]++;
if(b[i] == '0') {
sum0[i] = sum0[i - 1] + 1;
sum1[i] = sum1[i - 1];
} else {
sum0[i] = sum0[i - 1] + 1;
sum1[i] = sum1[i - 1] + 1;
}
}
//操作前面的不会影响到后面位置的可操作性
//因此要从后往前判断
bool flag = 1;
int round = 0;
for(int i = n; i >= 1; i--) {
if(round & 1) {//先根据round判断当前的1是1还是0
if(a[i] == '0') a[i] = '1';
else a[i] = '0';
}
if(a[i] == b[i]) {
if(round & 1) {
if(a[i] == '0') aa[1]--;//更新要维护的变量
else aa[0]--;
} else {
if(a[i] == '0') aa[0]--;
else aa[1]--;
}
continue;
}
else {
if(round & 1) {
if(aa[0] == aa[1]) {
if(b[i] == '0') {
aa[0]--;
} else {
aa[1]--;
}
} else {
flag= 0;
break;
}
} else {
if(aa[0] == aa[1]) {
if(b[i] == '0') {
aa[1]--;
} else {
aa[0]--;
}
} else {
flag= 0;
break;
}
}
round++;
}
}
if(flag) cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}
C. Balance the Bits
首先注意到头尾有0是不行的，因为a和b的头尾都得是(......)这样。其次n为奇数是不行的，并且1的数量为奇数是不行的。
然后就是构造了，官方给的构造方法是为1的位置前一半是(，后一半是)；为0的位置交替着填（b和a要相反）。
暂时没想出来这么构造的道理...
#include <bits/stdc++.h>
using namespace std;
int n;
string s;
bool valid(vector<char> v) {
int cnt = 0;
for(int i = 0; i < v.size(); i++) {
if(v[i] == '(') cnt++;
else {
if(cnt) cnt--;
else return 0;
}
}
return 1;
}
int main() {
int t;
cin >> t;
while(t--) {
cin >> n;
cin >> s;
int cnt = 0;
for(int i = 0; i < n; i++) if(s[i] == '1') cnt++;
if(s[0] == '0' || s[s.size() - 1] == '0' || n & 1 || cnt & 1) {
cout << "NO" << endl;
continue;
}
//接下来随便构造第一个肯定能构造出来
vector<char> v1, v2;
int cnt1 = 0, cnt2 = 0;
//cout << cnt / 2 << endl;
for(int i = 0; i < n; i++) {
if(s[i] == '1') {
cnt1++;
if(cnt1 <= cnt / 2) {
v1.push_back('(');
v2.push_back('(');
} else {
v1.push_back(')');
v2.push_back(')');
}
} else {
if(cnt2 & 1) {
v1.push_back('(');
v2.push_back(')');
} else {
v1.push_back(')');
v2.push_back('(');
}
cnt2++;
}
}
cout << "YES" << endl;
for(int i = 0; i < v1.size(); i++) cout << v1[i];
cout << endl;
for(int i = 0; i < v2.size(); i++) cout << v2[i];
cout << endl;
}
return 0;
//110011
//()()()
}