$\text{k-SAT}$
给定 $n$ 个 $\text{bool}$ 变量和 $m$ 个约束条件，每个条件形如 $x_1\oplus x_2\oplus … \oplus x_k=0/1$ (此处 $\oplus$ 表示一种 $bool$ 运算)，求是否有解并能构造，可证明当 $k>2$ 时 $\text{k-SAT}$ 是 $\text{NPC}$ 问题
$\text{2-SAT}$
建图
由于每个点只有 $0/1$ 两种取值，那么对于每个点 $i$ ，拆成两点 $i,i+n$ 分别表示 $x_i=1,x_i=0$
对于约束关系，考虑建有向边 $x\rightarrow y$ 表示选 $x$ 则必须选 $y$
- 当 $a_i\ \text{xor}\ a_j=1$ ，即 $i,j$ 不能同时选，则有 $i\rightarrow j+n,j\rightarrow i+n$
- 当 $a_i\ \text{xor}\ a_j=0$ ，即 $i,j$ 必须同时选，则有 $i\rightarrow j,j\rightarrow i$
- 当 $a_i\ \text{or}\ a_j=1$ ，即 $i,j$ 任选，则有 $i\rightarrow j+n,j+n\rightarrow i,j\rightarrow i+n,i+n\rightarrow j$
- 当 $a_i=1 \mid a_i\ \text{and}\ a_j=1$ ，即 $i$ 必须选，则有 $i+n\rightarrow i$
考虑到若有 $i\rightarrow j$ ，由于原命题与逆否命题真假相同，则有 $inv_i\rightarrow inv_j$ ，那么有简化代码：
inline void insert(int u,int v){ add(x,y),add(y>n ? y-n : y+n,x>n ? x-n : x+n)}
求解
不妨转化为强连通分量问题，即若 $i,i+n$ 在同一强连通分量则无解，用 $\text{tarjan}$ 求解即可
具体的， $\text{tarjan}$ 所得的拓扑序是逆序的，即后求出的强连通分量可能到达先求出的强连通分量，而先求出的不能到达后求出的，那么若 $scc_i<scc_{i+n}$ 则 $i$ 所在的强连通分量先求出，那么选 $i$
1 | const int N=2e6+100; |
例题
P4171 [JSOI2010] 满汉全席
没什么好说的板板题
P5782 [POI2001] 和平委员会
仍然是板板题，只不过数据输入方式对 $i\rightarrow i+n$ 建边方式并不友好
P3825 [NOI2017] 游戏
题面好长不想写
对于 $d=0$
即没有
x的赛场，可以发现这就是裸的 $\text{2-SAT}$对于给定的四元组，分类讨论：
- 第 $i$ 场不能用 $h_i$ : 不管该四元组
- 第 $j$ 场不能用 $h_j$ : 那么第 $i$ 场不能用 $h_i$
- 正常连边即可
通过字典序大小关系建边，输出方案时只有两种可能的赛车，那么仍按照字典序大小关系输出即可
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
26inline int get_num(int k,char ch){
if(s[k]=='a') return ch=='B' ? k : k+n;
return ch=='A' ? k : k+n;
}
int main(){
scanf("%d%d",&n,&d); scanf("%s",s+1); scanf("%d",&m);
// puts("here");
for(rei i=1,pos1,pos2;i<=m;++i){
scanf("%d %s %d %s",&pos1,ss+1,&pos2,tt+1);
flag1=ss[1],flag2=tt[1];
// printf("%d %c %d %c\n",pos1,flag1,pos2,flag2);
if(s[pos1]==flag1+32) continue;//大写
pos1=get_num(pos1,flag1),pos2=get_num(pos2,flag2);
if(s[pos2]==flag2+32) add(pos1,pos1>n ? pos1-n : pos1+n);
else add(pos1,pos2),add(pos2>n ? pos2-n : pos2+n,pos1>n ? pos1-n : pos1+n);
}
for(rei i=1;i<=(n<<1);++i) if(!low[i]) tarjan(i);
for(rei i=1;i<=n;++i) if(scc[i]==scc[i+n]) return puts("-1"),0;
for(rei i=1;i<=n;++i){
if(s[i]=='a') printf("%c",scc[i]<scc[i+n] ? 'B' : 'C');
else if(s[i]=='b') printf("%c",scc[i]<scc[i+n] ? 'A' : 'C');
else printf("%c",scc[i]<scc[i+n] ? 'A' : 'B');
}
getchar(),getchar();
return 0;
}再考虑全部的分
发现地图类型
x的最多只有 $8$ 个，可以考虑枚举该地图枚举三种地图的复杂度是 $O(3^8 \times (n+m))$ ，不能接受
考虑仅枚举
AB的情况，那么仍遍历了当前位上的三种选择情况，复杂度降至 $O(2^8 \times (n+m))$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
71const int N=4e5+100;
int n,m,d;
int head[N],ver[N<<1],Next[N<<1],tot;
int scc[N<<1],low[N<<1],scc_cnt,dfn_cnt;
int stk[N],top;
char s[N],flag1,flag2,ss[10],tt[10];
int I[N][2]; char h[N][2];
int pos_x[10],cnt;
inline void add(int u,int v){ ver[++tot]=v,Next[tot]=head[u],head[u]=tot;}
inline int get_num(int k,char ch){
if(s[k]=='a') return ch=='B' ? k : k+n;
return ch=='A' ? k : k+n;
}
void tarjan(int x){
low[x]=++dfn_cnt; stk[++top]=x; rei ori=dfn_cnt;
for(rei i=head[x];i;i=Next[i]){
rei y=ver[i];
if(!low[y]) tarjan(y),low[x]=min(low[x],low[y]);
else if(!scc[y]) low[x]=min(low[x],low[y]);
}
if(low[x]==ori) for(++scc_cnt; scc[ stk[top] ]=scc_cnt,stk[top--]!=x;);
}
inline void clear(){
memset(head,0,sizeof head); memset(scc,0,sizeof scc); memset(low,0,sizeof low); memset(stk,0,sizeof stk);
tot=scc_cnt=dfn_cnt=top=0;
}
inline int solve(){
clear();
for(rei i=1,pos1,pos2;i<=m;++i){
pos1=I[i][1],pos2=I[i][2],flag1=h[i][1],flag2=h[i][2];
if(s[pos1]==flag1+32) continue;
rei num1=get_num(pos1,flag1),num2=get_num(pos2,flag2);
if(s[pos2]==flag2+32) add(num1,num1>n ? num1-n : num1+n);
else add(num1,num2),add(num2>n ? num2-n : num2+n,num1>n ? num1-n : num1+n);
}
for(rei i=1;i<=(n<<1);++i) if(!low[i]) tarjan(i);
for(rei i=1;i<=n;++i) if(scc[i]==scc[i+n]) return 0;
return 1;
}
int dfs(int step){
if(step>d) return solve();
for(rei i=0;i<=1;++i){
s[ pos_x[step] ]='a'+i;
if(dfs(step+1)) return 1;
}
return 0;
}
int main(){
scanf("%d%d",&n,&d); scanf("%s",s+1); scanf("%d",&m);
for(rei i=1;i<=n;++i) if(s[i]=='x') pos_x[++cnt]=i;
// puts("here");
for(rei i=1,pos1,pos2;i<=m;++i){
scanf("%d %s %d %s",&pos1,ss+1,&pos2,tt+1);
flag1=ss[1],flag2=tt[1];
I[i][1]=pos1,I[i][2]=pos2; h[i][1]=flag1,h[i][2]=flag2;
}
if(!dfs(1)) return puts("-1"),0;
for(rei i=1;i<=n;++i){
if(s[i]=='a') printf("%c",scc[i]<scc[i+n] ? 'B' : 'C');
else if(s[i]=='b') printf("%c",scc[i]<scc[i+n] ? 'A' : 'C');
else printf("%c",scc[i]<scc[i+n] ? 'A' : 'B');
}
getchar(),getchar();
return 0;
}
前缀优化建图 例题
快跑
P6378 [PA2010] Riddle
$n$ 点 $m$ 条边的有向图分成 $k$ 个部分，选择一些关键点使每一部分恰有一个关键点且每条边至少有一个端点是关键点
由点仅有两种状态不难想到用 $\text{2-SAT}$ 解决
暴力的方法是，对于每一部分中的每个点，让选该点的状态向其他点不选的状态连边，由此有 $O(n^2)$
考虑在每一块中用前缀优化
具体的，设 $pre_i$ 表示在当前块 $\{w_1,w_2,…,w_{\lim}\}$ 中，前 $x$ 个点 $\{w_1,w_2,….,i\}$ 中有一个关键点的状态
那么有建边：
- 对于边 $(a_i,a_j)$ ，有 $inv_{a_i}\rightarrow a_j,inv_{a_j}\rightarrow a_i$ ，即，每条边只能有一个，一个不选时另一个必选
- $a_i\rightarrow pre_{a_i},pre’_{a_i}\rightarrow a’_i$ ，即，若自己是关键点，则状态 $\{前面的点及自己\}$ 中有一个关键点
- $pre_{a_{i-1}}\rightarrow pre_{a_i},pre’_{a_i}\rightarrow pre’_{a_{i-1}}$ ，即，若点 $a_i$ 前面的点已经有关键点，则状态 $\{前面的点及自己\}$ 一定有关键点
- $a_i\rightarrow pre’_{a_{i-1}},pre_{a_{i-1}}\rightarrow a’_i$ ，即，若点 $a_i$ 是关键点，则块中其前面的一定不能有关键点
由此能满足题目要求，边数降至 $O(n)$ 级别，虽然多了2倍的常数
1 | inline int inv(int x){ return x+n;} |
CF1215F Radio Stations
$n$ 个电台，第 $i$ 个波段在 $[l_i,r_i]$ ,在 $[1,m]$ 中选择主频 $f$ ，仅当 $f\in[l_r,r_i]$ 时电台 $i$ 可以使用。给定若干组限制 $(x,y)$ 表示电台 $x,y$ 至少启用一个/最多启动一个
求 $f$ 及构造方案
对电台的若干限制显然，即：
- 对于至少一个，有 $x’\rightarrow y,y’\rightarrow x$
- 对于最多一个，有 $x\rightarrow y’,y\rightarrow x’$
再考虑如何确定主频 $f$ ：
对于区间 $[l_i,r_i]$ ,考虑用前缀，分别考虑区间 $[1,l_i-1],[1,r_i]$ ：
- $f\not\in [1,l_i-1]\ ,\ f\not\in [1,r_i]$ ，$i$ 不能启用
- $f\not\in [1,l_i-1]\ ,\ f\in [1,r_i]$ ，$i$ 能启用
- $f\in [1,l_i-1]\ ,\ f\in [1,r_i]$ ，$i$ 不能启用
- $f\in [1,l_i-1]\ ,\ f\not\in [1,r_i]$ ， 不存在该情况
设 $pre_i$ 表示有 $[f\leq l_i]$ ，那么有建边：
- $pre_i\rightarrow pre_{i+1} , pre’_{i+1}\rightarrow pre’_{i}$
上面的 $4$ 种情况可以简化为一下 $3$ 个性质并用以建边：
- $i\rightarrow pre’_{l_i},i\rightarrow pre_{r_i+1}$ ，即，若电台 $i$ 启用则 $f\in[l_i,r_i]$
- $pre_{l_i}\rightarrow i’$ ，即，若满足 $f\in[1,l_i-1]$ 则 $i$ 不能用
- $pre_{r_i+1}’\rightarrow i’$ ，即，不满足 $f\in[1,r_i]$ 则 $i$ 不能用
跑 $\text{2-SAT}$ ，然后枚举找主频
1 | const int N=2e6+100; |
CF587D Duff in Mafia
$n$ 点 $m$ 边无向图，每条边有颜色和权值，选出一些边使它们是一个匹配，剩下的边的每种颜色也是一个匹配。其中，匹配表示其中的任意两条边均没有公共点
最小化选出的边的权值最大值并输出方案
对于最小化最大值，显然需要二分最大值 $MAX$ ，并不选择任何权值 $>MAX$ 的边
考虑 $\text{2-SAT}$ 维护边是否选择，具体的，需要有：
- $i\rightarrow i’$ ，当且仅当边 $i$ 的权值大于二分值
- 对于任意点 $x$ 有 $lim$ 条满足条件的边，$i\rightarrow j’$ 其中 $i,j\in [1,lim],i\not ={j}$
- 对于任意点 $x$ 有 $lim$ 条相同颜色的边，$i’\rightarrow j$ ，其中 $i,j\in[1,lim],i\not ={j}$
不难发现后两种情况的建图是 $O(m^2)$ 的复杂度，考虑用前缀优化，具体的：
设 $pre_i$ 表示对于当前节点的每一条边中，前 $i$ 条是否有一个被选，以第二种情况为例易得转移：
- $pre_{i-1}\rightarrow pre_i,pre’_i\rightarrow pre_{i-1}’$ 转移前缀
- $i\rightarrow pre_i,pre’_i\rightarrow i’$ 当前元素更新前缀
- $pre_{i-1}\rightarrow i’,i\rightarrow pre’_{i-1}$ 前缀约束当前元素
然而在码的时候我才意识到，对于已经建好的图，每次二分的时候第一种是重新建边的，而二三种的边不需要重新连接，这对邻接表建图并不友好，只能换成 vector 了qwq
然后由于边的编号问题不能直接加上常数得到 $pre$ ,所以换用 all 计数来解决
1 | const int N=3e5+100; |
P6965 [NEERC2016]Binary Code
$n$ 个
01串，每个串至多有一位未知，求是否存在一种方案使任意一个字符串不是其他任意字符串的前缀，并输出具体方案
为什么这题是紫的啊
一定是我太菜了
仍然可以由至多一位未知想到 $\text{2-SAT}$ ，而对于 01 串及前缀想到用 $\text{trie}$
那么将未知的拆成两个字符串，用 $\text{trie}$ 树维护并更新字符串之间的 true/false 关系
具体的：
对于没有 ? 的字符串，一定能选到自己，即，
- $i’\rightarrow i$
由题可以得到：$\text{trie}$ 树上任意一点到根节点的链上至多有一点被选中，对此用前缀优化，即
- $pre_{fa_i}\rightarrow pre_i$
- $i\rightarrow pre’_{fa_i}$ ，即，前面没有
- $i\rightarrow pre_i$ ，即，当前更新前缀
再考虑对于每个结束点，只能有一个字符串在此结束，设 $loc[node]$ 表示每个终点位于点 $node$ 的字符串的编号，那么有：
- $pre_{i-1}\rightarrow pre_i$
- $loc_{node,i}\rightarrow pre’_{i-1}$
- $loc_{node,i}\rightarrow pre_i$
含义显然
1 | const int N=6e6+100; |