异或粽子

给出一个序列,设表示区间的异或和。

我们把所有拿出来排序,求前大的和。

持久化 Trie 二分

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

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

时间复杂度

代码

字符串问题

给出一个字符串

从中取个子串,称为 A 类串。

从中取个子串,称为 B 类串。

此外,有个关系),表示第个 A 类串支配第个 B 类串。

现在要求你构造一个字符串,使得:

  • 可以被划分为)使得每个都是 A 类串;
  • 支配的前缀()。

要求你最大化的长度并输出。如果可以无限长,输出

SAM DP 拓扑 倍增 建图

考虑把倒过来。这样就变成了,的后缀被支配。如果从支配关系中连有向边,那么相当于跳到它的后缀再跳到。而后缀连边显然可以后缀树来做。

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

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

时间复杂度

代码

春节十二响

给出一棵个点有根树,每个点有点权。要求你把个节点划分到若干个集合中使得:

  • 每个点属于且仅属于一个集合;
  • 是祖孙关系,则在不同的集合。

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

启发式合并 盲猜

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

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

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

可以启发式合并。

使用 multiset 实现,时间复杂度

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

代码

皮配

个数(学校),第个数的颜色(城市)是

你有四个集合是两个阵营),你需要给每个数选一个集合放进去。

要求颜色相同的数放进相同的阵营(即,颜色相同的数,要么都放入,要么都放入)。

同时要求:

  • 里数的和
  • 里数的和
  • 里数的和
  • 里数的和

同时,有个数,他们有特殊的要求(偏好学校):不能放在某一个集合中。

问总方案数。

生成函数

考虑生成函数。对于一个人数为的学校,假设的系数代表的贡献,的系数代表的贡献,那么一个学校的生成函数就是

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

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

而对于偏好学校,首先要知道,他们的生成函数是与普通学校不同的(少一项),因此基本上是不能整理成的形式的。而由于一个城市选的阵营得一样,因此我们需要把偏好学校的生成函数整理成的形式。

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

那么所有城市的生成函数就是每个城市生成函数的乘积。设总人数为,那么我们要求的就是满足的系数和。

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

对于含有偏好学校的城市,首先可以把后面的的系数快速计算出来,合并到之前的多项式中。注意到这类学校的个数不超过个,而,因此我们可以暴力计算出,然后计算出偏好学校的二维生成函数。

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

时间复杂度。我也不知道复杂度算对没有,反正能过就对了。

代码