CF1673F 题解

· · 题解

首先我们不妨在一维的一根线上思考这个问题。

我们发现：我们可以这样安排：

小偷初始位置在 0 号点，追踪仪器初始化为 0。

走到 1 号点时，追踪仪器的数字变成 1。

此时需要异或 1，因此 0 号点到 1 号点路径长度为 1。

走到 2 号点时，追踪仪器的数字变成 2。

此时从 (01)_2 变成 (10)_2 需要异或 (11)_2 也就是 3，因此 1 号点到 2 号点的路径长度为 3。

走到 3 号点时，追踪仪器的数字变成 3。

此时从 (10)_2 变成 (11)_2 需要异或 (01)_2 也就是 1，因此 2 号点到 3 号点的路径长度为 1。

走到 4 号点时，追踪仪器的数字变成 4。

此时从 (11)_2 变成 (100)_2 需要异或 (111)_2 也就是 7，因此 3 号点到 4 号点的路径长度为 7。

以此类推，走到 31 号点时，追踪仪器的数字变成 31，也就是 (11111)_2。

由于走回头路时，两段相同的路径异或在一起会互相抵消，因此我们可以直接根据追踪仪器上的数字来确定此时小偷的位置。

同理我们可以把这个一维的东西上升到二维。

那么我们很容易想到，让前五位表示横着走的，后五位表示竖着走的。

举个例子，现在小偷的位置是 (32, 32)，也就是说小偷横着在 31 号点（注意 (1, 1) 是 0 号点）竖着也在 31 号点，那么我们希望追踪仪器上显示的就是 (1111111111)_2。

假如小偷的位置是 (16, 16)，那么追踪仪器上显示的就是 (0111101111)_2。

这样显然可以根据追踪仪器上的数来确定小偷的位置，但是也存在问题：这样的路径长是多少？

不难想到，我们这样设计路径长的时候，横着的每条路径的长度其实是 i \oplus (i - 1)，而竖着的路径长度为 (i \oplus (i - 1)) \times 2^5。

这么一合计，你发现你的路径总长度约为 1.36 \times 10^5，超出了题目限制。

我们考虑能不能精简路径长度呢？

我们发现 i \oplus (i - 1) 这个长度很浪费，因为每个 i \oplus (i - 1) 里都有好几个二进制位上有 1，而实际上我们不需要那么多 1。这时我们想起了格雷码，这个东西每次后一位只会和前一位最多有一位相差 1，是我们优化路径长度的不二之选。

然而就算加了格雷码之后，我们发现，所有路径的总长大约为 8.4 \times 10^4，仍然超出了题目限制。

那么应该怎么办呢？

我们想到，竖着的路径长度后面都需要乘一个 2 ^ 5，而横着的就不用，这就很不平衡，横着的往外延伸多远都很短，竖着的往外延伸一点就老长。

不患寡而患不均。

—— 《论语 · 季氏》

显然，让横竖相差过大不是我们希望看到的，那么我们可以考虑把横竖交叉排列，让 1, 3, 5, 7, 9 位表示横的，2, 4, 6, 8, 10 位表示竖的。比如 (2, 2) 就可以表示为 (0000000011)_2，这相比原来的 (0000100001)_2 要节约了很多。

此时就算 n 卡满，路径长的总和也只有 4.7 \times 10^4，刚好卡进了 4.8 \times 10^4 的限制，不多不少刚刚好。

如何求格雷码呢？官方题解给了我们一个很好的启发：

如果我们已经有了 k 位的格雷码，我们可以扩展到 k + 1 位。方法是先把它复制一遍，在复制后的格雷码前面加个 1，在原来的格雷码前面加个 0。

—— 译自官方题解

代码实现如下（部分参考官方题解）：

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

const int N = 32;
int memory[114514];

inline int read()
{
    long long xr = 0, F = 1;
    char cr;
    while(cr = getchar(), cr < '0' || cr > '9')
        if(cr == '-')
            F = -1;
    while(cr >= '0' && cr <= '9') xr = (xr << 3) + (xr << 1) + (cr ^ 48), cr = getchar();
    return xr * F;
}

int maxpow2(int t)
// 找到 t 里有几个因数 2 
{
    int k = t;
    if(memory[t] != -1)
        return memory[t];
    int p = 1;
    while(!(t & 1))
    {
        p <<= 1;
        t >>= 1;
    }
    return memory[k] = p;
}

int n, k;
int h[N][N - 1];
// 横着的街道的长度 
int s[N - 1][N];
// 竖着的街道的长度 
int way[N][N];
// 根据位置推测长度 

struct pos
{
    int x;
    int y;
};
pos p[N * N];
// 根据长度推测位置 

int main()
{
    n = read(), k = read();
    memset(memory, -1, sizeof(memory));
    for(int i = 0; i < N; i = i + 1)
        for(int j = 0; j < N - 1; j = j + 1)
            h[i][j] = maxpow2(j + 1) * maxpow2(j + 1);
    for(int i = 0; i < N - 1; i = i + 1)
        for(int j = 0; j < N; j = j + 1)
            s[i][j] = 2 * maxpow2(i + 1) * maxpow2(i + 1);
    for(int i = 0; i < n; i = i + 1)
    {
        for(int j = 0; j < n - 1; j = j + 1)
            cout << h[i][j] << " ";
        cout << endl;
    }
    for(int i = 0; i < n - 1; i = i + 1)
    {
        for(int j = 0; j < n; j = j + 1)
            cout << s[i][j] << " ";
        cout << endl;
    }
    for(int i = 0; i < n; i = i + 1)
        for(int j = 0; j < n; j = j + 1)
        {
            if(!i && !j)
                continue;
            if(!i)
                way[i][j] = way[i][j - 1] ^ h[i][j - 1];
            else
                way[i][j] = way[i - 1][j] ^ s[i - 1][j];
            p[way[i][j]] = (pos){i, j};
        }
    int now = 0;
    while(k --)
        now ^= read(),
        cout << p[now].x + 1 << " " << p[now].y + 1 << endl;
    return 0;
}