P13105 题解

· · 题解

妙妙交互题。

感觉这种题没有什么通用技巧啊，只能依题目而定。

先考虑 F = 10。

看到 N \le 1024 即 N \le 2 ^ {10}，很容易想到操作次数和 \log N 有关系。

想想怎样才能和 \log 产生关系。

考虑这样的事实：
将 N 改写为二进制后，N 的位数是 \log N 级别的。

于是我们想到：
用二进制给计算机编号，最后把回答的结果整合回十进制，看看少了哪些数，就知道哪些计算机出了故障。

以第一组样例为例，我们将下面的矩阵一行一行地发送给评测机： 

0 0 0 0 1
0 0 1 1 0
0 1 0 1 0

这个矩阵是什么意思呢？其实如果你竖着看，就会发现，第 i 行其实是 i - 1 的二进制表达形式。

也就是说，第 1 列就是二进制下的 0，第 2 列就是二进制下的 1，以此类推。

由于 0 和 3 出了故障，所以评测机返还给我们的是这样的： 

0 0 1
0 1 0
1 0 0

整合一下，第一列是 1，第二列是 2，第三列是 4。缺少了 0 和 3，所以答案就是 0 3。

代码应该很好写，就不给了。

或者直接看后面也行。

考虑如何做 F = 5。

容易观察到 B 的值实际上很小，这也就意味着我们在传输信息的过程中会浪费很多列的信息。

怎么样才能防止浪费呢？

考虑下面的算法：当 N 比较大的时候，我们将每若干列分成一块。我们取 32 列分一块，这样我们每一块只存 0 到 31 的二进制表示，最后再逐块整合统计答案。

为什么这样能减少浪费，且不会产生难以辨别的漏洞呢？因为 B 最大只有 15，而块长是 32，所以即使所有的 B 在同一块内，也不会让其中一块内的计算机全部故障。

这就意味着，只要在整合后我们发现某一列的结果比后一列大，那就可以说明这两列肯定在不同的块内，我们也就可以统计答案了。

具体的，如果我们发现编号 i 有缺失，那么这台计算机就是第 (i + 32 \times \texttt{前面出现的完整的块数}) 台。

由于我比较懒，所以当 N 较小的时候我直接用了 F = 10 的不分块代码。

#include <bits/stdc++.h>
using namespace std;
char s[1222][1222];
int flg[1222], z;
signed main() {
    int TT;
    cin >> TT;
    while (TT--) {
        memset(flg, 0, sizeof(flg));
        int n, b, f;
        cin >> n >> b >> f;
        if (n > 32) {
            for (int i = 1; i <= 5; i++) {
                for (int j = 0; j < n; j++)
                    cout << (((j % 32) >> (5 - i)) & 1);
                cout << endl;
                for (int j = 1; j <= n - b; j++) cin >> s[j][i];
            }
            int lst = -1, nct = 0;
            for (int i = 1; i <= n - b; i++) {
                int x = 0;
                for (int j = 1; j <= 5; j++)
                    x = x * 2 + s[i][j] - 48;
                if (x <= lst) {
                    for (int j = 0; j < 32; j++)
                        if (!flg[j]) cout << j + 32 * nct << " ";
                    nct++;
                    for (int j = 0; j < 32; j++) flg[j] = 0;
                }
                flg[x] = 1, lst = x;
            }
            for (int i = 0;i <= (n - 1) % 32;i++)
                if (!flg[i]) cout << i + 32 * nct << " ";
        } else {
            int cnt = 0, tmp = n - 1;
            while (tmp) tmp >>= 1, cnt++;
            for (int i = 1; i <= cnt; i++) {
                for (int j = 0; j < n; j++)
                    cout << ((j >> (cnt - i)) & 1);
                cout << endl;
                for (int j = 1; j <= n - b; j++) cin >> s[j][i];
            }
            for (int i = 1; i <= n - b; i++) {
                int x = 0;
                for (int j = 1; j <= cnt; j++) x = x * 2 + s[i][j] - 48;
                flg[x] = 1;
            }
            for (int i = 0; i < n; i++)
                if (!flg[i]) cout << i << " ";
        }
        cout << endl;
        cin >> z;
    }
    return 0;
}