洛谷5284 [十二省联考2019]字符串问题
Luogu LOJ 分析 容易想到一个图论模型，即从每个 A 类串向它所支配的 B 类串连边，从每个 B 类串向以它为前缀的 A 类串连边，并将所有 A 类串的权值设为长度。这样问题变为求最长路，如果有环输出 -1。 第一类边可以直接连，但第二类边暴力连显然不行，考虑一些优化。 对反串建 SAM，此时 Parent 树上每个点的祖先都是它的前缀，于是我们只需要将树上每个 B 类串对应的节点向...
博主已经退役，评论可能会审核很久才能通过。
博主已经退役，评论可能会审核很久才能通过。
Luogu LOJ 分析 容易想到一个图论模型，即从每个 A 类串向它所支配的 B 类串连边，从每个 B 类串向以它为前缀的 A 类串连边，并将所有 A 类串的权值设为长度。这样问题变为求最长路，如果有环输出 -1。 第一类边可以直接连，但第二类边暴力连显然不行，考虑一些优化。 对反串建 SAM，此时 Parent 树上每个点的祖先都是它的前缀，于是我们只需要将树上每个 B 类串对应的节点向...
Luogu LOJ 分析 走的路径应满足起点、终点的度数为奇数、其它点的度数为偶数，这个条件长得很像欧拉回路。 我们首先把 $m$ 条关键边连上，然后再在起点、终点间连一条边。这样子会有一些度数为奇数的点，显然相邻的两个间连一条边是最优的。这样子满足了度数限制。 但是我们还需要让图连通。我们把所有连通块缩成一个点，然后求最小生成树，那么可以花费最小生成树上边权和的两倍的代价让图连通起来。 时...
Codeforces 分析 先判掉只有一种数的情况，答案显然为 $0$。 再判掉原序列中有两种出现次数都是最多的数的情况，答案显然为 $n$。 那么现在出现次数最多的数唯一。找到这个数，设为 $x$，那么有结论：答案段出现次数最多的数一定是 $x$。 这是因为如果某一段出现次数最多的数不是 $x$，那么我们可以每次把这一段增长 $1$，根据介值定理，此过程中一定会有 $x$ 的出现次数等于原...
Codeforces Luogu 分析 考虑枚举一个分界点，如果左边的 ( 和右边的 ) 相等，那么深度就是左边的 ( 数。 设 $l$ 为左边的 ( 数、$f$ 为左边的 ? 数、$r$ 为右边的 ) 数、$g$ 为右边的 ? 数，枚举深度，方案数为 时间复杂度 $\mathcal{O}(n)$。 代码 // ==================================== //...
Luogu Gym 分析 一个做法是直接 meet in the middle，复杂度 $\mathcal{O}(2^{n/2})$，并不能过 $n\leq 64$。 但是题目中还有一个奇妙的性质 $a_i > \sum_{j=1}^{i-1} a_j$，套用得到 $a_1<2^{65-n}$。 发现随着 $n$ 增大 $a_i$ 的取值范围逐渐减小，这启发我们在 $n$ 大时去...
Luogu Gym 分析 我们只能先想办法问一个 $\frac{n}{2}$ 出来。先假设已经问出来了，稍后再来考虑怎么问。 规定一个串对应的集合就是它所有 $1$ 的下标集合，下面不再区分串和集合。 假设问出来的串是 $I$，考虑求出 $A=S\oplus I$。 考虑 $|A\oplus\{u,v\}|=|A|+|\{u,v\}|-2|A\cap\{u,v\}|$，即 $|A\oplus...
Luogu Gym 分析 考虑线性规划。设 $x_i$ 为第 $i$ 小时是否吃饭，可以列出线性规划 用 NOI2008 志愿者招募 一题的方法建图求最大费用最大流即可。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // =======...
Codeforces Luogu 分析 显然装备之间没有区别，我们只要计算一种装备的期望，然后乘上 $k$ 即可。 考虑倒推。设 $dp_{i,j}$ 表示剩余 $i$ 个怪物、装备等级为 $j$ 期望获得的金币数，转移有三种： 选到了其它装备：概率为 $\frac{k-1}{k}$，期望收益为 $dp_{i-1,j}$。 选到了等级为 $j+1$ 的当前装备：概率为 $\frac{1}{...
LOJ 分析 先考虑第一个条件。设 $c_i$ 为经过 $i$ 的 $s\to t$ 的最短路数，那么应该有 $c_a+c_b=c_t$。 再考虑第二个条件。我们可以对每个点求出最短路图上不能到达它的且它不能到达的点集，然后存到一个 bitset 里。这可以直接拓扑排序求出。 枚举 $a$，合法的 $b$ 应该满足 $c_t-c_a=c_b$。开一个 map 存下每个 $c$ 对应的点集，再...