5月补题

反思一下自己最近在干什么。

NOI 模拟 #15

A. 序列

想到了分治结构维护，但没有简化信息的思想。

正解：

考虑求解 \([l, r]\) 的答案，关注区间中最小值 \(a_{mn}\) 出现的位置组成的若干连续段。设一个连续段长度为 \(len\)。当 \(len\) 偶数的时候，应当将其合并成长度为 \(len/2\) 的 \(a_{mn}+1\) 段。否则必然剩下的一个 \(a_{mn}\) 将求解区间断成两半，分别求答案即可。

考虑在线段树上维护这个过程。观察到，一个区间中若存在 \(a_i<a_{i-1} \land a_i<a_{i+1}\)，则 \(a_i\) 必然被合并。这时区间可能被分隔，考虑合并区间时将分隔合并，记录分隔中间的答案，则我们最后得到的区间是单峰的，且峰顶可能有分隔。将相邻相等的 \(a_i\) 压成一个则序列长度只有 \(O(\max(a_i)+\log2(n))\)。于是维护合并的过程可以接受。

\(\color{red}{没补出来，菜了}\)

B. 染色

构造题，没意思。

考虑以 \(u\) 为根的子树记作 \(sub(u)\)。\(sub(u)\) 同外界的连边只有三个：\(u\) 的父亲 \(fa_u\)，\(sub(u)\) 中最左右的儿子 \(L_u, R_u\)。

假设 \(fa_u,L_u,R_u\) 颜色相同。

构造 1.

暴力一点，将 \(fa_{L_u}\) 到 \(u\) 并 \(fa_{R_u}\) 到 \(u\) 染上一种新的颜色，遍历路劲上的除了 \(u\) 以外的点 \(x\) ，将 \(L_x,R_x\) 也染上这个颜色。并递归下去。容易检查这是一个合法构造，且一种颜色的点数是 \(O(\log 总点数)\) 的。这个方法可以得到 60pts。

正解（构造 2.

称 \(Lu\) 到 \(fa_u\) 链上的点顺次为 \(ver_1 \sim ver_k\)，\(R_u\) 到 \(fa_u\) 链上的点顺次为 \(ver_1' \sim ver_k'\)。对于 \(1<x\le(k-1)/2\)，我们将 \(ver_{x+1}, ver_{k-x},ver_{x+1}',ver_{k-x}'\) 染上同一种新颜色。然后同样遍历 \(fa_{L_u}\) 到 \(fa_{R_u}\) 除了 \(u\) 以外的点 \(x\)，染 \(L_x,R_x\) 和 \(x\) 相同的颜色。可以检查这是一个合法构造。

再评：补了这个题跟没有补好像没啥区别。

NOI 模拟 #14

A. 清晰人类

对时间轴分治，每 \(B\) 的操作分一组。考虑第 \(k\) 组操作中的询问，前 \(k-1\) 组操作中修改的贡献可以一起做持久化线段树合并预处理，单组 \(O(\log n)\) 查询。第 \(k\) 组操作中直接枚举询问前的修改操作，每个修改操作的贡献可以 \(O(1)\) 计算。

考虑总时间复杂度：\(O(n^2\log n/B+nB)\)。理论复杂度取 \(B=\sqrt{n\log n}\) 达到最优 \(O(n\sqrt{n\log n})\)。实际上应取 \(B\) 较大平衡线段树合并常数。

B. 人造光

忽略 \(P_A=B\) 的限制，打表发现答案是卡特兰数。于是尝试想办法将刻画合法排列的过程和卡特兰数扯上关系。通常可以考虑转移式可以表达为格路计数的 DP。

观察一个合法排列 \(P\)。其最大元素的左边是比其小的若干元素递降排序，再考虑其右边，又可以在找出新的最大元素，然后递归这一过程。如果对 \(P\) 建出笛卡尔树，应形如根挂着一条右链，右链每个点左儿子可能又挂着一个右链。

排列 \(H=n,n-1,n-2,\cdots,2,1\)。合法方案形如钦定根右链上的元素，并在 \(H\) 中标记出来，不影响其标记元素相对顺序的前提下将它们任意往后面（指标增大的方向）移动。

依照这个形式，考虑通过 DP 计数。设 \(f_{i,j}\ (i\ge j)\) 表示考虑元素 \(1 \sim i\)，钦定了元素 \(i\) 移动到位置 \(j\) 的方案个数。有转移式：

其中 \(j'\le i+1\) 是为了保证不存在不作为任何钦定点右链的节点。但是这个限制显然不好处理。考虑转移 \((i,j)\to (i',j')\)，其中 \(j'>i+1\)。则 \(i+1 \sim j'-1\) 没有被归入任何右链。这时我们强制钦定它们所有点，并且没有左儿子，同时要求 \(f_{i, j}\) 中 \(j<i\)。这样第三个限制就没了。

新的 DP 式容易转成格路计数。接下来只需要把统计路径个数的组合数推出来即可。