JOISC2020 部分题解
先放一点上来，剩下的慢慢更。 ビルの飾り付け 4 / Building 4 不难想到一个 $\mathcal{O}(n^2)$ 的 DP：设 $f_{i, j, 0/1}$ 表示前 $i$ 个数选了 $j$ 个 A，最后一个是 A/B 是否可行，转移显然。最后逆序构造方案即可。 可以发现对于某个 $i, 0/1$，为真的 $j$ 一定是一段区间，因此我们只需要维护这段区间，即可去掉 $j$ ...
标签 tarjan 下的文章
- 首页
- tarjan
POI2011 简要题解
Conspiracy 考虑如果已经有了一组方案怎么得到其它的方案，可以发现只有以下三种情况：团内的一个点移了出去、团外的一个点移了进来、交换了团内和团外的两个点。只需要求出每个点是不是之和对方集合中的一个点冲突即可。 于是考虑构造一组方案。注意到每个点只能在团内或团外，于是 2-SAT 即可。 可能会有些卡空间。 代码 Lollipop 可以发现如果存在一段和为 $w$，则一定存在一段和为 ...
洛谷4630 [APIO2018]Duathlon 铁人两项
Luogu LOJ 分析 可以发现 $s$ 到 $t$ 的所有简单路径的并相当于 $s$ 到 $t$ 经过的所有点双连通分量（这里一条边也算点双）的并。 那么对于一对 $(s,t)$，满足条件的 $c$ 的数量就等于 $s$ 到 $t$ 经过的所有点双的大小之和减 $2$。 考虑怎么快速求两点之间所有点双大小之和。容易想到广义圆方树，可以想到将方点的权值设成点双大小，圆点的权值设成 $-1$...
CF487E Tourists
Codeforces Luogu 分析 可以发现，在从 $u$ 走到 $v$ 的过程中如果经过了一个点双联通分量，那么对于其中的每个点都存在一条经过它的路径。因此，我们一定会经过每个点双中权值最小的点。 从而可以想到广义圆方树。对于每个方点，它的权值应为与它相连的圆点中的最小值。这样子查询直接树剖+线段树即可。因为有修改圆点权值的操作，用 std::multiset 维护每个方点相连的圆点的...
洛谷1173 [NOI2016]网格
Luogu LOJ 分析 首先发现答案只可能是 $-1,0,1,2$ 中的一个：当图本就不连通时答案为 $0$，当图存在割点时答案为 $1$，当 $nm-c<2$ 或 $nm-c=2$ 且剩下两只跳蚤相邻时答案为 $-1$，否则答案为 $2$。 然而把整张图都建出来显然是不现实的。不难想到只把每只蛐蛐周围一圈跳蚤拿出来建图，但这样会有问题： .** .*# .** 此时第二行第二列的 ...
洛谷5025 [SNOI2017]炸弹
Luogu LOJ 分析 最简单的想法是每个炸弹向能炸到的所有炸弹连一条边，然后统计每个炸弹能到达多少个点。 然而这样子边数是 $O(n^2)$ 级别的。注意到一个炸弹一定是向一段区间连边，那么线段树优化连边即可。 统计的话，注意到每个炸弹能到达的的点一定是一段区间。那么缩点后按拓扑序算一下能到达的最小编号和最大编号就好了。 代码 `// ==========================...
CF894E Ralph and Mushrooms
Codeforces Luogu 分析 显然一个强连通分量内的所有边都可以无限走，因此可以考虑缩点。 缩点后，每个强连通分量的权值设为内部所有边能得到的蘑菇个数之和，连接强连通分量的边的权值设为边上的蘑菇数，然后 DP 求最长路即可。 考虑怎么求边权为 $w$ 的边无限走能得到的蘑菇数。设这条边走了 $t$ 次后蘑菇变为 $0$，那么 代码 // =====================...
CF1215F Radio Stations
Codeforces Luogu 分析 很神仙的 2-SAT 。 设表示第 $i$ 个电台启用的点为 $yes(i)$ ，表示第 $i$ 个电台不启用的点为 $no_i$ 。 先考虑一下 $u$ 和 $v$ 至少启用一个怎么连边。连 $no(u)\to yes(v)$ 和 $no(v)\to yes(u)$ 即可。 再考虑一下 $u$ 和 $v$ 不能同时启用怎么连边。连 $yes(u)\t...
洛谷4244 [SHOI2008]仙人掌图
Luogu 分析 设 $f_i$ 表示 $i$ 子树中以 $i$ 为端点的最长链的长度。 如果当前边是桥，直接转移，同时更新 $ans$ 。 否则当前边在环上，先不处理。 假设我们现在在 $u$，$v$ 已经被访问过了。那么 $u$ 是这个环的底端， $v$ 是这个环的顶端。 我们把这个环找出来单独考虑。 先考虑怎么用环上的点更新答案。 要求的实际上是 $\max\{f_i+f_j+dis(...
洛谷3225 [HNOI2012]矿场搭建
Luogu 分析 可以发现，在一个点双联通分量中，设割点的数目为 $s_1$，非割点的数目为 $s_2$，那么： 若 $s_1=0$，即没有割点，那么要有两个出口才能保证能出去。此时出口可以放在任意两个非割点上。 若 $s_1=1$，即只有一个割点，那么如果割点坍塌就都出不去了，所以要放一个出口。此时出口可以放在任意一个非割点上。注意到这里若非割点坍塌，其它点可以通过割点离开到其它分量去。...