洛谷4324 [JSOI2016]扭动的回文串
Luogu 分析 先对每个串跑一遍 Manacher。设求出的分别为 $f_i$ 和 $g_i$。 这时第一、二类的最长长度即为 $\max\left\{f_i\right\}$ 和 $\max\left\{g_i\right\}$。 考虑第三类的最长长度怎么求。枚举中点 $i$，发现此时的扭动串变成了三段：一段是某个串中 $i$ 向外扩展出的回文串，一段是 $A$ 中继续向左扩展出的串，一...
博主已经退役，评论可能会审核很久才能通过。
博主已经退役，评论可能会审核很久才能通过。
Luogu 分析 先对每个串跑一遍 Manacher。设求出的分别为 $f_i$ 和 $g_i$。 这时第一、二类的最长长度即为 $\max\left\{f_i\right\}$ 和 $\max\left\{g_i\right\}$。 考虑第三类的最长长度怎么求。枚举中点 $i$，发现此时的扭动串变成了三段：一段是某个串中 $i$ 向外扩展出的回文串，一段是 $A$ 中继续向左扩展出的串，一...
Luogu 分析 先考虑一个 $\mathcal{O}(n^2)$ 的做法。 先求出以每个节点为根，整棵树的哈希值。 然后，把 $A$ 的所有 $n$ 个哈希值丢到一个 map 里去，然后枚举 $B$ 的每一个叶子节点，判断删掉后的哈希值是否在 map 中即可。 这个算法的主要瓶颈在于 $\mathcal{O}(n^2)$ 求哈希值，我们考虑优化这个过程。 异或满足可减性，很容易抵消掉。所以...
Luogu 分析 第一问考虑最短路。对于每条线路建一个点，线路上的站向线路连边权为 $1$ 的边，线路向线路上的站连边权为 $0$ 的边。因为边权只有 $0$ 和 $1$ 所以可以 BFS。 第二问考虑一个 DP。设 $dp_i$ 表示到达 $i$ 时最多乘坐多少分钟的地铁。 假设一条线路的 $dis$ 为 $d$，则我们可能在 $dis$ 为 $d-1$ 的站上车，在 $dis$ 为 $d...
Luogu 分析 先考虑 $k|n$ 时的做法。显然所有串的长度应相等。枚举第一个串的起始位置，则需要比较 $k$ 个串中最大的，事先倍长然后后缀排序即可利用 $rk$ 比大小。 考虑 $k\nmid n$ 时怎么做。显然最长的串至多比最短的串长 $1$。 考虑二分答案的排名 $mid$，check() 时仍然枚举第一个串的起始位置 $i$，然后记录一个指针 $p$ 一开始等于 $i$，每次...
Luogu 分析 看到这个 $n\times m\leq 10^5$，可以考虑根号分治。 $n\leq m$ 首先枚举上下边界 $u,d$。 那么所有拼图可以分为两类：第 $u$ 行到第 $d$ 行均为白色的、第 $u$ 行到第 $v$ 行不均为白色的。 最后的拼法会是所有第一类拼图放在中间，然后左右各接上一个第二类拼图。 于是我们算一下第一类拼图的宽度之和，以及第二类拼图左右最多多少列...
Luogu 分析 这是一个线性规划做法。下面举的栗子为样例。 设 $X_i$ 为第 $i$ 类志愿者的招募数，$P_i$ 为第 $i$ 天招募志愿者的数量，那么可以列出一些不等式 注意到每个变量恰出现 $2$ 次且系数一正一负。 我们可以把每个等式看做一个点，正数代表流出，负数代表流入，那么等式相当于流量平衡。 因此我们得到了这样的建图方法： 如果 $P_i-P_{i-1}>0$，...
Luogu LOJ 分析 我们先考虑怎么算根节点的答案。 先假设它只有两棵子树 $u$ 和 $v$，榕树之心在根节点处。 如果 $u$ 长出一个节点，$v$ 长出一个节点，那么榕树之心还在根节点处，相当于这两次操作抵消掉了。 那么我们只需要判断根节点的所有子树能否相互抵消掉。 注意每棵子树是可以自行抵消一部分的，因此可以设 $f_u$ 表示 $u$ 子树内最多可以自行抵消多少对。 考虑 $f...
Luogu LOJ 分析 首先特判原图不是仙人掌的情况，直接输出 $0$ 即可。 显然连边不会跨过一个环，因此可以直接断掉所有环边，则原图变为一个森林，方案数即为每棵树的方案数之积。 考虑如何计算一棵树的方案数。 我们假装一个边也是一条链，那么就相当于求用若干条不相交的链覆盖树上所有边的方案数。 考虑 DP。设 $dp_u$ 为 $u$ 子树中所有边加上父边被覆盖的方案数，$g_n$ 为一个...
Luogu LOJ 分析 显然左边看到的是前缀 $\max$，右边看到的是后缀 $\max$，而最大值前后都能看到。 除去最大的，剩下的 $n-1$ 个数需要划分成 $A+B-2$ 个圆排列（圆排列的原因是因为我们需要钦定最大的放在某个端点）；然后这 $A+B-2$ 个前后缀 $\max$ 中需要选出 $A-1$ 个放在左边。 于是答案为 代码 // ===================...
LOJ 分析 考虑一个区间怎样才是满足条件的。 设 $A_{l,r}$ 为端点都在 $[l,r]$ 内的 exciting 的路径数，$B_{l,r}$ 为端点都不在 $[l,r]$ 内的 exciting 的路径数。则 $[l,r]$ 满足条件即 $A>B$。 现在我们要比大小，根据文化课那一套理论可以想到作差。设 $C_{l,r}$ 为一个端点在 $[l,r]$ 内、一个端点不在 ...