2025 vertigo - 杂题选讲 - K

*表示没写 / 懒得写。还有些非常蠢的题删掉了。

[*0] QOJ5416 Fabulous Fungus Frenzy

正着不好做那么倒着做，每次交换相邻元素或者把某个出现在 $k$ 个给定矩阵里的子矩阵填充成通配符。而且因为有任意交换所以我们只关心种类元素个数。不断填直到不能在填，操作数应该是 $n^2m^2(n+m)$，在限制以内。

[0] CF1909G Pumping Lemma

令 $L=\text{LCP}(s,t), R=\text{LCS}(s,t)$，那么 $s[n-R+1:L]$ 一定是 $y$ 的一个混循环串，且 $y$ 最后一定取得是这个串的子串，暴力枚举开头可以直接计算个数。

[2] CF1483E Vabank

很神秘的题啊。首先先倍增确定值域，如果每次二分那么会浪费一大堆钱，于是可以把二分点往左移一点，大约是 $\phi=0.3$，但是如果钱已经足够了肯定是二分最优。设计一个估计函数 $f(l,r)=l\log_{\phi}\dfrac{1}{r-l}$，如果当前的钱比这个多，那就二分查询，否则直接把二分点看成一次函数 $g(l,r)=0.2+0.3\dfrac{C}{f(l,r)}$，其中 $C$ 代表当前的钱，大概是 $104$ 次。

[0] CF1523F Favorite Game

暴力转移是 $f_{S,i,j}$ 表示 $S$ 的塔已经被激活，现在在地点 $i$，已经到达了 $j$ 个地点所需的最小时间。试着缩减状态，如果把塔和地点的状态分开设计，那么在哪个塔的位置 / 时间一维可以省去，$\mathcal O(2^nm^2)$。

[1] QOJ7677 Easy Diameter Problem

容易想到 dp 状态里要记录直径移动方向和半径，但如果最后一维记录移动方向上，距离为 $r$ 的点剩余个数是非常难的，因为有后效性，而且延续钦定需要多枚举一维，也就是 $\mathcal O(n^4)$。干脆直接不加了：每次决定顺序的时候不加移动方向上的点，等到决策他的时候再插进去，而且插进去范围一定是个后缀，变成 $\mathcal O(n^3)$ 了。

[2] CF1142E Pink Floyd

如果没有粉边非常简单。如果粉边构成 DAG，难点在于无法询问某些点对。我们试着维护一个两两无粉边的点集 $S$，初始话为所有入度为 $0$ 的点，然后 topo。每次可以取出两个数 $u,v$ 并询问。如果 $u\rightarrow v$ 有边，那么把 $v$ 删了并加入新的点。最后剩下的点一定能到达之前所有出现在队列中的点，没有的可以通过粉边到达。如果不是 DAG，那么每个联通分量里找一条链 / 生成树即可，这样其他边都是返祖边，不会影响到询问合法性。

[0] CF1450G Communism

令 $f_S$ 表示 $S$ 集合是否能合并成任意一个 $\in S$ 的颜色，同时定义 $g_S$ 表示可以合并的颜色集合，转移需要枚举子集。进一步观察如果枚举的集合 $T$ 和 $S\backslash T$ 对应的区间有交，那么一定能转移到 $S$。所以只要特别转移区间无交的的转移，$T$ 的取值只会是 $S$ 区间排序后的一个前缀，总复杂度是 $\mathcal O(m2^m)$，注意别忘了一个颜色单独转成另一个颜色的情况。

[1]【UER #11】企鹅游戏

容易分析 $s$ 的总出现次数是 $\mathcal O(L\sqrt L)$ 的，所以可以直接暴力在 ACAM 上跳 fail 统计，比根号分治常数小很多，时间复杂度 $\mathcal O(L\sqrt L)$。

• 结论：所有 $t$ 包含的不同 $s$ 个数之和级别为 $\mathcal O(L^{\frac 4 3})$。

如果 $|s|\le L^{\frac 1 3}$，每个串总出现次数最多为 $L$；如果 $|s|>L^{\frac 1 3}$，不同的 $s$ 个数上界为 $L^{\frac 2 3}$，而每个最多出现 $L^{\frac 2 3}$ 次，所以总出现次数级别为 $L^{\frac 4 3}$。

所以只要暴力跳的时候遇到标记过的点，直接打个 tag，最后一起 pushtag 就是对的，时间复杂度 $\mathcal O(L^{\frac 4 3})$。

---

这里还有一种方法，比较有参考价值。观察到 $3^i\bmod 2^{32}$ 一定是奇数，令其为 $2k+1$，如果编号为 $i$ 的串最终出现次数为 $x$，二项式展开一下有 $(2k+1)^x=\sum\limits_{i=0}^x\dbinom x i(2k)^i$，显然 $i\ge 32$ 时无贡献，所以标记次数 $\ge 32$ 时就可以不标记了，时间复杂度 $\mathcal O(32L)$。

---

听说还可以优化，不管了。

[1] CF1225G To Make 1

直接 dp 合并过程无法避免的要枚举子集，既然过程是难以刻画的，试着从结果来看问题。最终每个数的贡献一定是 $a_ik^{-b_i}$，其中 $b_i$ 表示 $a_i$ 在合并过程中除以 $k$ 的次数。猜测存在 $\{b\}$ 使得 $\sum a_ik^{-b_i}=1$ 就是合法的充要条件，构造性证明一下：每次取出所有 $b_i=\max b$，满足条件 $i$ 的个数肯定 $\ge 2$，而且一定能合并起来。发现 dp 值只有 bool，bitset 可以除个 $\omega$。