题解：CF1979D Fixing a Binary String

Engulf · 2024-06-08 15:58:03 · 题解

因为 k \mid n，所以最终的字符串一定是这两种形式中的一种。

• \underbrace{11\cdots1}_{k \ 个 \ 1} \underbrace{00\cdots0}_{k \ 个 \ 0} \cdots
• \underbrace{00\cdots0}_{k \ 个 \ 0} \underbrace{11\cdots1}_{k \ 个 \ 1} \cdots

题目已经告诉我们，若选择的位置为 p，则操作后的字符串是 s_{p + 1}s_{p + 2}\dots s_{n}s_ps_{p-1}\dots s_1，如果合法，则它一定等于上面两个字符串中的一个。

判断字符串相等可以哈希维护。

维护原序列的哈希和反转后的序列的哈希，以 s_n 和 s_p 为界分开字符串，设 s_{p + 1}s_{p + 2}\dots s_{n} 的哈希值为 h_1，s_ps_{p-1}\dots s_1 的哈希值为 h_2，则它们拼接起来的字符串的哈希值为 h_1 \cdot B^{p} + h_2，其中 B 是你字符串哈希使用的底数（base）。

如果你不明白为什么拼起来哈希值是它。

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pii = pair<int, int>;

#ifdef ONLINE_JUDGE
#define debug(...) 0
#else
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#endif

using ull = unsigned long long;

const int N = 1e5 + 5;

ull base = 233;

int n, k;
char s[N], revs[N];
char v1[N], v2[N];

inline char rev(char x) {return x == '0' ? '1' : '0';}

ull pre[N], suf[N];
ull pw[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    pw[0] = 1;
    for (int i = 1; i < N; i++) pw[i] = pw[i - 1] * base;
    int tt;
    cin >> tt;
    while (tt--) {
        cin >> n >> k >> s + 1;

        for (int i = 1; i <= k; i++) v1[i] = '1', v2[i] = '0';
        for (int i = k + 1; i <= n; i++) v1[i] = rev(v1[i - k]), v2[i] = rev(v2[i - k]);

        int cnt = count(s + 1, s + 1 + n, '1');
        ull h1 = 0, h2 = 0;
        int t1 = 0, t2 = 0;

        for (int i = 1; i <= n; i++) {
            h1 = h1 * base + v1[i], t1 += v1[i] == '1';
            h2 = h2 * base + v2[i], t2 += v2[i] == '1';
        }

        if (t1 != cnt) h1 = -1;
        if (t2 != cnt) h2 = -1;

        strcpy(revs + 1, s + 1);
        reverse(revs + 1, revs + 1 + n);

        pre[0] = suf[0] = 0;

        for (int i = 1; i <= n; i++) {
            pre[i] = pre[i - 1] * base + s[i];
            suf[i] = suf[i - 1] * base + revs[i];
        }

        int ans = -1;
        for (int i = 1; i <= n; i++) {
            ull h = (pre[n] - pre[i] * pw[n - i]) * pw[i] + (suf[n] - suf[n - i] * pw[i]);
            if (h == h1 || h == h2) {
                ans = i;
                break;
            }
        }

        cout << ans << "\n";

    }
    return 0;
}

样例第四个小点答案 1 或 5，我这个跑出来就是 1。