Codeforces Round #712 (Div. 2) 游记
次阅读
6 min read
掉分。
本想着破釜沉舟成 expert, 结果差点掉成 pupil。
因为上次打得比较好,所以感觉离蓝名不远了,所以直接开了 C 题,希望能通过 CBAD 的做题顺序获得更高的分数。
然后 C 题就翻车了,一开始想了一个复杂而错误的解法,WA 了两发才发觉做法不对。
后来发现是我想难了,这其实是一道很简单的题。
C
看题,观察了一下样例和自己的小数据,发现了一个似乎显而易见的结论,如果原串可以被分成几个长度为偶数的,一开头的回文,那么上面类似 ()()
的结构,下面用根据 串来做就可以了。
判断回文我选择了字符串哈希。
想到这个用的时间就比较的久,写得也比较慢,哈希最开始也写错了。然后到快一个小时才交第一发,当然,。
然后还抱着这个想法不肯放手,发现了一个小问题,但改完继续 WA, 代码也放一放吧,纪念。
#include <cstdio>
#include <vector>
#include <cstring>
#define int long long
const int N = 200005, p = 998244353;
std::vector<char> ans1, ans2;
char st[N];
int hashb[N], hashf[N], pow[N], T, n;
void init() {
memset(hashb, 0, sizeof hashb);
memset(hashf, 0, sizeof hashf);
ans1.clear();
ans2.clear();
}
bool check(int l, int r) {
int mid = l + (r-l)/2;
int hf = (hashf[mid] - hashf[l-1] + p) % p, hb = (hashb[mid+1] - hashb[r+1] + p) % p;
int len0f = l-1, len0b = n-r;
if(len0f > len0b) hb = hb * pow[len0f - len0b] % p;
else hf = hf * pow[len0b - len0f] % p;
if(hf == hb) return true;
else return false;
}
void getans(int l, int r) {
for(int i = l; i <= r; i++) ans1.push_back(((i-l) % 2 == 0) ? '(' : ')');
for(int i = l; i <= r; i++)
if(st[i] == '1') ans2.push_back(((i-l) % 2 == 0) ? '(' : ')');
else ans2.push_back(((i-l) % 2 == 0) ? ')' : '(');
}
signed main() {
scanf("%lld", &T);
while(T--) {
scanf("%lld", &n);
scanf("%s", st+1);
init();
pow[0] = 1;
for(int i = 1; i <= n; i++) pow[i] = pow[i-1] * 2 % p;
for(int i = n; i >= 1; i--) hashb[i] = (hashb[i+1] + (st[i] - '0' + p) % p * pow[n-i] % p) % p;
for(int i = 1; i <= n; i++) hashf[i] = (hashf[i-1] + (st[i] - '0' + p) % p * pow[i-1] % p) % p;
int now = 0;
st[n+1] = '1';
for(int i = 1; i <= n; i++)
if((i - now) % 2 == 0 && st[now+1] == '1' && check(now+1, i) ) {
getans(now+1, i);
now = i;
}
if((signed)ans1.size() < n) puts("NO");
else {
puts("YES");
for(int i = 0; i < (signed)ans1.size(); i++) printf("%c", ans1[i]);
puts("");
for(int i = 0; i < (signed)ans2.size(); i++) printf("%c", ans2[i]);
puts("");
}
}
}
哈希来判这样的回文倒是挺棒的想法,但是 hack 数据很显然。
11110011
虽然仍然是可以划分,但是我们的程序并不知道正确的划分位置,而且就算正确划分了,也不能得到正确答案。
写了那么多的代码,当然不肯放弃,觉得可能就是个小问题,所以一直想改改解决。
然后发现解决不了,终于放弃。
接着发现有很简单的做法。
即中间的 0
的部分反转后都是可以匹配的,只需要左右有多出来的就可以了,但是左右仍然要匹配。
所以找左右 0
之前较少的 1
的个数,括号向中间靠拢,其它的 0
和 1
分开正常匹配就可以了。
#include <cstdio>
#include <algorithm>
const int N = 200005;
int T, n;
char st[N], ans1[N];
int main() {
scanf("%d", &T);
while(T--) {
scanf("%d", &n);
scanf("%s", st+1);
int num1f = 0, num1b = 0;
for(int i = 1; i <= n; i++) {
if(st[i] == '0') break;
num1f ++;
}
for(int i = n; i >= 1; i--) {
if(st[i] == '0') break;
num1b ++;
}
if(num1f == 0 || num1b == 0) {
puts("NO");
continue;
}
int k = 0, flag1 = 0, flag0 = 0;
if(num1b != n) k = std::min(num1f, num1b);
for(int i = 1; i <= k; i++) ans1[i] = '(';
for(int i = n; i >= n-k+1; i--) ans1[i] = ')';
for(int i = k+1; i <= n-k; i++)
if(st[i] == '1') {
if(flag1) ans1[i] = ')';
else ans1[i] = '(';
flag1 = 1^flag1;
}
else {
if(flag0) ans1[i] = ')';
else ans1[i] = '(';
flag0 = 1^flag0;
}
if(flag1 || flag0) puts("NO");
else {
puts("YES");
for(int i = 1; i <= n; i++) printf("%c", ans1[i]);
puts("");
for(int i = 1; i <= n; i++)
if(st[i] == '1') printf("%c", ans1[i]);
else printf("%c", (ans1[i] == '(') ? ')' : '(');
puts("");
}
}
}
A 题是道有些细节的题,也花了我一定的时间,最后没有机会做 B 了,于是惨痛掉分。
所以题目开始写代码之前一定要想清楚,一定要验证好正确性,不然只会浪费大量的时间。
虽然陷入了一个低谷,但不可被此打倒而整天郁郁寡欢,振作起来,去完成目标,去实现梦想!