C. Cursed Game 题解

题意概述

每一轮都会有一张固定但未知的 $3 \times 3$ 打洞纸片，至少有一个洞。

你每次可以提交一张 $N \times N$ 的黑白纸，恶魔会把秘密纸片覆盖到你的纸上，并对每个 $3 \times 3$ 子矩形统计：

• 透过所有洞看到的黑格子个数；
• 如果这个个数是奇数，则结果格为 $1$，否则为 $0$。

于是每次询问会得到一个 $(N-2) \times (N-2)$ 的反馈网格。

目标是在所有位置都得到 $1$。

总共有 $333$ 轮，总询问数不能超过 $999$。

整体策略

这题分成两种情况：

1. 当 $N \ge 5$ 时，最多用 $2$ 次询问就能确定秘密纸片并构造必胜答案。
2. 当 $N = 3$ 时，直接随机一张纸即可，每次成功概率恰好是 $\dfrac12$，因此期望只要 $2$ 次询问。

这样总期望询问次数是：

$$333 \times 2 = 666.$$

远小于上限 $999$。

第一部分：$N \ge 5$ 时如何用第一次询问识别洞的位置

第一张纸非常简单：

• 只把单元格 $(3,3)$ 染成黑色；
• 其余格子全部染成白色。

为什么这能看出秘密纸片

设秘密纸片在位置 $(x,y)$ 有洞。

反馈网格中的单元格 $(r,c)$ 会看到这唯一的黑格子，当且仅当覆盖时满足：

$$r + x - 1 = 3,\qquad c + y - 1 = 3.$$

也就是：

$$r = 4 - x,\qquad c = 4 - y.$$

所以：

• 如果秘密纸片在 $(x,y)$ 有洞，那么反馈网格中的 $(4-x,4-y)$ 一定是 $1$；
• 反过来，反馈网格中这部分的 $1$ 也正好对应一个洞。

因此，第一张纸返回的结果就直接把秘密纸片完整地“照”出来了，只不过位置是翻转过的：

$$\text{hole}(x,y)=\text{feedback}(4-x,4-y).$$

注意当 $N \ge 5$ 时，反馈网格大小至少为 $3 \times 3$，所以这部分信息一定读得到。

第二部分：已知洞的位置后，如何构造第二张纸

现在问题变成：

• 已知一个固定的 $3 \times 3$ 的 $0/1$ 模板 hole
• 需要构造一个 $N \times N$ 的 $0/1$ 纸张 paper
• 使得每个 $3 \times 3$ 位置的异或卷积结果都等于 $1$

也就是对所有 $1 \le r,c \le N-2$，都满足：

$$\bigoplus_{i=1}^{3}\bigoplus_{j=1}^{3} \left(\text{hole}_{i,j}\land \text{paper}_{r+i-1,c+j-1}\right)=1. $$

贪心构造

我们选出秘密纸片中按行优先顺序最大的那个洞，记它的位置为 $(p_x,p_y)$。

也就是说，它满足：

• hole[px][py] = 1
• 对任意其他洞 $(x,y)$，都有 $(x,y)$ 在行优先顺序下不晚于 $(p_x,p_y)$

然后把整张 paper 初始化成全 0。

接着按行优先顺序枚举反馈网格中的每个位置 $(r,c)$。

设当前这个位置对应的异或值为：

$$cur= \bigoplus_{i=1}^{3}\bigoplus_{j=1}^{3} \left(\text{hole}_{i,j}\land \text{paper}_{r+i-1,c+j-1}\right). $$

如果当前 cur = 0，那么就把：

$$\text{paper}_{r+p_x-1,\ c+p_y-1}$$

设成 1；否则保持不变。

这样处理完所有位置后，整张反馈网格就会全部变成 1。

为什么这个贪心是对的

关键点在于：对于反馈格 $(r,c)$ 来说，所有会影响它的 paper 位置是：

$$(r+i-1,\ c+j-1)\qquad (1 \le i,j \le 3,\ \text{hole}_{i,j}=1). $$

而我们选的是按行优先顺序最大的洞 $(p_x,p_y)$，所以：

$$(r+p_x-1,\ c+p_y-1)$$

就是所有这些位置中，按行优先顺序最晚的那个。

这意味着：

1. 在处理 $(r,c)$ 时，这个位置是最后一个还能修改当前反馈值的纸张单元格；
2. 改动它不会影响任何已经处理过的更早反馈格。

于是我们就可以像一维前缀贪心那样，把每个反馈格当场修成 1，并且不会把前面的答案弄坏。

这就是题目提示中“row by row then column by column，并在最后一次还能影响某个反馈格的位置决定是否翻转”的具体实现。

第三部分：为什么 $N = 3$ 时随机即可

当 $N = 3$ 时，反馈网格大小只有 $1 \times 1$。

也就是说，每次询问只有一个比特结果，它等于：

$$\bigoplus_{\text{洞的位置}} \text{paper}_{i,j}.$$

如果我们把 $3 \times 3$ 纸上的每个格子都独立地随机染成黑白，那么对于秘密纸片上的每个洞，恶魔看到的是一个独立随机比特。

由于至少有一个洞，这些随机比特的异或结果一定仍然是均匀随机的，因此反馈值为 1 的概率恰好是：

$$\frac{1}{2}.$$

所以每次随机询问，成功概率都是 $\dfrac12$，期望只需要 $2$ 次。

询问次数为什么足够

对于 $N \ge 5$ 的轮次，最多只需 $2$ 次。

对于 $N = 3$ 的轮次，每次成功概率是 $\dfrac12$。

如果把全部 $999$ 次询问看作抛 $999$ 次公平硬币，那么失败的情况就是：到最后成功次数仍然严格少于 $333$ 次。这个概率极小，小于：

$$10^{-26}.$$

因此这份随机化做法在实战中是完全足够的。

复杂度分析

对于 $N \ge 5$：

• 第一次询问后读取秘密纸片是 $O(1)$；
• 第二次构造时，枚举每个反馈格并检查一个固定大小的 $3 \times 3$ 模板，因此复杂度是：

$$O(N^2).$$

对于 $N = 3$，每次询问都是常数复杂度。

标准程序

#include <bits/stdc++.h>
using namespace std;

mt19937 rng((unsigned)chrono::steady_clock::now().time_since_epoch().count());

int used_queries = 0;

vector<string> ask(const vector<string>& paper, bool& correct) {
    if (++used_queries > 999) {
        exit(0);
    }

    int n = (int)paper.size();
    for (int i = 0; i < n; ++i) {
        cout << paper[i] << '\n';
    }
    cout << flush;

    string verdict;
    if (!(cin >> verdict)) {
        exit(0);
    }

    if (verdict == "CORRECT") {
        correct = true;
        return {};
    }

    correct = false;
    vector<string> feedback(n - 2);
    for (int i = 0; i < n - 2; ++i) {
        cin >> feedback[i];
    }
    return feedback;
}

vector<string> build_probe(int n) {
    vector<string> paper(n, string(n, '0'));
    paper[2][2] = '1';
    return paper;
}

vector<string> build_solution(int n, const vector<string>& feedback) {
    int hole[3][3] = {};
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            hole[i][j] = feedback[2 - i][2 - j] - '0';
        }
    }

    int px = -1, py = -1;
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            if (hole[i][j]) {
                px = i;
                py = j;
            }
        }
    }

    vector<string> paper(n, string(n, '0'));
    for (int r = 0; r < n - 2; ++r) {
        for (int c = 0; c < n - 2; ++c) {
            int cur = 0;
            for (int i = 0; i < 3; ++i) {
                for (int j = 0; j < 3; ++j) {
                    if (hole[i][j]) {
                        cur ^= (paper[r + i][c + j] - '0');
                    }
                }
            }
            if (cur == 0) {
                paper[r + px][c + py] = '1';
            }
        }
    }

    return paper;
}

vector<string> build_random_3() {
    vector<string> paper(3, string(3, '0'));
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            paper[i][j] = char('0' + uniform_int_distribution<int>(0, 1)(rng));
        }
    }
    return paper;
}

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

    int n;
    while (cin >> n) {
        if (n >= 5) {
            bool correct = false;
            vector<string> feedback = ask(build_probe(n), correct);
            if (correct) {
                continue;
            }

            vector<string> answer = build_solution(n, feedback);
            feedback = ask(answer, correct);
            if (!correct) {
                exit(0);
            }
        } else {
            while (true) {
                bool correct = false;
                vector<string> feedback = ask(build_random_3(), correct);
                if (correct) {
                    break;
                }
            }
        }
    }

    return 0;
}