题解：CF1031E Triple Flips

· · 题解

题意简述

有一个长度为 n 的 01 序列，一次操作可以反转 a_x、a_y 和 a_z，当且仅当 1 \le x < y < z \le n 且 x + z = 2y，求一种在 \lfloor \frac{n}{3} \rfloor + 12 次操作内把原序列全部变成 0 的方案。

思路

观察限制 \lfloor \frac{n}{3} \rfloor + 12，这个 12 显然是留给调整用的，所以最劣情况（几乎全是 1）平均我们每次操作需要消除 3 个 1。

于是显然想到把原序列分成三个三个一组，尝试用 1 次操作清空这一组中的所有 1。

但经过简单尝试我们发现这是不可能的，因为除了 111 和 000，别的所有情况都不能在一次操作之内消除。

于是我们想到把长度翻倍，每 6 个数一组，用 2 次以内的操作清除。

我们钦定第一位为 1，则可以大力分讨 2^5 = 32 种情况，伪代码如下：

:::info[分类讨论] 其中 s 表示区间 [l, l + 5] 的状态，Flip(x, y) 表示操作 (x, y, 2y - x)。

大家可以手玩几组理解一下。

if (s == "100000") Flip(l, l + 2), Flip(l + 2, l + 4);
if (s == "100001") Flip(l, l + 5);
if (s == "100010") Flip(l, l + 4);
if (s == "100011") Flip(l, l + 3), Flip(l + 3, l + 4);
if (s == "100100") Flip(l, l + 3);
if (s == "100101") Flip(l, l + 3), Flip(l + 5, l + 6);
if (s == "100110") Flip(l, l + 5), Flip(l + 3, l + 4);
if (s == "100111") Flip(l, l + 3), Flip(l + 4, l + 5);
if (s == "101000") Flip(l, l + 2), Flip(l + 4, l + 6);
if (s == "101001") Flip(l, l + 2), Flip(l + 4, l + 5);
if (s == "101010") Flip(l, l + 2);
if (s == "101011") Flip(l, l + 2), Flip(l + 5, l + 6);
if (s == "101100") Flip(l, l + 4), Flip(l + 2, l + 3);
if (s == "101101") Flip(l, l + 2), Flip(l + 3, l + 4);
if (s == "101110") Flip(l, l + 2), Flip(l + 3, l + 6);
if (s == "101111") Flip(l, l + 2), Flip(l + 3, l + 5);
if (s == "110000") Flip(l, l + 4), Flip(l + 1, l + 4);
if (s == "110001") Flip(l, l + 3), Flip(l + 1, l + 3);
if (s == "110010") Flip(l, l + 1), Flip(l + 2, l + 4);
if (s == "110011") Flip(l, l + 4), Flip(l + 1, l + 5);
if (s == "110100") Flip(l, l + 5), Flip(l + 1, l + 3);
if (s == "110101") Flip(l, l + 3), Flip(l + 1, l + 5);
if (s == "110110") Flip(l, l + 1), Flip(l + 2, l + 3);
if (s == "110111") Flip(l, l + 4), Flip(l + 1, l + 3);
if (s == "111000") Flip(l, l + 1);
if (s == "111001") Flip(l, l + 1), Flip(l + 5, l + 6);
if (s == "111010") Flip(l, l + 1), Flip(l + 4, l + 6);
if (s == "111011") Flip(l, l + 1), Flip(l + 4, l + 5);
if (s == "111100") Flip(l, l + 1), Flip(l + 3, l + 6);
if (s == "111101") Flip(l, l + 1), Flip(l + 3, l + 5);
if (s == "111110") Flip(l, l + 4), Flip(l + 1, l + 2);
if (s == "111111") Flip(l, l + 1), Flip(l + 3, l + 4);

:::

但是这样会需要大量的冗余空间，如情况 110100，清除方法是：

  1. 翻转第 1、6、11 位；
  2. 翻转第 2、4、6 位。

最多触及后 11 位，所以对于 n \le 10 的序列，和 n > 10 的序列的最后 10 位，我们的算法无法操作。

到这里，显然的想法是对长度 l \le 10 的序列进行分讨，找出其中合法序列直接判断，但是经过简单搜索发现，长度为 10 的所有序列好像都有解。

于是，除非你想分讨 2^{10} = 1024 种情况，我们直接搜索是更经济的选择。

于是我们整个题目的思路就出来了：

  1. 对于所有的 1 \le i \le \max(0, n - 10) 的位置，如果它是 1，就把后面的 6 位全部清除。
  2. 对于最后的 \min(n, 10) 位，我们直接暴力搜索，找出最优解。

复杂度分析

前面的分讨复杂度 O(n)，最后的搜索状态数不会超过 2^{10} = 1024，可以接受。

前面的操作平均每次清除 3 个 1，最后的 10 位操作次数不超过 6 次，远小于限制 \lfloor \frac {n}{3} \rfloor + 12。

代码实现

实际实现时可以把 5 位状态压成一个二进制数，写起来更便捷。 :::success[AC 代码]

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 1e5 + 10;

bitset<N> a;
struct Ans {
    int a, b, c;
};
vector<Ans> ans;
pair<pair<int, int>, pair<int, int>> opt[32] = {
    {{0, 2}, {2, 4}},   {{0, 5}, {-1, -1}}, {{0, 4}, {-1, -1}},
    {{0, 3}, {3, 4}},   {{0, 3}, {-1, -1}}, {{0, 3}, {5, 6}},
    {{0, 5}, {3, 4}},   {{0, 3}, {4, 5}},   {{0, 2}, {4, 6}},
    {{0, 2}, {4, 5}},   {{0, 2}, {-1, -1}}, {{0, 2}, {5, 6}},
    {{0, 4}, {2, 3}},   {{0, 2}, {3, 4}},   {{0, 2}, {3, 6}},
    {{0, 2}, {3, 5}},   {{0, 4}, {1, 4}},   {{0, 3}, {1, 3}},
    {{0, 1}, {2, 4}},   {{0, 4}, {1, 5}},   {{0, 5}, {1, 3}},
    {{0, 3}, {1, 5}},   {{0, 1}, {2, 3}},   {{0, 4}, {1, 3}},
    {{0, 1}, {-1, -1}}, {{0, 1}, {5, 6}},   {{0, 1}, {4, 6}},
    {{0, 1}, {4, 5}},   {{0, 1}, {3, 6}},   {{0, 1}, {3, 5}},
    {{0, 4}, {1, 2}},   {{0, 1}, {3, 4}}};
int pre[N];
Ans pre_op[N];

int Mask(int x, int len) {
    int ans = 0;
    for (int i = x; i < x + len; ++i) ans = ans << 1 | a[i];
    return ans;
}

void Flip(int x, int y) {
    int z = y * 2 - x;
    ans.push_back({x, y, z});
    a[x] = a[x] ^ 1, a[y] = a[y] ^ 1, a[z] = a[z] ^ 1;
}

void Clear(int l) {
    int mask = Mask(l + 1, 5);
    Flip(l + opt[mask].first.first, l + opt[mask].first.second);
    if (~opt[mask].second.first && ~opt[mask].second.second) {
        Flip(l + opt[mask].second.first, l + opt[mask].second.second);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    for (int i = 1, x; i <= n; ++i) cin >> x, a[i] = x;

    for (int i = 1; i <= n - 10; ++i) {
        if (a[i]) Clear(i);
    }

    int l = max(1, n - 9), len = n - l + 1, s = 0;
    for (int i = n; i >= l; --i) s = s << 1 | a[i];
    memset(pre, -1, sizeof(pre));
    queue<int> q;
    q.push(s);
    pre[s] = -2;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        if (!x) break;
        for (int i = l; i <= n; ++i) {
            for (int j = i + 1; j <= n; ++j) {
                int k = j * 2 - i;
                if (k < l || k > n) continue;
                int nxt = x ^ ((1 << i - l) | (1 << j - l) | (1 << k - l));
                if (~pre[nxt]) continue;
                pre[nxt] = x;
                pre_op[nxt] = {i, j, k};
                q.push(nxt);
            }
        }
    }

    if (pre[0] == -1) return cout << "NO\n", 0;
    int x = 0, now_len = ans.size();
    while (pre[x] != -2) {
        ans.push_back(pre_op[x]);
        x = pre[x];
    }
    reverse(ans.begin() + now_len, ans.end());
    cout << "YES\n" << ans.size() << '\n';
    for (auto x : ans) cout << x.a << ' ' << x.b << ' ' << x.c << '\n';
}

:::

后记

其实对于所有的 n \ge 8 的序列都一定有解。 ::::info[证明] :::info[AI 使用声明] 本证明由 DeepSeek 生成，但文章其他部分均无 AI 参与，全文人类贡献大于 AI 贡献。 :::

当 n\ge 8 时，任意 0/1 数组都可以通过若干次 Triple Flips 变为全 0。

把每个位置看成 \mathbb F_2 上的一个坐标，翻转三个位置等价于加上向量

e_x+e_y+e_z,

其中 x,y,z 构成等差数列。

要证明任意数组都能变成全零，只需证明这些操作向量张成整个空间 \mathbb F_2^n。

反设它们不能张成整个空间。则存在非零向量

w=(w_1,w_2,\dots,w_n)\in\mathbb F_2^n

与所有操作向量正交，即对任意等差数列 x<y<z，都有

w_x+w_y+w_z=0\pmod 2. \tag{1}

先取公差为 1 的等差数列 (i,i+1,i+2)。由 (1) 得

w_i+w_{i+1}+w_{i+2}=0.

于是

w_{i+2}=w_i+w_{i+1}.

进一步，

w_{i+3}=w_{i+1}+w_{i+2} =w_{i+1}+w_i+w_{i+1}=w_i.

所以序列 w 以 3 为周期：

w_{i+3}=w_i.

记

A=w_1,\qquad B=w_2,\qquad C=w_3.

由 w_1+w_2+w_3=0 得

C=A+B.

因此 w 形如

A,B,A+B,A,B,A+B,\dots

因为 n\ge 8，以下两个等差数列都在范围内：

(1,4,7),\qquad (2,5,8).

由 (1) 对 (1,4,7) 得

w_1+w_4+w_7=0.

利用周期 3，有

w_4=w_1=A,\qquad w_7=w_1=A.

于是

A+A+A=0\pmod 2.

因为 A+A+A\equiv A\pmod 2，所以

A=0.

同理，对 (2,5,8) 得

w_2+w_5+w_8=0.

利用周期 3，

w_5=w_2=B,\qquad w_8=w_2=B.

于是

B+B+B=0\pmod 2,

从而

B=0.

因此

C=A+B=0.

所以所有 w_i=0，即 w=0，与假设 w\ne 0 矛盾。

因此操作向量张成整个 \mathbb F_2^n，任意数组都可以化为全零。