[比赛补题][2SAT][x] codeforces gym 101987 K TV Show Game

题目链接

题意:

题意:有一排 $n$ 个灯,可以是红色或者蓝色,然后k个人投票,每个人投的票会写上他猜测的某三盏灯的颜色。然后现在问是否有一种红蓝灯的安排方式使得每个人投的票至少有2个猜测是对的。

题解:

$2-SAT$ 板子题,但是比赛时候忘记了(主要这东西在中国真的很少考emm)相当于求让每个人的条件都为真的一组二进制向量。那么现在的问题就是怎么把每个人的约束条件转化为 $2-SAT$ 的子句的形式。

首先用 $x_1$ $x_2$ $x_3$ 表示一个人的三个选择,那么代表这个人的子句用文字表达来说就是 $x_1 x_2 x_3$ 中有2个或者3个为真。用条件的知识可以推出来这个说法等价于 $(x_1\lor x_2 )\land(x_1\lor x_3)\land(x_2\lor x_3)$ ,这样就把每个人的条件写成 $2-SAT$ 的形式了,接下来按板子连通分量+拓扑排序求解就OK了。

继续阅读“[比赛补题][2SAT][x] codeforces gym 101987 K TV Show Game”