比赛地址Scc Puzzle直接算一下就好了。代码Menagerie枚举前两只是羊还是狼,那么后面的都可以直接推出来,判断一下第一只和最后一只是否满足条件即可。代码Frequency我们肯定是选一个最高的标号最小的,然后把最高的标号大的减去 $1$。于是把所有数从大到小排序,那么在一个 $a_i\neq a_{i+1}$ 的地方,我们会把前面 $i$ 个 $a_i$ 都削成 $a_{i+1}...
Conspiracy考虑如果已经有了一组方案怎么得到其它的方案,可以发现只有以下三种情况:团内的一个点移了出去、团外的一个点移了进来、交换了团内和团外的两个点。只需要求出每个点是不是之和对方集合中的一个点冲突即可。于是考虑构造一组方案。注意到每个点只能在团内或团外,于是 2-SAT 即可。可能会有些卡空间。代码Lollipop可以发现如果存在一段和为 $w$,则一定存在一段和为 $w-2$,...
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)$,表示...
BZOJ分析根据要求的东西可以看出是二分答案。因此考虑怎么写 check()。注意到每个学生仅有 $2$ 种选择,因此可以考虑 2-SAT。对于每一个学生 $i$,枚举所有排名在 $[mid+1,n]$ 内的学生 $j$,并根据两人第一年选的老师连边即可。代码// =================================== // author: M_sea // webs...
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...
LuoguLOJ分析每个人在每个时刻只有 $2$ 种状况,考虑 2-SAT 。设 $(x,t,0/1)$ 表示 $x$ 在 $t$ 时刻活着/死了。那么直接连边就好了。另外还有一个隐藏条件:如果 $x$ 在 $t$ 时刻活着,那么在 $t-1$ 时刻也活着;如果 $x$ 在 $t$ 时刻死了,那么 $x$ 在 $t+1$ 时刻也死了。这个同样要连边。问题变为在建好的图上,从 $(i,T+1,...
LuoguBZOJ分析$\mathrm{2-SAT}$ 。首先把环抽出来,那么还会剩下很多边。考虑两条有交点的边(这里的 $(1,4)$ 和 $(2,5)$ ):显然只能一条不变(放在环里面),一条从外面绕一下(放在环外面)。于是就可以上 $\mathrm{2-SAT}$ 了。对于两条有交点的边 $i$ 和 $j$ ,连以下 $4$ 条边:$i\to j+m$ ,表示 $i$ 在里面 $j$...
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...