THUPC 2025 初赛部分题解

注意

题解写得可能非常抽象。

「如果一个题解你看不懂，那是题解垃圾而不是你垃圾。」

A. 骑行计划

题意

接下来 $n$ 天，每天会骑 $s_i$ 分钟共享单车，每分钟单价 $c$ 元。有 $m$ 种会员卡，每种卡售价 $w_i$ ，有效期 $d_i$ 天，可以使得接下来 $d_i$ 天每天前 $t_i$ 分钟骑车免费。多个会员卡叠加使用、免费额度取 $\max$ 。求最小花费。 $n\leq 150,s_i\leq 150$

首先，两个会员卡的区间如果有交错，可以视作 $t_i$ 较小的卡的有效期较短。允许买会员卡时不把有效期用满，这样所有会员卡的区间要么不交、要么 $t_i$ 小的包含 $t_i$ 大的。区间 DP，设 $f[l,r,t]$ 表示：考虑日子区间 $[l,r]$ ，买的会员卡使其内部的有效期均不小于 $t$ ，最小花费。转移时可以在整个区间买新卡、也可以拆成两个区间。应该前缀 min 优化一下之类的能跑出来。

B. 挑战大模型

题意

假设有一个 $n\times m$ 的矩阵，每个格子为黑色或者白色；现在其有一个小矩形覆盖在大矩形上面，将其向左平移，从而遮住大矩形的另一部分、露出另一部分。移动前后得到两个 $n\times m$ 的矩阵。给出这两个矩阵，判断其是否可能是上述方式得到的；如果是，给出小矩形的最大可能面积。 $n,m\leq 250$

题解

在确定小矩形的范围和移动距离之后，我们可以确定哪些格子可能会发生变化。

枚举移动的距离。考虑两个矩形不相等的地方，这些地方必须被「可能发生变化的格子」覆盖。考虑两个矩形按照平移距离错开后、不相等的地方，这些地方不能被小矩形包含。

小矩形尽量取大是最好的，使用悬线法找到所有极大的小矩形（ $O(nm)$ 个），随后判断「可能发生变化的格子」是否覆盖完不相等的地方即可。

C. Harmful Machine Learning

题意

两人在一个 $1\times n$ 的地图上博弈。每个格子有一个整数。BOT 初始位于 $(1,x)$ 。双方每一回合：

NIT 选择两个格子里的数，交换（可以相同，即不交换）。
BOT 向相邻格子移动一步，或者停留原地。
BOT 决定是否停止游戏（要求 $10^{114514}$ 回合内停止）。 BOT 希望最终停在一个数尽可能大的格子上，NIT 希望最终停在一个数尽可能小的格子上。求最后得分。 $n\leq 10^5$

题解

如果在回合第二阶段开始时、BOT 相邻的数都小于 $x$ （且至少有三个数小于 $x$ ），那无论 BOT 怎么移动，我都可以维持 BOT 相邻的数都小于 $x$ 。因此答案为【初始位置相邻数中的次大值】和【全局第三小值】中的较大者。

D. 摊位分配

题意

$n$ 个社团，每个社团有分数 $h_i$ ，争夺 $m$ 个摊位。每个社团会给出 $m$ 个数 $h_i/2^0, h_i/2^1, \cdots, h_i/2^{m-1}$ ；每次选出：

最大的数
若数相同，若有社团还没有摊位，选择这个社团；否则选择原始 $h_i$ 最大的社团
若还有并列，选择 $i$ 最小的社团给这个数（社团）分配一个摊位。直到 $m$ 个摊位被分配干净。求每个社团的摊位数量。 $n\leq 10^5,m\leq 10^9$ 。

题解

分两个阶段。第一阶段，用优先队列，每次取一个数，直到所有数都小于 $1$ 。第二阶段是周期性的，确定各个社团的顺序后即可直接计算。全体乘 $2^{32}$ 可以避免浮点误差。

E. 背向而行

题意

$m$ 堆积木，各堆位于特定坐标，有若干块。持续以下操作、直到每堆只剩一块：取有至少两块的堆中坐标最小的一堆，取一个向左一格、取一个向右一格。多次询问最后从左往右第 $x$ 个积木的坐标。 $m,q\leq 2\times 10^6$ ，查询的坐标单调。

题解

操作的顺序其实无关。可以证明，一堆积木会变成一个区间（可能挖掉一个点），两个区间有重叠会仍然是一个区间（可能挖掉一个点）。操作会维持坐标和不变，通过坐标和和积木个数可以唯一确定区间形状。用一个栈维护目前的区间，每次输入一个新的堆就不断合并。查询时双指针。复杂度线性。疑似需要快速 IO。

Fun fact：队友粘了个快速 IO 板子，但是当时正在使用一个没有询问的数据调试，又没有去掉调试信息。因此把调试信息当做了快输的输出，以为板子挂了。

H. waht 先生的法阵

题意

给定一个序列 $a_i$ 。有两种操作：

修改：区间乘一个正整数 $c$ 。
查询：给定 $x$ ，每次从 $x$ 跳到 $x+\gcd(x,a_x)$ ，直到跳出 $n$ 。求经过的位置的数的和。 $n,q,c\leq 2.5\times 10^5$ ， $a_x<998244353$

题解

考虑维护跳跃的边：对于每个 $i$ 考虑 $\gcd(i, a_i)$ 离 $i$ 还有多少质因子，对于每个质数都维护一个 set 来记录这个质因子没有顶满的 $i$ ，每次修改时从 set 里取出 $\gcd$ 发生变化的 $i$ ；这样的 $i$ 至多取出 $O(n\log \log n)$ 次，用分块（详见弹飞绵羊）维护这个跳跃关系。

经过的位置的数的和同样可以在分块中维护；整块修改打 tag，块内修改暴力更新。

I. 乒乓球赛

题意

一场乒乓球赛恰好 $n$ 回合结束。对于某些 $i$ ，有信息：第 $i$ 回合结束时，双方比分 $a_i:b_i$ 或 $b_i:a_i$ 。求有多少可能的胜负序列满足这些信息。 $n\leq 10^5$

题解

设 $f[i,j]$ 表示 $i$ 回合结束、双方分差为 $j$ 的方案数； $j$ 在前期不超过 $\pm 11$ 、后期不超过 $\pm 2$ 。

K. 峰回路转

题意

我们使用三种记号来描述一个字符串应当以什么顺序阅读：

没有记号的话，则直接顺序阅读
近邻逆接记号：X * Y 表示 X 一定紧跟在 Y 后面，如 研表*究明 -> 研究表明，林暗草*惊*风 -> 林暗风惊草
近邻顺接记号：X # Y 表示 Y 一定紧跟在 X 前面（必须结合遥远跳转结构使用）
遥远跳转结构：X a-b .... Y a-1，一个记号形如「层级-序号」，每个结构都是由很多个记号组成，用来描述有较大跨度的逆序：
- ... X a-3 ... Y a-2 ... Z a-1 表示，读了 Z 后再依次读 Y、X、……。每个记号只影响其前面的一个字符。
- 每个结构之间不能交叉、只能并列或者嵌套。
- 第一个整数表示内部嵌套的层数。
- 例如：然后知生1-2于忧患1-1而死1-2于安乐1-1也 -> 然后知于忧患生而于安乐死也
- 近邻顺接记号只能在一个序号非 1 的遥远跳转结构的标记后使用，用来把影响往后扩大：
  - 例如 严1-3#霜结1-2庭兰1-1 -> 庭兰结严霜
除此之外还有亿些额外的规定，如 * 应当优先于遥远跳转结构使用等等，详见题目描述。

现在给定一个排列，表示希望每个字第几个被读到。求唯一的（在题目限制下是唯一的）一个合法的记号序列，或无解。 $n\leq 10^5$

$a_i\to b_i$ ：容量为 $1$ 。其余所有边容量为 $\infty$ 。
$b_i\to p_i$
$p_i\to a_i$
对于边 $u\to v$ $u \to v$ 、属于 $r$ $r$ 管辖：
- 若 $u=p_r$ ，连接 $b_r\to v$
- 若 $v=p_r$ ，连接 $u\to a_r$