CF461E Appleman and a Game
我们可以先建出 SAM,设 \(dp_{i,u}\) 表示当前处理到 \(i\) 位,SAM 上到 \(u\) 节点当前最小答案。
由于答案具有单调性,考虑二分答案,也就是二分 \(mid\),考虑如何检验最短的串是否不超过 \(\le n\)。
考虑把 SAM 修改一下,若某点不存在 \(c\) 的出边就将其连向根到 \(c\) 的节点。
现在问题转化为:给你一张有向图(即修改完的 SAM),满足上面有 \(4\) 个特殊点。
你从根开始走,每经过一条边则 \(cnt_1\) 加一,每到达一个特殊点则 \(cnt_2\) 加一。
当 \(cnt_2\) 为 \(mid\) 时过程终止。 你可以任意安排你走的路径,需要求出终止时 \(cnt_1\) 的最小值。
那么我们可以 dp,设 \(dp_{i,c}\) 表示当前走了 \(cnt_2=i\),走到了第 \(c\) 个特殊点的最小答案。
考虑最短路求出特殊点之间的最小的 \(cnt_2\)。最后 dp 明显可以用矩阵快速幂优化。非常好一个题。
之所以想到可以二分答案是因为“最小值最大”;还有随着 \(n\) 增大答案不降,所以答案增大,\(n\) 也不降。
可以二分转倍增优化复杂度。
CF1442E Black, White and Grey Tree
发现颜色相同且相邻的点可以缩点起来,一定是一起被操作的。
我们假设只有一条链,且只有黑色和白色的点,发现最小的操作次数为 \(len/2+1\),\(/2\) 需要向上取整。
把链推广到树上,贪心地,考虑每次删掉叶子节点,因为如果删成了多个连通块一定不优。
如果只有黑色和白色的点,把颜色不同的点之间的边设为 \(0/1\),那么 \(len\) 就是树的直径。
考虑灰色的点,由于灰色的点一定是跟白色或黑色一起删掉,所以可以把灰色的点看做是黑色或白色。
那么我们考虑树形 dp 即可。转移的话对于儿子合并上来的时候取儿子两种颜色最小值。
这个题的话,是一个从链到树的直径跟贪心的结合。每次删叶子的思想比较常见。
CF2004F Make a Palindrome
我们先要考虑一个数组最小操作多少次使得其变成回文。首先上限是 \(n-1\),只需要全部合并。
经过猜测,我们认定将一个数分裂成两份是没有用的,所以我们考虑最大化最后剩下的数的个数。
结论:所以一个数组考虑做前缀/后缀和,最后能剩下的个数,是前缀和与后缀和所有数中相等的个数。考虑拆贡献,也就是求区间和相等对数。把所有区间的和存进桶里,桶里两两可以做贡献。
CF1687D Cute number
我们观察到,合法的段是诸如 \([w^2,w^2+w]\) 这种情况。合法与不合法交替,长度为 \(2,1,3,2,4,3,5,4...\)
称 \([w^2,w^2+w]\) 为第 \(w\) 段,到第 \(V=a_n\) 段后,所有的数一定在一个段里。
不妨枚举 \(a_1+k\) 所在的段,只有 \(V\) 种段。我们令 \(a_1+k\) 紧贴左边,算后面要合法会使 \(k\) 增大多少。
因为合法的段长度最多比后面不合法的段长度大 \(1\),所以,每个 \(a_i+k\) 满足条件时 \(k\) 是一个区间。
然后把 \(k\) 的取值范围求交集,于是乎我们得到了一个 \(O(nV)\) 的做法。
观察到:如果当前从小到大枚举到第 \(w\) 段,若 \(a_{i+1}-a_i\le w\),那么他们一定在一个段中。
在一个段中的我们可以合并他们。考虑两个端点即可。
枚举到第 \(w\) 段时,在不同段的只有 \(\frac{V}{w}\) 种,复杂度调和级数。
CF1984E Shuffle
考虑转化题意,考虑最后流程结束时树被删成什么样。显然此时每个连通块大小为 \(1\)。
因为这些连通块大小为 \(1\),他们一定是叶子节点。这些没被删的点相当于一个独立集。
相当于求树的最大独立集。但是这样有一个问题,就是被删的点不一定不是叶子。
如果一个原来的叶子是第一个被删除的,那么其最后一定还是叶子节点。
所以设计一个 \(dp_{u,0/1,0/1}\) 表示当前节点选/不选,其子树有无叶子第一个被删除的答案,转移平凡。
转化为独立集模型确实精妙。
CF627D Preorder Test
显然地,我们需要二分答案,考虑如何检验答案 \(mid\),考虑把 \(< mid\) 的点都删掉,形成若干连通块。
在每个连通块中可能有若干个点连向 \(<mid\) 的点,这代表什么?代表这个点无法回溯,称为黑点。
如果走进一个无法回溯的点的子树里,那么一定会在该子树终结。
所以,我们 dfs 遍历的 \(k\) 个点中如果存在有黑点,其一定连成一条路径。
相当于我们选两个黑点出来,其路径上所有点的儿子的,且不存在黑点的子树大小的和使其 \(\ge k\)。
考虑 dp,维护 \(f_u\) 表示 \(u\) 连向其子树里某个点最大的贡献,(不考虑 \(u\) 子树外的贡献)。
特判不存在黑点的情况。
CF1976F Remove Bridges
我们要让割边最少,且原来树上不是割边的边连接成包含根节点的一个连通块。
我们连接 \(u\to v\) 时,可以使树上 \(u,v\) 路径上所有边都不是割边,此时可以将 \(u\to v\) 的边全部删去。
这是划分子任务的思想。我们有了一个贪心的策略,每次删除最长的一条路径,且与根节点联通的。
如果存在一个很长的路径 \(u\to O\to v\),需要先删 \(1\to O\) 才能到达;不妨先删除 \(1\to u\),再删 \(O\to v\)。
这证明了贪心是正确的。考虑如何表示一条路径,拆分成两条到 \(1\) 的路径,\(dis_u+dis_v\)。
当我们删了一条路径时,考虑对 \(dis\) 产生什么影响,这里需要把 \(dis_u\) 定义成删 \(u\) 会减少多少割边。
假设 \((x, fa_x)\) 是被删除的一条边且第一次被删,那么 \(x\) 子树里所有的 \(dis\) 都会减少 \(1\)。
由于每条边只会被删除一次,删除的时候直接执行子树减,同时维护出 \(dis\) 的最大值即可。
关于删除 \(u\to v\) ,需先找出 \(u\),然后设 \(u\) 向上跳 \(dis_u-1\) 的位置是 \(Q\),找非 \(Q\) 子树里最大的 \(v\) 即可。
经过实践发现上面是错的,我们需要给贪心加上“反悔”。
也就是,除了第一次操作,不需要找非 \(Q\) 子树里最大的 \(v\),因为可以通过交换使得其满足条件。