zcmimi's blog

arrow_back2-sat共5篇文章

avatar
zcmimi
2020-10-02 23:34:21

SAT指Satisfiability(可满足性问题)

k-SAT指每个限制有k个条件,而当k>2时该问题为NP完全的,只能暴力

LG 4782 【模板】2-SAT 问题

n个布尔变量x_1,x_2,\dots,x_n,另有m个需要满足的条件,每个条件的形式都是「x_itrue/falsex_jtrue/false」.

比如「x_1truex_3false」、「x_7falsex_2false」。

2-SAT问题的目标是给每个变量赋值使得所有条件得到满足。

avatar
zc
2020-10-06 10:38:49

查看原题

点击跳转

可以发现除了x地图,其他地图都只有两种状态,

如果没有x地图,那就是2-sat裸题,

x地图最多只有8张,我们可以暴力枚举x地图

avatar
zc
2020-10-06 00:18:02

查看原题

点击跳转

首先每条边(x,y)至少有一个端点是关键点

条件 连边
x,y任选一个 \neg x\to y,\neg y\to x

接下来是对每部分进行连边

若将每个点向该部分中出它以外的所有点连边,复杂度为\mathcal O(n^2)

我们可以前缀优化建图

设该部分为a_1,a_2,\dots,a_w

对每个点a_i新增一个状态pre_{a_i}表示a_{1\sim i}中有没有被选为关键点

条件 连边
a_i,pre_{a_i}必须同时选 a_i\to pre_{a_i},\neg pre_{a_i}\to \neg a_i
pre_{a_{i-1}},pre_{a_i}必须同时选 pre_{a_{i-1}}\to pre_{a_i},\neg pre_{a_{i-1}}\to \neg pre_{a_i}
pre_{a_{i-1}},a_i不能同时选 pre_{a_{i-1}}\to \neg a_i,a_i\to \neg pre_{a_{i-1}}

这样就可以\mathcal O(n)连边了

avatar
zc
2020-10-05 16:10:20

查看原题

点击跳转

avatar
zc
2020-10-03 11:47:30

查看原题

点击跳转

1/1
Search
search