洛谷5289 [十二省联考2019]皮配
Luogu LOJ 分析 首先注意到学校选择导师和选择派系是等价的。 考虑 $k=0$ 的情况。则此时城市选择阵营与学校选择派系独立，可以分开处理。 设 $f_{i,j}$ 表示前 $i$ 个城市有 $j$ 个人在蓝阵营的方案数，$g_{i,j}$ 表示前 $i$ 所学校有 $j$ 个人在鸭派系的方案数。转移即为 0/1 背包。最后卷积合并即可。 考虑 $k\neq 0$ 的情况。注意到有限...
分类 题解 下的文章
- 首页
- 题解
洛谷4364 [九省联考2018]IIIDX
Luogu LOJ 分析 先考虑一个贪心。我们把 $d_i$ 从大到小排序，那么每个子树都对应一段区间，我们把儿子按照编号排序，然后把区间依次划分下去即可。 这样子只能通过所有 $d_i$ 互不相同的点，原因是在 $d_i$ 相同时可以通过一些交换使得编号小的点的 $d_i$ 变大。 考虑修正这个贪心。我们维护 $c_i$ 表示 $\leq d_i$ 的可用的难度的个数，那么节点 $u$ 只...
洛谷4383 [八省联考2018]林克卡特树
Luogu LOJ 分析 问题相当于选出恰好 $k+1$ 条点不相交的路径使得权值和最大，这里 $1$ 个点也算一条路径。 先考虑一个朴素 DP。设 $dp_{i,j,0/1/2}$ 表示以 $i$ 为根的子树、选了 $j$ 条路径、$i$ 的度数为 $0/1/2$ 的最大权值和，转移讨论各种情况把子树合并进来即可。 设 $f(k)$ 为选恰好 $k$ 条点不交路径时的最大权值和，通过打表或...
洛谷4384 [八省联考2018]制胡窜
Luogu LOJ 分析 首先容斥一下，求出三段都不包含 $s_{l..r}$ 的方案数，然后用 ${n-1\choose 2}$ 减掉即为答案。 我们先把所有和 $s_{l..r}$ 相等的子串位置都找到，然后分类讨论一下： 如果有三个互不相交的串，方案数是 $0$。 如果最左边的串和最右边的串相交： 考虑 $i$ 的位置： 如果 $i\in[1,l_1)$，那么 $j\in(l_m,...
洛谷6665 [清华集训2016] Alice 和 Bob 又在玩游戏
Luogu UOJ 分析 考虑对每棵子树计算其 SG 函数值，即为每种删除情况得到的若干棵子树的 SG 函数的异或和的 mex。 于是我们要想办法求出每种选择情况得到的 SG 函数异或和的集合。 如果选择根节点，得到的就是它的每棵子树，子局面的 SG 函数值即为每棵子树的 SG 函数值的异或和。 如果选择了某棵子树中的节点，那么相当于这棵子树的 SG 函数异或和的集合异或上了其它子树 SG ...
洛谷4365 [九省联考2018]秘密袭击coat
Luogu LOJ 分析 首先把第 $k$ 大转化掉： 不妨再设一个 $g_{i,j,k}$ 表示子树 $f_{i,j,k}$ 的和，并设 $G_{i,j}(x)=\sum_k g_{i,j,k}x^k$。答案即为 $\sum_{i=k}^n[x^i](\sum_j G_{1,j})$。 看起来这个转移并没有什么可以优化的地方。但是 $F_{i,j}$ 和 $G_{i,j}$ 的最高次项都...
洛谷5284 [十二省联考2019]字符串问题
Luogu LOJ 分析 容易想到一个图论模型，即从每个 A 类串向它所支配的 B 类串连边，从每个 B 类串向以它为前缀的 A 类串连边，并将所有 A 类串的权值设为长度。这样问题变为求最长路，如果有环输出 -1。 第一类边可以直接连，但第二类边暴力连显然不行，考虑一些优化。 对反串建 SAM，此时 Parent 树上每个点的祖先都是它的前缀，于是我们只需要将树上每个 B 类串对应的节点向...
洛谷6628 [省选联考 2020 B 卷]丁香之路
Luogu LOJ 分析 走的路径应满足起点、终点的度数为奇数、其它点的度数为偶数，这个条件长得很像欧拉回路。 我们首先把 $m$ 条关键边连上，然后再在起点、终点间连一条边。这样子会有一些度数为奇数的点，显然相邻的两个间连一条边是最优的。这样子满足了度数限制。 但是我们还需要让图连通。我们把所有连通块缩成一个点，然后求最小生成树，那么可以花费最小生成树上边权和的两倍的代价让图连通起来。 时...
CF1446D2 Frequency Problem (Hard Version)
Codeforces 分析 先判掉只有一种数的情况，答案显然为 $0$。 再判掉原序列中有两种出现次数都是最多的数的情况，答案显然为 $n$。 那么现在出现次数最多的数唯一。找到这个数，设为 $x$，那么有结论：答案段出现次数最多的数一定是 $x$。 这是因为如果某一段出现次数最多的数不是 $x$，那么我们可以每次把这一段增长 $1$，根据介值定理，此过程中一定会有 $x$ 的出现次数等于原...
CF1264D2 Beautiful Bracket Sequence (hard version)
Codeforces Luogu 分析 考虑枚举一个分界点，如果左边的 ( 和右边的 ) 相等，那么深度就是左边的 ( 数。 设 $l$ 为左边的 ( 数、$f$ 为左边的 ? 数、$r$ 为右边的 ) 数、$g$ 为右边的 ? 数，枚举深度，方案数为 时间复杂度 $\mathcal{O}(n)$。 代码 // ==================================== //...