自动搬运

查看原文

来自洛谷，原作者为

	ix35 垒球

搬运于2025-08-24 21:28:36，当前版本为作者最后更新于2021-06-17 14:33:14，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

一道非常有意思的题目。

考虑第 $i$ 位，有以下几种情况：

1. $a,b,c$ 第 $i$ 位全是 $0$；

2. $a,b,c$ 中恰有一个第 $i$ 位是 $1$；

3. $a,b,c$ 中恰有两个第 $i$ 位是 $1$；

4. $a,b,c$ 第 $i$ 位全是 $1$。

$1,4$ 和 $2,3$ 分别对称，所以我们只讨论 $1,2$。

1. $a,b,c$ 第 $i$ 位全是 $0$。

那么我们只要 $x_i\to !x_i$，即可保证所有满足约束的数都是第 $i$ 位为 $0$ 的。

2. $a,b,c$ 中恰有一个第 $i$ 位是 $1$（不妨设为 $a$）。

由于我们希望结果只有这三种，所以只要第 $i$ 位是 $1$，我们就可以立刻推出这个数一定是 $a$，也就需要 $n$ 个条件，形如 $x_i\to x_j$ 或 $x_i\to !x_j$，其中 $x_j$ 还是 $!x_j$ 取决于 $a$ 的第 $j$ 位。

这样一来，考虑有哪些数能够符合全部的条件：

• $a,b,c$ 肯定都是符合的；

• 假如一个不是 $a,b,c$ 的数也符合，那么考虑第 $i$ 位，如果是情况 $1$ 则这个数的第 $i$ 位一定和 $a,b,c$ 相同；如果是情况 $2$，那么这个数的第 $i$ 位一定不能和 $a$（也就是独特的那个）相同。

也就是说，这个数是取出 $a,b,c$ 每一位的众数构成的，设为 $d$。

如果 $d=a$ 或 $d=b$ 或 $d=c$，那么上面的构造可以保证满足题意。

否则，一定不存在满足题意的构造，这是因为使得 $a,b,c$ 满足的约束，也会使得 $d$ 满足，证明如下：

不妨设约束为 $x_i\to x_j$，假设 $d$ 不满足，那么有 $d$ 的第 $i$ 位为 $1$ 且第 $j$ 位为 $0$，所以 $a,b,c$ 有至少两个第 $i$ 位为 $1$，也至少有两个第 $j$ 位为 $0$，那么根据抽屉原理肯定有一个数同时满足这两个条件，也就不满足约束 $x_i\to x_j$，矛盾。

但是现在的构造约束数量是 $O(n^2)$，有些大，考虑优化。

如果 $a$ 中有许多“独特”的位置（和 $b,c$ 都不同的），我们钦定其中一个 $i$ 向其他所有位置限制约束，而其他独特位置只需要约束 $i$ 即可，这样就实现了 $O(n)$ 个约束。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=60;
int n,cnt,a[MAXN],b[MAXN],c[MAXN],pos[3],flg[3];
int ans1[MAXN*MAXN],flg1[MAXN*MAXN],ans2[MAXN*MAXN],flg2[MAXN*MAXN];
ll va,vb,vc,vd;
int main () {
	scanf("%d",&n);
	for (int i=1;i<=n;i++) {
		scanf("%d",&a[i]);
		if (a[i]) {va+=(1ll<<i);}
	}
	for (int i=1;i<=n;i++) {
		scanf("%d",&b[i]);
		if (b[i]) {vb+=(1ll<<i);}
	}
	for (int i=1;i<=n;i++) {
		scanf("%d",&c[i]);
		if (c[i]) {vc+=(1ll<<i);}
		if (a[i]+b[i]+c[i]>=2) {vd+=(1ll<<i);}
	}
	if (vd!=va&&vd!=vb&&vd!=vc) {
		printf("-1\n");
		return 0;
	}
	for (int i=1;i<=n;i++) {
		if (a[i]==b[i]&&a[i]==c[i]) {
			if (a[i]==1) {
				cnt++;
				ans1[cnt]=ans2[cnt]=i,flg1[cnt]=0,flg2[cnt]=1;
			} else {
				cnt++;
				ans1[cnt]=ans2[cnt]=i,flg1[cnt]=1,flg2[cnt]=0;
			}
		} else if (b[i]==c[i]) {
			if (pos[1]) {
				cnt++;
				ans1[cnt]=i,flg1[cnt]=a[i],ans2[cnt]=pos[1],flg2[cnt]=a[pos[1]];
			} else {
				for (int j=1;j<=n;j++) {
					if (j!=i) {
						cnt++;
						ans1[cnt]=i,flg1[cnt]=a[i],ans2[cnt]=j,flg2[cnt]=a[j];
					}
				}
				pos[1]=i;
			}
		} else if (a[i]==b[i]) {
			if (pos[3]) {
				cnt++;
				ans1[cnt]=i,flg1[cnt]=c[i],ans2[cnt]=pos[3],flg2[cnt]=c[pos[3]];
			} else {
				for (int j=1;j<=n;j++) {
					if (j!=i) {
						cnt++;
						ans1[cnt]=i,flg1[cnt]=c[i],ans2[cnt]=j,flg2[cnt]=c[j];
					}
				}
				pos[3]=i;
			}
		} else {
			if (pos[2]) {
				cnt++;
				ans1[cnt]=i,flg1[cnt]=b[i],ans2[cnt]=pos[2],flg2[cnt]=b[pos[2]];
			} else {
				for (int j=1;j<=n;j++) {
					if (j!=i) {
						cnt++;
						ans1[cnt]=i,flg1[cnt]=b[i],ans2[cnt]=j,flg2[cnt]=b[j];
					}
				}
				pos[2]=i;
			}
		}
	}
	printf("%d\n",cnt);
	for (int i=1;i<=cnt;i++) {
		if (!flg1[i]) {printf("!");}
		printf("x%d -> ",ans1[i]);
		if (!flg2[i]) {printf("!");}
		printf("x%d\n",ans2[i]);
	}
	return 0;
}