洛谷1864 [NOI2009]二叉查找树
Luogu 分析 首先应该可以一眼看出来这就是个 treap，然后改权值就相当于旋转。 考虑到 treap 旋转后中序遍历是不变的，因此我们可以先给所有节点按数据值排个序，这样就能得到中序遍历了。 进一步发现，中序遍历中一段区间在 treap 上是连通的一部分。因此可以考虑区间 DP。 设 $dp_{i,j,k}$ 表示 $[i,j]$ 内的节点，根节点权值 $\geq k$ 的最小代价。因...
分类 题解 下的文章
- 首页
- 题解
洛谷3320 [SDOI2015]寻宝游戏
Luogu LOJ 分析 通过手玩一些数据可以发现，我们一定会从一个有宝藏的点出发，而且按照 DFS 序遍历所有有宝藏的点会最优。 不妨设现有的有宝藏的点按 DFS 序排序后为 $a_1,a_2,a_3,\cdots,a_k$，那么我们要求的就是 $\operatorname{dis}(a_1,a_2)+\operatorname{dis}(a_2,a_3)+\cdots\operatorn...
CF1004E Sonya and Ice Cream
Codeforces Luogu 分析 显然选的路径是直径的一部分。为了方便，把直径上的点重编号为 $1\sim cnt$。 我们把这棵树想象成一条链上挂了一些子树。那么设一个 $maxdis_i$ 表示 $i$ 子树中到 $i$ 最远的点的距离。 一个暴力做法是枚举选的路径 $[l,r]$，此时最大距离就是 $1\sim l$ 的距离、$r\sim cnt$ 的距离、$\max_{i=l}...
BZOJ3714 [PA2014]Kuglarz
BZOJ 分析 设 $sum_i$ 表示 $\sum_{j=1}^i[i\text{中有球}]$。显然我们只需要知道所有的 $sum_i$ 就可以知道每个杯子中是否有球了。 考虑到如果询问了 $[i,j]$，那么一旦知道 $sum_{i-1}$ 或 $sum_j$ 中的一个就可以知道另一个。 因此考虑这样一个模型：对于每个区间 $[i,j]$ ，在 $i-1$ 和 $j$ 间连一条边权为 $...
洛谷5025 [SNOI2017]炸弹
Luogu LOJ 分析 最简单的想法是每个炸弹向能炸到的所有炸弹连一条边，然后统计每个炸弹能到达多少个点。 然而这样子边数是 $O(n^2)$ 级别的。注意到一个炸弹一定是向一段区间连边，那么线段树优化连边即可。 统计的话，注意到每个炸弹能到达的的点一定是一段区间。那么缩点后按拓扑序算一下能到达的最小编号和最大编号就好了。 代码 `// ==========================...
CF343E Pumping Stations
Codeforces Luogu 分析 显然先把最小割树建出来。 首先有一个结论：第一问答案的上界为最小割树上所有边权之和。 下面考虑怎样达到这个上界。 考虑最小割树上的最小边，我们应让它只被经过一次。设它的两个端点为 $a_i,a_{i+1}$ ，则 $a_{1..i-1}$ 中任意两点不经过该边，$a_{i+2..n}$ 中任意两点不经过该边。于是将该边断掉后两边递归处理即可。 代码 /...
AGC001F Wide Swap
AtCoder Luogu 分析 令 $a_{p_i}=i$。注意到要使 $p$ 的字典序最小，则应使 $a$ 的字典序尽量小。 那么题目变为：给定排列 $a_{1..n}$，如果 $|a_i-a_j|\geq k$ 且 $|i-j|=1$ 则可以交换 $a_i,a_j$，求可能排列中字典序最小的。 注意到如果 $a_i,a_j$ 不可能发生交换（也就是说 $|a_i-a_j|<k$）...
CF894E Ralph and Mushrooms
Codeforces Luogu 分析 显然一个强连通分量内的所有边都可以无限走，因此可以考虑缩点。 缩点后，每个强连通分量的权值设为内部所有边能得到的蘑菇个数之和，连接强连通分量的边的权值设为边上的蘑菇数，然后 DP 求最长路即可。 考虑怎么求边权为 $w$ 的边无限走能得到的蘑菇数。设这条边走了 $t$ 次后蘑菇变为 $0$，那么 代码 // =====================...
洛谷2414 [NOI2011]阿狸的打字机
Luogu 分析 做完这题感觉对 AC 自动机有了新的理解... 注意到 fail 树上某个节点子树中的节点都以该节点对应的字符串为一个后缀（这里建议想一想 fail 的定义），因此我们要查 $X$ 是否作为 $Y$ 的一个后缀出现就相当于查 $Y$ 是否在 fail 树上 $X$ 的子树中。 然而现在要找的是子串而不是后缀。注意到所有前缀的所有后缀包含了所有子串，于是我们只需要把 $Y$...
洛谷5446 [THUPC2018]绿绿和串串
Luogu LOJ 分析 这个“翻转”操作很容易想到回文。 考虑一个位置怎样才是合法的。可以发现该位置一定满足以下两个条件之一： 回文半径右侧达到 $|S|$ 。 回文半径左侧达到 $1$ ，且右端点合法。 那么只需要用 manacher 求出回文半径，然后从后往前判断就好了。 代码 // =================================== // author: ...