题解：CF1031E Triple Flips

· · 题解

直接手动模拟的做法也太拉了，考虑不手动模拟的做法。

首先考虑判无解。

手玩一下发现没有简单的策略，考虑爆搜。

发现只有 n \le 7 可以会有无解情况，可以直接 \mathcal{O}(2^n) 搜索。

upd2：n \le 7 可以不跑爆搜，可以直接随机化，如果构造不出，则输出 No。

下文只考虑 n \ge 8 时候的做法。

有简单的 n 次做法为每次取最左边的 1 将其操作，但是可能会出现最右端的两个位置可能会出现 1 且没法继续操作。

我们发现在随机数据下该算法有概率跑出构造，可以进行若干次随机扰动再跑以上算法，如果无解则重新随机扰动。

以上做法还是太劣了，第 10 个点就 WA 了。 考虑不每次都取连续的 3 个进行操作。

我们可以每次取出最靠前的两次 1 的出现位置 x, y，对 x, y, 2y - x 进行操作，如果 2y - x > n 则取最左端为 x 的最长的进行操作。

我们不会分析这个东西，但是因为有随机扰动，无法刻意构造数据来卡，感觉上每次最靠前的 1 的移动位置数是对的。

需要特殊注意的是如果 1 非常多，不能进行过多的随机扰动。

upd：期望就是 \lceil \frac{n}{3} \rceil 的。 每次考虑前 3 个位置，000 不需要操作，110 需要 2 次操作，其余情况需要 1 次操作，所以 3 个位置期望需要 1 次操作，总操作数为 \lceil \frac{n}{3} \rceil。

::::info[code]

#include <bits/extc++.h>

using namespace std;
using ll = long long;
using ull = unsigned ll;
using st = short;
using ust = unsigned st;
using db = double;
using ldb = long db;

const int N = 1e6 + 5;

int n, a[N], b[N];

struct Node{
    int x, y, z;
};
vector<Node> ans;

void solve(int x, int y, int z){
    assert(x < y && y < z && y * 2 == x + z && x >= 1 && z <= n);
    a[x] ^= 1, a[y] ^= 1, a[z] ^= 1;
    ans.push_back({x, y, z});
}

int check(){
    for(int i = 1; i <= n; i++)
        if(a[i])return i;
    return 0;
}

namespace sub1{
    int dis[1 << 7];
    struct Node{
        int a, b, c;
    }vis[1 << 7];

    void out(int x){
        if(!x)return;
        cout << vis[x].a + 1 << ' ' << vis[x].b + 1 << ' ' << vis[x].c + 1 << '\n';
        out(x ^ (1 << vis[x].a) ^ (1 << vis[x].b) ^ (1 << vis[x].c));
    }

    void solve(){
        fill(&dis[0], &dis[1 << n], 1000000000);
        queue<int> que;
        que.push(0);
        dis[0] = 0;
        while(!que.empty()){
            int x = que.front();
            que.pop();
            for(int i = 0; i + 2 < n; i++)
                for(int j = i + 1; j + (j - i) < n; j++){
                    int y = x ^ (1 << i) ^ (1 << j) ^ (1 << (j * 2 - i));
                    if(dis[y] == 1000000000)dis[y] = dis[x] + 1, vis[y] = {i, j, j * 2 - i}, que.push(y);
                }
        }
        int x = 0;
        for(int i = 1; i <= n; i++)
            x += (1 << i - 1) * a[i];
        if(dis[x] == 1000000000)cout << "No\n";
        else cout << "Yes\n" << dis[x] << '\n', out(x);
    }
}

signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    mt19937 rnd(time(0));
    cin >> n;
    int s = 0;
    for(int i = 1; i <= n; i++)
        cin >> a[i], b[i] = a[i];
    if(n <= 7){
        sub1::solve();
        return 0;
    }
    int flag = 0, ct = 0;
    while((check() || ans.size() > (n / 3) + 12) && (++ct) * n <= 80000000){
        if(flag){
            ans.clear();
            int ct = 0;
            for(int i = 1; i <= n; i++)
                a[i] = b[i], ct += a[i];
            for(int i = 1; i <= min((n / 3) + 8 - (ct / 3), n / 1000 + 3); i++){
                if(i <= 10){
                    int x = rnd() % min(n, 2) + 1;
                    while(x >= n - 1)x = rnd() % min(n, 2) + 1;
                    int len = rnd() % min(8, ((n - x) / 2)) + 1;
                    solve(x, x + len, x + len * 2);
                }else{
                    int x = rnd() % min(n, 100) + 1;
                    while(x >= n - 1)x = rnd() % min(n, 100) + 1;
                    int len = rnd() % min(2000, ((n - x) / 2)) + 1;
                    solve(x, x + len, x + len * 2);
                }
            }
        }
        flag = 1;
        for(int i = 1; i + 2 <= n; i++){
            if(a[i]){
                if(a[i + 1])solve(i, i + 1, i + 2);
                else if(a[i + 2] && i + 4 <= n)solve(i, i + 2, i + 4);
                else if(a[i + 3] && i + 6 <= n)solve(i, i + 3, i + 6);
                else{
                    int x = (n - i) / 2;
                    solve(i, i + x, i + x * 2);
                }
            }
        }
    }
    cout << "Yes\n";
    cout << ans.size() << '\n';
    for(Node i : ans)
        cout << i.x << ' ' << i.y << ' ' << i.z << '\n';
    return 0;
}

::::