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