task18

[TOC]

1. NOI2024 - 树形图 [K] ✔️

题面

给定一张 个点 条边的有向图 ，定义点 是 的根，当且仅当其到其他所有点都恰有一条简单路径

按照如下方式给所有点分类：

• 一个点 是一类点当且仅当其是 的根
• 一个点 是二类点当且仅当其不是一类点，且存在一种删除一些图中有向边的方案得到一个新图 ，使得是 的根的点都是 的根，并且 是 的根
• 其余点均为三类点

请你求出 中每个点的分类。 组数据。

特殊性质 A：不存在一类点

特殊性质 B：不存在二类点

特殊性质 C：保证 为 的一类点

存在 A、BC、B、C 的部分分

题解

Sol

首先，如果图中不存在一类点，那么是容易做的，二类点即为能到其他所有点的点

接下来我们观察一下结构：以一个一类点为根后，一定有唯一的一棵外向生成树，并且这棵生成树上只有祖孙回边

此时求解其他点是否是一类点就比较容易了，判定一个点 时，考虑如下事情：

• 一个一类点子树向外一定有恰好一条回边，否则 会有两条路径
• 如果恰好有一条回边，设这条回边指向了 ，那么 是一类点当且仅当 是一类点

那么我们就解决了已知一个一类点时，其他点是否是一类点的判定问题

接下来考虑解决二类点的判定问题，我们还是以一个一类点为根。

我们现在要将这个图删成一个子图，而原来一类点还要是一类点，因此所有树边都不能删除，且对每个一类点 ，其子树内连到子树外的回边不能删除

那么判断一个点 时，考虑如下事情：

• 如果有两条不能删的回边跨过了这个点，或者没有回边跨过这个点，那么一定倒闭了
• 否则我们需要在跨过这个点的回边中选择一条，使得这条回边指向的点为一类点或二类点，这个也是容易处理的，用一些支持树上链覆盖的数据结构维护即可

那么现在唯一剩下的问题就是找到一个一类点

注意到以一类点为根之后，只有回边，那么叶子一定入度为 ，其唯一的入度来源为它的父亲

这启发我们进行这样的过程：每次选择一个入度为 的点 ，设其入度来源为 ，我们将 的所有出边都给到 上，然后将 删除，并删除 的自环，但是不叠合重边

如果一个点没有被删除，那么原来它是一类点，进行一次操作后它应该仍是一度点，如果删成只剩一个点，那么我们可以将操作序列倒过来，生成出来的树就是符合条件的树，因此其一定是一类点

而如果删到最后剩 个点，那么说明这些点入度都 ，因此不存在一类点

那么我们只要维护这个过程即可。

使用启发式合并，维护每个点的入边和出边，将一度点 和其入度 合并时可以发现 的入度集合并不会变化，我们只要将出度合并，而自环的数量也可以通过小的一边数出来

时间复杂度

---

2. AGC028F2 - Reachable Cells [K] ✔️

题面

给定一个 123456789# 组成的 字符矩阵 ，你可以从一个非 # 格子开始，每次向下或向右走到一个非 # 格子

求所有格子有序对 的 之和，满足 ， 均不为 #， 能到达

题解

Sol

这题好像能被 草过，很坏了。

我们可以观察到一个性质：对于一个格子 ，其能到达的位置满足在每一行上都是一个区间，再扣掉从第 行任意一个位置不可到达的格子

有了这个我们就可以比较容易地做到 了，但是难以优化。

考虑分治，如果我们当前得到的矩阵大小为 ，设 ，我们将矩形分为上下两半，设我们从第 行分开

注意到如果我们枚举上半部分的格子，那么其能到达的第 行的点是一个区间扣掉一些格子

进一步地，如果我们对上半部分的一行 ，从左到右枚举所有第 行的格子，其能到的区间左右端点都是逐渐递增的，并且哪些格子会被扣掉也是可以提前确定的

因此，我们可以考虑动态维护一个第 行的格子集合 ，需要支持以下操作：

• 在 最右边加入一个格子
• 删除 最左边的格子
• 查询 中的格子能到的下半部分的并集大小

接下来我们考虑如何维护这件事情。

我们维护 ，表示第 个格子能到的格子，且不能被任何 及更靠右的格子到达的格子数量，并且在加入一个格子的时候时刻更新这个值，维护出这个值之后剩下两个操作都是容易处理的

那么我们加入一个格子的时候就需要考虑有哪些点的 值会被更新

如果我们令 表示 向下能到达的最靠下的行号，那么可以发现会被更新的 一定要满足 ，因为 一定要“越过”中间的所有点的可达范围才能有可能被 新截掉一些部分

而容易发现我们用一个单调栈维护后缀最大值，这就是被 弹掉的部分，因此总共更新的次数是 的

那么我们现在就是要对于一对 ，求出 会被 截掉的部分大小，可以发现，这就是 行及以下，能同时被 到达的格子数量

称 表示能同时被 到的第 行的格子数量，我们需要支持对这个函数 求值

考虑如果处理出来 表示 能到的第 行的区间，那么可以发现求 时，即为 行中 和 的交集大小

但是这样我们还是不好 求值，但我们观察到，在 第一次相遇的行 及以下，到 或 为空为止，这之间我们直接用行的前缀和 计算一定不会错，因为这之间要么有 ，要么 到 之间没有任何可达的格子，所以这样计算是正确的

因此我们只要处理出 ，我们预处理一下前缀和就可以 查询

对于一个 ，处理 时我们每次向下走，设当前我们在 ，那么如果我们能向下走， 就是 ，否则我们找到右边下一个可达的格子，然后再进行判断是否能下走，这样即可得出 ，找右边下一个能向下走的可达格子可以预处理加速

处理 的过程是类似的，只需要额外注意 走到一行之后还需要尽可能向右走即可

而处理 的时候，考虑固定 ，那么我们发现随着 递增， 一定也是递增的，所以我们用一个指针扫，在枚举 的时候用 判断是否有交，如果无交就将指针 ，这样求解一个 的所有 是线性的

那么我们一层的复杂度就是 ，总复杂度

---

3. AGC028E - High Elements [E] ⭐

题面

给定一个 的排列 ，要求将其划分为两个子序列 ，使得 和 的前缀最大值数量相等

额外地，我们将每个元素属于 看成一个字符串，你需要输出字典序最小的合法字符串，或者判断无解

题解

Sol

首先获取一些关于这个题的直觉。

注意到如果 ，那么可行当且仅当 为偶数，因此大概率和奇偶性有一些关系

而如果 ，那么我们至少可以造出来一边是 ，一边是 的解，剩下的点都可以被 挡掉

进一步地，我们考虑每个前缀最大值属于哪个子序列：

可以发现，我们确定了每个前缀最大值属于哪个子序列之后，在相邻的两个红色前缀最大值之间，我们可以任选一个递增序列作为红色序列的前缀最大值，剩下的部分都可以用绿色的前缀最大值挡掉

因此如果我们考察红减绿的值，初始是红色前缀最大值减去绿色前缀最大值数量，每个红色区域可以让这个值 ，每个绿色区域可以让这个值

而不难发现我们一定只会选择红色区域或者绿色区域中的一个，因为同时加减正数没有意义，不妨假设我们选择了红色的

那么初始假设所有前缀最大值都是绿色，然后我们需要选择一个红色上升序列，每选到一个非前缀最大值会 ，选到一个前缀最大值会 ，我们需要求出是否有一个序列的权值能恰好使红减绿为

而我们发现如果 的子序列可以选出，那么 的子序列一定也可以选出，因此我们维护奇偶性的两个树状数组

那么我们就可以用树状数组上查询即可判断是否有解，求字典序最小只要把树状数组倒着撤销判断即可，总复杂度

---

4. AGC030F - Permutation and Minimum [E]

题面

给定一个长为 的序列 ，满足每个位置要么为 ，要么为 之内的整数，保证所有非 的元素互不相同

定义 ，求将 填成 的排列能生成多少种不同的 序列，对 取模

题解

Sol

将已经配对好的 删除。

画到数轴上就是 会互相匹配，那么我们就是不能让已经填了的数互相匹配起来，因此初步思路就已经可以设出 dp 状态了

令 表示考虑了 的数，当前前面有 个未填好的数要向后匹配，前面有 个填好的数要向后匹配

转移需要注意的点：当未填好的数作为更小的数时，如果匹配了一个填好的数，那么我们是关心它匹配了哪个填好的数的，所以可以在转移的时候提前选定这个数之后会和填好的数匹配还是未填好的数匹配

复杂度

---

5. AGC030E - Less than 3 [E]

题面

给定两个长为 的 01 串 ，保证 中都不包含三个连续相同字符

每次你可以反转 中任意一位，需要保证操作之后 中仍然不含三个连续相同字符

求 变为 的最小操作次数

题解

Sol

在 10 之间画一条蓝线，在 01 之间画一条红线

每次操作后需要保证相邻两条线距离依然为 或

枚举一下原来的线和新的线的对应关系即可，只有 种

总复杂度

---

6. QOJ6011 - Map Reduce [E] ⭐

题面

给定一个 的字符矩阵，字符矩阵内的字符有以下几种可能：

• #：这个格子为一个障碍，无法经过，保证最外圈都是 #
• .：这个格子为空地，可以经过
• S：这个格子为起点，其余和空地相同，保证恰有一个 S
• F：这个格子为终点，其余和空地相同，保证恰有一个 F

保证所有 .SF 四联通，且保证任意 2x2 不会为以下两种之一：

#.   .#
.#   #.

（同样地，上图中 . 任意替换为 SF 后的结构也不能出现）

给定一个常数 ，你需要将图中一些 # 改为 .，使得新图依然满足上述所有性质，并且 S 到 F 的最短路为 （每次移动到一个四联通的格子）

题解

Sol

显然 需要和初始最短路同奇偶，且需要大于等于曼哈顿距离，小于等于初始最短路，画一画可以发现好像这样的情况都能造出来。

那么我们考虑按某种顺序删除障碍，使得每删一个障碍任意一对空地之间的最短路减少不超过

这是可以做到的，我们必定能找到以下两种情况的障碍之一，使得其删除后仍然合法：

...   ???
.#.   ?##
???   ?##

用队列维护所有可以删除的字符，可以做到 求出障碍删除顺序

求出顺序后我们在这个序列上二分，对比中点的最短路和 的大小关系，求出我们想要的位置即可

复杂度

---

7. QOJ9698 - Twenty-Two [E] ✔️

题面

给定一个长为 的数列 ，接下来有若干次在这个序列上的操作：

• 给定 ，对每个 执行
• 给定 ，对每个 执行

有 个一操作， 个二操作，并且这些操作的参数都已经给定，求任意重排这些操作能得到多少种不同的最终序列，对 取模

题解

Sol

看起来无从下手。

注意到 ，也就是说实质上我们可以首先将每个 对 操作的最小值取 ，然后操作序列中的每个 操作是将区间内的数对

因此不难发现我们的 操作是递增排列的，并且每个 可以选择对一段后缀的 操作的 取

那么我们现在就只有 操作了，可以考虑在笛卡尔树上 dp，令 表示区间 的最小值 ，并且只考虑在 内的操作，得到的序列数量

转移就是选择 内一个子集让它们值为 ，需要满足这些点都被能变成 的操作覆盖，从点分成的区间的 转移过来

转移的时候再做一个 dp 即可做到复杂度 ，循环展开即可通过。

内层 dp 的转移应当是

有两种手段优化到 ：

Sol1

我们内层 dp 需要在所有被覆盖的位置之间转移，而我们固定 扫描 ，每次对被覆盖的位置形如将一段后缀从为未被覆盖变为被覆盖

那么我们倒着扫描所有新被覆盖的位置，扫到 时首先枚举所有 ，计算 对 的贡献，计算之后，我们再枚举 的所有位置，此时转移的区间一定全都被覆盖，考虑预处理出 表示 全被覆盖的情况下， 对 的贡献系数，那么我们就可以 做完向后的转移

因此每次复杂度是 ，总复杂度为

Sol2

考虑容斥，改成钦定转移路径上一些点必须是未被覆盖的位置，剩下的点随意

那么现在我们就是在未被覆盖的位置之间转移，每次后缀覆盖操作对转移的影响很小，只是舍弃掉最后几个状态，再加上最多一个状态，因此我们可以 更新 dp 值

总复杂度为

---

8. QOJ9222 - Price Combo [E]

题面

有 个物品，第 个物品在 A 商店的价格为 ，在 B 商店的价格为

这两个商店都推出了优惠政策：你可以在同一个商店打包购买两个物品，你只需要支付这两个物品价格的

你需要在合适的商店购买每个物品，使得总花费最小

题解

Flamire 做法

Sol

首先注意到两个物品 ，如果满足 ，那么一定不会出现 在 A 商店购买， 在 B 商店购买的情况

因此我们以横坐标为 A，纵坐标为 B，那么一定存在一条左下到右上的折线，使得折线右下方均在 B 商店购买，左上方均在 A 商店购买

那么有了这个我们就可以设出 dp 状态，注意到我们可以通过若干个“极左上”的 B 的位置定义这条折线

我们从右上到左下转移，令 表示第 个物品是这样的一个拐点，并且在这之前我们选的 A 物品和 B 物品数量的奇偶性

从 转移到 时，我们会新确定这两个区域的点的商店，这个看起来不是很好做

考虑从上到下扫描线，可以发现 A 区域的部分和高度无关，而 B 区域的部分和 无关，因此我们使用线段树：

• 在每次加入一个新的点 时，我们将 的物品的 B 区域值更新，这个可以打 tag
• 在询问一个新点 会被更新的 dp 值时，我们对 的所有物品区间询问，询问 pushup 的时候维护出 A 区域的点带来的影响

总复杂度

另一个做法

Sol

考虑建两张数轴分别表示 ，这样每个物品就是两个数轴之间的一条边

初始我们所有物品都选择 ，接下来我们要做的就是将一些物品换大，使得我们可以通过优惠减小总代价

那么注意到我们一定不会交换两条交叉的线，因此我们最后交换的物品一定如右图

那么我们就在被交换的物品之间 dp，令 表示第 个物品被交换了，且前面一共交换了奇数/偶数对

从 转移到 时，我们需要满足 ，转移时只要统计上更小的一端在 内或 内的物品即可，这个可以通过前缀和拆开，直接用树状数组维护

复杂度

---

9. QOJ1876 - MIPT: Connecting People [K] ✔️

题面

有一个柱状图，第 列高度为 ，其中高度为 的格子记为

每一列内部 和 之间有一条边权为 的无向边

现在你需要额外添加 条边使得这张图连通，你可以添加如下的边：

• 对于两列 ，以及一个高度 ，如果 ，那么你可以在 之间建一条边权为 的无向边，其中 为给定常数

你需要最小化柱状图任意两个格子 之间的距离和，即 ，距离定义为两点间最短距离长度

题解

Sol

这是一棵生成树，因此统计两两距离和我们可以拆到边上，贡献两边 乘积次

考虑如果我们拿出最高的列作为我们分析的根，此时一个好的性质就是生成树不会有一条边跨过该列，也就是两边被分成了独立的问题

而进一步地，我们可以发现每个左右每个子树都占据了一个区间内的列：

因此我们就可以产生一个初步的想法： 表示区间 的列组成了一个子树，并且这个子树和外界相连的点在 ，注意到此时还是不会有跨过 的边，因为 要么向左连出区间，要么向右连出区间

但是直接转移也只能做到比较高的复杂度，需要进一步优化。

注意到我们没必要在列上考虑子树关系，我们可以把状态设到内部的点上

具体地，我们考虑转移 的时候暴力拆解出向上和向下的子树，设如下三个状态：

• ，表示区间 的列组成了一个子树，这个子树和外界相连的点在
• ，表示我们只考虑 的列内在 及之下的部分的子树，包含了 区间的列
• ，表示我们只考虑 的列内在 及以上的部分的子树，包含了 区间的列，注意到这个状态只用存一个区间的列，并且满足 不在 内，这是因为在根向上的部分，其一定向左或者向右一边能出子树，因此能出子树的这一边一定不会在 的状态里

具体如图：

写一个记搜，使用分步转移可以做到单次转移 ，总复杂度 ，其中 ，但是常数很小

---

10. TOIP2024 - 棲息地分配 [E] ⭐

题面

给定一张 个点 条边的无向图，要求将点集划分为三个非空集合 ，使得只保留端点不属于同一个集合的边后图无环

给出构造或判断无解

题解

Flamire 做法

Sol

考虑一些极端情况：我们限制 ，设其中两个点分别为

讨论两种情况：

• 有连边，此时限制相当于 不能有共同的邻点
• 没有连边，此时限制相当于 最多只有一个共同的邻点

而无解的必要条件即为对于任意一对 ，上述条件均不满足

找出度数最小的节点 ，对 的度数分类讨论：

• ：取 和任意一个没有连边的点，显然有解
• ：取 和任意一个没有连边的点，显然有解
• ：与 相连的两个点之间必须有一条连边，因此这三个点就使用了三条边，而不与 相连的点至少要有两个点和 的出边集合重复，因此边数至少为 ，不合法
• ：与 相连的三个点之间必须有两条连边，因此这四个点就使用了五条边，而不与 相连的点至少要有两个点和 的出边集合重复，因此边数至少为 ，不合法
• ：边数 ，不合法

因此根据上面的分析，至少存在一个点 使得 是合法的节点对

由于 的度数是 ，因此 check 一对 即可，总复杂度

题解做法

Sol

图不联通显然有解。

图联通，拉出任意一棵生成树，我们合理划分集合，使得最后所有集合之间的边都是树边，如果这个可以达成那么显然合法

只要把非树边连接的端点 merge 起来即可，最多 条非树边，因此至少剩下三个连通块，每个连通块对应一个集合即可

---

11. QOJ9357 - Aho-Parasick [E] ✔️

题面

给定两棵 个点的无根树 ，请构造一个字符串集合 满足如下条件：

• 对 建 AC 自动机，得到 trie 树 ，fail 树 ，存在一个点集上的映射 ，使得 中有边 当且仅当 中有边 ， 中有边 当且仅当 中有边
• 中所有字符串长度之和

数据保证有解，你可以使用的字符集足够大。

题解

Sol

这个看起来性质就不是很好，所以我们最后大概率是要缩小一下解的空间，然后直接 check。

考虑对于一个固定的根我们是否能判断合法，可以发现这是可行的，我们只要用并查集合并一下必须相等的字符，这个可以用倍增上并查集实现，建出等价关系后，我们一定是希望等价关系不同的数尽可能不同才好，因为我们希望避免出现一些额外相等的后缀

合并出等价关系之后再建出 trie 树判一下 fail 是否真的相等即可，一次 check 复杂度 ，其中

接下来考虑如何缩减需要判的根的数量，注意到根的儿子的 fail 一定指向根，这个非常优美。

找出 中所有重叠的边，建出一张新图，这些边最后的结构一定是一些以根为中心的链组成的类菊花：

• 如果存在一个度数 的点 ，那么可以发现 必须是根，否则 的儿子必定会有相同字符，因此只要判一个点即可

• 否则，这张图一定是一条链，这条链上的字符一定形如 aaaaaaabbbbbb，以根为分界：

  • 如果 trie 直接是这条链，直接取端点作为根即可，容易构造

  • 否则，找到任意一条从重叠链通过 trie 边连出的点 ，这个点代表的串最后一定形如 aaaaaax 的形式，因此一定存在一个这样的点最后的 fail 指回链上，找到一个这样的点 ，设其连回链上的点为 ，可以发现 其他连出的 fail 边一定不在链上，这条边是唯一的

    找到这样的一条边之后， 代表的串要么是空串，要么单个字符是 x，因此我们只要判两个点即可

因此最后我们只需要判断 个点是否能作为根，复杂度

---

12. QOJ6111 - Two Paths [E]

题面

给定一棵 个点的树，边有边权

次询问，每次给定两个点 ，以及两个权值 ，你需要选择两条点不交的路径 ，满足 的起点为 ， 的起点为 ，求 的最小值，其中 代表 的边权和

题解

Sol

直接硬维护不太干净，考虑进行一些分析。

相当于我们要在 的路径上断掉一条边，然后 分别取所在连通块内的最远点

当断掉的边是确定的时候，我们直接合并直径维护即可

我们选出任意一条带权直径 ，讨论 和直径的情况：

• 路径不经过直径：此时可以发现至少有 和 中的一个路径走到了直径上去找最远点，这个可以简单地调整说明
• 路径经过直径：
  • 如果断掉的边不在直径上，设 没有和直径连通，那么 一定走到直径上取找最远点，也可以容易发现这是不劣的
  • 如果断掉的边在直径上，我们特殊处理

因此我们现在所有要处理的情况都可以转化为 和 都在直径上的情况，进一步地：

• 如果 不经过直径带权中点，设 更靠近直径中点，那么不难发现 一定跨过直径中点找最远点

因此最后我们需要处理的情况就只有 和 分别在直径中点两侧，这可以拆成两个询问端点在直径中点的问题，最后我们就把所有询问转化成了以询问端点为直径中点，并且是一条链的问题

此时问题就好做了，我们只要在这条链上 dfs，可以发现以每条边断开的贡献就可以表示成一个一次函数的形式，而随着我们越来越向下，有一个维度是有单调性的，因此我们的凸包可以用单调栈维护，每次询问就是在凸包上面二分

因此总复杂度为

---

13. NOI2025 - 数字树 [K]

题面

给定一棵 个点的树，点 为根， 的节点均有恰好两个儿子， 为叶子

初始叶子上都没有数字，接下来有 次操作，第 次操作会在选择两个仍没有数字的叶子在上面写上

每次操作后，你需要对 种 dfs 序，计数其中有多少满足，将叶子上存在的数字按照访问顺序连起来得到的序列 ，可以通过每次删除相邻相等元素删空，答案对 取模

保证每次至少存在一个合法的 dfs 序

题解

Sol

可以观察到答案是 的次幂，并且在至少存在一个合法的 dfs 序的情况下，我们不妨假设一开始取了一个合法的 dfs 序

那么所有可能的操作就是翻转一个子树管理的区间，将其在最终 dfs 序中 reverse

注意到我们 reverse 一个子树实际上影响的是子树中所有出现奇数次的数，因为偶数次一定会在内部先合并完，上面翻转并没有影响

手模一下，可以猜测同一类的子树必须翻转偶数次，事实上这也是正确的（排除掉子树内只有 种数出现奇数次的情况）

因此第 次操作后若有 个等价类，那么答案为 ，因为初始自由度为 ，而在 个等价类中，有 个是包含 种元素

那么此时问题就变为了如何维护。

我们将每个子树看成一个长为 的 01 串，每次询问的就是前 位有多少种不同的串

这个问题看起来很熟悉，我们可以直接将所有串按照字典序之后求相邻两个串的 lcp，因此我们能够询问串的哈希值即可，而这可以用线段树合并达成

搭配上线段树二分求 lcp，最后的复杂度是

存在做到单 log 的做法，将线段树长度开到 的整数次幂，然后自底向上进行类似倍增后缀排序的事情

---

14. NOI2025 - 绝对防御 [K]

题面

有 张牌，每张牌是 0 或 1 中的一种，牌的种类已经给定，初始你会取走前 张牌作为你的手牌

你会进行如下游戏：

• 每一回合开始，取走最靠前的两张还未取走的牌，加入你的手牌中，如果不足两张则全部取走
• 你需要选择手牌中一张 0 和一张 1 打出，获得发动技能，发动技能后需要选择两张 0 打出

技能隔三个回合才能发动一次，即如果 回合发动技能，那么 回合开始才可以再次发动技能

到牌堆被取空的回合为止，如果你都合法地进行了出牌，那么你获得胜利

次询问，每次单点修改牌堆中一张牌的类型（0 变为 1 或 1 变为 0），求最小的 使得你在一开始取走前 张牌的情况下能获得胜利

题解

Sol

赛后听说这题是差分约束，于是自己搓了一个。

后来发现还是写麻烦了，所以搬运一下 wmh 老师的题解。

令 ，即技能的冷却时间。

假设固定 ，考虑如何 check：

为了方便，设我们的下标依然是 ，并且不同点即为初始手牌有 张 0， 张 1，设 表示 共发动了多少次技能

设 表示 回合抽的 0 数， 表示 回合抽的 1 数

那么我们可以列出需要满足的几个条件即为：

• 不能发动负数次技能：

• 每一时刻 0 的数量足够：

• 每一时刻 1 的数量足够：
• 技能冷却：

按照差分约束的方式连边之后，我们只需要判断这张图上是否存在负环

可以发现，负环的形式相当局限，只需要要求如下事情：

• 从 走一条边到 ，然后再走链回 ：
• 从 走链到 ，然后再走一条边回 ：
• 从 走一条边到 ，然后再走链从 到 ，最后再走一条边回 ：
• 从 走一条边到 ，然后再走链从 到 ，最后再走一条边回 ：

此时容易做到 check。

并且这个做法也很容易扩展，可以发现同奇偶的 只是进行一些下标偏移，那么我们下面考虑上这个影响，再进行一些简单变形：

• 注意到当 时，，下面两个可以简化为：

此时二分一个 ，不难用线段树维护式子的值。

事实上，套上一个线段树二分即可做到单 log，复杂度

---

15. UNR9 - 欢迎来到最前线 [E] ⭐

题面

给定两个长为 的非负整数数列

你需要选出 个 对进行匹配，匹配 的代价为

请对每个 求出最小代价和

题解

Sol

画到数轴上，为了思考起来方便我们假设没有相等的数，这和原问题是等难的，因为我们可以加减 eps

考虑匹配在数轴上的形态，可以发现如果有一对匹配 ，那么 内的所有点必须参与匹配，否则一定可以调整将解变小

因此最后匹配的形态形如数轴上有一些连续区间，每段区间内的 数量相等并且内部匹配上了

注意到内部匹配上了可以变成括号匹配一样的形式，此时设 表示数轴上 的部分 的值，任意最优解就可以被我们调成只有 相等的两个位置之间的匹配

因此我们只需要对每一层，设其有 个数，做只有 和 可以匹配，匹配 对的最小代价和，最后闵和起来即可，而这个是可以反悔贪心解决的

复杂度

---

16. CF2084H - Turtle and Nediam 2 [E]

题面

给定一个长为 的 01 串 ，你可以不断进行如下操作：

• 设当前长度为 ，选择一个 ，设 为 的中位数，删除 的最小的

求能得到多少种本质不同的串，对 取模

题解

Sol

按连续段考虑这个串，设当前一共有 个连续段，第 段长度为 ，我们可以发现一次操作为以下两种之一：

• 如果 ，那么可以将 减
• 如果 ，那么可以将 删除， 和 （如果存在）合并

进一步地，如果存在四个相邻的段 ，那么我们可以经过若干次操作将其变成 ，或者变成

再注意到最后一段永远不会消失，也不会变得比原来更长

接下来考虑判断一个串 能不能被操作出，我们取出其连续段序列 ：

• 一个大致想法是我们依次匹配每一个段，假设当前匹配到了 ，并且在匹配的是 ，且这两个段是同字符的

  此时如果 ，那么我们一定是用 去匹配 ，因为下一次匹配之前的偶数个段都可以被删掉，直接令 和 都加一即可

  否则我们需要延长当前段，或者转而使用后面的某个段，对于一个 ，如果我们使用它去匹配 ，那么需要吞掉 之前的所有段给 延长，找到这个的最小值即可

• 特殊处理结尾：结尾必须是最后一段 ，并且长度不会变长，这意味着我们要匹配最后一段的时候需要跳过前面的所有东西

• 特殊处理开头：

  • 如果开头字符相等，可以发现我们必须使用 去匹配 ，因为此时如果匹配 的话，不存在一个前面的段帮我们把 吞掉，最后的结果就是我们为了将前面干掉必定会将 消成 ，这就不如一开始匹配 ，因此 的时候我们一定使用 匹配
  • 如果开头字符不等，手模可以发现我们要匹配 必须将前 段删成长度为 的，才能把字符不相等的干掉

那么开始列出 dp，令 表示匹配到了 ，并且当前匹配的 至少为 ，我们希望这个状态的有效值满足 ，这样我们的状态数依然是线性的，转移如下：

• 如果 ：

  下一步可以从 转移过来，或者令当前的 直接 ，然后从 开始匹配下一段，即从 转移

• 如果 ：

  由于我们的状态只到 ，我们需要想办法快速处理上面的所有转移，但是这个找到最小的 会非常难搞

  考虑如下方案：

  我们维护一个指针 ，初始为 ， 开始不断向上枚举 的长度，那么每次 ， 就需要 ，多吃掉两个段来弥补长度，这时候我们如果发现 ，那么我们可以直接用 来接管之后的匹配过程，也就是从 转移过来，前面的就是一个区间和

  因此我们预处理 ， 表示最小的 使得 ，转移的时候先用 算掉前面的贡献，然后从 转移过来

  注意 时我们必须一直使用前面的贡献，即使 存在，因为“特殊处理开头”中开头字符相等的部分指出我们第一段必须用第一段匹配

• 在过程中和 相等的时候我们可以直接跳到匹配最后一段，这个是上面“特殊处理结尾”部分，这个可以通过给每个 加上 达成

最后答案是 ，其中 对应着两串开头相等的情况， 对应着两串开头不等的情况

总复杂度

---

17. CF2124H - Longest Good Subsequence [E] ✔️

题面

定义一个序列 是好的当且仅当：

• 对于任意 ，
• 存在一个 的排列 使得对于任意 ， 是满足 的最小正整数

给定一个长为 的数列 ，求其最长好子序列

题解

Sol

不难发现一个序列是好的当且仅当所有 包含或不交

那么考虑 dp 来算这个事情，任意一个满足条件的序列都可以切成若干段，每一段 都满足 ，然后 是一个子问题

但是这依然不好计算，因为如果我们要区间 dp 的话，需要记录 中的区间 ，以及前面选了多少个 ，这就并不是很好

注意到划分出来的每一个段中，第一个选择的位置一定满足 ，也就是说我们可以通过第一个元素确定当前区间的排名

因此我们可以设出 dp 状态：设 表示当前考虑 ， 必选，且满足 ，这个区间内最多能选出多长的子序列

转移的时候考虑把状态按照上面的方式切段：

• 没有选入子序列中：
• 整个序列只有一段，即 的 覆盖了整个区间：如果 则进行
• 序列有 段，枚举包含 的段的开头在哪里，设其为 ，那么需要满足 且 ，若满足则进行

只有第三种转移复杂度为 ，注意到 ，所以随着 增大， 就越容易满足，且 就越劣，因此我们只需要找到满足条件的第一个

由于 随 递增而递增，这个是容易处理的，只要维护 表示最小的 使得 ，然后再找 后面第一个 即可

总复杂度

---

18. CF1969F - Card Pairing [E]

题面

给定 ，保证 都为偶数

有 张牌，每张牌为 中的一种，你一开始会先取掉前 张牌作为手牌，接下来每个回合你会做如下的事情：

• 选择手牌中任意两张打出，如果它们相等则你的得分
• 如果牌堆非空，则抽取牌堆中接下来的两张牌加入手牌

问将手牌和牌堆都打空的时候最多获得多少分数

题解

Sol

一个非常符合直觉的结论：当手牌中存在相同的时，随便丢掉一对相等的都是最优的

那么可以发现决策不固定的只有手里恰好是 的情况，此时假设丢掉了 ，那么决策会固定一段，然后经过若干回合之后再次回到

因此我们可以设状态 表示 回合后我们手上剩下了 ，在这之间转移

转移的时候依次枚举 ，如果此时恰好有两个数出现了奇数次，那么令 等于这两个数就可以在 下一次取到 （如果之前没有出现过同样的两个数出现奇数次）

这个是容易做到 的，对于 是最后一次 的情况只要计算一下 中有 个在 中出现奇数次的种类数，可以发现每种情况内部是等价的，如果种类数非零那么我们就可以进行对应的转移

总复杂度

---

19. CF2124I - Lexicographic Partition [E]

题面

对于长为 的数列 ，定义 为：

• 将 切分为若干非空段 ，生成一个新序列 为每个 中的最小值的拼接
• 字典序最大的 的长度即为 的值

现在给定长为 的序列 ，满足 ，请构造一个 的排列 ，使得

给出构造或者判断无解

题解

Sol

考虑如何求一个序列的 值：我们维护一个指针 从 开始，直到 走到 位置，每次如果 ， 那么从 走到 ，否则找到最小的 满足 （不存在则为 ），走到 中的最大值位置，这样走出来的序列就是字典序最大的

可以发现 ，且 ，，否则必定无解

我们的路径每一步从值的大小来看一定是上升或者下降，其中下降无论后面加什么都不会改变，而上升若后面还没有小于它的数，还是可能改变的

而我们在末尾加一个数，要么是直接加入到路径后面，要么是原来路径上某一个位置 ，后面没有 的数，它之前连向一个 的数，现在后面的最大值为 ，因此转而连向 ，这会让路径长度减去一个非负的值，即弹掉最后的一段后缀

因此我们是可以通过 得出所有时刻的路径是什么的。

而如果发生了第二种事件，我们就要求它的前驱下一步必须要走上升，因此我们这样扫一遍可以得到每个元素是否下一部必须走上升，任意时刻如果有连续两个走上升的就爆掉了

否则我们一定可以构造出来解，直接默认剩下的都是下降，然后将新数用链表插入到对应位置即可

复杂度

---

20. APIO2025 - Hack! [K] ⭐

题面

交互题。

交互库有一个 内的整数 ，每次你可以向交互库询问一个值域在 内的非空正整数集合 ，交互库会返回有多少对 满足

你需要在询问的 的情况下求出 是什么

题解

Sol

设 中可以填任意整数，这没有什么影响

显然我们只要求出一个 的倍数就好了，试除带来的代价很小，可以忽略不计

乍一看好像无从下手，但是我们仔细思考一下：如果我们想体现出一段区间内的所有 ，直接线性地建塞数显然是不可行的

经过灵机一动，我们可以想到使用根号。具体地，设我们要表示出 内的所有元素，我们取 ，在集合里放 ，这样差就会覆盖 内的所有数，并且集合大小大约是 的

但是这时有一个问题：我们还额外包含了两边各自内部产生的差

仔细分析一下可以发现直接二分的话是不会产生问题的：

• 对于形如 的区间，我们包含的恰好是
• 对于不为 的区间，一定有 ，而我们额外包含的区间长度一定 ，因此只要我们二分的时候优先走左边就不会产生问题

此时的代价大概为 ，大概在 左右，还是无法通过

注意到我们只需要找到任意一个 的倍数，而至少有一个倍数在 之内，因此我们只用在这个范围内二分

重新分析一下二分的正确性：

• 对于一个长为 的区间，我们额外包含的差一定都 ，而只要 ，这段区间内就必然有一个 的倍数，所以我们直接走进去也无妨

因此我们现在的代价就变为了 ，大概在 左右，可以通过

实际使用次数在 附近。

---

21. APIO2025 - Permutation Game [K]

题面

给定一张 个点 条边的连通图 ，以及一个 的排列

你在和交互库玩游戏，每次你选择 个不同下标填到 的每个点上，然后交互库会选择一条 中的边，若两端你填入的下标为 ，则交换 和

你可以随时停止操作，你希望最大化 的数量，交互库希望最小化 的数量

你需要：

• 计算出双方都以最优策略操作的情况下最后有多少 ，称这个值为
• 和交互库玩一局游戏，不保证交互库策略最优，但是你需要让最后 的数量

你需要满足你玩游戏的时候，使用的操作数不超过

部分分：

部分分：

部分分：

部分分：

题解

Sol

排列可以表示为多干个环。

注意到如果 中有三度点，那么无论我们怎么选，一定有一条边交换了不会增加 的数量，因此当有三度点的时候交互库总是可以让 的数量不增

此时直接结束游戏即可。

因此现在需要考虑的情况就只剩下了链和环的情况

链的情况

可以发现当非自环的边数不超过 的时候，我们必定无法让链的每条边都增加 的数量，因此如果初始的答案 直接返回即可，否则答案有一个上界是

这个上界也确实是可以达到的

我们用链将一些环串在一起，这样会强制交互库产生一个自环，或者将两个环拼在一起

而对于一个 的环，我们可以将链绕在这个环上，这样可以强制交互库从这个环上拆出去一个自环

结合这两种操作容易构造到

环的情况

首先考虑一些简单的情况：

环长为 3

经过手模我们可以发现似乎只有一个偶环的时候我们无法从中创造一个自环

事实上这是正确的：我们可以证明交互库可以让奇环的数量不增：

• 如果这三个点不属于同一个环，交互库只要合并两个环，奇环的数量一定不增
• 如果这三个点属于同一个奇环，任意交换一条边必定会将这个奇环拆成一个奇环和一个偶环，奇环数量不变
• 如果这三个点属于同一个偶环，由于 是奇数，因此一定存在一条边会将这个偶环拆成两个偶环，奇环数量不变

因此答案有一个上界即为奇环数量，事实上这也是可以取到的：

• 对于一个长为 的环，我们显然可以从中造出一个自环
• 对于一个长 的奇环，我们只要操作三个相邻的点，交互库要么使环长 ，要么造出一个自环

环长为 4

经过手模可以发现大部分情况下上界为 ，特殊情况为初始即 的情况，这种情况是容易处理的，因此我们只考虑 如何构造

观察到对于一个 的环，如果我们从 开始顺序编号，那么我们操作 一定可以强制交互库拆出一个自环或一个 环，而 环经过一次操作可以产生一个自环

因此我们按照如下方式操作：

• 如果存在一个 环，就操作这个 环产生一个自环
• 如果存在 环，就操作这个环产生一个自环或 环
• 否则就随便将环拼在一起

可以发现，这样操作到最后只会剩若干个大小和为 的环，也即达到上界

此时我们考虑直接做原题，而环长为 和环长为 答案的区别启示我们这和 的奇偶性有一定关系

环长为奇数

奇环不会增加的结论依然成立。

但同时，对于过小的奇环我们同样无法操作。

具体地，如果最大的奇环加上所有偶环的大小 ，那么我们无法在不减少奇环数量的前提下进行任何有意义的操作

这种情况下我们需要献祭掉最大的一部分奇环，将它们合并到一起，直到最大的奇环加上所有偶环的大小 ，此时我们就可以对当前最大的奇环进行操作

而注意到此时操作之后所有偶环的大小和为 ，因此后面环长一定满足条件

因此我们可以提前计算出要献祭掉多少奇环，这就是我们的最终答案

得知答案之后构造是容易的（奇环均指未被献祭掉的奇环）：

• 若存在奇环大小 则直接操作

• 当最大奇环大小不足 时，我们往上拼偶环

• 否则最大奇环大小 ，采用 ，该环每步差为 或 ，交互库必定会拆出一个自环或让环长

分析一下操作步数：我们的过程可以看成，先把最大的奇环拼到 ，然后不断 ，直到环长 的时候我们会操作这个环将它变成 ，此后每次我们只要将这个 拼到下一个奇环上必定会使奇环长度 ，如此往复

每个奇环会贡献 次操作，分别为拼上 ，不断 ，然后拆出自环

一开始我们还需要花不超过环数的代价造出第一个 的奇环

由于奇环大小至少为 ，所以算出来可以发现显然是不超过 的

环长为偶数

答案依然是 。

此时我们不断给一个环 会得到 或 ，而 无法直接操作得到自环，因此这不是很好

的环没有什么救了，我们可以尝试直接从一个 的环得到

若环长为 ，则我们的边长度为 都是合法的

因此可以认为我们在 的数轴上，每步可以 ，要求一条走出长为 的不经过重复点的回路

这个之前我做麻烦了，所以我阅读了一下 qoj 上 bachbeo2007 的提交记录，他使用了如下的构造：

将 按照 个一段进行分段，先走红线出发，走到一段的开头时直接跳 ，然后继续每步 ，这样重复走 步

然后走绿线返回，一开始先跳一步 ，然后每次走到一段的第二个的时候跳 ，其余时候均跳

调整一下长度容易做到访问 步，而中间我们浪费的距离显然不超过 ，因此总共用到的值域也不会超过

现在我们具备了从任意 上拆下来一个 环的能力，一个简单的策略就是将所有环合并到一起，再每次拆一个 环，然后拆自环，再合并起来

但非常不幸的是，这样会使用 次操作，具体地，一开始合并会产生 次操作（因为每个环最小为 ），然后每次拆出一个自环会用 次操作，后面总共会用 次操作

我们需要把这个降到 以内，那么我们尽可能希望的就是每次合并之后都会出现一个 的数，这样我们就能再用 次操作拆出一个自环

而为此我们可以有 步额外操作，具体方案需要手玩手玩，我最后采用的方案是：

• 首先合并一些环造出来一个 的，把它操作掉，得到至少一个 的环，这部分最多 次操作
• 然后开始用这个 的环去合并其它的环，对于任意 ，我们都可以在三次操作内拆出一个自环将它变为
• 我们在剩下的环中再合并再造出来一个 （如果造不出来那么直接乱合即可），此时对于任意一个环 ，我们只需要用两个 不断操作，把其中一个从 变成 ，然后用 和 合并即可，我们又会得到一个新的
• 最后将其它所有环操作完之后，将这两个环操作掉

再改一下这个方案，让它对于交互库的其它策略也合理即可

---

22. CF2129F - Top-K Tracker [K]

题面

交互题。

交互库有一个 的排列 ，定义 ，即 中每个数出现的位置

你需要通过询问猜出 ，你可以进行如下四种操作：

• 操作 1：给定 个不同的下标 ，交互库会返回 中的前 大的值
• 操作 2：给定 个不同的数 ，交互库会返回 中的前 大的值
• 操作 3：给定 个不同的下标 ，交互库会返回 中的前 大的值
• 操作 4：给定 个不同的数 ，交互库会返回 中的前 大的值

设四种询问使用的次数分别为 ，你需要保证 ，且

F1：

F2：

题解

Sol

对于 F1，我们只使用操作 1 和 3，并且一操作只使用 ，三操作只使用

我们一共有 次操作，我们只要对每个下标 都分配一个长为 的二进制数，表示其在每个询问内是否被询问到，然后保证所有下标的二进制数均不同，就能确定整个排列

这些二进制数中最多一共有 个 1，我们可以使用出现 1 最少的若干二进制串 ，其中 ，是足够的

因此我们只要构造一种合法的赋值二进制数的方案即可

这是容易做到的。

对于 F2，我们需要进一步利用操作的性质，我们现在开始使用大于对应长度的操作

不妨假设我们仍然先使用 次大小为 的操作，然后用 的操作做一些事情

用类似的配对方式，我们依然给 个数赋值二进制数，但现在 个 1 不支持我们区分出所有数

因此我们分为 个出现两次的二进制数，以及 个出现一次的二进制数，此时总 1 个数是

现在我们最后一次操作需要解决的就是，我们有 组条件形如：，而我们需要用一次 的操作确定每一对

注意到 之间的配对我们是可以控制的，每一对 就是我们一开始分配标号的时候分到相同标号的两个数

那么我们将 分为一组，此时好处是所有大的数大于所有小的数

这时，我们每组 ，随机从 中选择一个数 ，然后将所有 个数放在一起做四操作，会得到其中前 大，如果一组 ，有一个数在结果中出现，那么显然 对应的是这个下标，否则我们认为 对应的是 中较小的

由于大数都大于小数，所以我们这样做会出问题当且仅当 个数中随机选出了超过 个大的数，这个概率是很低的，因此问题得到了解决

---

23. UNR9 - 滑冰 [K] ✔️

题面

给定一个 的包含 #. 的字符矩阵，其中 # 为障碍，. 为空地

你初始从一个空地出发，每一步可以选定上下左右中的一个方向，你会一直移动直到撞到边界或者障碍

你需要求从哪些空地出发能存在一条路径经过所有空地（在移动中滑过也算，不需要停下）

组数据。

题解

Sol

下文 均指矩阵面积。我们从高复杂度开始逐渐优化做法。

做法

我们首先将格子之间的可达关系建图连边，然后缩点，我们需要走一条缩点 dag 上的路径

在这张图上，如果一个格子四个方向都不紧贴障碍，那么它就是一个入度为 0 的单点 scc，这没有什么意义，所以我们删除这样的点

此时一个格子被经过的条件是：要么它竖着走的 scc 被经过，要么它横着走的 scc 被经过

并且从一个格子起点出发就是：要么从它竖着走的 scc 出发，要么从它横着走的 scc 出发

此时我们就可以把它描述成一个 2-sat 模型了，用布尔变量表示一个点有没有被经过：

• 每个格子都必须被经过：横着的 scc 和竖着的 scc 至少要访问一个
• 走过的应该是一条路径：保证被选上的任意两个 scc ，要么 能到达 ，要么 能到达 ，这样限制出来一定存在一条路径经过所有选中的 scc
• 限制起点是某个 scc：将这个 scc 设为必选，将逆拓扑序大于这个 scc 的点全设为不能选

此时对每个 scc 作为起点跑一遍 2-sat，点数为 ，边数为 ，因此总复杂度为

可以通过手段实现到 ，但我写了一下发现跑的没 快，可能是我的问题。

及 做法

进一步观察性质。

考虑 scc 之间的连边是怎么产生的：

必然是通过这样至少一边是紧贴障碍的红色格子产生的，而这个红色格子又必须被经过，因此我们可以得到一个关键的结论：任意一条有向边的两个端点必须至少经过一个

有了这个结论，可以发现有解的图会受到非常强的约束。具体来说，我们拎出一条最长的合法解路径，称路径上的点依次为 ：

可以发现：

• 由于 是合法路径，所以不存在形如红色的，两个端点均不在 上的边
• 由于 是最长的合法路径，所以不存在 ，或者 ，或者 的点

可以发现，这条合法路径的长度一定等于原图中最长路径长度

那么我们求出从原图中每个点出发的最长路长度 ，并且随意拉出一条最长路径

此时 还不一定是合法路径，但是其为我们提供了一些便利：

• 上任意两个相邻的点至少要选一个
• 我们按照 为节点分层，那么对于每个 ，这样的点必须选恰好一个
• 如果我们选了一个不在 内的点 ，那么 和 层的 必选， 为了让选出的点集是一条路径，我们需要要求 的边均存在

可以发现保证这些条件后我们求出来的解就一定满足条件，一三条件是容易用 的边保证的，二条件我们在 2-sat 限制下做到至多选一个，不过这不影响，可以用前后缀建图优化到 条边

而加入判断端点可以完成的，注意到 的边至少要经过一个端点，所以可能的起点 scc 一定是 ，或者指向 所有点

对每个起点做一下即可做到

注意到判断 时比较特殊，需要 ban 掉所有指向 的点，再强制 必选，而判断指向 的点唯一的变化只是强制对应点必选

因此我们可以先花 的时间判一下 ，然后再建出原图， 判一下是否已经不合法，如果还合法，那么接下来每个指向 的点 只需要满足 2-sat 图中 不能到 ，这个可以用 bitset 维护连通性解决，复杂度

做法

称连向 的点的集合为

我们唯一需要优化的部分是每个 能不能到

观察一下 2-sat 图的结构：这些 唯一向外可能的连边是连到其它 的

也就是说 能不能到 可以等价于其它 能不能到 ，即我们要判断 内所有的 ，有哪些不能被其它任意一个 到达

这个可以直接在缩点 dag 上递推得到，容易做到线性

因此我们在 的复杂度内解决了本题。

---

24. IOI2025 - Souvenirs [E] ⭐

题面

交互题。

有 个物品，价格依次为 ，满足

你只知道 的值，你可以通过如下方式购买物品：

• 你指定一个钱数 ，如果 或者 你就会原地爆炸
• 否则，会依次考虑 ：
  • 如果 ，那么你会获得一件 的物品，并且 会减少
  • 否则不做任何变化
• 最后你会得到你购买的所有物品，以及你剩余的钱数

你有足够多的钱，请合理操作使得最后你没有原地爆炸，并且恰好买了 件 的物品，你能使用不超过 次购买

题解

Sol

注意到 的限制很有提示性，因为我们是不知道 的，每一步都必须保证不会爆炸

那么我们一开始先询问一次 ，显然一定会购买 ，接下来分两种情况讨论：

• 如果只购买了 ，那么我们可以直接通过剩下的钱数求出 的值，此时 就转化为了形式类似的问题

• 如果购买了 件物品，那么设一共用了 的钱，这其中最小的物品必定小于等于 ，那么我们以 作为界就可以将其转化为更小规模的问题

  求出 的所有物品之后，我们可以再结算一遍购买的所有物品，把已知的物品都结算进剩余钱数，然后再重复这个过程

可以发现，我们每个区间 我们会恰好询问一次，所以求出所有 之前，第 个物品购买的次数不会超过

最后再重复买一个物品把次数补齐即可

---

25. IOI2025 - World Map [E]

题面

给定一张 个点 条边的无向图 ，请构造一个 的矩阵（ 可自选），每个元素都为 内的整数，使得：

• 各至少出现一次
• 对于任意一个四联通的方格对，上面的数组要么相同，要么在 中有连边
• 对于任意一条 中的边 ，至少存在一组四联通方格对，使得两个数字分别为

你需要保证 以获得满分，数据保证有解

， 组数据

题解

Sol

显然图需要连通。

一种 的构造方案是：

通过一列纯色 、一列所有 的邻点（中间用 分割），然后再一列 ，可以处理掉 的所有邻边

然后我们用 步在 中任意一个生成树上走并回溯，经过每个点都做一次上面的过程，这样是

注意到一个数只有第一次出现需要三列，之后出现都只需要一列，这样列数降到

斜过来放在对角线上，一个颜色用三条对角线，此时我们就不需要用 分割了，但是可用的长度有可能不足 了

仔细思考一下，可以发现我们只需要每个节点的可用长度偏序 即可，而在限制下，任意选 个连续三列，中间那列的长度的数组一定偏序

而 时对角线有 条，刚好够

咋克优化

考虑优化一下处理边的方式：假设 之间有边，我们可以用这样的方式处理掉与 相连的各种点

    1f12
   1e12
  1112
 11d2
12c2
2b2
a2

其中 代表只与 相连的点， 代表同时与 相连的点， 代表只与 相连的点

我们需要的斜线长度恰好是需要处理的点数，而这种构造中每个点额外用了一条斜线，只要我们能够合理地匹配每个点，最后得到的矩阵应该满足

找出原图的一棵 dfs 树，先按照 dfs 序遍历，得到一个长为 的序列，接下来我们在这个序列上额外添加一些匹配处理邻边

匹配的方式是：dfs 时，如果当前点 还没有匹配，那么就把它和它最后的一个儿子匹配 ，并且这对匹配处理所有 连向祖先的边

注意到此时会剩下一些叶子没有匹配，因此我们额外要求每一对匹配 ，处理 向其子树内未匹配叶子的连边

现在我们需要给每个匹配分配在什么时候处理它们的邻边，使得斜线长度都够用

可以说明，我们在遍历完 子树，最后一次访问 时处理 的匹配，是长度足够的，为了说明这件事情，称 需要处理的点集为 ，我们只需要说明其前后各有 条其它斜线，即可说明这条斜线长度 ：

• 前面是容易说明的，处理这对匹配时，前面必定 dfs 到过 的所有祖先，以及 子树内的所有叶子
• 后面只出现过 的所有祖先，但是由于我们叶子空余了一些叶子没有匹配上，所以我们实际上使用的斜线不超过 ，因此相当于叶子数量个空斜线放在最后，这样后面的斜线个数也是足够的

因此我们在 内解决了问题

---

26. IOI2025 - Triple Peaks [E]

题面

给定一个长为 的数组 ，定义 为满足 ，且可重集 的三元组数量

第一问：给定 ，求 ，

第二问：给定 ，要求构造一个 的数列 ，满足 ，且

数据点：

题解

Sol

第一问：

分类讨论情况：

• 最大值为 ，那么 已经确定， check
• 最大值为 ，同理
• 最大值为 ，且 ，依然 check
• 最大值为 ，且 ，这种情况需要处理

可以通过简单的加加减减可以发现有 ，

那么我们枚举 ，然后找到 的桶，和 的桶，选更小的那一边枚举，进行 check

可以证明，这样的复杂度是 的：

• 对于 的桶，称其大小从小到大为 ， 的桶大小从小到大为 ，显然有
• 我们会从中选择 个不相同的对 ，然后贡献
• 对于 ，其和所有 配对贡献不超过 ，而这样的 个数不超过 ，因此这部分复杂度不超过
• 对于 ，其配对一次复杂度不超过 ，最多匹配 次，因此这部分复杂度不超过

因此我们在 的时间复杂度内解决了这个问题

比较需要注意力的做法：

在 和 之间连边， 为最大值等价于三元环，三元环计数即可

第二问：

显然我们要造的是最后一种情况，因为只有这种情况可能出现 级别的对数

注意到这种情况实际上是经过 的斜率为 的直线与经过 的斜率为 的直线交点在 上，且经过 的斜率为 的直线与经过 的斜率为 的直线交于

因此我们可以考虑选定若干个 的点，然后将所有经过 的斜率为 的直线交一下得到的所有的交点，把这些交点选成 的点，这样看起来合法的对数就比较多

我们需要让交点尽可能横坐标都不同，直接随机即可获得 ~90pts。

再加一点乱搞调整可以获得 100pts。

哦，好像直接每次去新交点最多的就可以在 的时候造到 了，直接爆杀

---

27. IOI2025 - Festival [E]

题面

有 个物品，第 个物品价格为 ，并且有一个系数 ，每种物品最多被购买一次

你如果当前有 块钱，你购买一个物品 需要满足 ，买完之后你的钱数会变为

你初始有 块钱，你需要以合理地顺序购买物品，使得你购买的物品数量尽可能多

题解

Sol

不管怎么样先 exchange argument 一下。

考虑 与 的大小关系，推一下式子可以发现当 时 放在前面更优

而注意到如果过程中任意时刻我们的钱数 ，按这个式子算出来最后钱数一定也 ，所以我们只要判断最后钱数 即可

那么我们取物品的顺序一定是按照 从大到小，即 从小到大

的物品显然都在最后，所以我们先把它扔掉，最后再考虑

考虑一下什么时候我们取物品会赚钱，即 ，推一下可以发现条件是 ，也就是说我们直接按顺序操作 就是最可能赚的方式

那么我们先把赚钱的都操作掉，接下来不管我们怎么操作钱数都不会再增加了，任意操作都至少会让我们的钱数

进一步地，可以发现我们操作不了多少轮就破产了。

具体地，对于一个物品 ，如果我们以 的钱数购买它，钱数最多为 ，而下一个物品时这个 会被乘上下一个物品的 ，因此下一次钱数最多为 ，接下来操作钱数最多为 ，只需要 轮就必定破产了

因此直接在原序上 dp，记 表示考虑完前 个物品，购买了 个物品，最多剩下的钱数，状态 ，转移

最后再枚举每个状态二分一下统计 的贡献即可

复杂度

---

28. IOI2025 - Obstacles for a Llama [E] ✔️

题面

给定一个长为 的数组 和一个长为 的数组

定义一个 的矩形，矩形上 的格子 是空白的，其余格子上有障碍

次询问，每次给定 ，以及 ，保证 和 都是空白的，求 和 是否属于同一个四连通块

部分分：对于所有询问

题解

Flamire 做法

比较麻烦。

考虑一个过程：维护两个区间 分别表示行区间和列区间，不断执行如下操作：

• 找到 中的最小列，用这个最小值去扩展 ，让 向两边扩展直到扩展不了为止
• 找到 中的最大行，用这个最大值去扩展 ，让 向两边扩展直到扩展不了为止

最后操作不动的时候，如果 和 得到的区间相同，则它们连通，证明不会，正确性也不清楚，反正在数据上是对的。

考虑维护这个过程，注意到所有起点的行为 ，所以我们其实可以只关心 是什么， 即为取 中最小值能走到极大区间

因此对于 的部分， 是大根笛卡尔树上区间，所以状态是 的，可以随便求

而对于有 限制的部分，我们首先倍增向上跳，直到区间某部分出了 ，不妨假设出的一边是

那么接下来我们 的区间都一直是 ，其中 会不断向左跳

这就等价于，我们要找到长度最小的 使得其不能向左扩展，在这里停下

注意到对于一个 ，随着 的增大它一定越来越不容易停下，因此我们可以用一个 从左向右扫的过程，时刻维护一个栈表示当前 会停下的所有区间，可以发现每次一定是这个栈的最后几个元素会停不下来，依次检查把它们弹出即可

这形成了一棵树，每次我们要找的就是 对应那条链上第一个长度大于当前长度的停点，继续倍增即可

复杂度

le0n 做法

考虑割是什么样的。

经过一些手模可以发现，如果我们提前在两端分别加入全是障碍的列，任意 到 的割都可以被替换成若干个 U 型割，即 的割

证明不会。

那么我们只用考虑 U 型割就能判断两个格子是否连通，求出所有 U 型割之后这个可以使用 xor-hash 实现

而两列 之间的 U 型割有效当且仅当 ，否则我们一定 中的另一列分开，将其分为两个 U 型割，这是等效的

有效的区间只有 个，直接 check 即可，check 的时候我们先求出两列的前缀障碍长度，然后在这个长度内找一个 最小的看是否能把这中间全割掉，这是容易做的

那么我们就解决了 的问题

而当有区间的限制的时候，相当于多加了两列障碍，因此原来不连通的现在还是不连通，而我们需要额外考虑的就是 J 型割和 L 型割，即中间某一列拐一下拐到边界上

这种也是比较容易处理的，我们提前预处理出来每一列的前缀障碍段，这上面向左向右延伸的最长长度

查询的时候只要查询 和 之间有没有列向左延伸到 或向右延伸到

复杂度

---

29. IOI2025 - Migrations [K]

题面

通信题。

有一棵 个点的树，节点为 ，其中 为根，且每个点 都满足 ，你需要实现两个人的策略：

• 考古队：

  依次考虑 ，考古队会收到 ，然后考古队需要结合之前收到的 ，决策是否要发送信息，其中信息是一个正整数

• 博物馆：

  博物馆会得到每一时刻，考古队发送的信息（或者没有发送信息），博物馆需要根据这些信息返回任意一条原树上的直径的两个端点的编号

设你发送的信息整数最大值为 ，发送信息的次数为

可以获得各种分数不等， 可以获得满分

题解

Sol

做法

考虑直接使用最后 位。

我们最后需要发送两个值为 的信息 ，那么考虑使用最后若干位来传递这个信息

但是在传递信息的过程中， 或 可能被当前点 替换掉

我们每次发送一个 bit 的信息，发送信息 ，而如果我们发现有一个 被替换了就返回 ，表示 被替换了

如果没有被替换，那么我们就只需要 个 bit 来传递完所有信息

而如果中途有一个位置被替换了，不妨设替换的是 ，那么我们剩下只用传另一个数就好了，用 传 是否被替换和一个信息位，如果替换了 则传

在传 之后，我们每次传 表示新的 替换了

这样我们最多会损失一位信息，总共需要 位

做法

改进一下上面的做法。

注意到一开始我们使用二进制发 ，而在此之外作为标识的也只有两个，也就是说我们还剩了一个数，因此我们其实可以改成三进制

但这样还是不够优，考虑将用作标识的数也削减到一个，这样我们就有四个数可以传信息

具体地，我们用 ，每次传递 各一位，然后 表示当前 更新了 或

那么接到 之后，我们需要再想办法确定是 中哪个被更新了，因此我们再用一位

上一位改 ，这一位改 ，这样一共有 种状态，但是注意到如果上一位改 这一位改 和上一位改 这一位改 是一样的，所以可以缩减到 种状态，刚好能用一次表示

在这之后，用二进制继续传即可，其余部分和上面类似

这样总共需要 位

做法

注意到我们可以用一个位表示前四位是否进行了对 的修改，如果修改了那么是哪一位

考虑四个位一块 ，其中 用五进制传 ， 用五进制传 ， 表示这一块的 以及上一块的 对 的修改， 表示这一块的 对 的修改

但是这样有一个问题，就是 对 的修改没法记录。

因此我们还需要最后开一位用于特判。

，而注意到 第一次有值之后 一定不需要了，所以 最多有 个位置有值， 同理，因此总共需要 位

做法

我们需要尽可能最小化非零的位置数量，因此考虑优化一下我们的信息表示：我们把连续 个位划成一块，这个块内我们只使用一个非零的位置，那么一共可以传递 的信息

那么我们用这个信息同时限定 ，具体地，设 的可能集合为 ，那么我们设一个权值 ，将 和 分别切成 块，我们只要 的信息就可以确定 分别在哪个块内，就将 的大小除以 上取整

具体地，对于一个块 ，我们进行如下操作：

• 令 ，那么我们可以用这个块传递一个 的信息
• 选定 ，将 分别分成 个块，然后返回块二元组的编号
• 对应地缩减 ，然后将 同时加入

但是这个效果还是不够，我们可以加一点小优化：

• 第一个块我们可以让 ，所以这样我们只用考虑 个块的二元组
• 每个块处理的时候我们可以先将 加入 ，然后再做处理，最后将 加入

加了这些改进之后，跑一个 dp 算出最优的分块方式，可以发现我们可以用前 位让

接下来我们手玩一下后 位的决策方式。

在 时，可以认为此时我们所有可能的解是一个左部右部分别 个点的满二分图，并且再加上新的 向前面的所有 个点有连边，每条边就对应着一种 组合的方案

现在我们要给每条边分配一个 中的颜色，然后 时得到的就是与正确的边同色的所有边

为了让我们的讨论简单一点，我们希望拆出来的图都是同构的，这样我们就只用讨论一种情况

这个是很松的限制，我们限制图形如 ，然后随便写一个搜索就能搜出来一种划分方式

后面的类似，但是划分更加 ，最后经过 之后我们就只剩下一条边了，因此是可以确定的

---

30. 图灵杯 2025 - 棋无常树 [K]

题面

给定一个 个节点的有根树，每个节点有属性 ，该属性为 内的整数， 表示该点属性还未确定

额外有限制 ，其中 表示 的子树的 值的 mex 为 ，特别地，若 则表示无限制

现在给定一些点的 值，求有多少将 值补全的方式，使得其满足所有 的限制

题解

Sol

在一个子树内定义“确定出现的数”，即为 到子树内最大 减 的所有数，以及子树内已经出现过的所有

可以发现，我们设状态记录子树内，除了确定出现的数之外还出现了多少种数，这个是几乎可以转移的。

问题在对于 子树内（不含 ）的 ，有些点能填 ，而有些点不能填

因此我们最后的状态是： 表示 的子树中，除了确定出现的数之外还有 种数，在这 种数之外， 是否出现了

转移 的时候我们依次进行如下操作，称 的子树（不含 ）最大 值为 ：

• 枚举每个儿子 ：
  • 处理一下值为 ，将 的 维转变为记录 是否存在
  • 然后依次枚举每个值 ，如果其在 中必然出现，但在 中不必然出现，那么对于 做一遍转移，转移其中是否包含
  • 最后将 合并到 上
• 合并完所有儿子 之后：
  • 若 则直接删除所有出现过 的状态
  • 否则依次枚举 的每一个还未被标记为必然出现的数，进行一次转移，让它必然出现

注意到过程中只有将 合并到 上是 的，剩下的都可以通过一些手段分析到

而这相当于我们需要解决如下问题：

• 给定一个长为 的数组 以及一个长为 的数组 ，枚举每个 ，以及一个 ，将 贡献到 ，要求在 时间内求出

这个即为两个集合合并，去除重复元素的转移

事实上，这也是可以做到的，我们从小到大枚举 ，每次进行一次 上的转移，转移 是否有 的第 个元素，然后枚举完 后，用当前这个做过 次转移的 和 直接卷积，贡献到该卷的位置上去，这样即可做到

讨论一大堆细节，即可在 的时间复杂度内解决本题。

---