比赛地址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分析可以发现 $s$ 到 $t$ 的所有简单路径的并相当于 $s$ 到 $t$ 经过的所有点双连通分量(这里一条边也算点双)的并。那么对于一对 $(s,t)$,满足条件的 $c$ 的数量就等于 $s$ 到 $t$ 经过的所有点双的大小之和减 $2$。考虑怎么快速求两点之间所有点双大小之和。容易想到广义圆方树,可以想到将方点的权值设成点双大小,圆点的权值设成 $-1$,这样子 ...
CodeforcesLuogu分析可以发现,在从 $u$ 走到 $v$ 的过程中如果经过了一个点双联通分量,那么对于其中的每个点都存在一条经过它的路径。因此,我们一定会经过每个点双中权值最小的点。从而可以想到广义圆方树。对于每个方点,它的权值应为与它相连的圆点中的最小值。这样子查询直接树剖+线段树即可。因为有修改圆点权值的操作,用 std::multiset 维护每个方点相连的圆点的权值,修...
LuoguLOJ分析首先发现答案只可能是 $-1,0,1,2$ 中的一个:当图本就不连通时答案为 $0$,当图存在割点时答案为 $1$,当 $nm-c<2$ 或 $nm-c=2$ 且剩下两只跳蚤相邻时答案为 $-1$,否则答案为 $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)$,表示...
LOJ分析考虑建一个图,即如果某两个颜色为 $i$ 的点的路径上存在一个颜色为 $j$ 点,则从 $i$ 向 $j$ 连一条边。那么一条边 $(u,v)$ 的实际意义是要想把颜色为 $u$ 的点连通,则必须把 $u,v$ 合并。考虑一个强连通分量,显然其中任意一种颜色想要连通都只能将其它 $sz-1$ 个颜色合并,因此一个强连通分量需要合并 $sz-1$ 次。于是我们缩点并将 $sz-1$ ...
LuoguLOJ分析最简单的想法是每个炸弹向能炸到的所有炸弹连一条边,然后统计每个炸弹能到达多少个点。然而这样子边数是 $O(n^2)$ 级别的。注意到一个炸弹一定是向一段区间连边,那么线段树优化连边即可。统计的话,注意到每个炸弹能到达的的点一定是一段区间。那么缩点后按拓扑序算一下能到达的最小编号和最大编号就好了。写起来还是很休闲的代码`// ========================...
CodeforcesLuogu分析显然一个强连通分量内的所有边都可以无限走,因此可以考虑缩点。缩点后,每个强连通分量的权值设为内部所有边能得到的蘑菇个数之和,连接强连通分量的边的权值设为边上的蘑菇数,然后 DP 求最长路即可。考虑怎么求边权为 $w$ 的边无限走能得到的蘑菇数。设这条边走了 $t$ 次后蘑菇变为 $0$,那么代码// =============================...
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...