专栏文章

题解：CF1628C Grid Xor

JJim_Franklin
CF1628C题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@miqkix83
此快照首次捕获于
2025/12/04 06:18
3 个月前
此快照最后确认于
2025/12/04 06:18
3 个月前
查看原文
是 zak 的做法 QwQ。
我们钦定 bb 的第一行都是 00。
然后根据 ai,j=bi−1,j⊕bi+1,j⊕bi,j+1⊕bi,j−1a_{i,j}=b_{i-1,j}\oplus b_{i+1,j}\oplus b_{i,j+1}\oplus b_{i,j-1} （不存在的 bb 我们将他设为 00 ）就可以递推出 bb 数组，现在要证明此时的 bb 数组一定是合法的。
题目中提到了 bb 一定是有解的（这个其实可以构造证明）。
设 v=b1,1v=b_{1,1} 将 b1,1b_{1,1} 异或上 vv 这时会影响到的位置有 (2,1)(2,1) 和 (1,2)(1,2) 发现能够同时影响到他们的格子还有 (2,2)(2,2) 于是把 b2,2b_{2,2} 再异或上 vv 重复这么做下去，并对第一行的其他格子如法炮制，就能把第一行的 bb 全部变成 00。
于是我们证明了对于任意一个合法的 bb 我们一定可以将他转换为一个第一行都是 00 的且合法的 b′b' 。
于是我们的做法就得到了证明。
CPP
void sol(){
	n=rd();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)a[i][j]=rd();
	int ans=0;
	for(int i=1;i<n;i++)
		for(int j=1;j<=n;j++)
			res[i+1][j]=a[i][j]^res[i-1][j]^res[i][j+1]^res[i][j-1];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
          ans^=res[i][j],res[i][j]=0;
	cout<<ans<<'\n';
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...