「十二省联考 2019」解题报告

· · 个人记录

给定序列 a_{1\dots n}，求出前 k 大的区间异或和之和。n\le 5\times 10^5，k\le 2\times 10^5。

首先建一棵可持久化 Trie 方便求出每个后继对应的最大异或前驱，然后放入堆中。每次从堆中取出最大值，找到它后继对应的下一名前驱（这个也可以用 Trie 方便实现），再次放入堆中即可。时间复杂度 O((n+k)\log n)。

Code 1.47KB

首先注意到题目的限制可以方便的利用图论模型来刻画。翻转字符串，将前缀限制变为后缀限制。串 A 是串 B 的后缀在 SAM 上体现为 B 在 A 的子树中，所以先建出 fail 树，再将所有父亲连向儿子。对于支配 (A,B)，相当于串 B 所在结点向 A 所在结点连边。但在相同结点，只有长度短的向长度长的可以连边。所以拆点，对单点长度离散化一下，建边即可。

接下来就是模板的最长路径长度。注意存在环的时候长度为 \infty。时间复杂度 O(Tn)。

Code 3.67KB

这道题真的有人做吗

简化题意来自 Mirach。

有 c 个豆荚，共 n 颗豆子，每颗豆子都有自己的重量，现在需要将给豆子设定为 (黄色/绿色，圆粒/皱粒)，要求满足以下条件：

  • 给定这四种性状的阀值 C_0,C_1,D_0,D_1，要求为这种性状的豆子重量和不能超过该阀值。
  • 与此同时，这 n 颗豆子中存在 k 颗顽皮豆，顽皮豆都有自己的想法，比如拒绝成为 (黄圆/黄皱/绿圆/绿皱)。
  • 同一个豆荚里的豆子必须 同时为黄色 或 同时为绿色。

首先根据两种性状可以将问题划分为两个维度——颜色和圆皱。在不存在顽皮豆的情况下这两个维度不会有影响。颜色按照豆荚划分，而圆皱按照豆粒划分。

设 f_i 表示有 i 个黄色豆子，g_i 表示有 i 个圆粒豆子，答案则为 \sum_{i=n-C_1}^{C_0}\sum_{j=n-D_1}^{D_0}f_ig_j。

现在考虑划分这些顽皮豆。假设有顽皮豆的豆荚是有毒的豆荚，那么这种豆荚不超过 k 个。对于没毒的豆荚显然可以按照上面的 DP 来做颜色划分。同样的，对于无毒的豆子也可以照常进行圆皱划分。

那么有毒的呢？首先对于颜色性状的重量和可以 “集中” 到顽皮豆上。对于每个有毒豆荚，先钦定它的颜色，再对于每颗有毒的豆子枚举它的性质，设 h_{i,j} 为有毒豆荚 “黄色” 和 “圆粒” 分别的重量之和，进行普通背包即可。

最后对 f,g,h 数组进行类似于卷积的合并即可。

Code 3.36KB

给定一棵 n 个点的树，需要将点划分为若干个集合，每个集合中不存在祖先后代关系，同时使得每个集合的最大值之和最小。n\le 2\times 10^5。

显然这是一道贪心题。考虑怎样才能合并一个结点的若干个子树。

首先最大值无法被消灭，所以我们就希望贪心的让最大值被分配完后，剩下的最大值最小。所以找到最大值后，将其它几棵子树的最大值一起拖下水。用堆实现即可。这种操作是单次均摊 O(\log n) 的。

一直这样操作，最后肯定还会剩下一棵子树无法被消灭了。此时使用启发式合并即可。时间复杂度 O(n\log^2n)（也有人说 O(n\log n)）。

Code 1.31KB

给定一棵 n 个点的树，你需要找到 k 个连通块，使得存在一个点在每一个连通块当中，而且所有点距离它不超过 L。L\le n\le 10^6，k\le 10。

注意到确定这 k 个集合后，剩下的所有合法点一定能够构成一个连通块。对这个连通块进行 “点数-边数” 的容斥。考虑换根 DP，设 f_{x,i} 为 x 子树内包含 x，且距离 x 不超过 i 的连通块数量（包括空块），g_{x,i} 表示在 x 以及父亲子树范围内，包含 x 且距离 x 不超过 i 的连通块数量（必选 x）。

那么对于每个点，答案就是 ((f_{x,L}-1)\times g_{x,L})^k。对于每条边，在儿子处进行计算，答案为 ((f_{x,L-1}-1)\times g_{x,L})^k。接下来就需要着手去解决 f 和 g 的计算。有下列公式：

\begin{cases} f_{x,i}&=1+\prod_{y\in \operatorname{son}(x)}f_{y,i-1}\\ g_{x,i}&=g_{fa,i-1}\prod_{y\not= x,y\in \operatorname{son}(fa)}f_{y,i-2} \end{cases}

注意到第二维跟深度有一定关系，考虑长链剖分优化。

首先自己可以直接继承重儿子的子树。接下来的问题是轻儿子的计算。设 len_y 为 y 向下延展的链长。对于 i\in [0,len_y+1] 的 f_{x,i}，可以直接计算。但对于 i>len_y+1 的时候，我们需要 f_{y,>len_i} 的取值。如果直接暴力计算的话会影响时间复杂度。但注意到 f_{y,>len_i}=f_{y,len_i}，所以我们只需要记下来这个值，然后对于 f_{y,i} 中 i>len_y 的情况做一次后缀乘即可。

但本题时间限制紧，只能使用 常数级别数据结构 解决问题。正难则反，后缀乘可以看成一次全局乘和一次前缀乘逆元。注意到前缀长度是 len_y，支持暴力操作。加个全局乘标记 mul 可以解决问题。在实际代码中，出于将实际值改写成序列值的需要，还得维护标记的逆元 imul。

这个时候问题又来了：如果 f_{y,len_y}=0\bmod p 怎么办？这个时候就相当于对一段后缀清零。记录下来需要清零的后缀 lim=len_y+2。不过这里还有个问题，那就是清零点后续可能还会有新值加入（比如 f 数组最后的 +1）。这个时候稍稍修改下定义，把 “清零点” 变成 “等值点”，再存储下等值点对应的权值 val 即可。

最后的 +1 操作其实就是个全局加法，打个加法标记 add 即可解决。这个时候，我们用 (add,mul,imul,lim,val) 这五中标记构建的常数级别数据结构解决了问题。

在普通 DP 中，长链剖分的过程可以用 “合并” 来描述。在换根 DP 中，我们的 DP 顺序的从上往下的，所以长剖的顺序由 “合并” 变成了 “分裂”，即子结点继承父结点的信息。

首先对于数组 g_i，只有 g_{i,L-len_i}\sim g_{i,L} 这部分信息是有用的，因为儿子对于父亲信息的利用相当于右移一位，而最多右移 len_i 次，所以信息大小为 O(len_i) 级别，可以用长剖维护。

接下来的问题就出在数据 \prod_{y\not= x,y\in \operatorname{son}(fa)}f_{y,i-2} 的计算上。它照理来说等于 \dfrac{f_{y,i-1}-1}{f_{x,i-2}}，但有个问题就是 f_{x,i-2} 有可能等于零。解决这类问题的经典方法就是拆成前缀积和后缀积之积。前缀积可以在枚举的过程中维护，但后缀积却因为空间限制不能这样。

考虑 回退数据结构，考虑用栈存储二元组 (key,val)，即元素的地址和原来的值。每次修改时加入原来的位置和地址，回退时不断弹栈即可。回退完当前 x 做出的改变之后，此时 f_{fa_x,i-1} 的值就是后缀积。

考虑轻儿子对重儿子的贡献时，仿照 f 的维护方式，利用五标记体系的常数级别数据结构即可解决问题。

我们需要批量求出 f_{x,len_x} 的逆元。如果直接快速幂是 O(n\log V) 的，完全过不去。但 f_{x,len_x} 是很好预处理的，预处理完后仿照阶乘逆元的处理方式，求出前缀积和它们的逆元即可。

用来存 g 的长剖数组只需要求出 L-len_i\sim L 这些位，注意到下标 <0 的指针仍然是可用的（虽然会导致 UB），且我们最终利用的下标 \ge 0，所以直接指针左移 \max(L-len_i,0) 位是不会出事的。

对邻接表去掉父亲和重儿子，再按照 len 从大到小排序，可以规避很多不必要的分类讨论。这里虽然会多个 log，但 sort 可比桶排好写多了！

在继承和合并的过程中，势必会出现很多位不能由之前的位来转移，此时一定要对它们重新赋值成 0/1。

注意 f 数组的 lim 一开始要赋值在未定义位 len+1，g 则是未定义位 l+1。时间复杂度 O(n\log k)。

Code 5.55KB