2022牛客OI赛前集训营-提高组（第四场）题解

本场模拟没有生硬的多合一，或者是坑人的套路题，有较强的思维性，基本是对照 noip2021 的难度出的。

对题面的一些问题影响了选手的参赛体验表示歉意。

另外 D 题数据似乎造水了qwq

A. 博弈

xor-hashing 可能最近普及开来了，记得 PKUSC 和 ABC 都有考过啊。

另外，参考学习资料：link。

Part1

我们先来研究，在数组 确定的情况下，先手必胜的条件。

首先，当 的最小值只有 个的时候，显然先手必胜。

我们发现，只要 的最小值出现奇数次，那么先手就会必胜。

当 的最小值出现偶数次的时候，先手就不能第一个取最小值了，那么就可以把所有的最小值去掉，然后继续研究先手的必胜策略。

最后我们得到结论：先手必胜，当且仅当数组 中出现至少一个数，满足它的出现次数为奇数。

Part2

我们为每种边权赋一个随机关键值 。可以选取某个 如 ，然后 （自然溢出）。

我们记一个数组 的权值为 中每个元素的 的异或和。

考虑这样的权值有什么性质，如果一个元素出现偶数次，那么它的 就会因为异或变成 。

所以我们得出结论：当且仅当 的权值不为 的时候，先手必胜。

Part3

现在 的意义是树上某两点的路径上所有边的权值构成的数组。

回忆树上两点异或距离的解法，设 是从根到点 的路径的边权异或和，则 到 路径上所有边的边权异或和等于 。

本题中同理，设 为根到点 的路径所形成的 数组的权值，显然 到 路径构成的 的权值就是 。

预处理 后，只需要每次判断 是否等于 即可。

可以做到 的复杂度，也可以带个 之类的。

B. 跳跃

那这个可能思维比去年两个 ez T2 强很多，然而说不定今年正赛难度也会更上一层楼啊。

Part1

一个直接的想法是，找到整个序列 中和最大的一段连续段，然后反复横跳直到 次机会用完。

但是从样例 可以看出，我们并不能够第一次一下就跳到这样的连续段。

但是可以发现，跳跃方式，一定是第一次跳到某个位置 ，然后在 横跳若干次，然后跳到 并在 横跳若干次，....，最后跳到 ，并在 反复横跳到机会用完。( 是一个未知的量)

注：这里的 ，定义为在右端点确定下，和最大的连续段的左端点。

思考一下，我们为什么会有多个反复横跳段，是因为我们并不能一下跳到和最大的那个段进行反复跳跃，需要在一些和小一些的段跳几次，使得分数变大，然后使得我们可以跳到下一个和更大的段进行反复横跳。

Part2

令 保存从 跳到 （下一步应该是以 为右端点的区间，进行一个反复横跳。）所需要的最少次数，和跳到 以后的分数。

转移很简单，我们枚举上一个横条段 ，可以求出最少需要在 结尾的段横跳的次数，然后跳到 。注意由于方向会交替变化所以横条次数的奇偶性是有要求的。

最后统计答案时， 个点结尾的横条段都枚举一下，进行反复横跳来更新答案即可。

时间复杂度：，转移的时候我写了一个二分所以是 的也可以通过。

C. 大陆

感谢 45dino 提供并准备了本题，原定的折半 + FWT 感觉不太适合放这个位置。

感觉比 NOIP 2020 那个神秘 T3 简单很多。

本题构造方法不唯一，如果有其他做法欢迎在讨论区提出。

分析构成一个省的城市的联通情况，可以发现，一个省要不然是一个连通块，要不然可以通过加上一个点（省会城市）变成一个连通块。

将整棵树定为一个以 为根的有根树，对于每个节点 ，记录一个点集 ，表示 的子树里还有哪些点暂时没有被分配到城市。

从下往上求 ，对于当前节点 ，依次把儿子节点的 合并到 里，如果当前点集大小刚好大于等于 ，就把 里目前的所有点全部划分成一个省，这个省的省会为 。最后 里会剩下一些节点，这些节点会被分配到 中去，其中 表示 的父亲节点。

容易发现，这样可以保证每次 内剩余的节点数小于 ，因此必然可以构造出一个合法的解。

实现时需要注意的一点是，每次应该合并完 节点的所有儿子后，再将 插入 ，这样可以使 内剩下节点是一个包含 的连通块，这样就能使得构造符合第二条要求。

D. 排列

平衡树是提高考纲内容

Part0：

需要对 fhq-treap 有一定了解。

Part1：

考虑用 fhq-treap 在线处理这个问题。区间循环右移就是 split 一下再换个顺序 merge，关键是维护答案。

我们先考虑一个弱化的问题：询问全局是否存在二元上升子序列。

对于这个问题，在平衡树的每个节点里维护一个 ，意义是该节点为根的子树内是否存在二元上升子序列，同时维护 和 ，表示子树最大/最小值。这样， 的时候，就可以根据左右子树的信息，来维护 。

Part2：

问题回到全局是否存在三元上升子序列。还是维护 ，定义为子树内是否存在三元上升子序列。注意到合并子树的时候，左子树或者右子树可能贡献两个元素作为三元上升子序列的一部分，所以只维护 和 不行了。

我们可以多维护两个 和 。 的定义是，子树里最大的元素值 ，满足子树内存在一个以 结尾的二元下降子序列；类似地定义 为子树里最小的元素值 ，满足子树内存在一个以 结尾的二元上升子序列。

有了 和 ，就可以进行 的维护了。

问题是， 和 似乎无法维护。

Part3：

下面我们仅关注 的维护， 的维护是一样的。

首先 这是显然的，问题是可能出现一个在左，一个在右的情况。

显然右边的那个点的值就是 ，而左边的点的值应该是最大的小于 的值。

看上去平衡树应该可以直接维护这个东西，但是我们的平衡树要支持区间循环右移，所以一开始就是按照 （位置）排序的。

我们想一下，如果当前子树的 已经为 了，那么我们现在就不需要维护 了，因为答案肯定是 YES。也就是说我们只用在子树 为 的情况下，维护它的 ，根据 的定义，子树内不存在三元上升子序列。

所以，左子树里小于 的元素单调递减。

所以只要找到左子树里最左侧的小于 的元素，类似地还要找右子树最右侧的大于 的元素。

这两个查找和常规平衡树的查排名（给定排名求值）是一样的，期望复杂度都是树高即 。

所以总复杂度 。