鸽了这么久的题解，还是要补一发
虽然还有一堆堆题要刷（意味着可能会有一堆题解被鸽掉（＞人＜；））
# 题意
有 $n$ 个取值为 1或 0 的变量 $x_1,\cdots,x_n$，以及两个函数 $f(),g()$。有四种形式的式子：
- $(x_i\text{OR }x_j)$
- $(\neg x_i\text{OR }x_j)$
- $(x_i\text{OR }\neg x_j)$
- $(\neg x_i\text{OR }\neg x_j)$
Hint. $\neg x_i$ 表示 “反 $x_i$”：若 $x_i=0$ 则 $\neg x_i=1$，若 $x_i=1$ 则 $\neg x_i=0$。
函数 $f()=F_1\text{AND }F_2\text{AND }\cdots\text{AND }F_{m_1}$，其中 $F_i$ 是上述四种式子之一；
$g()=G_1\text{AND }G_2\text{AND }\cdots\text{AND }G_{m_2}$，同理。
给出 $n,m_1,m_2$ 和 $F_1,\cdots,F_{m_1}$、$G_1,\cdots,G_{m_2}$。求是否存在一种 $x_1,\cdots,x_n$ 的取值使得 $f()\not=g()$，如果存在，输出任意一种满足条件的 $x_1,\cdots,x_n$ 的取值。
> 数据规模 $1\le n\le1000$；$1\le m_1,m_2\le n^2$。
# 解析
从 $x_i$ 只能取 0/1 就能够感到有一点 2-sat 的意思，再看到那四种形式的式子以及 $f(),g()$ 的表达式都能够用 2-sat 表示出来，就可以往这个方向想。
于是先分别建出 $f()$ 和 $g()$ 的 2-sat 的有向图 $F’,G’$。
不妨先考虑几种特殊情况：
- $F’$ 和 $G’$ 都无解，那么 $f()=g()=0$，不存在满足条件的 $x_1,\cdots,x_n$；
- $F’$ 无解，那么求出 $G’$ 的任意一个解就是答案；
- $G’$ 无解与 2. 同理。
于是就剩下 $F’$ 和 $G’$ 都有解的情况了。
我们先给 $F’$ 和 $G’$ 做一个传递闭包 （如果原图存在一条从 $u$ 到 $v$ 的路径， 则在新图中连一条 $u\to v$ 的边）。但是要快速地传递闭包需要一些操作 : ) —— bitset ，用 bitset 存储 邻接表，传递闭包就像这样：
1
2
3
4
| for(int v=0;v<2*n;v++)
for(int u=0;u<2*n;u++)
if(lnk[u][v])
lnk[u]|=lnk[v];
|
做完传递闭包后，我们就可以清楚地看到变量之间互相影响的关系。然后就可以开始构造 解了：
先求出“要使 $f()=1$，哪些 $x_i$ 的值是确定的”：
① 找到 $F’$ 中的边 $x_i\to x_i’$ 或 $x_i’\to x_i$，出现这种边意味着 $x_i’/x_i$ 一定被选。
② $x_i’/x_i$ 的所有儿子的取值也是确定的。
再求出“要使 $g()=1$ 哪些 $x_i$ 的值是确定的”，同理。
如果在 $f()$ 中，$x_i$ 已经确定，而在 $g()$ 中没有确定或者确定的值和 $f()$ 中不同，就固定 $x_i$ 为 $f()$ 中的相反值，求出 $G’$ 的一个解，此时 $g()=1,f()=0$。
如果在 $g()$ 中，$x_i$ 已经确定，在 $f()$ 中没有确定或相反，同理。
如果还没找到，就找是否存在 $x_i,x_j$，满足在 $f()$ 和 $g()$ 中都没有确定，但 $f()$ 中存在 $x_i$ 对 $x_j$ 的限制（比如“如果 $x_i=1$ 则 $x_j=1$”）、$g()$ 中 $x_i$ 和 $x_j$ 互不影响，这样就可以固定 $x_i$ 和 $x_j$ 使得它们的取值不满足 $f()$ 中 $x_i$ 与 $x_j$ 的限制，从而使 $f()=0,g()=1$。
如果 $x_i,x_j$ 满足在 $f()$ 中 $x_i$ 和 $x_j$ 互不影响、$g()$ 中存在 $x_i$ 对 $x_j$ 的限制，同理。
如果还没有解，则说明所有情况下，$f()=g()$。
# 源代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
|
#include<bitset>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1000;
struct _2SAT{
int n,m,fail;
int fix[N*2+3];
bitset<N*2+3> lnk[N*2+3];
void Fix(int u){
fix[u]=1;fix[u^1]=0;
for(int v=0;v<n*2;v++)
if(lnk[u][v] && fix[v]==-1)
Fix(v);
}
void Build(int _n,int _m){
n=_n,m=_m;
for(int i=1;i<=m;i++){
int u,v;scanf("%d%d",&u,&v);
if(u>0) u=(u-1)<<1|1;
else u=(-u-1)<<1;
if(v>0) v=(v-1)<<1|1;
else v=(-v-1)<<1;
lnk[u^1][v]=lnk[v^1][u]=1;
}
for(int i=0;i<2*n;i++) lnk[i][i]=1,fix[i]=-1;
for(int v=0;v<2*n;v++)
for(int u=0;u<2*n;u++)
if(lnk[u][v])
lnk[u]|=lnk[v];
fail=0;
for(int i=0;i<n;i++)
if(lnk[i<<1][i<<1|1] && lnk[i<<1|1][i<<1])
fail=1;
if(!fail){
for(int i=0;i<n;i++){
if(fix[i<<1]!=-1 || fix[i<<1|1]!=-1) continue;
if(lnk[i<<1][i<<1|1]) Fix(i<<1|1);
if(lnk[i<<1|1][i<<1]) Fix(i<<1);
}
}
}
void Solve(int fixA=-1,int fixB=-1){
if(fixA>=0) Fix(fixA);
if(fixB>=0) Fix(fixB);
for(int i=0;i<2*n;i++)
if(fix[i]==-1)
Fix(i);
for(int i=0;i<n;i++){
printf("%d",fix[i<<1|1]);
if(i==n-1) putchar('\n');
else putchar(' ');
}
}
}SaA,SaB;
int main(){
int n,ma,mb;
scanf("%d%d%d",&n,&ma,&mb);
SaA.Build(n,ma);
SaB.Build(n,mb);
if(SaA.fail && SaB.fail){printf("SIMILAR\n");return 0;}
if(SaA.fail){SaB.Solve();return 0;}
if(SaB.fail){SaB.Solve();return 0;}
for(int i=0;i<2*n;i++){
if(SaA.fix[i]!=0 && SaB.fix[i]==0){
SaA.Solve(i);
return 0;
}
if(SaA.fix[i]==0 && SaB.fix[i]!=0){
SaB.Solve(i);
return 0;
}
}
for(int i=0;i<2*n;i++){
if(SaA.fix[i]==-1){
for(int j=0;j<i;j++)
if(SaA.fix[j]==-1 && !SaA.lnk[i][j] && SaB.lnk[i][j]){
SaA.Solve(i,j^1);
return 0;
}
}
if(SaB.fix[i]==-1){
for(int j=0;j<i;j++)
if(SaB.fix[j]==-1 && !SaB.lnk[i][j] && SaA.lnk[i][j]){
SaB.Solve(i,j^1);
return 0;
}
}
}
printf("SIMILAR\n");
return 0;
}
|
# The End
Thanks for reading!
只是因为这道题很有意思 : )