题解：CF1628C Grid Xor

· · 题解

神奇做法，被同学锐评在看懂题面之前就过题了。

题意

给出一个 n \times n 的方阵 a，求另外一个 n \times n 的方阵 b 使得 a 的每个位置的值都是方阵 b 上同样位置相邻元素的异或和，只需要输出方阵 b 的异或和。n 是偶数。

题解

我们可以把题目转化为一个点灯游戏。有一个 n \times n 的网格，每个网格上都有灯，最开始所有的灯都没有点亮。每一次可以选择一个位置，把它相邻位置的灯都亮变暗，暗变亮。要使得最后所有的灯都点亮。容易发现原问题的答案就是 a 在点灯方案中所有选择的位置上的异或和。

点灯游戏可以这么做：每次看点灯位置的左侧和上侧相邻元素有没有被点亮（假设超出边界的所有灯怎么点都不会亮），都没被点亮就选择该位置点灯。

上图展示了 n=50 时的点灯情况（为 1 的是点灯的位置）。我们发现整个方阵被大致分为了四个部分分别点灯，可以参照图思考这种点灯方案为什么是正确的。我们实际上在用船形密铺方阵。船形长这样（可以旋转）：

 ++
++++
 ++

经过简单的讨论后我们就证明了这种方案可以使得 n \times n 的网格上的灯都被点亮。那么求 a 对应位置的元素的异或和，就相当于求 b 的所有元素的异或和，就是答案了。

代码：

#include<iostream>
using namespace std;
bool vis[1001][1001];//点灯情况
int a[1001][1001];
int main(){
    int T;
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                cin >> a[i][j];
                vis[i][j]=false;
            }
        }
        int ans=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if((i-1>=1 && vis[i-1][j]) || (j-1>=1 && vis[i][j-1])){
                    continue;//左侧或上侧的灯被点了，这次的点灯就跳过
                }
                if((i-1>=1))    vis[i-1][j]^=1;
                if(i+1<=n)  vis[i+1][j]^=1;
                if(j-1>=1)  vis[i][j-1]^=1;
                if(j+1<=n)  vis[i][j+1]^=1;
                ans^=a[i][j];
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

附注

对于 n 是奇数的情况，本方案不能给出正确的结果（事实上，答案也可能不唯一）。原因是：方阵 b 的最后一行元素的异或和实际上要等到下一行再来求，所以就会把最后一行的若干元素漏掉。