NOIP 模拟赛十六

A.

发现答案只有 \(0, 1, 2\) 三种。

将 \(0\) 直接判掉，\(1\) 可以通过树状数组+双指针解决。

记 \(k\) 为需要减少的逆序对数量。

具体的，枚举左端点 \(l\) ，加入右端点 \(r\) ，判断逆序对数 \(cnt\) 是否 \(\ge k\) ，如果是，结束。

如果 \(=k\) ，操作此时的左右端点，否则右移 \(l\) 继续此过程。

如果上述过程未求出解，接下来证明答案一定可以做到 \(2\) 。

将 \(l\) 定为 \(1\) ，向右移动 \(r\) ，直到满足 \(cnt < k\) 的最大的 \(r\) 。

此时一旦加入 \(r+1\) ，就会导致 \(cnt>k\) ，也就是说 \([1, r]\) 内比 \(a_{r+1}\) 大的数多于 \(k\) 个。

直接操作 \([1, r]\) ，然后取后 \(k\) 个元素与 \(r+1\) 操作，可以使减少的逆序对数刚好到 \(k\) 。

由上面的证明，这样是一定有解的。

B.

首先需要发现第一问即最大深度，因为每次操作最多使最大深度 \(-1\) ，而操作最长链显然可以做到这些次数。

然后考虑计数，我们只考虑操作某条最长链，最后再说明为什么是不重不漏的。

如果我们切掉了一条边，合法当且仅当这会使得最少操作次数减少，否则不合法。

如果我们想要割掉节点 \(p\rightarrow fa_p\) 的边，需要满足两个限制：

• 分成的两个连通块深度无交。
• \(p\) 并没有被之前的操作删除。

第二个限制显然。对于第一个限制，因为两个连通块已经互不影响，所以最少次数即分别相加。

如果深度有交，则最大深度和一定不会减少，与要求不符。

（图中的 \(p\) 节点就不能被割掉）

由于最大深度最多不超过 \(100\) ，而子问题又明显具有区间的形式，考虑 区间 DP 。

记 \(len\) 表示最长链的深度，将链依次映射到 \([1, len]\) 后，记 \(f[l, r]\) 表示只考虑 \([l, r]\) 内的方案数。

转移枚举断点，然后我们发现，仅凭这些无法判断是否合法。

于是多加一维状态 \(i\) 表示 \(l\) 节点及以上总共执行了 \(i\) 次对 \(l\) 子树有影响的操作。

转移分两种，对根操作以及对 \((l, r]\) 操作，也就是根据是否分裂出新的子问题来分类。

第一类直接继承 \(f[l, r, i] \leftarrow f[l, r - 1, i+1]\) 。

第二类枚举断点 \(d\) ，表示将 \([d, r]\) 断开，如果 \(d\) 合法则 \(f[l, r, i] \leftarrow f[l, d - 1, i]\times f[d, r - 1, i+1]\times {r-l\choose r-d}\) 。

\(r-1\) 即断去叶子。

最终 \(ans=\sum_i f[1, len, i]\) 。

如何判定合法性呢？容易发现对于固定的 \(d\) ，合法的 \(i\) 是一个区间。

\(L[d]\) 为 \(d\) 所有祖先子树内次长链最大深度与 \(d\) 的深度差 \(+1\) ，即上端最少需要操作多少次才能使断开后深度无交。

\(R[d]\) 为 \(len-dep_d\) ，即不被作为叶子删去最多进行的操作次数。

为什么这样是对的呢？

可以通过类似记忆化搜索的方式，考虑回溯我们计数一种方案的路径，先后切去蓝色和红色的边：

如果蓝色边是合法的，那么 \(a\) 外侧的连通块已经与 \(a\) 子树的深度无交了，所以 \(b\) 也一定满足下界的限制。

如果存在割蓝色边的可能，其一定存下来所有对其有影响的操作次数，所以不会漏。

那么为什么多条最长链只需处理一条呢？因为如果有多条最长链，合法的方案一定是在链尾的 LCA 以上进行操作，所以 DP 哪一条都一样。

C.

记 \(f[i, j]\) 为 \(s\) 匹配了前 \(i\) 位， \(t\) 匹配了前 \(j\) 位是否可行。

转移分两类，假设 \(f[i,j]=true\) ，如果 \(s_{i+1}=t_{j+1}\) ，则 \(f[i+1,j+1] = true\) 。

如果 \(t_{j+1}=t_{j+2}\) ，则 \(f[i, j+2] = true\) 。

发现下面这个相同比较难维护，转换一下， \(f[j, i]\) 用 bitset 维护。

维护 \(s\) 中每种字符的出现位置的 bitset 可以轻松转移，复杂度 \(O(\frac{nm}{\omega})\) 。

D.

记一种新做法，添加叶子可以使用文艺平衡树动态维护欧拉序（括号序）。

定位子树只需要存左右括号编号以及每个节点的父亲即可，可以 \(O(\log n)\) 找到排名然后分裂。

每个节点再维护 \(coc[c]\) 表示子树内颜色为 \(c\) 的个数，更新发现形如子树内被染成 \((c+dep_u)\bmod k+1\) ，打标记即可。

再维护 \(cnt[d]\) 表示子树内 \(dep\equiv d\pmod k\) 的节点个数来辅助即可。