isaunoya's blog

Sep 12, 2026

IOI 2026 中国国家集训队作业泛做

PDF

题目来自 IOI 2026 中国国家集训队作业（试题泛做）。

1. Cells Blocking

题意 给定部分格子已经阻塞的 𝑛×𝑚 网格，再选择两个不同的空格阻塞，求使得从 (1,1) 到 (𝑛,𝑚) 不存在仅向右或向下经过空格的路径的方案数。允许选择起点或终点；初始时也可能已经无路可走。

数据范围 1≤𝑛,𝑚≤3000；网格字符为 . 和 *，分别表示空格与阻塞格。

Solution

2. Giant Penguin [done]

题意 给定连通简单无向图，每个顶点至多属于 𝑘 个简单环。初始没有标记，依次支持标记一个尚未标记的顶点，以及查询给定顶点到最近已标记顶点的最短距离。

数据范围 1≤𝑛≤105，𝑛−1≤𝑚≤2×105，0≤𝑘≤10，1≤𝑞≤2×105；查询距离时保证已有标记点。

Solution

将点分治推广为每次删除至多 𝑘+1 个点。对于当前连通子图，任取生成树 𝑇 及其重心 𝑐。连接 𝑇−𝑐 不同分量的每条边都与树上路径组成一个经过 𝑐 的简单环，且这些环互不相同，因此这样的边至多有 𝑘 条。

将 𝑐 和每条跨分量边的任意一个端点加入 𝑆，则 |𝑆|≤𝑘+1。删除 𝑆 后，每个连通分量都包含于 𝑇−𝑐 的某个分量中，大小至多减半，故递归深度为 𝑂(log𝑛)。

对每个分治结点的𝑠∈𝑆，在当前子图中 BFS，预处理距离𝑑𝑠(𝑣)。维护𝑏𝑠，表示𝑠到当前子图中最近标记点的距离，初始为∞。

标记𝑥时，沿分治祖先用𝑑𝑠(𝑥)更新𝑏𝑠；查询𝑣时，沿分治祖先取

min𝑠(𝑑𝑠(𝑣)+𝑏𝑠).

候选值不会小于真实距离。取从 𝑣 到最近标记点的最短路，在分治过程中第一次与它相交的分隔集中，必有一个 𝑠 取到等号。

预处理时间为 𝑂((𝑘+1)(𝑛+𝑚)log𝑛)，空间为 𝑂((𝑘+1)𝑛log𝑛+𝑚)，单次操作时间为 𝑂((𝑘+1)log𝑛)。

实现 QOJ 提交 2959409。

3. Edit Distance Yet Again

题意 给定两个小写字母串 𝑠,𝑡 和整数 𝑘，判断其编辑距离是否不超过 𝑘。允许插入、删除或替换一个字符，每次代价为 1。若满足条件，还需输出最少操作次数及任意一组最优操作序列。

数据范围 1≤𝑧≤100，1≤𝑛,𝑚≤106，0≤𝑘≤1000；所有测试用例中两个字符串的长度总和不超过 107。

Solution

4. Cactus

题意 给定一个连通简单无向图，且每个顶点至多属于一个简单环。用 𝑘 种颜色给顶点染色，要求每条边的两端颜色不同，求方案数模 109+7。

数据范围 1≤𝑧≤50000，1≤𝑛≤3×105，0≤𝑚≤4×105，2≤𝑘≤109；所有测试用例的 𝑛 之和不超过 3×106，𝑚 之和不超过 4×106。

Solution

5. Social Distancing

题意 树上有 𝑘 名学生，初始位置与目标计算机位置各构成一个独立集。一次只能让一名学生沿一条边移动，且每步后学生不能同点或相邻。判断能否使所有学生占据目标位置；若能，输出不超过 4𝑛2 次的移动方案，学生与目标的对应关系可任选。

数据范围 1≤𝑧≤105，2≤𝑛≤2000，1≤𝑘<𝑛；所有测试用例的 𝑛2 之和不超过 4×107。保证初始与目标位置集合不同。

Solution

6. Social Justice

题意 给定 𝑛 人的工资与 𝐾=𝑝𝑞>1。选择人数尽可能多的非空集合，使其中每人的工资都不超过该集合平均工资的 𝐾 倍。输出在所有最大人数的合法集合中都不可能被保留的人的数量及升序编号。

数据范围 1≤𝑧≤1000，1≤𝑛≤2×105，0≤𝑎𝑖≤109，1≤𝑞<𝑝≤1000；所有测试用例的 𝑛 之和不超过 106。

Solution

7. Final Exam

题意 给 𝑛 门考试分配非负实数复习时间 𝑥𝑖，总时间不超过 𝑀。第 𝑖 门的得分为 𝑓𝑖(𝑥𝑖)=max(0,min(𝑑𝑖,𝑎𝑖𝑥𝑖2+𝑏𝑖𝑥𝑖+𝑐𝑖))，求最大总分。时间不必全部用完。

数据范围 1≤𝑛≤105，0<𝑀≤108，|𝑎𝑖|≤10，|𝑏𝑖|≤5000，0≤𝑐𝑖≤𝑑𝑖≤5000；至多 18 个 𝑎𝑖>0。所有输入实数精确至小数点后三位；答案误差要求 |𝑣−𝑣∗|max(𝑣∗,1)≤10−6。

Solution

8. Travel around China

题意 给定 3×𝑚 网格，每格有正点权，可以在上下左右相邻格之间移动。路径费用为所有经过格子的点权之和，包含两端，重复经过需重复计费。求所有起终点不同的有序格子对之间的最小路径费用之和，模 109+7。

数据范围 𝑛=3，1≤𝑚≤150000，1≤𝑎𝑖,𝑗≤109。

Solution

9. Thanks to MikeMirzayanov

题意 给定一个排列。一次操作把整个排列切成 𝑘≥2 个非空连续段，将这些段的顺序反转，每段内部的顺序不变。输出不超过 120 次操作，使排列升序排列；每次输出分段数及各段长度。

数据范围 1≤𝑛≤20000；输入是 1 到 𝑛 的排列。保证存在满足操作次数上限的方案，无须最少操作。

Solution

10. Excluded Min

题意 对非负整数多重集，可以选一个至少出现两次的数 𝑥，把其中一次改成 𝑥+1 或非负的 𝑥−1。给定数组与若干区间询问，分别求对该区间的多重集任意操作后能得到的最大 mex；mex 为未出现的最小非负整数。

数据范围 1≤𝑛,𝑞≤5×105，0≤𝑎𝑖≤5×105，1≤𝑙𝑖≤𝑟𝑖≤𝑛。

Solution

11. Best Subsequence [done]

题意 每次询问给定 𝐿,𝑅,𝐾，从 𝐴𝐿,…,𝐴𝑅 中选取长度恰为 𝐾 的子序列 𝐶，将其首尾也视为相邻。求所有环形相邻两数之和的最大值的最小可能值。

数据范围 1≤𝑛,𝑄≤105，0≤𝐴𝑖≤109，1≤𝐿≤𝑅≤𝑛，1≤𝐾≤𝑅−𝐿+1；当 𝐾=1 时该元素与自身相邻。

Solution

参考 #114。二分答案𝑥，统计满足2𝑎𝑖≤𝑥的 small 数量，以及相邻 small 之间能补入 big 的间隙数。

将数组首尾相连，按𝑎𝑖递增插入位置，用有序集合维护循环前驱、后继。位置𝑖在𝑥=2𝑎𝑖时成为 small，给自身加一。若插入前集合非空，设相邻位置为𝑢,𝑣，则𝑖是间隙内的最小值，能作为 big 补入的条件为

𝑎𝑖+max(𝑎𝑢,𝑎𝑣)≤𝑥<2𝑎𝑖.

将这段贡献挂在右端点𝑣上，在两个阈值处分别加一、减一，空区间忽略。所有事件按阈值排序，用可持久化线段树维护位置权值，处理完同一阈值后保存版本。

询问[𝑙,𝑟)时，取阈值不超过𝑥的最后一个版本，用 ST 表和二分找到首末 small 𝑝,𝑞；不存在则不可行。先查询[𝑝+1,𝑟)的权值和再加一：排除𝑝前可能跨出左边界的间隙，只补回𝑝自身。再取[𝑙,𝑝)和[𝑞+1,𝑟)的最小值𝑚，若𝑚+max(𝑎𝑝,𝑎𝑞)≤𝑥，则再加一，补上询问首尾的间隙。空区间最小值取+∞，最终判断总数是否不少于𝑘。

事件共𝑂(𝑛)个，每次判定用时𝑂(log𝑛)。设值域上界为𝑉，总时间复杂度为𝑂(𝑛log𝑛+𝑄log𝑉log𝑛)，空间复杂度为𝑂(𝑛log𝑛)。

实现 QOJ 提交 2960713。

12. Binary Search Tree

题意 初始有 𝑛 棵空的二叉搜索树。支持向编号在 [𝑙,𝑟] 的每棵树中插入值 𝑤，以及查询在第 𝑥 棵树中查找值 𝑎 的代价。插入采用普通 BST 规则，不进行平衡；查找从根出发，按大小关系走向左右孩子，找到目标或走到空孩子时结束，代价为访问的所有非空节点的值之和。

数据范围 1≤𝑛,𝑚≤2×105，1≤𝑤,𝑎≤109；所有插入操作中的 𝑤 全局互不相同，查询值不保证存在。

Solution

13. Game

题意 机器人初始等概率位于数组的任意位置，每轮你知道其位置 𝑖，可以停止并获得 𝐴𝑖，或让它等概率移动到 𝑖−1 与 𝑖+1；位于端点时只能停止。求最优策略下的期望得分，以有理数模 998244353 的形式输出。

数据范围 1≤𝑛≤5×105，1≤𝐴𝑖≤1012；保证答案分母与模数互质。

Solution

14. Local Maxima

题意 将 1 到 𝑛×𝑚 各一次填入 𝑛×𝑚 矩阵。若某格的数不小于其所在行、列的所有数，则称其为局部最大值。求恰好只有一个局部最大值的矩阵数量，模给定素数 𝑃。

数据范围 1≤𝑛,𝑚≤3000，108≤𝑃≤109+7，保证 𝑃 为素数。

Solution

15. 100 Boxes Per Hour…

题意 交互题。每轮依次收到 100 个、共三种颜色的盒子，只知道三种颜色数量的无序集合。只有两个容量不限的箱子，每个非空箱子中只能放同色盒子。看到当前盒子后，可以清空任意箱子，再选择把盒子放入合法箱子或丢弃。要求每轮结束时两箱合计保留至少 43 个盒子；每轮开始两箱均为空。

数据范围 正式测试固定 𝑇=100 轮；0≤𝐴,𝐵,𝐶≤100，𝐴+𝐵+𝐶=100，但不知道数量与颜色的对应关系。盒子顺序预先固定，交互器非自适应；样例为缩小规模，不代表正式限制。

Solution

16. Designing a PCB

题意 在横轴上依次有 2𝑛 个点，第 𝑖 个坐标为 (𝑖−1,0)，每种标签恰出现两次。为每对同标签点构造由水平或竖直线段组成的折线，要求折线不自交、不自接触，且不同折线无公共点；不可行则报告无解。输出每条折线从左端点出发的方向和长度序列。

数据范围 1≤𝑛≤1000；标签为 1 到 𝑛，各出现两次。每条折线使用 1 到 10 条正整数长度线段，所有折点坐标的绝对值不超过 104。

Solution

17. Knowledge Is…

题意 有 𝑁 个项目和 𝑀 名学生，完成项目 𝑖 必须占用整个闭区间 [𝐿𝑖,𝑅𝑖]。每名学生最多完成两个项目，且同一学生负责的项目时间不能相交，端点重合也不允许。尽可能多地完成项目，并输出每个项目分配给哪名学生，未完成的项目标为 0。

数据范围 1≤𝑀≤𝑁≤3×105，1≤𝐿𝑖<𝑅𝑖≤109。

Solution

18. Lights On The Road

题意 一条路分为连续的 𝑁 段，在第 𝑖 段安装路灯需花费 𝑊𝑖。选择若干路段安装路灯，使每段自身或至少一个相邻路段装有灯。将所有合法选择方案按总费用非递减排序，输出前 𝐾 个方案的费用；不同方案即使费用相同也分别计数，不足 𝐾 个的位置输出 −1。

数据范围 1≤𝑁,𝐾≤250000，0≤𝑊𝑖≤109。

Solution

19. Koosaga’s Problem

题意 给定简单连通无向图，统计删去至多两条边后使图变为二分图，且删除边数在所有可行方案中最少的方案数。可以不删边；若至少需要删除三条边，则答案为 0。

数据范围 3≤𝑁≤250000，𝑁−1≤𝑀≤250000；图连通，无自环和重边。

Solution

20. Rhythm Game

题意 按顺序经过 𝑁 个音符，最多选择击中 𝐾 个。若击中第 𝑖 个音符后，当前连续击中的长度为 𝑗，得到 𝐴𝑖×𝐶𝑗 分；漏掉音符会中断连击，每段非空连击结束时额外得到 𝑃 分，歌曲结束也会结算最后一段连击。求最大总分。

数据范围 1≤𝑁,𝐾≤2000，−109≤𝑃≤109，0≤𝐴𝑖≤105，−105≤𝐶𝑗≤105，且 𝐶𝑗≥𝐶𝑗+1。

Solution

21. Stone Catch Game

题意 棋盘为 [0,109]×[0,109]，白石初始在原点，另有 𝑁 颗黑石，允许重合。Yuto 先手，双方轮流行动：Yuto 将白石向右或向上移动一格；Platina 选择一颗黑石向左或向下移动一格。白石逃出棋盘则 Yuto 获胜；在此之前白石与任一黑石重合，则 Platina 获胜，包括初始已经重合的情况。求双方最优策略下的胜者。

数据范围 1≤𝑁≤3×105，0≤𝑥𝑖,𝑦𝑖≤109。

Solution

22. Setting Maps

题意 给定有向图、起点 𝑆 和终点 𝐸。可以在任意顶点安装一张地图，包括起终点，每点最多一张，费用为 𝐶𝑣。要求所有从 𝑆 到 𝐸 的路径都经过至少 𝐾 个装有地图的顶点。求费用最小的安装方案并输出这些顶点，或报告无解。

数据范围 2≤𝑁≤200，1≤𝑀≤500，1≤𝐾≤5，1≤𝐶𝑖≤107；𝑆≠𝐸，图无自环和重边。

Solution

23. How to Move the Beans

题意 给定 𝐻×𝑊 的圆柱形网格，最左列与最右列相邻。部分格子有盘子，部分盘子初始有一颗豆子。Alice 先手，双方轮流选择任意一颗豆子，将它向左、向右或向下移动一格，目标格必须有盘子，且该颗豆子此前没有到过该格，包括初始位置。豆子彼此可区分，允许多颗豆子共处一个盘子。无法移动任何豆子的一方输，求最优策略下的胜者。

数据范围 1≤𝐻,𝑊≤1000；每格为无盘子、空盘子或有一颗豆子的盘子，允许初始没有豆子。

Solution

24. Interesting Coloring

题意 给定没有桥的简单连通无向图。用编号 1 到 𝑀 的颜色给边染色，使有公共端点的边颜色不同，并且对于每条边 (𝑢,𝑣)，都存在一条不使用这条边的 𝑢 到 𝑣 路径，其使用的颜色不超过 8 种。输出一种染色，并为每条边输出至多 8 种颜色，保证仅用这些颜色的边就能组成该边的替代路径；颜色集合不必最小。

数据范围 3≤𝑁≤5555，3≤𝑀≤min(𝑁(𝑁−1)2,9999)；图无自环、重边或桥且连通，保证有解。

Solution

25. Joy with Permutations

题意 交互题，需要唯一确定一个隐藏的 1 到 𝑁 的排列。第一类询问选择三个不同位置，得到这三个位置所对应数值的中位数；第二类询问选择两个不同位置，得到其中数值较小者的位置编号。交互器可以自适应地修改排列，只需与先前所有回答一致，因此必须在排列被唯一确定后再提交答案。

数据范围 4≤𝑁≤60000；第一类询问最多 2𝑁 次，第二类询问最多 2 次。

Solution

26. Lazy Judge

题意 交互题，由程序回答评测器关于某个 1 到 𝑁 的排列的询问。三类询问分别要求：三个不同位置对应数值的中位数、两个不同位置中数值较小者的下标、两个不同位置对应数值的最小值。回答时可以改变排列，但须与此前回答一致。评测器初始耐心为 2𝑁，前两类询问每次消耗 2，第三类每次消耗 1。收到结束指令后，设剩余耐心为 𝑝，须构造两个都符合全部回答的排列，并使它们至少在 ⌈𝑝2⌉ 个位置上不同。

数据范围 4≤𝑁≤50000；三类询问次数为 𝑞1,𝑞2,𝑞3，保证 𝑝=2𝑁−2𝑞1−2𝑞2−𝑞3≥3，即每次询问后剩余耐心均大于 2。保证存在满足要求的策略。

此处按 AtCoder 日文原题取 𝑝>2；QOJ 中文题面将该条件误译为 𝑝≥2。

Solution

27. AND Permutation

题意 给定由互异非负整数构成的序列 𝑎，保证将其中任意一个数的二进制表示中的若干个 1 改为 0 后，得到的数仍在序列中。重新排列这些数得到 𝑏，使每个位置的 𝑎𝑖 与 𝑏𝑖 按位与均为 0，输出任意合法排列。

数据范围 1≤𝑛<218，0≤𝑎𝑖<260；各数互异，满足上述封闭性，保证有解。

Solution

28. Permutation CFG

题意 给定 1 到 𝑛 的排列。定义替换规则：数字 𝑘 替换为该排列中所有不超过 𝑘 的数，保持它们在排列中的相对顺序。从只含 𝑛 的序列开始，每轮同时替换所有元素，共进行 𝑠 轮。回答 𝑞 个询问，每次给出 𝑘,𝑎，求最终序列的前 𝑎 项中数字 𝑘 出现的次数。

数据范围 2≤𝑛≤105，1≤𝑠≤5，1≤𝑞≤2×105，1≤𝑘≤𝑛，1≤𝑎≤109；保证 𝑎 不超过最终序列长度。

Solution

29. Special Cycle

题意 给定简单无向图，其中 𝑘 条边被标为特殊边。寻找一个简单环，使每条特殊边要么本身在环上，要么两个端点都不在环上。输出任意合法环的顶点顺序，或报告无解。

数据范围 2≤𝑛≤150，1≤𝑚≤𝑛(𝑛−1)2，1≤𝑘≤𝑚；无自环和重边，输入的前 𝑘 条边为特殊边。

Solution

30. The King’s Guards

题意 给定村庄间的无向道路，每条道路有修缮费用；另有 𝑔 名守卫，每人只能部署在各自允许的村庄集合中。选择要修缮的道路并部署全部守卫，使每个村庄通过已修缮道路恰好能到达一名守卫，也就是每个连通分量恰有一名守卫。求最小总修缮费用，或报告无解。

数据范围 1≤𝑛≤300，0≤𝑟≤𝑛(𝑛−1)2，1≤𝑔≤𝑛，1≤𝑐≤1000；每对村庄至多一条道路。每名守卫的允许集合大小在 [1,𝑛] 内，不同守卫的允许集合可以重叠。

Solution

31. Joke

题意

给定排列 𝑝 及部分已知的排列 𝑞，二者长度均为 𝑛。用 1 到 2𝑛 各一次填入一个 2×𝑛 矩阵，要求第一行元素的大小关系与 𝑝 相同，第二行与 𝑞 相同。每列按上方元素是否小于下方元素产生一个二进制位，小于时为 0，否则为 1。设 𝑓(𝑝,𝑞) 为能够得到的不同二进制串数量，求所有合法补全 𝑞 的 𝑓(𝑝,𝑞) 之和，对 998244353 取模。

数据范围

  • 1≤𝑛≤100；𝑝 是 1 到 𝑛 的排列。
  • 0≤𝑞𝑖≤𝑛，0 表示未知，所有非零的 𝑞𝑖 互不相同。

Solution

32. K-onstruction

题意

给定 𝐾，构造长度为 𝑁 的整数数组 𝐴，使下标集合 {1,2,…,𝑁} 恰有 𝐾 个子集的对应元素之和为 0。空集计入其中，数组允许重复元素。要求 1≤𝑁≤30 且所有元素均在指定范围内；保证存在解，输出任意一个合法数组。

数据范围

  • 测试组数 1≤𝑡≤1000，每组 1≤𝐾≤106。
  • 输出满足 1≤𝑁≤30、−1016≤𝐴𝑖≤1016。

Solution

33. Cactus

题意

给定一张连通无向仙人掌图，即每条边至多属于一个简单环。可以任意次选择当前度数为奇数的顶点，删除其所有邻接边；还可以至多一次复制整张当前图，并将每个原顶点与其副本连边。两类操作可按任意顺序进行。求最终边数的最小值，并输出达到该值的操作序列。

数据范围

  • 1≤𝑛≤3×105，𝑛−1≤𝑚≤3𝑛−12。
  • 输入无重边、无自环，顶点编号为 1 到 𝑛。
  • 复制后副本顶点编号为 𝑛+1 到 2𝑛，复制操作至多一次。

Solution

34. Hamiltonian Path

题意

有向图的顶点为 0 到 𝑛−1。对每个顶点 𝑖，若 𝑖+𝑝<𝑛 则连边 𝑖→𝑖+𝑝，若 𝑖−𝑞≥0 则连边 𝑖→𝑖−𝑞。构造一条恰好访问每个顶点一次的有向哈密顿路径，输出顶点顺序；不存在时输出 −1。

数据范围

  • 测试组数 1≤𝑇≤104。
  • 1≤𝑝,𝑞≤𝑛≤106，所有测试组的 𝑛 之和不超过 106。

Solution

35. Goldberg Machine 2

题意

两台机器各有一个 𝑛×𝑚 网格，含箭头的格子位置相同。箭头向右或向下；从左上角投入一个标记后，它沿箭头移动，每离开一个箭头格子就将该箭头翻转，直到到达空格或走出网格。每次修改永久翻转指定机器的一个箭头。在初始状态及每次修改后，求向两台机器分别投入若干标记，使最终所有箭头配置相同所需的最少标记总数；无法达到时输出 −1。回答中的投入操作仅用于询问，不改变后续修改的基准状态。

数据范围

  • 1≤𝑛,𝑚≤100，1≤𝑞≤105，共输出 𝑞+1 个答案。
  • 两个网格形状相同，左上角均有箭头；每个箭头格子均能在连续投入足够多标记后被访问。
  • 每次修改的位置保证有箭头；答案以十进制输出，不取模且不得有前导零。

Solution

36. Nein

题意

给定 𝑘 和 𝑛，将满足 𝑥×(10𝑘−1) 的十进制表示中不出现数字 9 的正整数 𝑥 从小到大排列，输出其中第 𝑛 个数。

数据范围

  • 1≤𝑘≤18，1≤𝑛≤1018。

Solution

37. MIPT: Connecting People

题意

一排 𝑛 栋楼，第 𝑖 栋有 ℎ𝑖 层，每层一名居民，楼内每上下移动一层耗时 𝑡𝑣,𝑖。可以在两栋楼的相同楼层 𝑥 之间修建水平走廊，但两楼之间所有楼的高度必须小于 𝑥；通过任意走廊均耗时 𝑡ℎ。恰好建造 𝑛−1 条走廊，使所有楼层互相可达，并最小化所有无序居民对之间的最短通行时间之和。输出最小值。

数据范围

  • 1≤𝑛≤60，1≤ℎ𝑖≤3000，总楼层数 𝑅=∑𝑖ℎ𝑖≤3000。
  • 1≤𝑡ℎ,𝑡𝑣,𝑖≤106。

Solution

38. Mission Impossible: Grand Theft Auto

题意

给定一棵树，小偷初始位于未知顶点。每天选择两个端点，检查两点间简单路径上的所有顶点；若未抓到，小偷随后可以走到相邻顶点或留在原地。设树有 𝑚 个叶子，构造恰好 ⌈𝑚2⌉+1 天的检查路径，使任意初始位置和移动方式的小偷都必定被抓到。若更少天已足够，可在末尾补任意路径；保证有解。

数据范围

  • 测试组数 1≤𝑇≤100。
  • 2≤𝑛≤2×105，所有测试组的 𝑛 之和不超过 2×105。
  • 每天的两个端点可以相同；此题输出完整计划，不进行交互。

Solution

39. Edit

题意

给定两棵边带权的有序有根树，每个顶点的子节点次序固定。允许以下操作，将第一棵树变成第二棵树，求最小总代价：

  • 在任意子节点位置插入新叶子，或用一个新子节点包住原有的连续一段子节点；新增边权为 𝑤 时，代价为 𝑐1𝑤，其余边权不变。
  • 收缩一条边，将被删除子节点的子节点列表按原顺序接回父节点；被收缩边权为 𝑤 时，代价为 𝑐2𝑤。
  • 将边权从 𝑤1 改为 𝑤2，代价为 𝑐3|𝑤1−𝑤2|。

新增的边不能再修改权值，修改过权值的边不能收缩。两棵树相同要求根、子节点顺序和对应边权均一致，顶点编号可以不同。

数据范围

  • 第一棵树至多 50 个顶点，第二棵树至多 2000 个顶点。
  • 1≤𝑐1,𝑐2,𝑐3≤106。
  • 输入按“子节点编号、边权”给出；原英文题面该处标注 0≤𝑐𝑖≤106，但使用了子节点符号 𝑐𝑖，边权范围的符号疑似笔误。

Solution

40. Hamilton Path

题意

给定有向图，统计顶点排列 𝑝，要求对任意 𝑖<𝑗，存在边 𝑝𝑖→𝑝𝑗 当且仅当 𝑗=𝑖+1；反向边不受此条件限制。输出合法排列数，对 109+7 取模。若实际合法排列数在 1 到 𝑛 之间，还要按排列的字典序依次输出其值 ∑𝑖=1𝑛𝑝𝑖×10𝑛−𝑖mod(109+7)；没有解或数量超过 𝑛 时不输出这一行。

数据范围

  • 测试组数 𝑇≤105，每组 𝑛≥1、𝑚≥0。
  • 所有测试组满足 ∑𝑛≤5×105、∑𝑚≤106。
  • 顶点编号为 1 到 𝑛，允许重边，不允许自环。

Solution

题意

初始有 𝑛 个顶点、没有边。依次加入 𝑚 条有向边，每次加边后，输出互相可达的无序不同顶点对数量，即满足 𝑢<𝑣 且 𝑢 可达 𝑣、𝑣 可达 𝑢 的数对数量。

数据范围

  • 1≤𝑛≤105，1≤𝑚≤250000。
  • 允许重边和自环；每次加入一条边后均需输出答案。

Solution

42. Juggler’s Trick

题意

一排 𝑁 个球，初始为红色、蓝色或未染色。先将每个未染色球染成红色或蓝色，此后每次可以删除一段连续的 𝑟+𝑏 个球，要求其中恰有 𝑟 个红球、𝑏 个蓝球；删除后两侧剩余球保持相对顺序拼接。合理选择染色和删除顺序，求最多能删除多少次。

数据范围

  • 1≤𝑁≤2×105，1≤𝑟,𝑏≤𝑁−1，𝑟+𝑏≤𝑁。
  • 初始字符串长度为 𝑁，字符 R、B、W 分别表示红色、蓝色和未染色。

Solution

43. Lion and Zebra

题意

在树上进行追捕。狮子始终知道斑马的位置，每秒沿一条边追赶；斑马不知道狮子的位置，但始终知道双方距离，每秒可以走到相邻顶点或原地停留。双方在顶点或边上相遇即被捕，相向走过同一条边时会在半秒后相遇。每次询问给定斑马初始顶点 𝑣 和双方初始距离 𝑑，斑马选择使最坏情况下被捕时间尽可能晚的策略，其中最坏情况涵盖所有满足距离的狮子初始位置。输出双方最优行动下的保证生存时间。

数据范围

  • 2≤𝑁≤105，1≤𝑄≤105。
  • 1≤𝑣≤𝑁，1≤𝑑≤𝑁−1，保证存在距 𝑣 为 𝑑 的顶点。
  • 每次询问输出一个整数时间；各轮游戏独立。

Solution

44. AND PLUS OR [done]

题意

给定长度为 2𝑁 的非负整数数组 𝐴，寻找下标 𝑖,𝑗，使 𝐴𝑖+𝐴𝑗<𝐴𝑖∧𝑗+𝐴𝑖∨𝑗，其中 ∧ 和 ∨ 分别表示下标的按位与、按位或。输出任意一组满足条件的下标；不存在时输出 −1。

数据范围

  • 0≤𝑁≤20，0≤𝐴𝑖≤107。
  • 下标从 0 到 2𝑁−1。

Solution

把下标看成其二进制表示中值为 1 的位置组成的集合，定义

𝐷(𝑋,𝑌)=𝐴𝑋∩𝑌+𝐴𝑋∪𝑌−𝐴𝑋−𝐴𝑌.

只要存在 𝐷(𝑋,𝑌)>0 的集合对，就一定存在只相差两个二进制位的解。

若 |𝑋\𝑌|>1，取 𝑋∩𝑌⊊𝑍⊊𝑋，则

𝐷(𝑋,𝑌)=𝐷(𝑍,𝑌)+𝐷(𝑋,𝑍∪𝑌).

展开后 𝐴𝑍 与 𝐴𝑍∪𝑌 抵消即可验证。右侧至少有一项为正，且两项中集合的对称差都更小。对 𝑌\𝑋 同理，因此反复分解可使两个差集都只剩一个元素；具有包含关系时 𝐷(𝑋,𝑌)=0，不会成为正值解。

于是枚举两个二进制位 𝑎<𝑏，以及不含这两位的集合 𝑆，检查

𝐴𝑆∪{𝑎}+𝐴𝑆∪{𝑏}<𝐴𝑆+𝐴𝑆∪{𝑎,𝑏}.

满足时输出 𝑆∪{𝑎} 与 𝑆∪{𝑏}；均不满足则输出 −1。时间复杂度为 𝑂(𝑁22𝑁)，空间复杂度为 𝑂(2𝑁)。

实现 QOJ 提交 2955576。

45. Curly Racetrack

题意

在 𝐻×𝑊 的棋盘上，已有一些方向固定的直角弯道图块。你只能向空格添加直角弯道，之后由管理员填满剩余格子。可用图块有空地、一个外部端口接内部环路、直道、直角弯道、T 形路和十字路六类，均可旋转。合法赛道要求每条外部道路端口均与邻格端口相连，不能出现断头路或伸出棋盘。

部分空格要求你必须放弯道，部分空格禁止你放置图块，但管理员仍会填充。求在仍可补全为合法赛道的前提下，原有及你放置的弯道图块总数最大值；无解输出 −1。

数据范围

  • 1≤𝐻,𝑊≤100。
  • 1、2、3、4 分别表示连接上左、下左、上右、下右的固定弯道，不能移除、替换或旋转。
  • o 为必须放弯道的空格，x 为禁止你放置图块的空格，. 为空格且无额外限制。

Solution

46. Maximal Subsequence

题意

定义序列的美观度为其最长严格上升子序列长度。给定数组 𝑎，选择一个子序列，使其美观度严格小于原数组的美观度，并最大化所选子序列的长度。输出最大长度，允许选择空子序列。

数据范围

  • 1≤𝑛≤5×105，1≤𝑎𝑖≤109。

Solution

47. Lucky Tickets

题意

考虑所有允许前导零、恰有 𝑞 位的 𝑛 进制数，数字依次为 𝑎1,…,𝑎𝑞。当所有数字的乘积与数字之和相加后模 𝑛 等于 𝑠 时，这张票为幸运票。其幸运度定义为

∏𝑖=1𝑞(𝑎𝑖+𝑖)+∑𝑖=1𝑞2𝑖−1𝑎𝑖.

求所有幸运票的幸运度之和，对质数 𝑞 取模。

数据范围

  • 2≤𝑛≤106，0≤𝑠<𝑛。
  • 2≤𝑞≤106，保证 𝑞 为质数；每个数字满足 0≤𝑎𝑖<𝑛。

Solution

48. Soccer Match

题意

给定 𝑁 个人及 𝑀 对双向朋友关系，将部分人分别选入非空的红队和蓝队，其余人作为观众。要求两队的每个人在对方队伍中均至少有 𝐾+1 个朋友。保证 𝑀≥2𝐾𝑁 且存在方案，输出任意合法的两队名单，两队人数可以不同。

数据范围

  • 测试组数 1≤𝑇≤50000。
  • 1≤𝑁,𝑀,𝐾≤50000，𝑀≥2𝐾𝑁；所有测试组的 𝑀 之和不超过 50000。
  • 每对朋友关系只出现一次，无自环。

Solution

49. Gachapon

题意

单次抽卡得到 𝑖 星物品的概率为 𝑎𝑖∑𝑗=0𝑚𝑎𝑗，单次抽卡称为 0 级抽卡；一次 𝑘 级抽卡由 𝑏𝑘 次独立的 𝑘−1 级抽卡组成。一次 𝑛 级抽卡合法，当且仅当对于每个 0≤𝑘≤𝑛，其中包含的每次 𝑘 级抽卡（包括整次 𝑛 级抽卡本身）都至少出现一个星级不低于 𝑘 的物品。设整个抽卡合法的概率为 𝑞，在合法条件下 𝑖 星物品数量的条件期望为 𝑝𝑖，对所有 0≤𝑖≤𝑚 输出 𝑝𝑖𝑞，按有理数模 998244353 表示。

数据范围

  • 1≤𝑛≤𝑚≤4000。
  • 1≤𝑎𝑖≤4000，2≤𝑏𝑘≤4000。
  • 共输出 𝑚+1 个结果。

Solution

50. Build a City

题意

城市初始为原点处的退化矩形，其余 𝑛 个居民点均在第一象限。依次选择尚未获取的居民点，将城市扩张为覆盖旧城市与新点的最小轴对齐矩形。每次新修围墙长度等于新矩形周长减去新旧边界重合部分的长度，已有围墙可原位利用，不能移动；新点已在城内时费用为零。判断能否安排获取顺序，使每次新修围墙的长度均不超过 𝑚。

数据范围

  • 测试组数 1≤𝑇≤5×105，每组 1≤𝑛≤5×105。
  • 所有测试组的 𝑛 之和不超过 5×105。
  • 1≤𝑚≤4×109，1≤𝑥𝑖,𝑦𝑖≤109。

Solution

51. Kilk Not

题意

给定由 0、1、? 组成的字符串，其中恰有 𝑎+𝑏 个问号。必须将其中 𝑎 个替换为 0，其余 𝑏 个替换为 1，使最终字符串中最长连续相同字符段的长度最小。输出最小长度和任意一个达到最小值的完整字符串。

数据范围

  • 测试组数 1≤𝑇≤105。
  • 1≤𝑛≤250000，𝑎,𝑏≥0；所有测试组的 𝑛 之和不超过 250000。
  • 字符串长度为 𝑛，问号数恰为 𝑎+𝑏。

Solution

52. Angle Beats 2.0

题意

给定由 * 和 . 组成的棋盘，为每个 * 放置一个以该格为直角中心的 L 形三格骨牌，另外两个格子必须为与中心边相邻、方向互相垂直的 . 格。所有骨牌不能重叠，. 格可以不覆盖。求合法放置方案数，对 998244353 取模。

数据范围

  • 测试组数 1≤𝑇≤250000，每组 2≤𝑛,𝑚≤100。
  • 所有测试组的棋盘面积之和不超过 106。

Solution

53. Good Coloring

题意

给定无向图及一个使用至多 𝑘 种颜色的合法顶点染色，即每条边两端颜色不同。构造一个使用 𝑥≤𝑘 种颜色的新合法染色，并找出一条恰有 𝑥 个顶点的路径，使路径上的顶点颜色两两不同。输出颜色数、每个顶点的新颜色及这条路径；保证存在解。

数据范围

  • 测试组数 1≤𝑇≤600000。
  • 1≤𝑛≤300000，0≤𝑚≤300000，1≤𝑘≤𝑛。
  • 所有测试组的 𝑛+𝑚 之和不超过 600000。
  • 图无自环、无重边，初始颜色满足 1≤𝑐𝑖≤𝑘。

Solution

54. Balance

题意

给定 𝑁×𝑁 整数矩阵 𝐴，构造同样大小的整数矩阵 𝐵，要求每个位置 𝐵𝑖,𝑗≥𝐴𝑖,𝑗，且每个相邻 2×2 子矩阵两条对角线的元素之和相等，即 𝐵𝑖,𝑗+𝐵𝑖+1,𝑗+1=𝐵𝑖+1,𝑗+𝐵𝑖,𝑗+1。最小化 𝐵 的全部元素之和，输出最小值及任意一个最优矩阵。

数据范围

  • 1≤𝑁≤50，0≤𝐴𝑖,𝑗≤35000。
  • 输出矩阵元素没有 35000 的上界限制。

Solution

55. Gravity

题意

给定由 # 和 . 组成的矩阵，初始每个 # 的极大四连通块为一个不可分割的刚性碎片。所有碎片以相同速度竖直下落，不旋转、不合并、不分裂；每秒所有仍能下落的碎片同时向下一格；若下一次向下移动会越过矩阵底边，或与已停止的碎片重叠，则该碎片停止。输出所有碎片停止后的矩阵。

数据范围

  • 1≤𝑁,𝑀≤2000。
  • 矩阵的 𝑁 行均有 𝑀 个字符，字符集为 # 和 .。

Solution

56. Qnp

题意

每次询问给出十进制数字 0 到 9 的出现次数及 𝐾。将给定的所有数字各按指定次数使用，考虑允许前导零的所有不同排列，将得到的整数从小到大排序。输出其中第 𝐾 小的整数对 109+7 取模的结果。

数据范围

  • 1≤𝑄≤5000，1≤𝐾≤1012。
  • 每次询问的数字总数严格大于 0 且不超过 70000；题面未给出各询问数字总数之和的额外限制。

Solution

57. Taxi

题意

给定一棵边带正权的树，放置 𝑀 辆有编号的出租车和 𝑀 名有编号的乘客，各自可以位于任意顶点，同一顶点可放多个对象。对每种放置方式，将车与乘客一一匹配，最大化所有匹配点对之间的树上距离之和。将全部 𝑁2𝑀 种放置方式对应的最大值相加，输出结果对 109+7 取模的值。

数据范围

  • 1≤𝑁,𝑀≤2500。
  • 每条边的长度为整数 1≤𝑙≤10000。

Solution

题意

给定两两不同的整数序列。称序列单峰，当它严格先升后降或严格先降后升，转折点允许在端点。对每个前缀，求通过交换相邻两个元素，将该前缀变为单峰序列所需的最少交换次数。各次询问均针对原始序列的对应前缀。

数据范围

  • 1≤𝑛≤200000，1≤𝑎𝑖≤109，所有 𝑎𝑖 两两不同。
  • 输出 𝑛 个答案。

Solution

59. Grammy Sorting

题意

给定连通无向图、两个不同的特殊顶点 𝐴,𝐵，以及写在各顶点上的 1 到 𝑛 的一个排列。一次操作选择从 𝐴 出发的简单路径，将路径上的数字向 𝐴 方向循环移动一位，即 (𝑎1,…,𝑎𝑘) 变为 (𝑎2,…,𝑎𝑘,𝑎1)。目标是使每个顶点 𝑥 都位于某条从 𝐴 到 𝐵、数字严格递增的路径上。判断能否实现，并在可行时输出至多 10000 次操作，无须最小化操作数；不可行时输出 −1。

数据范围

  • 2≤𝑛≤1000，1≤𝑚≤2000，𝐴≠𝐵。
  • 图连通，无自环、无重边；初始数字是 1 到 𝑛 的排列。
  • 若目标可实现，保证存在不超过 10000 次操作的方案。

Solution

60. Great Party

题意

两人轮流操作若干石子堆。每次先从一个非空堆中取走正数个石子，再选择将该堆剩余石子留在原处，或全部并入另一个非空堆；无法操作者输。给定石子堆数组，每次询问区间 [𝐿,𝑅]，统计其内部有多少个子区间 [𝑙,𝑟]，满足只用该子区间的石子堆开始游戏时先手必胜。

数据范围

  • 1≤𝑛,𝑞≤105，1≤𝑎𝑖≤106。
  • 每个询问满足 1≤𝐿≤𝑅≤𝑛。

Solution

61. Easy Problem

题意 有 𝑛 只鸡，第 𝑖 只鸡最多吃 𝑎𝑖 粒谷物；第 𝑗 个喂食器存有 𝑐𝑗 粒谷物，可以分配给编号位于 [𝑙𝑗,𝑟𝑗] 的鸡。对每个 𝑖，仅保留覆盖第 𝑖 只鸡的喂食器，求此时所有鸡合计最多能吃多少粒谷物。

数据范围 1≤𝑡≤104，1≤𝑛,𝑚≤105，0≤𝑎𝑖,𝑐𝑗≤109，1≤𝑙𝑗≤𝑟𝑗≤𝑛；所有测试用例的 𝑛 之和、𝑚 之和分别不超过 105。

Solution

62. Hard Problem

题意 给定数组 𝑎 和整数 𝑘。长度为 2𝑚 的连续子段 𝑎𝑖,…,𝑎𝑖+2𝑚−1，若前后两半的最大值之差的绝对值不超过 𝑘，则称其为好子段。求所有好子段的 (𝑎𝑖+𝑚−1+10)×𝑓𝑚 之和，模 998244353。其中 𝑓1=3240，𝑓2=3081，𝑓3=2841，𝑓4=343；对 𝑖>4，有

𝑓𝑖=223×𝑓𝑖−1+229×𝑓𝑖−2+239×𝑓𝑖−3×𝑓𝑖−4+17.

数据范围 1≤𝑡≤104，1≤𝑛≤5×105，0≤𝑘≤min(𝑛,10)，1≤𝑎𝑖≤𝑛；所有测试用例的 𝑛 之和不超过 5×105。

Solution

63. Battleship: New Rules

题意 交互题。在 𝑛×𝑛 棋盘上放置 𝑘 艘形状为 1×𝑎 或 𝑎×1 的战舰，1≤𝑎≤𝑛；不同战舰不能边相邻或角相邻。给定战舰数后，其放置方案保证占据格子总数最大。你只知道 𝑛，每次可以询问一个格子是否被占据；需要找出一个全空的 2×2 子方格，或报告不存在。

数据范围 1≤𝑡≤100，3≤𝑛≤1000，𝑛≤𝑘≤⌈𝑛2⌉2，所有游戏的 𝑛 之和不超过 5000。每局最多询问 6𝑛 次，交互器非自适应。

Solution

64. Fast Bridges

题意 在 𝑘×𝑘 网格中，相邻格子间移动耗时为 1。另有 𝑛 座双向桥，连接不同行、不同列的两个格子；走桥的耗时为两端曼哈顿距离减 1。求所有无序格子对之间的最短距离之和，模 998244353。

数据范围 0≤𝑛≤500，2≤𝑘≤109。每座桥满足 1≤𝑥1<𝑥2≤𝑘、1≤𝑦1,𝑦2≤𝑘、𝑦1≠𝑦2，所有桥的端点四元组互不相同。

Solution

65. Building Bombing

题意 从左到右有 𝑁 座高度为 ℎ𝑖 的建筑。若一座建筑严格高于其左侧所有剩余建筑，则从左侧可见。可以炸毁除第 𝐿 座外的一些建筑，要求第 𝐿 座建筑从左侧可见，并且是所有可见建筑中第 𝐾 高的。求最少炸毁数量，无解输出 −1。

数据范围 1≤𝐿≤𝑁≤105，1≤𝐾≤10，1≤ℎ𝑖≤109。

Solution

66. Routes

题意 𝑛 个城市分别位于 𝑚 条铁路上，每个城市恰属于一条铁路，并带有 𝑘 种区域标记之一。在同一铁路的相邻城市之间、或同一区域的任意两个城市之间移动，均花费 1 小时。保证任意两座城市之间可达。每条铁路用一个字符串按顺序表示各站区域，求所有无序城市对之间的最短路长度之和。

数据范围 1≤𝑇≤1000，1≤𝑚≤𝑛≤106，1≤𝑘≤16；每条铁路非空，每个区域至少有一个城市。所有测试用例的 𝑛 之和不超过 5×106，至多 5 组测试满足 𝑘>8。

Solution

67. One, Two, Three

题意 给定仅含 1,2,3 的序列 𝐴。选择尽可能多的下标三元组 (𝑖,𝑗,𝑘)，要求 𝑖<𝑗<𝑘，对应元素为 (1,2,3) 或 (3,2,1)，且不同三元组不共用下标。输出最多能选多少组及任意一种最优方案。

数据范围 1≤𝑁≤6×105，1≤𝐴𝑖≤3；输出下标从 0 开始。

Solution

68. Lonely King

题意 给定以 1 为根、边由父亲指向孩子的树，顶点 𝑖 住着 𝐶𝑖 人，所有边初始为蓝色。一次操作可以删除一条由蓝边构成的有向路径上的全部边，并用从起点指向终点的一条红边替代；可操作任意次。对于住在不同顶点的有序个人对 (𝐴,𝐵)，若 𝐴 所在顶点可以沿任意颜色的有向边到达 𝐵 所在顶点，则计一次接触。求操作后最少的接触总数。

数据范围 1≤𝑁≤2×105，1≤𝐶𝑖≤106；给定的父亲数组保证构成以 1 为根的树。

Solution

69. Beautiful Sequence

题意 给定一个整数序列，可以任意重排。定义优美度为不小于其所有相邻元素的位置数，其中端点只与唯一的邻居比较。求重排后可达到的最大优美度，只需输出数值。

数据范围 1≤𝑇≤2222，1≤𝑁≤3×105，1≤𝐴𝑖≤109；所有测试用例的 𝑁 之和不超过 5×106。

Solution

70. Connect the Dots

题意 横轴上从左到右排列 𝑁 个不同的点，第 𝑖 个点颜色为 𝐴𝑖。在异色点之间连曲线，每对点至多连接一次。曲线除端点外必须完全位于横轴上方，不同曲线不能有公共内部点，但可以共用端点。求最多可以连多少条曲线，并输出每条曲线的端点编号。

数据范围 1≤𝑇≤101，2≤𝑁≤2×105，2≤𝑀≤𝑁，1≤𝐴𝑖≤𝑀；所有测试用例的 𝑁 之和不超过 2×105。

Solution

71. Greedy Bipartite Matching

题意 二分图左右各有 𝑛 个点，按权值 1,2,…,𝑞 依次加入对应的边，允许重边。定义贪心匹配为使“权值为 1 的边数、权值为 2 的边数、……”组成的序列字典序最大的匹配。对每个 𝑖，求只保留权值不超过 𝑖 的边时，贪心匹配的边数。

数据范围 0≤𝑛≤105，0≤𝑞≤103，权值为 𝑖 的边数 𝑚𝑖≥0，∑𝑖𝑚𝑖≤2×105。

Solution

72. Forever Young

题意 给定两个无限长、非负且单调不增的整数数组 𝐴,𝐵，它们均仅有有限个非零元素。每次将一个元素加 1 或减 1，并保证数组仍然非负、单调不增。求从 𝐴 恰好经过 𝑘 次操作得到 𝐵 的操作序列数，模 998244353。

数据范围 两个数组的非零元素数均在 [0,60] 内，非零元素均不超过 60，且 ∑𝑖𝑎𝑖≤60、∑𝑖𝑏𝑖≤60；0≤𝑘≤106。

Solution

73. Sets May Be Good

题意 给定一个无向简单图，求有多少个顶点子集，其诱导子图的边数为偶数。答案模 998244353，空集也计入。

数据范围 1≤𝑛≤1000，0≤𝑚≤𝑛(𝑛−1)2；无自环、无重边。

Solution

74. Counting Cactus

题意 给定一个无向简单图，保留全部 𝑛 个顶点并选择一个边集，要求得到的图连通，且每条边至多属于一个简单环，即构成仙人掌图。求合法边集数量，模 998244353。

数据范围 1≤𝑛≤13，0≤𝑚≤𝑛(𝑛−1)2；无自环、无重边。

Solution

75. Fast Spanning Tree

题意 初始有 𝑛 个孤立点，点权为 𝑤𝑖，另有 𝑚 个候选边三元组 (𝑎𝑖,𝑏𝑖,𝑠𝑖)。每一步选择编号最小且满足以下条件的候选边：两端位于不同连通分量，且这两个分量的点权总和之和至少为 𝑠𝑖。加入此边并继续，直到没有可选边。输出加入的边数及按加入顺序排列的边编号。

数据范围 1≤𝑛,𝑚≤3×105，0≤𝑤𝑖,𝑠𝑖≤106，1≤𝑎𝑖,𝑏𝑖≤𝑛，𝑎𝑖≠𝑏𝑖；候选边可以重复。

Solution

76. Grammarly

题意 将字符串 𝑠 的所有不同非空子串作为顶点；若 𝑏 是 𝑎 的子串且 |𝑏|+1=|𝑎|，则连有向边 𝑎→𝑏。求从 𝑠 出发、终点任意的简单路径数，包含只含 𝑠 的长度为零的路径，答案模 998244353。

数据范围 1≤|𝑠|≤3×105，𝑠 仅含小写英文字母。

Solution

77. Honorable Mention

题意 给定整数数组 𝑎，回答 𝑞 个询问 (𝑙,𝑟,𝑘)：在区间 [𝑙,𝑟] 中恰好选择 𝑘 个非空且互不相交的连续子段，求被选元素的最大总和。

数据范围 1≤𝑛,𝑞≤35000，−35000≤𝑎𝑖≤35000；1≤𝑙≤𝑟≤𝑛，1≤𝑘≤𝑟−𝑙+1。

Solution

78. Independent Set

题意 交互题。有一张未知无向图，可能包含重边和自环，已知点数 𝑛。一次询问提交一个可重复的顶点序列：交互器从空集合 𝑆 开始依次处理每个顶点，返回该顶点与当前 𝑆 之间的边数；若边数为零，则将此顶点加入 𝑆。利用这些回答恢复图中全部边，包括重数和自环。

数据范围 1≤𝑛≤4000，0≤𝑚≤104；每次询问的序列非空，所有询问序列的长度总和不超过 176000。

Solution

79. Anti-Plagiarism

题意 给定两棵无根树 𝑇1,𝑇2，判断能否向 𝑇2 添加若干顶点和边，并重新编号，使其变成 𝑇1；等价于判断 𝑇1 是否包含一个与 𝑇2 同构的子树。

数据范围 1≤𝑡≤104，两棵树的点数满足 2≤𝑚≤𝑛≤105；所有测试用例的 𝑛 之和不超过 5×105，𝑛×𝑚 之和不超过 107。

Solution

80. Bit Component

题意 将 1 到 𝑛 按某个排列逐行写成二进制，并将各行的最低位对齐。要求所有值为 1 的格子通过上下左右相邻关系组成一个连通块。构造任意一个满足条件的排列，或报告无解。

数据范围 1≤𝑛≤2×105。

Solution

81. Jumping Lights

题意 给定一棵树，初始所有顶点均未标记。支持三种操作：取消一个点的标记；标记一个点；同时更新所有点，使每个点当且仅当更新前至少有一个邻居被标记时被标记。每次操作后输出被标记的顶点数。

数据范围 2≤𝑛≤3×105，1≤𝑞≤106。

Solution

82. Bulbasaur

题意 有 𝑛 层、每层 𝑘 个点的有向图，边只从第 𝑖 层指向第 𝑖+1 层，以相邻层之间的邻接矩阵给出。令 𝑓(𝑖,𝑗) 为从第 𝑖 层到第 𝑗 层的两两不共用顶点的路径最大数量，求 ∑1≤𝑖<𝑗≤𝑛𝑓(𝑖,𝑗)。

数据范围 2≤𝑛≤40000，1≤𝑘≤9；输入包含 𝑛−1 个 𝑘×𝑘 的 01 邻接矩阵。

Solution

83. Cloyster

题意 交互题。一个 𝑛×𝑛 矩阵的元素两两不同，且除全局最大值外，每个格子在八邻域中都至少有一个值更大的格子。每次询问一个格子的值，要求找出全局最大值的位置。

数据范围 2≤𝑛≤2000，1≤𝑎𝑖𝑗≤109；最多询问 3𝑛+210 次，交互器非自适应。

Solution

84. Different Summands Counting

题意 考虑所有满足 𝑎1+…+𝑎𝑚=𝑛 的正整数有序序列。每个序列的贡献为其中不同数值的个数，求所有序列的贡献之和，模 998244353。

数据范围 1≤𝑛≤1018，1≤𝑚≤500，𝑚≤𝑛。

Solution

85. Emerging Tree

题意 从 𝑛 个孤立点开始，按给定顺序加入 𝑛−1 条有向边，最终形成一棵边由根指向后代的有向树。给每个顶点 𝑣 分配互不相同的编号 𝑝𝑣，构成 1 到 𝑛 的排列，要求在加边过程中的每个时刻，对任意顶点 𝑣，从 𝑣 可达的全部顶点（含自身）的新编号恰为一段连续整数。构造任意合法排列，或报告无解。

数据范围 2≤𝑛≤106；输入的完整边集保证构成一棵向外有向树。

Solution

86. Jaw-Dropping Set

题意 从 {1,2,…,𝑛} 中选择一个子集，要求任意两个不同元素互不整除。先使所选元素数量最大，再使元素总和最小，输出该最小总和。

数据范围 1≤𝑡≤105，每组 1≤𝑛≤109。

Solution

87. 𝑘-coloring

题意 给定一个连通无向简单图，从顶点 1 出发沿边行走，可以重复经过顶点和边。每走 𝑘 步，就给该步经过的边染色；若再次给已染色的边染色则失败。要求构造一个行走序列，使所有边恰好被染色一次，或报告无解。

数据范围 1≤𝑛≤105，𝑛−1≤𝑚≤105，1≤𝑘≤10；输出序列包含的顶点数不超过 1000001。

Solution

88. Three Vectors

题意 给定三个两两不同的长度为 𝑛 的 01 向量。构造关于 𝑛 个布尔变量的 2-CNF 公式，要求三个给定向量均满足公式，并使全部满足赋值的数量最少。每个子句是两个文字（变量或其否定）的析取，输出任意最优公式。

数据范围 2≤𝑛≤105；输出的子句数须满足 0≤𝑚≤2×105，允许一个子句的两个文字使用同一变量；空公式视为恒真。

Solution

89. Decorative Birds

题意 第 𝑖 只鹅的速度为 𝐴𝑖，得分为 𝐶𝑖，在时间闭区间 [𝑇𝑖,𝑇𝑖+𝐿] 内等待食物。可以在任意时刻投喂任意多次，每次由当前仍在等待且速度最快的鹅吃到食物，获得其得分，随后该鹅离开。未进食的鹅在等待时间结束后离开。求能获得的最大总分。

数据范围 1≤𝑛≤3×105，1≤𝐿≤109，1≤𝐴𝑖≤𝑛 且速度两两不同；−109≤𝐶𝑖≤109，0≤𝑇𝑖≤109。

Solution

90. Holes in Queue

题意 初始无限队列为 1,2,3,…。一次操作同时删除当前队列中位置为 𝑎1,…,𝑎𝑛 的元素，再将剩余元素从 1 开始重新编号。重复相同操作 𝑑 次后，回答 𝑞 个询问：队列第 𝑥 个位置上的数是多少。

数据范围 1≤𝑛,𝑞≤5×105，1≤𝑎𝑖,𝑑,𝑥≤1012，所有 𝑎𝑖 两两不同，不保证按顺序给出。

Solution

91. Build Well

题意 有 𝑛 种弧长为整数的砖，每种数量无限。用它们逐层围成周长恰为 𝑤 的圆井，每层的起始偏移也必须为整数。相邻两层不能有位置重合的砖缝，覆盖整圈的一块砖也有一道砖缝。判断能否用两种层配置交替构造无限深的稳定圆井；若能，输出两层各自的起始偏移和砖块序列。

数据范围 1≤𝑛,𝑤≤3×105，1≤𝑏𝑖≤𝑤。

Solution

92. Permutation Recovery

题意 将 𝑘 个 1 到 𝑛 的排列及其逆排列各写成一行，得到 2𝑘×𝑛 的矩阵，再独立打乱每一列。给定打乱后的矩阵，恢复任意一组可能的 𝑘 个原排列。

数据范围 1≤𝑛≤4×104，1≤𝑘≤7，1≤𝑎𝑖,𝑗≤𝑛；保证存在合法解。

Solution

93. Split the Picture

题意 平面上有 𝑛 个带正权的整点，允许重合。用直线 𝑋=𝑥+0.5 与 𝑌=𝑦+0.5 将平面分成四部分，其中 𝑥,𝑦 为整数。代价为四部分点权和的最大值减去最小值。对每个 𝑥=1,2,…,𝑛−1，求自由选择 𝑦 后的最小代价。

数据范围 2≤𝑛≤2×105，1≤𝑥𝑖,𝑦𝑖≤𝑛，1≤𝑠𝑖≤109。

Solution

94. Single-Crossing

题意 给定 𝑛 个长度为 𝑚 的排列，重新安排这些排列的顺序，使任意两个不同的数在各排列中的相对先后关系最多改变一次。输出任意一种合法的排列编号顺序，或报告无解。

数据范围 1≤𝑡≤5；每组 1≤𝑛≤105，1≤𝑛×𝑚≤106。

Solution

95. Fractal Maze

题意 从四周封闭的一个方格开始，进行 𝑛 次扩展：将当前迷宫的四个副本按 2×2 拼接；新中心向右、上、左、下延伸的四段分隔墙中，恰有一段保持封闭，其余三段各在指定位置开一个单位宽的通道。位置从中心向外按单位线段编号。最终任意两格之间均有唯一简单路径。回答 𝑞 次询问，求两格之间的路径长度，即相邻格移动次数。

数据范围 1≤𝑛≤30，1≤𝑞≤1000；第 𝑖 次扩展的四个通道参数中恰有一个为 0，其余位于 [1,2𝑖−1]；询问的行列坐标均位于 [1,2𝑛]。

Solution

96. Interactive Primality

题意 交互题。需要依次猜出 𝑇 个隐藏整数。对于当前整数 𝑥，每次可以给出整数 𝑦，交互器回答 𝑥+𝑦 是素数还是合数。猜出 𝑥 后提交答案，再处理下一个数。所有隐藏整数在交互前固定；除样例外，它们均在指定区间内独立均匀随机生成。

数据范围 1≤𝑇≤10，1≤𝑥,𝑦≤1018；所有隐藏整数合计最多询问 8750 次，提交最终猜测不计入询问次数。

Solution

97. Slot Machine

题意 一个 𝑘 位显示屏初始全为问号，机器藏有一个允许前导零的 𝑘 位十进制串；给定所有可能隐藏串的集合。每修改一位显示字符花费 1，按按钮免费：若显示串不含问号，机器会回答它与隐藏串按数值比较的大小关系，相等则获胜。求采用最优自适应策略时，保证获胜所需的最小最坏情况费用。

数据范围 1≤𝑇≤104，1≤𝑘≤5；每组用长为 10𝑘 的二进制串表示可能集合，集合非空；所有二进制串的总长度不超过 105。

Solution

98. Mausoleum

题意 给定一个底边水平、上边界关于横坐标单调的直角多边形，以及严格位于多边形外的起点 𝑆 和内部的终点 𝑇。只能选择多边形的一个顶点穿过边界进入内部，其他位置不能穿墙。求从 𝑆 到 𝑇 的最短欧几里得路径长度。

数据范围 顶点数 𝑛 为偶数，4≤𝑛≤105；边的坐标参数 0≤𝑣𝑖≤106，𝑣1=𝑣𝑛=0，每条边长至少为 1；−106≤𝑠𝑥,𝑠𝑦≤2×106，0<𝑡𝑥,𝑡𝑦<106。答案绝对误差须小于 10−3。

Solution

99. Protecting Kingdom

题意 给定一棵带正边长的树，每条边内部标记若干危险点。可以在树上任意选择两个点作为端点，保护它们之间长度不超过 𝑤 的路径。求最多能覆盖多少危险点，路径端点上的危险点也计入。

数据范围 2≤𝑛≤250000，1≤𝑤,𝑙𝑖≤1018；第 𝑖 条边连接点 𝑖+1 与 𝑝𝑖，1≤𝑝𝑖≤𝑖；危险点位置均为整数且满足 0<𝑥𝑖,1<…<𝑥𝑖,𝑘𝑖<𝑙𝑖，危险点总数不超过 106。

Solution

100. Square Stamping

题意 平面上给定 𝑛 个不同的点，它们均位于 𝑦=−9999、𝑦=0 或 𝑦=9999 上。用边长为 10000、边与坐标轴平行的正方形覆盖所有点，正方形的内部和边界均算覆盖。求最少需要多少个正方形。

数据范围 1≤𝑛≤3×105，−109≤𝑥𝑖≤109，𝑦𝑖∈{−9999,0,9999}。

Solution

101. String Rank

题意 定义 𝑄𝑡(𝑠) 为字符串 𝑠 中所有长度不超过 𝑡 的不同子序列组成的集合，包含空串。给定字符串 𝑤，求最小正整数 𝑡，使 𝑤 的任意两个不同后缀的 𝑄𝑡 集合均不相同。

数据范围 1≤|𝑤|≤3×106；𝑤 仅含小写英文字母。

Solution

102. AmazingTalker

题意 𝑁 个人各有两项能力排名 (𝑥𝑖,𝑦𝑖)，排名越小能力越强，允许并列。构造一个无自环、无重边的无向友谊图，使每个人的邻居中严格超过一半的人，至少在一项能力上严格强于自己。判断是否有解；若有，输出一个边数不超过 3.1416𝑁 的方案。

数据范围 1≤𝑁≤5×105，1≤𝑥𝑖,𝑦𝑖≤𝑁；若有解，保证存在边数 𝑀≤3.1416𝑁 的方案。

Solution

103. Flappy Bird

题意 在矩形 [0,𝐿]×[0,𝐻] 内，从 (0,𝑠) 移动到 (𝐿,𝑡)。有 𝑁 道位于不同横坐标 𝑥𝑖 的竖直障碍，只允许从纵坐标区间 [ℓ𝑖,𝑟𝑖] 穿过。将移动物体视为点，路径可以是任意曲线。求避开障碍的最短欧几里得路径长度。

数据范围 1≤𝑁≤3×105，1≤𝐿,𝐻≤109，0≤𝑠,𝑡≤𝐻，0<𝑥𝑖<𝐿，0≤ℓ𝑖<𝑟𝑖≤𝐻；𝑥𝑖 互异但不保证有序。答案绝对或相对误差不超过 10−6。

Solution

104. Judge Error

题意 给定简单无向图的邻接矩阵，判断图是否恰有一个完美匹配。若有，输出这个匹配；每对端点按较小编号在前，所有匹配边按较小端点递增排列。这里无需检查图的边数是否最大。

数据范围 2≤𝑁≤2000，𝑁 为偶数；输入为 𝑁×𝑁 的对称二进制矩阵，主对角线全为 0。

Solution

105. Advanced Evolution Studies

题意 给定 𝑛 个指定顶点与 𝑚 条限制，每条限制 (𝑎,𝑏,𝑐,𝑑) 要求 LCA(𝑎,𝑏) 是 LCA(𝑐,𝑑) 的严格后代。构造一棵满足全部限制的有根树，可以添加新顶点，但总顶点数须在 [𝑛,2𝑛] 内；输出各点父亲，或报告无解。指定顶点不要求是叶子。

数据范围 4≤𝑛≤2000，1≤𝑚≤2000，1≤𝑎,𝑏,𝑐,𝑑≤𝑛，𝑎≠𝑏，𝑐≠𝑑；若有解，保证存在不超过 2𝑛 个顶点的解。

Solution

106. Joy of Sushi

题意 𝑛 位顾客和 𝑛+1 位厨师分别排在编号连续的位置上；顾客 𝑖 初始有 𝑎𝑖 个寿司，厨师 𝑖 每分钟制作 𝑏𝑖 个。每分钟先由前 𝑛 个位置上的厨师给同位置顾客制作寿司，最后一个位置的厨师休息；随后厨师循环右移一位，顾客也在自己的 𝑛 个位置中循环右移一位。顾客每凑满 𝑘 个寿司便立即吃掉。求首次所有顾客剩余寿司均为 0 的分钟数，可以为 0；若永远无法达到则输出 −1。

数据范围 1≤𝑛≤2000，2≤𝑘≤106，0≤𝑎𝑖<𝑘，1≤𝑏𝑖<𝑘。

Solution

107. Kid’s Game

题意 在字符为 G、Z、D、P、X 的 𝑟×𝑐 棋盘上博弈，Scallion 先手。Scallion 每次将水平相邻、从左到右为 GZ 的两格改为 DP；Aubergine 每次将竖直相邻、从上到下为 DP 的两格改为 GZ。轮到一方时必须操作，无法操作者输；经过 10100 回合仍未结束则平局。双方优先争取获胜，其次争取平局，求最终结果。

数据范围 2≤𝑟,𝑐≤2500；棋盘仅含上述五种字符。

Solution

108. Colorful Doors

题意 桥上从左到右有 2𝑁 扇门，每种颜色 1,…,𝑁 各出现两次。一个人从最左端不断向右走，每次碰到门时，立即传送到另一扇同色门的右侧。给定长为 2𝑁−1 的二进制串，记录每对相邻门之间的路段是否曾被走过。判断是否存在符合记录的门颜色排列，若有则构造一个。

数据范围 1≤𝑁≤105，|𝑠|=2𝑁−1，𝑠 仅含 0 和 1。

Solution

109. Construct Point

题意 给定 𝑄 个顶点坐标为整数的非退化三角形，顶点按逆时针顺序给出。分别判断每个三角形的严格内部是否存在整点；若存在，输出任意一个，否则输出 (−1,−1)。

数据范围 1≤𝑄≤104；所有顶点坐标均为 [0,109] 内的整数。

Solution

110. Rectangles

题意 将 𝐴×𝐵×𝐶 的长方体划分为单位立方体，并将三个方向都视为首尾相接。一个 𝑎×𝑏×𝑐 的环面长方体由三个方向上分别连续的 𝑎,𝑏,𝑐 个坐标组成，允许跨越边界，方向固定。求用这种环面长方体无重叠地恰好铺满全部单位立方体的方案数，对 109+7 取模；每个方案按所选长方体的集合计数。

数据范围 1≤𝑎<𝐴≤100，1≤𝑏<𝐵≤100，1≤𝑐<𝐶≤100。

Solution

111. Simple APSP Problem

题意 𝐻×𝑊 网格中有 𝑁 个黑格，其余为白格。只能在白格之间上下左右移动。对所有不同白格组成的无序对，求两格之间最短路径长度之和，对 109+7 取模。

数据范围 1≤𝐻,𝑊≤106，1≤𝑁≤30，0≤𝑥𝑖<𝐻，0≤𝑦𝑖<𝑊；黑格互异，至少有一个白格，且所有白格连通。

Solution

112. Hamilton

题意 在编号 1 到 𝑛 的一排格子中，从 𝑎 出发、在 𝑏 结束，并恰好访问每格一次。可以免费走到相邻格，也可以花费一次飞行，从当前格 𝑥 到满足 gcd(𝑥,𝑦)=1 的格子 𝑦。求最少飞行次数并构造访问顺序，或报告无解。

数据范围 1≤𝑡≤103，2≤𝑛≤2×105，1≤𝑎,𝑏≤𝑛，𝑎≠𝑏；所有测试的 ∑𝑛≤2×105。

Solution

113. I’ve Got Friends

题意 给定 𝑛 个人之间完整的潜在朋友关系图。每个人须选出两种不同的食物，且任意两人相邻当且仅当他们选择的食物至少有一种相同。判断能否为所有人安排食物；若能，为每个人输出两个不同的食物编号。

数据范围 1≤𝑛≤105，0≤𝑚≤105；输入为无自环、无重边的无向图。输出的食物编号须为 [−109,109] 内的整数。

Solution

114. Best Subsequence [done]

题意 给定长度为 𝑛 的正整数序列，选出一个长度恰为 𝑘 的子序列。将选出的数按原顺序首尾相接，代价为每对环上相邻元素之和的最大值。求最小可能代价。

数据范围 3≤𝑘≤𝑛≤2×105，1≤𝑤𝑖≤109。

Solution

不妨钦定最小值被选：用它替换前一个选中的元素，相邻和都不会增大。将数组循环移位，把最小值放到第一位。

二分答案𝑋，称满足2𝑤𝑖≤𝑋的元素为 small，其余为 big。两个 small 可以相邻，两个 big 不能相邻。

small 可以全选。补入一个未选的 small，若与相邻的 big 冲突，就用它替换这个 big；big 原本两侧都是 small，因此替换后仍然合法，数量也不减少。故为了选 big 而放弃 small 不会更优。

若 small 已有𝑘个则可行，否则考虑相邻 small 之间的间隙。每个间隙至多补入一个 big，取其中的最小值𝑚，两端值记为𝑢,𝑣，满足𝑚+max(𝑢,𝑣)≤𝑋即可补入。统计可选总数，判断是否达到𝑘。

从第一位扫描一圈，维护前一个 small 和间隙最小值，最后再访问第一位以结算首尾间隙。没有 small 时不可行。总时间复杂度为𝑂(𝑛log𝑉)，其中𝑉=max𝑖𝑤𝑖，空间复杂度为𝑂(𝑛)。

实现 QOJ 提交 2959650。

115. Cool pairs

题意 给定两个 1 到 𝑛 的排列 𝑝,𝑞 和整数 𝑘。构造整数数组 𝑎,𝑏，满足 𝑎𝑝1≤…≤𝑎𝑝𝑛、𝑏𝑞1≤…≤𝑏𝑞𝑛，并使满足 𝑖<𝑗 且 𝑎𝑖+𝑏𝑗<0 的数对恰好有 𝑘 个。输出任意方案，或报告无解。

数据范围 1≤𝑛≤3×105，0≤𝑘≤𝑛(𝑛−1)2；输出元素须满足 −𝑛≤𝑎𝑖,𝑏𝑖≤𝑛。

Solution

116. Unfair Card Deck

题意 牌堆共有 30 张牌，每种牌有一张或两张，第 𝑖 种牌有固定未知权重 𝑋𝑖。每次抽牌时，若各类剩余张数为 𝑐𝑖，则抽到第 𝑖 类的概率为 𝑐𝑖𝑋𝑖∑𝑗𝑐𝑗𝑋𝑗。给定 𝑚 局完整抽牌顺序，估计各类权重 𝑊𝑖；要求所有两类牌的归一化权重比例与真实比例之差严格小于 0.02，即 |𝑋𝑖𝑋𝑖+𝑋𝑗−𝑊𝑖𝑊𝑖+𝑊𝑗|<0.02。

数据范围 正式测试 𝑚=100000，1≤𝑛≤30，𝑎𝑖∈{1,2}，∑𝑖𝑎𝑖=30，每局记录恰有 30 项；0<𝑋𝑖≤1，输出须满足 10−300<𝑊𝑖≤1。

Solution

117. Permutasino

题意 给定长为 𝑛 的整数向量 𝑥，构造至多 𝑛 个 1 到 𝑛 的排列，并为它们分配非负概率，使概率和为 1，且随机选中排列的每个位置的期望恰为对应的 𝑥𝑖。输出排列及概率，或报告无解。

数据范围 1≤𝑛≤500，1≤𝑥𝑖≤𝑛；输出排列数 1≤𝑘≤𝑛，每个概率位于 [0,1]。概率总和与 1 的绝对误差不超过 10−6，各坐标期望的绝对误差不超过 10−2。

Solution

118. Humongous String

题意 字母表含 𝑘 个不同字符 𝑠0,…,𝑠𝑘−1。令 𝑇0=𝑠0，𝑇𝑖=𝑇𝑖−1𝑠𝑖mod𝑘，再将 𝑇0,𝑇1,𝑇2,… 依次拼接为无限串 𝑆。给定 𝑛,𝑘，求 𝑆 的长度为 𝑛 的前缀中，不同非空子串的数量。

数据范围 1≤𝑇≤105；每组 1≤𝑛,𝑘≤109。

Solution

119. K-Triangles

题意 给定 𝑛×𝑚 的整数矩阵。选择一个格子作为直角顶点，并选择四个轴对齐象限中的一个，该象限内与顶点曼哈顿距离严格小于 𝑘 的全部格子构成一个 𝑘-三角形；三角形须完整位于矩阵内，四种朝向均可选择。三角形的权值为其全部格子元素之和。求两个没有公共格子的 𝑘-三角形的最大权值和。

数据范围 1≤𝑛,𝑚,𝑘≤1500，−109≤𝐴𝑖,𝑗≤109；保证至少存在两个不相交的合法 𝑘-三角形。

Solution

Comments

Sign in with GitHub to comment.