自动搬运

查看原文

来自洛谷，原作者为

	chen_03 AFO | 垫底人，啥都不会 | 谁能赐予我一个脑子？ | Brute force 出不了奇迹。

搬运于2025-08-24 22:23:37，当前版本为作者最后更新于2020-12-26 18:17:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我的做法是二进制加法器。似乎大多数人都不是这个做法？

首先，查询每一行、每一列的异或和。

以每一行为例，如果两个黑色像素在同一行，那么所有行的异或和都为 $0$；如果不在同一行，则它们所在的行的异或和为 $1$，黑色像素的竖直距离就是这两个 $1$ 之间的距离。

如果我们把这个异或和再做一遍前缀异或和，那么黑色像素的竖直距离就是前缀异或和中 $1$ 的数量。我们只要想办法统计 $1$ 的数量即可。

每一列同理。注意到行的前缀异或和中，最后一个数一定为 $0$，所以我们可以把行和列的前缀异或和放在一起统计。

那么如何统计前缀异或和中 $1$ 的数量呢？

我们想到了二进制加法器：从 $0$ 开始，把前缀异或和中的数一个一个地加上去。实现起来，就是维护每一位上的数字分别是什么，以及每一位上有没有进位。由于每次加法都是加 $0$ 或 $1$，所以每次进位操作可以只用一个指令。

我们要统计的数（距离）最多为 $H+W-2\le 398$，有 $9$ 个二进制位，所以每次加法用 $9$ 个指令维护每一位上的数字，用 $8$ 个指令维护每一位上有没有进位（最高位上一定不会进位）。每一位上的数字用异或操作维护，进位用与操作维护。

统计出 $1$ 的数量后，我们把它与 $K$ 一位一位地进行比较。把每一位都异或一下，把异或操作的结果或起来，再取非即可。此前要用某种方法搞出一个结果一定为 $0$ 的指令和一个结果一定为 $1$ 的指令。

我的代码使用的指令数最多为 $7200+$，读入值的数量最多不超过 $10^5$，可以轻松通过本题。当然这个数量可以继续优化，但没必要。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
int add_not(int);
int add_and(vector<int> Ns);
int add_or(vector<int> Ns);
int add_xor(vector<int> Ns);
int n,m,k,cnt,zero,one;
vector<int> vec;
inline void add(int pos){
	int bg=cnt-16;
	add_xor({bg,pos});
	cnt=add_and({bg,pos});
	for(int i=1;i<8;++i){
		add_xor({bg+i*2,cnt});
		cnt=add_and({bg+i*2,cnt});
	}
	cnt=add_xor({bg+16,cnt});
}
void construct_network(int H,int W,int K){
	n=H;m=W;k=K;
	vec.resize(m);
	for(int i=0;i<m;++i)vec[i]=i;
	cnt=add_xor(vec);
	vec.resize(m+1);
	for(int i=1;i<n;++i){
		for(int j=0;j<m;++j)vec[j]=i*m+j;
		vec[m]=cnt;
		cnt=add_xor(vec);
	}
	vec.resize(n+1);
	for(int i=0;i<m;++i){
		for(int j=0;j<n;++j)vec[j]=j*m+i;
		vec[n]=cnt;
		cnt=add_xor(vec);
	}
	zero=add_xor({0,0});
	for(int i=1;i<17;++i)
		cnt=add_or({zero});
	for(int i=n*m;i<n*m+n+m;++i)add(i);
	int bg=cnt-16;
	vec.resize(9);
	one=add_not(zero);
	for(int i=0;i<9;++i)
		vec[i]=add_xor({bg+2*i,(k>>i)&1?one:zero});
	add_not(add_or(vec));
}