题解：CF1955E Long Inversions

FiraCode · 2024-04-16 06:03:35 · 题解

显然的，遇到一个 0 就一定要从当前开始翻转，若不够无法翻转，那么无解。

然后对于翻转，实际上就是将区间 +1 并 \bmod 2，那么 +1 直接差分，然后边做边记录前缀和即可，然后用到当前值时再 \bmod 2。

然后枚举 k 按照刚才的思路翻转即可。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int T;
int n;
char s[5010];
int sum[5010];

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        scanf("%s", s + 1);

        for (int k = n; k >= 1; --k) {
            for (int i = 0; i <= n; ++i) sum[i] = 0;
            for (int i = 1; i <= n - k + 1; ++i) {
                int t = s[i] - '0';
                sum[i] += sum[i - 1];
                if (!((t + sum[i]) & 1)) {
                    ++sum[i];
                    --sum[i + k];
                }
            }

            for (int i = n - k + 2; i <= n; ++i) sum[i] += sum[i - 1];

            bool ok = true;

            for (int i = 1; i <= n; ++i) {
                int t = s[i] - '0';

                if (!((t + sum[i]) & 1)) {
                    ok = false;
                    break;
                }
            }

            if (ok) {
                printf("%d\n", k);
                break;
            }
        }
    }

    return 0;
}