跳转至

题解：P13134 [GCJ 2018 Qualification] Go, Gopher!

思路与算法

Special Thanks : @kzt123，教会了我交互题并一起写了一份代码。

题意理解

你和人机 Gopher 交流时，你指定布置一个格子，它会在指定的格子以及周围一圈九个格子随机布置，现在需要你跟它进行交互，使得它能够布置一个大小不小于 \(\mathbf{A}\) 的矩形。

样例分析

根据题意，我们不难发现，Gopher 始终会在你选定的格子为中心的 \(9 \times 9\) 的区域布置，也就是说，我们每次都在一个点不停的布置，总会有一个时候，Gopher 能够布置完全部九个格子。

首先我们看到题目给出的例子：img

这里我们铺设了一个 \(3 \times 4\) 的大小的矩形，根据我们的思路，我们把它分为多个部分。（如下表，\(\text A\) 部分和 \(\text{B}\) 部分）

行 列 1 2 3 4
1 A A A B
2 A A A B
3 A A A B

这里，跟着我们的思路，我们可以先布置 \(3 \times 3\) 的区域 A，这部分区域可以照着我们的思路解决，即：不断布置点 \((2, 2)\) 使得 \((1, 1)\) 到 \((3, 3)\) 的所有区域均被布置。

这时候，就只剩下最后一列了。为了避免往外布置更多无用的格子，我们在点 \((2, 3)\) 不断布置，使得第四列的所有点被布置。

所以，总的操作就是：处理完整的九宫格，处理最后剩下的不完整的九宫格。

这个时候，@kzt123 提出，我们可以使用 STL 中 bitset 的特性来存储我们当前行的格子的布置状态，同时，它还可以直接被赋值为 \(0\) 来快速初始化整个数组为零。

小小科普一下

Tips : bitset 是 C++ 中用来存储 0 或 1 的类型，它可以直接给出数的二进制编码，且对二进制位数没有要求，同时，我们还可以直接用十进制数来赋值（整形）。

定义方法：

1
bitset <128> bs;

注：<> 中的 128 可被替换成为任何正整数，表示这个 bitset 所占的二进制位数。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<bits/stdc++.h>
using namespace std;

// b[1], b[2], b[3]分别表示第1,2,3行的准备状态
bitset<1005> b[4];

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int t;
    cin >> t;

    while(t--) {
        // 重置状态
        b[0] = b[1] = b[2] = b[3] = 0;

        int a;
        cin >> a;

        // 计算需要的列数
        int b1 = ceil(a / 3.0);

        // 从第 2 列开始，每次加三（移动到下一次的中心点）
        for(int i = 2; i + 1 <= b1; i += 3) {
            // 确保当前区域的格子都被布置
            while(!b[1][i-1] || !b[1][i] || !b[1][i+1] ||
                !b[2][i-1] || !b[2][i] || !b[2][i+1] ||
                !b[3][i-1] || !b[3][i] || !b[3][i+1]) {
                // 当前区域的中心坐标
                cout << 2 << " " << i << endl;

                // 实际准备的格子
                int t1, t2;
                cin >> t1 >> t2;

                // 已经完成
                if(t1 == 0 && t2 == 0) {
                    break;
                }

                // 标记该格子
                b[t1][t2] = 1;
            }
        }

        // 处理最后几列
        int t1, t2;
        cout << 2 << " " << b1 - 1 << endl;

        // 不断发出坐标，直到完成
        while(cin >> t1 >> t2) {
            if(t1 == 0 && t2 == 0) {
                break;
            }
            cout << 2 << " " << b1 - 1 << endl;
        }
    }
    return 0;
}