洛谷3825 [NOI2017]游戏
LuoguLOJ分析没有 x 时显然是 2-SAT。将每张图拆成两个点表示能填的两种赛车。为了方便，设 $(i,a)$ 表示 $i$ 填 $a$ 所对应的点，$(i,\neg a)$ 表示 $i$ 不填 $a$（即填另一种赛车）对应的点。对于每个条件 $(i,a,j,b)$如果 $s_i\neq a$，忽略。如果 $s_j\neq b$，连边 $(i,a)\to (i,\neg a)$，表示...
标签 2-SAT 下的文章
- 首页
- 2-SAT
BZOJ5172 [Jsoi2014]学生选课
BZOJ分析根据要求的东西可以看出是二分答案。因此考虑怎么写 check()。注意到每个学生仅有 $2$ 种选择，因此可以考虑 2-SAT。对于每一个学生 $i$，枚举所有排名在 $[mid+1,n]$ 内的学生 $j$，并根据两人第一年选的老师连边即可。代码// =================================== // author: M_sea // webs...
ARC069F Flags
AtCoderLuogu分析容易想到二分答案，那么只要判定能不能找到一组方案使得所有点的距离都 $\geq mid$ 即可。考虑 2-SAT 。如果某面旗帜选了某个位置的话，会有一些旗帜只能选某个位置。于是 $O(n^2)$ 连边后 tarjan 即可。这个算法的瓶颈在于连边太慢了，考虑优化。首先，把所有位置都拿出来排个序，那么一个点一定会向一段区间内的点的反点连边，而这个区间是可以二分出来...
CF1215F Radio Stations
CodeforcesLuogu分析很神仙的 2-SAT 。设表示第 $i$ 个电台启用的点为 $yes(i)$ ，表示第 $i$ 个电台不启用的点为 $no_i$ 。先考虑一下 $u$ 和 $v$ 至少启用一个怎么连边。连 $no(u)\to yes(v)$ 和 $no(v)\to yes(u)$ 即可。再考虑一下 $u$ 和 $v$ 不能同时启用怎么连边。连 $yes(u)\to no(v...
洛谷5332 [JSOI2019]精准预测
LuoguLOJ分析每个人在每个时刻只有 $2$ 种状况，考虑 2-SAT 。设 $(x,t,0/1)$ 表示 $x$ 在 $t$ 时刻活着/死了。那么直接连边就好了。另外还有一个隐藏条件：如果 $x$ 在 $t$ 时刻活着，那么在 $t-1$ 时刻也活着；如果 $x$ 在 $t$ 时刻死了，那么 $x$ 在 $t+1$ 时刻也死了。这个同样要连边。问题变为在建好的图上，从 $(i,T+1,...
洛谷3209 [HNOI2010]平面图判定
LuoguBZOJ分析$\mathrm{2-SAT}$ 。首先把环抽出来，那么还会剩下很多边。考虑两条有交点的边（这里的 $(1,4)$ 和 $(2,5)$ ）：显然只能一条不变（放在环里面），一条从外面绕一下（放在环外面）。于是就可以上 $\mathrm{2-SAT}$ 了。对于两条有交点的边 $i$ 和 $j$ ，连以下 $4$ 条边：$i\to j+m$ ，表示 $i$ 在里面 $j$...
洛谷4171 [JSOI2010]满汉全席
LuoguBZOJ分析很裸的 $\mathrm{2-SAT}$ 。把 $i$ 拆成 $i$ 和 $i+n$ ，分别表示汉式和满式。对于每个要求 $(a_c,b_d)$ ，这样子连边：如果 $a$ 为 $m$ ， $b$ 为 $m$ ，那么 $c$ 向 $d+n$ 连边，$d$ 向 $c+n$ 连边。如果 $a$ 为 $m$ ， $b$ 为 $h$ ，那么 $c$ 向 $d$ 连边， $d+n...