[CERC2016]Lost Logic 题解
ix35
·
·
题解
一道非常有意思的题目。
考虑第 i 位，有以下几种情况：
-
-
-
-
---
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)$ 个约束。
```cpp
#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;
}
```