arrow_back2-sat共5篇文章

SAT指Satisfiability(可满足性问题)

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

LG 4782 【模板】2-SAT 问题

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

比如「x_1为true或x_3为false」、「x_7为false或x_2为false」。

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

查看原题

点击加载点击跳转

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

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

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

查看原题

点击加载点击跳转

首先每条边(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)连边了

查看原题

点击加载点击跳转

查看原题

点击加载点击跳转