Codeforces Round#767(Div.2) E. Grid Xor

本文主要是介绍Codeforces Round#767(Div.2) E. Grid Xor，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

注：集合{s1，s2，…，sm}的异或和被定义为 $s_1⊕s_2⊕…⊕s_m$ ，其中⊕ 表示按位异或运算。

在赢得IOI后，维克多给自己买了一个n×n的网格，每个单元格中都包含整数。n是一个偶数。第i行和第j列单元格中的整数为 $a_{i,j}$ 。

不幸的是，Mihai从Victor那里偷走了网格，并告诉他，他将只返回一个条件：Victor必须告诉Mihai整个网格中所有整数的异或和。
Victor不记得网格的所有元素，但他记得一些关于它的信息：对于每个单元格，Victor记得所有相邻单元格的异或和。
如果两个单元共享一条边，则它们被视为相邻单元——换句话说，对于某些整数 $1 \leq i 、 j ， k ， l \leq n$ 如果| i，则第i行和第j列中的单元是第k行和第l列中的单元的邻居.那么有 $∣ i - k ∣ = 1 且 j = l 或 i = k 且 ∣ j - k ∣ = 1$

维克多想让你帮他找回电网。你能用维克多记得的信息来找到整个网格的异或和吗？

可以证明，答案是独一无二的。

输入

输入的第一行包含一个整数t（1≤T≤100）-测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个偶数整数n（2≤N≤1000）-网格的大小。

然后跟随n行，每行包含n个整数。第i行中的第j个整数代表第i行和第j列中所有相邻单元格中的整数的异或和。

保证所有测试用例中n的总和不超过1000，并且在原始网格中为0≤i，j≤2³⁰−1.

黑客格式

要破解解决方案，请使用以下格式：

第一行应该包含一个整数t（1≤T≤100）-测试用例的数量。
每个测试用例的第一行应该包含一个偶数整数n（2≤N≤1000）-网格的大小。

接下来应该有n行，每行包含n个整数。第i行中的第j个整数是Victor原始网格中的 $a_{ij}$ 。网格中的值应为 $0<=a_{ij}<=2^{30}-1$

所有测试用例中n的总和不得超过1000。

输出

对于每个测试用例，输出一个整数——整个网格的异或和。

题解

官方：
让我们表示 count(i,j) 单元格 (i,j) 在查询中贡献的次数。我们注意到 count(i,j) 对于所有单元格 (i,j) 必须是奇数。
以下构造满足条件：遍历从第 2 行到第 n 行的所有行。对于每一行，遍历它的所有单元格并查询单元格 (i,j) 如果它上面的单元格如果单元格 (i-1,j) 被贡献 (count(i-1,j) =0 (mod 2)) 一个偶数次数和与 $a_{ij}$ 异或curent_answer（curent_answer 最初为 0）
我们可以证明第 1 行的任何初始排列都会产生一个有效的唯一解，该解可以贪婪地构造。这是通过以使第 1 行有效的方式选择第 2 行来完成的，并且很明显看到只有一个解决方案。
让我们假设存在一些解决方案。如果我们交换第 1 行中的某个元素 (1,x)，您会注意到它会改变元素 (2,x+1) 和 (2,x−1)，这同样会改变 (3,x−2)，( 3,x), (3,x+2)。通过 n/2 行，它将只交换所有 x 的 (n/2,2x) 或 (n/2,2x+1)。这对最后一行没有影响，因为它在那之后对称地循环。所有其他行都在传播中得到处理。
个人
题中给出每个数相邻的异或和，求全部数的异或和。只要将数组的每一个值都异或一遍就是答案。题中给出相邻异或和，已经遍历过了周围的数，将给的相邻异或和记录，只需要记录哪个数已经被用过用过，哪个数没用过，用过了就不用管了，已经将他的和记录了，（用过的是当前这个数周围的数），没用过将他的值加入答案即可标记周围的数用过了。但可能出现的情况是这个数被用了两次（因为是通过周围影响的），这个数异或两次相当于又去掉了，所以这个点应当是没用过的，之后再加上即可

#include<bits/stdc++.h>
using namespace std;
int st[1005][1005], a[1005][1005];
void solve()
{int n;cin >> n;for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)st[i][j] = 0;for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)cin >> a[i][j];int ans = 0;for(int i=2;i<=n;i++)for (int j = 1; j <= n; j++){if (st[i-1][j] == 0){   ans ^= a[i][j];st[i][j - 1] ^= 1;st[i][j + 1] ^= 1;st[i - 1][j] ^= 1;st[i +1][j] ^= 1;}}cout << ans << endl;
}
int main()
{int t;cin >> t;while (t--){solve();}
}