题解：P3677 [CERC2016] 关键的膝盖 Key Knocking

Conan15 · 2026-05-14 14:59:38 · 题解

很简单的题。

从前往后考虑相邻四个位置，若反转中间两个之后权值更大了（即 +2）则反转，获得 65pts。\ 这样的策略不够优秀，考虑如下样例：

001000
010000
010110

因此我们再考虑相邻六个位置，反转中间四个，这样能获得 95pts，其实只是细节实现出了问题。

再考虑特殊情况如 3n=6，发现有如下样例：

001001
010001
010010

即：边界也可以被反转，但权值只 +1。

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
int n;
char a[N];
bool st[N];

inline int get(int l, int r) {
    int res = 0;
    for (int i = l; i <= r; i++) {
        if (i == 1 || i == n + 1) continue;
        res += a[i] ^ a[i - 1];
    } return res;
}

int main() {
    scanf("%s", a + 1), n = strlen(a + 1);
    if (n == 3) {
        int res = (a[1] ^ a[2]) + (a[2] ^ a[3]);
        if (res) puts("0");
        else puts("1\n1");
        return 0;
    }
    int cnt = 0;
    for (int i = 1; i <= n - 1; i++) {
        int res = get(i, i + 2);
        a[i] ^= 1, a[i + 1] ^= 1;
        int res2 = get(i, i + 2);
        if (res < res2) cnt += st[i] ? -1 : 1, st[i] ^= 1;
        else a[i] ^= 1, a[i + 1] ^= 1;
        if (cnt + 1 > n / 3) break;
    }
    for (int i = 1; i <= n - 3; i++) {
        int res = get(i, i + 4);
        a[i] ^= 1, a[i + 1] ^= 1, a[i + 2] ^= 1, a[i + 3] ^= 1;
        int res2 = get(i, i + 4);
        int need = (st[i] ? -1 : 1) + (st[i + 2] ? -1 : 1);
        if (cnt + need > n / 3) continue;

        if (res < res2) cnt += need, st[i] ^= 1, st[i + 2] ^= 1;
        else a[i] ^= 1, a[i + 1] ^= 1, a[i + 2] ^= 1, a[i + 3] ^= 1;
    }
    printf("%d\n", cnt);
    for (int i = 1; i <= n; i++)
        if (st[i]) printf("%d ", i);
    return 0;
}
/*
001001
*/