AtCoder Regular Contest 069 简要题解
比赛地址Scc Puzzle直接算一下就好了。代码Menagerie枚举前两只是羊还是狼，那么后面的都可以直接推出来，判断一下第一只和最后一只是否满足条件即可。代码Frequency我们肯定是选一个最高的标号最小的，然后把最高的标号大的减去 $1$。于是把所有数从大到小排序，那么在一个 $a_i\neq a_{i+1}$ 的地方，我们会把前面 $i$ 个 $a_i$ 都削成 $a_{i+1}...
标签 tarjan 下的文章
- 首页
- tarjan
POI2011 简要题解
Conspiracy考虑如果已经有了一组方案怎么得到其它的方案，可以发现只有以下三种情况：团内的一个点移了出去、团外的一个点移了进来、交换了团内和团外的两个点。只需要求出每个点是不是之和对方集合中的一个点冲突即可。于是考虑构造一组方案。注意到每个点只能在团内或团外，于是 2-SAT 即可。可能会有些卡空间。代码Lollipop可以发现如果存在一段和为 $w$，则一定存在一段和为 $w-2$，...
洛谷4630 [APIO2018]Duathlon 铁人两项
LuoguLOJ分析可以发现 $s$ 到 $t$ 的所有简单路径的并相当于 $s$ 到 $t$ 经过的所有点双连通分量（这里一条边也算点双）的并。那么对于一对 $(s,t)$，满足条件的 $c$ 的数量就等于 $s$ 到 $t$ 经过的所有点双的大小之和减 $2$。考虑怎么快速求两点之间所有点双大小之和。容易想到广义圆方树，可以想到将方点的权值设成点双大小，圆点的权值设成 $-1$，这样子 ...
CF487E Tourists
CodeforcesLuogu分析可以发现，在从 $u$ 走到 $v$ 的过程中如果经过了一个点双联通分量，那么对于其中的每个点都存在一条经过它的路径。因此，我们一定会经过每个点双中权值最小的点。从而可以想到广义圆方树。对于每个方点，它的权值应为与它相连的圆点中的最小值。这样子查询直接树剖+线段树即可。因为有修改圆点权值的操作，用 std::multiset 维护每个方点相连的圆点的权值，修...
洛谷1173 [NOI2016]网格
LuoguLOJ分析首先发现答案只可能是 $-1,0,1,2$ 中的一个：当图本就不连通时答案为 $0$，当图存在割点时答案为 $1$，当 $nm-c<2$ 或 $nm-c=2$ 且剩下两只跳蚤相邻时答案为 $-1$，否则答案为 $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)$，表示...
LOJ3280 「JOISC 2020 Day4」首都城市
LOJ分析考虑建一个图，即如果某两个颜色为 $i$ 的点的路径上存在一个颜色为 $j$ 点，则从 $i$ 向 $j$ 连一条边。那么一条边 $(u,v)$ 的实际意义是要想把颜色为 $u$ 的点连通，则必须把 $u,v$ 合并。考虑一个强连通分量，显然其中任意一种颜色想要连通都只能将其它 $sz-1$ 个颜色合并，因此一个强连通分量需要合并 $sz-1$ 次。于是我们缩点并将 $sz-1$ ...
洛谷5025 [SNOI2017]炸弹
LuoguLOJ分析最简单的想法是每个炸弹向能炸到的所有炸弹连一条边，然后统计每个炸弹能到达多少个点。然而这样子边数是 $O(n^2)$ 级别的。注意到一个炸弹一定是向一段区间连边，那么线段树优化连边即可。统计的话，注意到每个炸弹能到达的的点一定是一段区间。那么缩点后按拓扑序算一下能到达的最小编号和最大编号就好了。写起来还是很休闲的代码`// ========================...
CF894E Ralph and Mushrooms
CodeforcesLuogu分析显然一个强连通分量内的所有边都可以无限走，因此可以考虑缩点。缩点后，每个强连通分量的权值设为内部所有边能得到的蘑菇个数之和，连接强连通分量的边的权值设为边上的蘑菇数，然后 DP 求最长路即可。考虑怎么求边权为 $w$ 的边无限走能得到的蘑菇数。设这条边走了 $t$ 次后蘑菇变为 $0$，那么代码// =============================...
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...