题目链接：QOJ Contest 3789 Problem A

题目要求动态维护一个访问顺序。每次交换相邻两个点后，要在整棵树中重新选择根，使得“后访问的点是先访问点的祖先”的点对数量尽量少。

如果固定一个根去计算答案，根一变，所有祖先关系都会变，似乎很难维护。更好处理的方向是反过来：固定一对点，去看它会对哪些根产生贡献。

对两个点 ，记 为删去 到 路径上的第一条边后，包含 的那个连通块。若当前选 为根，那么

这是因为当根在 这一侧时，从根走到 的路径一定经过 ；反过来，如果从根到 的路径经过 ，根也必然在删去第一条边后 所在的那一侧。

于是，排列中一个有序点对的贡献就不再是“对某个根加一”，而是“对某个连通块里的所有根加一”。这样就可以维护每个点作为根时的危险度，并支持对一块连通区域整体加减。

为了把这种连通块更新变成常规数据结构操作，先以 为根跑 DFS，得到每个点的子树区间。对于 ，如果 不是 的祖先，它就是 的子树；如果 是 的祖先，设 是从 走向 的下一个点，那么它就是全集去掉 的子树。也就是说，每次连通块更新都能表示成 DFS 序上的一个区间，或者一个区间的补集。用线段树维护每个根的当前危险度，即可支持区间加和全局最小值查询。

再看一次相邻交换。设本次交换的是

除了 这一对以外，任意两点的相对顺序都没有变化，所以答案数组的变化也只来自这一对。交换前， 在 前面，这一对贡献的是“ 是否为 的祖先”，也就是对 加一；交换后变成“ 是否为 的祖先”，也就是对 加一。因此操作时只要把前者减掉、后者加上：

每个 都能拆成常数个区间更新，所以一次交换只需要 。

剩下的是初始状态怎么建出来。设 表示点 在访问顺序中的位置。我们枚举后出现的点 ，统计它与所有更早出现的点会对哪些根产生贡献。

先假装无论根在哪里， 都会作为前面所有点的祖先，那么可以对所有根加上

这当然会多算。删去点 后，树会分成若干连通块。若根落在某个连通块 内，那么 内那些更早出现的点，从根到它们的路径不会经过 ，因此它们不该贡献。于是需要在这个连通块上减去

这些连通块仍然可以表示成子树或子树补集，所以最终也还是线段树上的区间加。

上式中的计数可以离线完成。按 从小到大扫描，用树状数组在 DFS 序上标记已经出现过的点。这样查询任意子树里已经出现过多少点，就是一次区间求和。得到所有需要减去的数量后，把每个点 对初始答案数组的贡献加入线段树即可。

建好初始线段树后，根的最小危险度就是线段树全局最小值；之后每次交换只做两次 更新，再输出全局最小值。

预处理、离线统计和建初值的复杂度为 ，每次交换复杂度为 。总时间复杂度为

题目链接：QOJ Contest 3789 Problem D

这题的操作看起来是在“重排字符串”，但真正不变的是每个位置的奇偶性：奇数下标上的字符永远只能留在奇数下标集合里，偶数下标上的字符也一样。

因此我们不需要关心字符的具体位置，只需要分别统计两类位置中每个字母出现了多少次。

记：

接下来只要看回文串中一对对称位置 和 的奇偶性。

如果 是偶数，那么 和 的奇偶性一定不同。也就是说，每一对相等字符都必须由一个奇数下标位置和一个偶数下标位置提供。所以对每个字母 ，必须有

如果 是奇数，那么 和 的奇偶性一定相同。中心位置是奇数下标，因此：

• 偶数下标中的字符必须全部两两配对；
• 奇数下标中的字符允许有一个字母剩下来放在中心。

也就是要求

并且

满足对应条件就输出 YES，否则输出 NO。

复杂度为 。

题目链接：QOJ Contest 3789 Problem G

我们要删除一个非空连续区间，然后把剩下的两段拼起来。麻烦的地方在于，拼接以后右半段的符号可能会改变。

定义交替前缀和

设删除区间是 ，令

也就是说，我们要统计 的二元组。

删除 后，前半段 的符号不变；后半段 是否翻转，取决于删除长度 的奇偶性。

如果 是偶数，右半段的符号不变，删除后的能量为

要求它等于 ，即

这时 同奇偶。

如果 是奇数，右半段的符号会翻转，删除后的能量为

要求它等于 ，即

这时 异奇偶。

于是可以从左到右枚举右端点 ，用两个哈希表维护此前出现过的 ：一个存偶数下标，一个存奇数下标。

对于当前 ：

• 同奇偶情况需要找 ；
• 异奇偶情况需要找 。

把两类方案数加入答案后，再把当前的 放入对应奇偶性的哈希表。

注意删除区间要求非空，而我们始终枚举 ，所以不会把空区间算进去。

使用哈希表时，时间复杂度为期望 ，空间复杂度为 。如果使用平衡树或 map，时间复杂度为 。

题目链接：QOJ Contest 3789 Problem J

棋盘只有两行，因此一条路径完全由下移列 决定。题目要我们填出一个棋盘，使得“白让自己拿到最多硬币”的策略会唯一地选择某条路径，但这条路径并不是让空收益最小的正确选择。

先把真正影响路径比较的格子提出来。无论白选择哪条路径，左上角 和右下角 都一定会被经过，所以它们不会影响路径之间的优劣。相邻两条路径的差别只来自每两列之间的一对斜对角格子，记

若原格子已经给定，对应变量的上下界相等；若原格子为 ，上下界就是 。记为

白选择下移列 后，没有被白拿走的部分分成上方剩余和下方剩余两段：

空会选择自己能拿到更多的一边，所以白真正应该最小化的是

但错误策略是让白自己拿到最多硬币。设棋盘总和为 ，白选择 时拿到 ，所以错误策略等价于最小化

我们要构造的就是这样一种局面： 有唯一最小点 ，但 不是 的最小点。

先刻画“ 唯一最小”。相邻两条路径满足

因此

若 是唯一最小，那么从 往左或往右走， 都必须严格变大。写成条件就是

以及

也就是说， 左边所有后缀和为正， 右边所有前缀和为正。

接着看怎样让这个唯一选择变成错误选择。假设白唯一选择了 。如果 ，空在路径 下主要拿上方剩余部分；这时把下移列向右挪，会减少上方剩余、增加下方剩余。若某个更右的路径能让 变小，那么相邻的 已经能做到。左边的情况完全对称。因此只需要尝试两类构造：让 比 更优，或者让 比 更优。下面只描述右侧反例；左侧可以把序列反过来用同样的方法处理。

右侧反例要求 。由

可知，只要

就够了。展开后为

于是我们希望左边尽量大、右边尽量小，同时还要维持 唯一最小。

先处理 左边。为了让左侧所有后缀和尽量容易为正，并且让上式右边尽量小，取

令 $e_i=\mathrm{ux}_i-\mathrm{ly}ie_1,\ldots,e{p-1}$ 的所有后缀和都为正；若可行，上式右边能取到的最小值是

$$
\mathrm{leftMinY}p=\sum{i=1}^{p-1}\mathrm{ly}_i.
$$

后缀和是否全为正可以线性预处理。设

则 ，只要 ，左侧就可行。

再看中心位置 。为了让 右边的 一开始严格上升，需要 。记

它必须满足

我们会取满足所有条件的最小 ，因为这样留给右半边的限制最宽松。

对 ，为了让右侧反例的不等式左边尽量大，先取 ，再令 。于是

其中

右侧所有前缀和为正等价于

记

$$
\mathrm{need}p=\max\left(0,\max{t>p}\sum_{i=p+1}^{t}L_i\right).
$$

那么为了让右半边至少有解，必须让 。综合中心位置的上下界，最小可行的

如果这个值超过 ，当前 就不可能作为右侧反例中心。

确定 后，设 。右半边还要在所有前缀和不超过 的条件下最大化 。这个最大值为

$$
\mathrm{best}p=
\min\left(
\sum{i=p+1}^{n-1}U_i,
C+\min_{q\ge p+2}\sum_{i=q}^{n-1}U_i
\right).
$$

可以理解成：如果全取上界不会出问题，就全取上界；否则某个前缀会先被 卡住，之后的后缀继续尽量取上界。这个式子可以用 的后缀和与后缀最小值 求出。

于是右侧不等式左边能达到的最大值是

$$
\mathrm{maxRight}p=-z+\sum{i=p+1}^{n-1}\mathrm{uy}_i+\mathrm{best}_p.
$$

右侧反例存在，当且仅当左半边可行，并且

这些量都能通过前缀和、后缀和、最大前缀下界、后缀最小值在线性时间内预处理，因此可以枚举每个 判断。

找到可行的 后，构造也沿用判定时的取法。左边取 ；中心选一组满足 且在上下界内的 ；右边固定 ，再构造 。

构造 时，需要满足 ，并且所有前缀和不超过 。可以先从左到右算每个前缀和的最小可能值 ，再算最大可能值 并用 截断，最后从最终前缀和倒推。若当前前缀和为 ，正在倒推第 个变量，则上一个前缀和 需要落在

中。任选一个合法的 ，令 即可。判定阶段已经保证可行，所以这个倒推一定能成功。

如果右侧反例找不到，就对称地尝试左侧反例；两边都找不到则输出 。最后把构造出的变量还原成棋盘：

没有参与变量的 和 不影响路径选择，若原本是 ，填 即可，否则保留原值。

总时间复杂度为 ，空间复杂度为 。

题目链接：QOJ Contest 3789 Problem K

原图是一棵基环树。变异时，每个原图点被替换成一个长度至少为 的环；原图中的每条边，则变成两个环之间的一条连边。

我们的目标不是恢复唯一的原图，而是输出任意一张同构的基环树。因此只要能把每个“被扩出来的环”重新识别成一个点，再把环与环之间的边连回去即可。

先看变异后的边会分成哪几类：

• 扩展环内部的边；
• 原图基环上的边，对应扩展环之间的非桥；
• 原图基环外树枝上的边，对应扩展环之间的桥。

所以第一步很自然：在变异后的图中找出所有桥，并把这些桥先删掉。

删掉桥之后，树枝部分的连接被断开了；而每个扩展环本身仍然存在，原图基环上的环间连接也仍然存在。

接下来考虑删桥后的度数。

对于某个扩展环 ，如果环上的一个点没有承担原图基环上的连接边，那么它只连着环内左右两个邻点，度数就是 。如果它承担了基环上的连接边，那么除了两个环内邻点外，还会连到别的扩展环，度数至少为 。

因为原图是基环树，一个点在基环上最多只会连出两条非桥边；又因为每个扩展环长度至少是 ，所以每个扩展环里一定能找到度数为 的点。

这个度数为 的点很有用：在删桥后的图里，它的两条边一定都是环内边，因此它和它的两个邻点一定来自原图中的同一个点。我们可以把这三个点合并。

不断重复这个过程，同一个扩展环中的所有点最终都会被合并到一起。不同扩展环之间不会被错误合并，因为跨环连接的端点在删桥后度数至少为 ，不会作为“度数为 的中间点”去把两边粘起来。

完成缩点后，每个缩点就对应原图中的一个点。

最后重新扫描变异后图的所有边。设一条边的两个端点分别属于缩点 ：

• 如果 ，它是扩展环内部的边，忽略；
• 如果 ，它对应原图中的一条边，输出这条缩点之间的边。

这样得到的图就是一张合法的基环树。

找桥、缩点和扫描边都可以线性完成，时间复杂度和空间复杂度都是 。

原文：洛谷专栏

Day -inf

马导（学校教练）说有一个出题任务你们接不接，我说接了。考虑到老一辈 NJU 出题组学长在准备 HK 赛，所以只能新拉一个出题组，成员大概是我（@paulzrm）、@HugeWide、@chen_zida、@lingluo_Official 和 @HHH666666 等。

然后开始出题。出题出题出题。以组题人的身份毙掉了好多题目，我好坏。继续出题出题出题。@lingluo_Official 真是出题自动机吧怎么这么能出题。

我自己先出了 AK，然后把想给 CF Div.2 A 的题拿过来当 D，顺便帮不想造数据（？）的队友造了 C。

五一出去上了次集训，小朋友做题给了个错解，然后灵光一现有了 J。

此时第一套题已经好了，拉了学长和朋友来验题。发现原 G 假了，紧急出了新 G。

作为资深二刺螈把四道题目套了二刺螈背景。以及悄悄放了两道《未闻花名》背景，熟悉我们的队伍会发现这是在致敬我们队名（我们仍未知道那天所看见的 acmer 的名字）。

然后说需要搞一场热身赛，只能被迫一个人糊了四道题出来。其实还好，热身赛 B、C 都是出完了结果发现撞原题就没用的，A 是想整个活新出的，D 直接用了我们上一次出的 CF 原题（CF2173），不知道有没有选手通过这道题发现出题人是我们（X

Day 1

平常美国作息的我破例早起来看比赛直播了。

开场一小时开出了一车题目，很符合预期，本来还以为出难了。

AK 被速通了（悲）。A 过的大部分都是中学生队伍，果然大学生老登像我一样都快写不动代码了。

I 是个奇妙结论计算几何题，果然靠这个就能防止中学生超过大学生（笑）。

299 min：你告诉我 J 被过了？我防 AK 的 J 被过了？本来验题群都在说川大夺冠比赛结束了，呃呃。

总之是我们第一次出正式赛，希望大家打得开心。

本文迁移自洛谷原文。

首先发现 是一定没有被抠掉的。如果没有其他别的数字，那么只有 显然是无法得到 的正整数倍数，输出 。

考虑将 除去其所有 因子得到 ，那么 与 互质。由欧拉定理得，，即 个 是 的倍数。再考虑把 补为 的过程，即乘上很多 和 ，只需要在我们的构造后面添上足够多的 即可。

现在我们得到了仅用 就能构造的方案，显然把 换为任意非 数字均成立。由于 ，所以不能直接计算 。我们预处理到 ，然后由 得，可以输出 个相同的任意没被抠掉的数字，最后输出 个 即可，仅需两步。

原文：洛谷专栏

T1

给定一个长度为 的字符串，支持修改和查询。每次询问给定区间 ，求其中最长的、由若干个 fudan 组成的子序列长度。

考虑使用线段树。每个节点存：若区间内第一个有用字符是 ，那么对应区间内最右边的有用字符 和字符个数 。合并时枚举状态即可。

T2

一个朴素想法是先二分答案（因为要求下取整），然后让所有 减去这个答案，要求每一段的和大于 ，再进行 DP。

令 表示考虑到第 个人、此前已经分了 段时，最少有多少段的和小于 。转移大致为：

1
2
3
4
5
6
7

for i in [1,n]:
    for j in [1,k]:
        for f in [i-r,i-l]:
            if sum[i] >= sum[f]:
                dp[i][j] = min(dp[i][j], dp[f][j-1])
            else:
                dp[i][j] = min(dp[i][j], dp[f][j-1] + 1)

加入线段树可以优化转移，但复杂度仍然超标。

观察这种形式下每次转移的 最多只会加 。对于直接加 的情况，维护 递减、 递增的单调队列。对于不加 的情况，新的 最多只会在原值基础上减 ，维护每段区间内相应状态是否存在即可。

T3

首先可以看出每次跳之后，行或者列的奇偶性不变。

于是大胆猜测：对于一行（或一列）有多个弹弓的情况，只需要考虑它们两两位置差的最大公约数的两倍。

T4

观察到一、三象限的车辆只会和二、四象限的车辆碰撞。直接暴力连边并运行最小割。

判断两辆车是否相撞时，可以先将它们绕原点旋转 ，转到第一、第二象限，然后枚举哪辆车先通过。

原文：洛谷专栏

共 5 道简答题，每题 20 分，共 2 小时。

T1

有一个面积为 的正方形和 个半径为 的圆。这个正方形合法仅当对于其内部任意一个点，以它为圆心、 为半径作圆，在这 个圆中至少有一个圆与这个圆相交或者重合。

证明合法的 。

T2

已知

令

比较

和

的大小关系。

T3

均为实数，且 已知。

定义一种 的填法的权值为

其中 ，且 和 之间有边相连。

求权值最小的一组 。

T4

有一个定义域在大小为 的环上（定义域为 ）的函数 ，满足 不全为 ，并约定 。

定义

定义 为函数 的特征值，当且仅当对于任意 ，满足

1. 当 时，求所有满足条件的函数 。
2. 求证：对于所有函数 ，其特征值 在 范围内。

T5

有一个 条边的凸多边形，顶点为 ，其内部有一个点 。定义

求证

根号分治，是暴力美学的集大成体现。与其说是一种算法，我们不如称它为一个常用的trick。

首先，我们引入一道入门题目 CF1207F Remainder Problem：

给你一个长度为 的序列，初值为 ，你要完成 次操作，操作有如下两种：

1. 1 x y: 将下标为 的位置的值加上 。
2. 2 x y: 询问所有下标模 的结果为 的位置的值之和。