AtCoder Regular Contest 069 简要题解
比赛地址Scc Puzzle直接算一下就好了。代码Menagerie枚举前两只是羊还是狼，那么后面的都可以直接推出来，判断一下第一只和最后一只是否满足条件即可。代码Frequency我们肯定是选一个最高的标号最小的，然后把最高的标号大的减去 $1$。于是把所有数从大到小排序，那么在一个 $a_i\neq a_{i+1}$ 的地方，我们会把前面 $i$ 个 $a_i$ 都削成 $a_{i+1}...
标签 2-SAT 下的文章
- 首页
- 2-SAT
POI2011 简要题解
Conspiracy考虑如果已经有了一组方案怎么得到其它的方案，可以发现只有以下三种情况：团内的一个点移了出去、团外的一个点移了进来、交换了团内和团外的两个点。只需要求出每个点是不是之和对方集合中的一个点冲突即可。于是考虑构造一组方案。注意到每个点只能在团内或团外，于是 2-SAT 即可。可能会有些卡空间。代码Lollipop可以发现如果存在一段和为 $w$，则一定存在一段和为 $w-2$，...
洛谷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)$，表示...
BZOJ5172 [Jsoi2014]学生选课
BZOJ分析根据要求的东西可以看出是二分答案。因此考虑怎么写 check()。注意到每个学生仅有 $2$ 种选择，因此可以考虑 2-SAT。对于每一个学生 $i$，枚举所有排名在 $[mid+1,n]$ 内的学生 $j$，并根据两人第一年选的老师连边即可。代码// =================================== // author: M_sea // webs...
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...