Codeforces Round #712 (Div. 2) 游记

掉分。

本想着破釜沉舟成 expert, 结果差点掉成 pupil。

因为上次打得比较好,所以感觉离蓝名不远了,所以直接开了 C 题,希望能通过 CBAD 的做题顺序获得更高的分数。

然后 C 题就翻车了,一开始想了一个复杂而错误的解法,WA 了两发才发觉做法不对。

后来发现是我想难了,这其实是一道很简单的题。

C

看题,观察了一下样例和自己的小数据,发现了一个似乎显而易见的结论,如果原串可以被分成几个长度为偶数的,一开头的回文,那么上面类似 ()() 的结构,下面用根据 ss 串来做就可以了。

判断回文我选择了字符串哈希。

想到这个用的时间就比较的久,写得也比较慢,哈希最开始也写错了。然后到快一个小时才交第一发,当然,Wrong answer on pretest 2\texttt{Wrong answer on pretest 2}

然后还抱着这个想法不肯放手,发现了一个小问题,但改完继续 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 的个数,括号向中间靠拢,其它的 01 分开正常匹配就可以了。

#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 了,于是惨痛掉分。

所以题目开始写代码之前一定要想清楚,一定要验证好正确性,不然只会浪费大量的时间。


虽然陷入了一个低谷,但不可被此打倒而整天郁郁寡欢,振作起来,去完成目标,去实现梦想!