题解 - 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$，满足：

1. $g_1=\min_{1\le j\le m} a_{1j}$。
2. $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$：

1. 对 $i=1$，显然成立；
2. 若 $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,1)\to (n,m)$ 的四连通路径，且路径上不经过任何 $B_x$ 中的格子；
2. 在 $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$，代表值域。

根据这个思想，我们可以对每一个 $i$ 处理出一个 $L_i=\min\{j\mid g_j=b_i\}$，根据前面的单调性，这是可以二分的。

具体地说，我们二分一个 $m$，然后用 ST 表查询 $m\sim i$ 的 $\gcd$ 即可，那么这样的话复杂度是 $O(n\log n\log V)$；预处理 ST 表的复杂度也是 $O(n\log n\log V)$。

对于每一个询问，我们可以先暴力的找出这 $O(\log n)$ 个区间，然后对于每一个区间 $[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 n)$。

这样的话总复杂度为 $O(n\log n\log V+q\log n)$。

1002 1003 通行证

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

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

反过来看，设 $S_{k-1}=\bigcup_{d_{ij}\le k-1} a_{ij}$，$S_{k}=\bigcup_{d_{ij}\le k} a_{ij}$，那么对于所有满足 $S_{k-1}\subseteq Q$ 并且 $S_k\not\subseteq Q$ 的询问 $Q$，答案都会被 $+k$。

这里特殊之处在于 $S_{k-1}\subseteq S_k$，那么根据 SOS DP 的方法，我们可以给 $dp(S_{k-1}) \gets dp(S_{k-1}) + k$，并且 $dp(S_k)\gets dp(S_k)-k$。

那么朴素预处理加上一个 SOS DP 就可以做到 $O(n^3+V\log V)$ 预处理，其中 $V=2^{15}$ 代表值域。

对于询问，我们发现在 $\ge 2^{15}$ 的二进制位都是没有用的，所以我们可以给每一个询问取前 $15$ 个二进制位，直接 $O(1)$ 回答。

进一步地，我们可以发现，当 $S_{k-1}\neq S_k$ 的 $k$ 的数量很少，至多只有 $15$ 个。

我们可以 $O(\log V)$ 枚举每一个位，然后 $O(n^2)$ 对每个 $(i,j)$ 处理出来上下左右四个方向的第 $k$ 位发生变化并且距离最近的那个位置。

这样的话复杂度就变成了 $O(n^2\log V+V\log V)$ 预处理，$O(q)$ 处理询问。

实现上来说，我们给每一个位置都加入一个边界当作变化的位置 $\min(i+1,j+1,n-i+2,n-j+2)$，当遍历到这里的时候就不再给 DP 数组减。