十二省联考 部分题解

异或粽子

给出一个序列$a$，设$w(l,r)$表示区间$[l,r]$的异或和。

我们把所有$1\le l<r\le n$的$w(l,r)$拿出来排序，求前$k$大的和。

$n\le 5\times 10^5,k\le 2\times 10^5,0\le a_i<2^{32}$。

持久化 Trie 二分

由于$k$不大，我们考虑依次求出第$i$大的异或和。那么区间异或可以转化为两个数的异或，于是我们维护一个堆，首先把以$i$为右端点的最大异或和放进去。每次我们拿出来一个$(i,k)$（表示以$i$为右端点第$k$大的异或和）后，我们就把$(i,k+1)$求出来并放到堆里。

查询的话，把 Trie 可持久化一下，就变成了异或第$k$大的问题，可以在 Trie 上二分求解。

时间复杂度$O((n+k)\log_2n)$。

代码

字符串问题

给出一个字符串$S$。

从中取$n_a$个子串$S[la_i,ra_i]$，称为 A 类串。

从中取$n_b$个子串$S[lb_i,rb_i]$，称为 B 类串。

此外，有$m$个关系$(x_i,y_i)$（$1\le x_i\le n_a,1\le y_i\le n_b$），表示第$x_i$个 A 类串支配第$y_i$个 B 类串。

现在要求你构造一个字符串$T$，使得：

• $T$可以被划分为$t_1t_2\cdots t_k$（$k\ge 0$）使得每个$t_i$都是 A 类串；
• $t_i$支配$t_{i+1}$的前缀（$1\le i<k$）。

要求你最大化$T$的长度并输出。如果$T$可以无限长，输出$-1$。

$n_a,n_b,|S|,m\le 2\times 10^5$。

SAM DP 拓扑 倍增 建图

考虑把$S$和$T$倒过来。这样就变成了，$t_i$的后缀被$t_{i+1}$支配。如果从支配关系中$y$向$x$连有向边，那么相当于$t_i$跳到它的后缀再跳到$t_{i+1}$。而后缀连边显然可以后缀树来做。

具体地，把后缀树中的节点和 A 类串，B 类串放在一起建图。边要分两种，支配边和非支配边。如果图中有环则可以无限长。否则就是 DAG 上做一个简单 DP 即可。

在建图过程中，由于要定位 A（B）类串在 SAM 上的状态，可以在后缀树上倍增。

时间复杂度$O(n|\Sigma|+(n_a+n_b)\log_2n+m)$。

代码

春节十二响

给出一棵$n$个点有根树，每个点有点权$m_i$。要求你把$n$个节点划分到若干个集合中使得：

• 每个点属于且仅属于一个集合；
• 若$u,v$是祖孙关系，则$u$和$v$在不同的集合。

一种划分的代价是所有集合点权最大值的和。求最小代价。

$n\le 2\times 10^5,m_i\le 10^9$。

启发式合并 盲猜

根节点一定单独一个集合。那么考虑根节点的儿子，他们会划分在哪些集合中？

不同的子树是互不影响的。因此根节点的儿子要么自己开一个集合，要么放在别的子树中点权最大值比它的点权大的集合。

然后再简单盲猜一下，发现两个不同子树的集合是可以合并的。对于两个子树的集合，我们把他们分别按照点权最大值排序，然后依次合并（两个集合的合并就是取 max）即可。

可以启发式合并。

使用 multiset 实现，时间复杂度$O(n\log^2n)$。

注意：虽然本题不需要担心这个问题，但 multiset 仍然不是个好东西，它的 count() 方法复杂度与找到的元素数线性相关。

代码

皮配

有$n$个数（学校）$s_i$，第$i$个数的颜色（城市）是$b_i$。

你有四个集合$A_0,A_1,B_0,B_1$（$A$和$B$是两个阵营），你需要给每个数选一个集合放进去。

要求颜色相同的数放进相同的阵营（即，颜色相同的数，要么都放入$A_0,A_1$，要么都放入$B_0,B_1$）。

同时要求：

• $A_0,A_1$里数的和$\le C_0$；
• $B_0,B_1$里数的和$\le C_1$；
• $A_0,B_0$里数的和$\le D_0$；
• $A_1,B_1$里数的和$\le D_1$；

同时，有$k$个数，他们有特殊的要求（偏好学校）：不能放在某一个集合中。

问总方案数。

$c\le n\le 1000,k\le 30,\max(C_0,C_1,D_0,D_1)\le 2500$。

生成函数

考虑生成函数。对于一个人数为$s$的学校，假设$x$的系数代表$C_1$的贡献，$y$的系数代表$D_1$的贡献，那么一个学校的生成函数就是$(1+x^s)(1+y^s)=1+x^s+y^s+x^sy^s$。

考虑一个城市的生成函数。假设这个城市的学校的集合是$S$。

先假设这个城市里没有偏好学校。由于他们选的阵营是一样的，容易得到

$$\left(1+x^{\sum_{s\in S}s}\right)\prod_{s\in S}(1+y^s)$$

而对于偏好学校，首先要知道，他们的生成函数是与普通学校不同的（少一项），因此基本上是不能整理成$(1+x^s)(1+y^s)$的形式的。而由于一个城市选的阵营得一样，因此我们需要把偏好学校的生成函数整理成$1\cdot A+x^s\cdot B$的形式。

对于含有偏好学校的城市，假设这个城市中普通学校集合为$S_0$，偏好学校集合为$S_1$，那么可以得到

$$\left(1\cdot \prod_{S_1}A + x^{\sum_{s\in S_0\cup S_1}s}\cdot \prod_{S_1}B\right)\prod_{s\in S_0}(1+y^s)$$

那么所有城市的生成函数就是每个城市生成函数的乘积。设总人数为$X$，那么我们要求的就是满足$X-C_0\le a\le C_1,X-D_0\le b\le D_1$的$x^ay^b$的系数和。

考虑如何计算这个生产函数。对于无偏好学校的城市，他们的生成函数可以分别计算$x$和$y$的多项式系数。

对于含有偏好学校的城市，首先可以把后面的$(1+y^s)$的系数快速计算出来，合并到之前的多项式中。注意到这类学校的个数不超过$30$个，而$s_i\le 10$，因此我们可以暴力计算出$\prod_{S_1}A$和$\prod_{S_1}B$，然后计算出偏好学校的二维生成函数。

然后我们枚举二维生成函数中的每一项，则他们对答案的贡献系数就是$x$和$y$多项式的一段区间和。那么前缀和优化一下即可。

时间复杂度$O(k^2s^2_i+\max(n,C_0,C_1,D_0,D_1)^2))$。我也不知道复杂度算对没有，反正能过就对了。

代码