题解 - 2026 杭电春季联赛 (4)

1010 Sort

我们可以用调整法构造出唯一的贪心方案。

如果存在一种选择方案，那么将 $b_1$ 调整为 $a_1$ 中最小的元素，一定仍然合法；将 $b_2$ 选择 $a_2$ 中最小的、大于 $b_1$ 的元素，一定仍然合法，并且不会比原来的 $b_2$ 更大。

以此类推，我们可以构造出唯一的序列。

形式化地，对于任意一组 $b_1,b_2,\dots,b_n$ ，我们可以定义序列 $g_1,g_2,\dots,g_n$ ，满足：

$g_1=\min_{1\le j\le m} a_{1j}$ 。
$g_i=\min\{a_{ij}\mid 1\le j\le m,g_{i-1}<a_{ij}\}$ ， $i\ge 2$ 。

我们可以证明 $\forall i,g_i\le b_i$ ：

对 $i=1$ ，显然成立；
若 $i-1$ 成立，则 $i$ 时，既然 $b_i>b_{i-1}\ge g_{i-1}$ ，那么 $b_i>g_{i-1}$ ，于是 $b_i$ 也在 $g_i$ 的候选元素中，所以 $g_i\le b_i$ 。

因此只要存在一个解，那么贪心解就一定存在；反之，贪心解本身就是一个可行解。

此外，由于每一步都选择当前行中满足条件的最小元素，所以该序列是唯一确定的。

复杂度 $O(nm)$ 。

1007 Turn of a Page

如果存在一个 $a_i>S$ ，那么包含这个元素的部分和一定大于 $S$ ，不可能等于 $S$ 。

如果存在一个 $0<a_i<S$ ，那么无论如何排列，一定存在第一个满足条件的 $a_p$ ；由于这样的元素前面只有 $0$ 或 $S$ ，所以一定不存在 $1\le q\le p$ ，使得 $\sum_{i=q}^p a_i=S$ 。

所以现在可以将元素限制为 $0$ 和 $S$ 两种。如果 $S$ 出现了，那么只要将序列排列成 $S,S,\dots,S,0,0,\dots,0$ 即可；如果 $S$ 没出现，自然不存在这样的重排。

复杂度 $O(n)$ 。

1008 谁输谁洗碗

直接暴力标记非法数字即可，复杂度 $O(nk)$ ，其中 $k=10^4$ ，是可以过的。

其实本地造一个极限数据需要跑大概 $10$ 秒，我个人认为如果是正式赛，这种题目应当适当放小数据范围。

1004 左右脑互搏

观察到 $n$ 作为指数是可以接受的，所以可以对局面进行状压 DP。

具体地讲，对于 $\varnothing$ 状态，是输态；预处理出 $S_l$ 表示 $\operatorname{popcnt}(x)=l$ 的所有 $x$ ，然后枚举 $l=1\sim n$ ，所有 $S\in S_l$ 都可以从 $S\setminus \{x\}(x\in S)$ 并且满足异或和要求的集合转移过来，如果存在一个满足条件的集合是输态，那么当前就是赢态，否则是输态。

复杂度 $O(n2^n)$ 。

1001 布布吃地瓜

我们先从简单的情况入手。

检查 $0$ 是否能够成为答案，可以发现，如果存在一条不经过 $0$ 的 $(1,1) \to (n,m)$ 的四连通路径，那么 $0$ 是答案；

否则，如果存在每一条不经过 $1$ 的 $(1,1)\to (n,m)$ 的四连通路径，那么 $1$ 是答案；以此类推。

然后我们有一个 $O((nm)^2)$ 的做法：

从 $x=0$ 开始枚举答案，每一次删掉所有 $a_{ij}=x$ 的 $(i,j)$ ，使用 BFS 检查 $(1,1)\to (n,m)$ 是否是四连通的。

考虑如何进行优化。设 $B_x=\{(i,j)\mid a_{ij}=x\}$ ，那么 $\sum_{x} |B_x|=nm$ 。

如果能够用上这个条件，即让复杂度为 $O( \sum_x |B_x|)=O(nm)$ ，那么复杂度就是正确的。

这启示我们在每一轮循环只考虑 $a_{ij}=x$ 的那些位置。

通过感性观察可以发现，下面这两件事是等价的，严谨证明需要依靠拓扑学知识，这里不做展开：

存在一条 $(1,1)\to (n,m)$ 的四连通路径，且路径上不经过任何 $B_x$ 中的格子；
在 $B_x$ $B_{x}$ 中，不存在一个八连通分量同时接触
- 上边界或右边界；
- 下边界或左边界。

我们可以用 BFS 判断，复杂度是 $O(nm)$ 。

1005 列车停放站

对于这种覆盖的问题，通常是需要通过贪心和考虑类似“第一个位置”这样的思路去做的。

对于每个询问 $(x,y)$ ，考虑 $i=\arg\max_{j} \{l_j \mid r_j\le y\}$ 。

如果 $l_i<x$ 或者 $\arg\max$ 的集合是空的，说明没有合法答案，答案就是 $0$ 。

否则答案至少是 $1$ ，那么假设最优解选择了 $i_1,i_2,\dots,i_k$ ，由于最优解选择的区间都是合法的，那么有 $r_{i_k}\le y$ ；根据 $i$ 的定义，我们可以知道 $l_i\ge l_{i_k}$ ，于是调整 $i_k$ 为 $i$ 后仍然是一个最优解。如果有多个满足条件的 $i$ ，那么对于每一个满足条件的 $i$ ，交换论证都成立，因此任选即可。虽然 $i$ 不一定唯一，但是 $l_i$ 一定是唯一的。

设 $f(x,y)$ 是询问 $(x,y)$ 的答案，那么 $f(x,y)=\begin{cases}0\quad l_i<x \operatorname{or} \{j\mid r_j\le y\}=\varnothing\\1+f(x,l_i)\quad \text{otherwise}\end{cases}$ 。

于是我们可以离散化后预处理，然后对每一个询问倍增，这样复杂度是 $O((n+m)\log n)$ 。

1006 游戏

其实这个题目并不是很难，但是看上去比较吓人，所以过的人不多。

重要的观察只是：如果某一个属性对最终答案能够产生贡献，那么它一定要 $\ge 40$ 。

将每一个属性分开来看，设属性 $i$ 最多能达到的值为 $s_i$ ，将 $s_i$ 降序排序，由于 $\sum s_i\le 150$ ，并且 $s_i\ge 0$ ，那么可以反证法证明 $s_4<40$ ，即只有 $s_1,s_2,s_3$ 有可能产生贡献。

于是背包 DP 即可，复杂度 $O(mk^3)$ 。

1009 GCD

对于每一个 $i$ ，令 $g_j=\gcd(b_j,b_{j+1},\dots,b_i)$ ，根据 $\gcd$ 的结合律，有 $g_j=\gcd(b_j,g_{j+1})(j<i)$ ，又根据 $\gcd$ 性质有 $g_j\le g_{j+1}$ 。

当 $g_j<g_{j+1}$ 时，这等价于 $\cfrac{g_{j+1}}{g_j}>1$ ，又因为 $g_j\mid g_{j+1}$ ，于是 $g_j\le \cfrac{1}{2} g_{j+1}$ 。又因为 $g_j\ge 1$ ，所以从 $g_i=b_i$ 开始，到 $g_1$ 为止，至多只有 $O(\log V)$ 个不同的值，其中 $V=10^9$ ，代表值域。

根据这个思想，我们可以对每一个前缀 $[1,i]$ 预处理出它的后缀等值区间，具体地讲，用 vector 存每一个前缀对应的 $O(\log V)$ 个区间，更新的时候，可以从 $i-1$ 继承而来，然后给每一块的 $g\gets (g,a_i)$ 并且再次双指针合并，这样预处理是 $O(n\log^2 V)$ 的，其中有一个 $O(\log V)$ 是求 gcd 的复杂度。

对于这 $O(\log V)$ 个区间 $[L,R]$ 来说，我们有这样的一个贪心的调整论证法：如果最优解存在一个不在 $L$ 处的操作，我们可以把它取消掉，并且让这个操作在 $L$ 处进行，那么操作仍然是合法的。根据这样的思路，每一段的操作都可以在区间的左端点处进行。

对于第一个区间 $[L_1,R_1]$ ，容易看出 $L_1$ 处的操作数 $t_1\ge \left\lceil\cfrac{\max_{L_1\le j\le R_1} a_j}{g_{L_1}}\right\rceil$ 。

如果 $t_1>\left\lceil\cfrac{\max_{L_1\le j\le R_1} a_j}{g_{L_1}}\right\rceil$ ，我们可以把多出来的操作都放到 $L_2$ 处，由于 $g_{L_2}>g_{L_1}$ ，所以操作仍然合法，那么我们就可以断定 $t_1=\left\lceil\cfrac{\max_{L_1\le j\le R_1} a_j}{g_{L_1}}\right\rceil$ 。

对于后续的段，我们可以记录一下前面累积减去了多少，然后最大值用 ST 表查，于是单次询问复杂度 $O(\log V)$ 。

upd: 同样的前缀思路也被用在了 CCPC Final 2025 L 题。

1002 1003 通行证

把二进制数看成集合，设询问的集合是 $x$ ，那么对于每一个位置 $(i,j)$ ，它的答案为 $k$ 的充要条件是，在这个十字框中，所有距离 $\le k-1$ 的 $(i,j)$ 都满足 $a_{ij}\subseteq x$ ；距离 $=k$ 的 $(i,j)$ 中存在一个 $a_{ij}\not\subseteq x$ 。

简单讨论可以发现这这等价于 $\bigcup_{d_{ij}\le k-1} a_{ij}\subseteq x$ 并且 $\bigcup_{d_{ij}\le k} a_{ij}\not\subseteq x$ 。

对于一个给定的查询 $x$ ，我们可以形式化地写出答案：

$Q(x)=\sum_{i=1}^n \sum_{j=1}^n \sum_{k=1}^{\infty} \left[\bigcup_{d_{ij}\le k} a_{ij}\subseteq x\right]$

反过来看，可以枚举每一个格子 $(i,j)$ 对哪些 $x$ 产生了贡献，这就导出了一个 $O(n^3)$ 的做法：

枚举每一个格子 $(i,j)$ ，再枚举距离 $k$ ，给所有的满足 $\bigcup_{d_{ij}\le k} a_{ij}\subseteq x$ 的 $x$ 的答案 $+1$ 。

考虑进一步优化。对于每一个位置 $(i,j)$ ，设 $V$ 是值域，其二进制位最多改变 $O(\log V)$ 次，这就导出了一个 $O(n^2\log V)$ 的优化：

用 DP 求出上下左右每一个位置第一次变化的位置，最后把这些位置取出来排序，给相同的 $\bigcup_{d_{ij}\le k} a_{ij}$ 统一操作即可。

关于给所有超集 $+1$ 的操作，这可以用 SOS DP 以 $O(V\log V)$ 的复杂度解决。