落沙：题解

思路

把每块沙子视为一个顶点。若扰动顶点 (u) 会直接扰动顶点 (v)，就在 (u\to v) 之间连边。对位于 ((r,c)) 的沙块，只需连接：

1. 同列正上方紧邻的沙块；
2. 同列下方最近的沙块；
3. 左右相邻列中行号不小于 (r) 的最近沙块。

更远的沙块会由这些最近沙块继续触发，因此每个顶点只有常数条边，图的可达关系恰好等于真实的连锁扰动关系。

第 (c) 列若要求至少落下 (a_c>0) 块沙子，则从下往上数第 (a_c) 块沙子必须被扰动，称它为该列的特殊点。反之，只要这个特殊点被扰动，它和下方的沙子都会落下，该列要求就满足。

先求触发图的强连通分量并缩点。若一个特殊分量能够到达另一个特殊分量，那么满足前者时后者必然同时满足，后者可以删去。按拓扑序传播“是否已有特殊祖先”即可在线性时间完成删除。

剩余特殊分量按所在列从左到右编号。题目的几何结构保证：任意缩点分量能够到达的剩余特殊分量构成一个连续区间。逆拓扑序维护每个分量可达的最左、最右编号，就得到所有可选操作对应的区间。

最后变成经典问题：用最少区间覆盖从左到右的全部特殊点。每次对最左侧未覆盖点，选择所有左端点不超过它的区间中右端点最大的一个。这一贪心是最优的。

做法

子任务 1

当 (n\cdot m\le 20) 时，求出每个沙块的可达闭包。枚举所有被主动扰动的沙块子集，检查其可达并集是否包含全部特殊点，取最少操作数。

复杂度为 (O(2^S\cdot S+S^2))，其中 (S) 是沙块数。

子任务 2

当 (n\cdot m\le 2000) 时，从每个沙块出发做一次图搜索，显式求出两两可达关系。删除被其他特殊点到达的特殊点后，扫描每个起点可覆盖的特殊点区间，再做区间覆盖贪心。

复杂度为 (O(S(S+E))=O(S^2))，空间复杂度为 (O(S^2)) 位。

子任务 3

使用迭代式 Kosaraju 算法求强连通分量。缩点图是 DAG：

• 正向拓扑传播特殊祖先，删除冗余特殊分量；
• 逆向拓扑传播最左、最右特殊点编号，得到每个分量的覆盖区间；
• 对区间左端点做前缀最大值，贪心跳到当前能够覆盖的最右位置。

整个过程为线性复杂度。

正确性证明

引理 1

稀疏触发图中从 (u) 可达 (v)，当且仅当扰动沙块 (u) 会使沙块 (v) 落下。

证明：每条边都对应下落过程中一次真实的相邻扰动，所以图上可达必然会被扰动。反过来，同列下方或相邻列中的更远沙块，都会先经过所连的最近沙块，再由最近沙块继续触发；同列上方只有初始时紧邻的一块可能被直接扰动。因此所有真实直接触发都由图中路径表示。证毕。

引理 2

第 (c) 列满足要求，当且仅当该列从下往上第 (a_c) 块沙子被扰动。

证明：同列中一块沙子被扰动后，它下方的沙子都会被扰动，所以落下的沙块始终形成一个后缀。后缀长度至少为 (a_c)，恰好等价于第 (a_c) 块沙子属于该后缀。证毕。

引理 3

若特殊分量 (A) 能到达特殊分量 (B)，则删去 (B) 不改变最优答案。

证明：任何使 (A) 被扰动的操作，沿可达路径也一定使 (B) 被扰动。因此覆盖 (A) 的方案自动覆盖 (B)，(B) 不再提供独立约束。证毕。

引理 4

任意分量可达的剩余特殊分量按列构成连续区间。

证明：下落路径只能在相邻列间传播。若某分量能到达左右两个剩余特殊分量，则传播路径跨过中间列时会触发足够低的沙块；中间仍未被删除的特殊分量若未被触发，就会与这两条传播路径矛盾。故中间的剩余特殊分量也必可达。证毕。

引理 5

对最左侧未覆盖特殊点，选择可覆盖它且右端点最大的区间，不劣于任何最优方案的第一段。

证明：任意可行方案的第一段必须覆盖该点。把它替换为右端点最大的可选区间，不会减少已覆盖范围，也不会增加区间数。证毕。

定理

算法输出完成谜题所需的最少操作次数。

证明：由引理 1、2，问题等价于选择若干图中起点覆盖全部特殊分量；由引理 3 可安全删除冗余特殊分量；由引理 4，每个起点对应一个区间；由引理 5，区间贪心使用最少区间。因此输出即最少操作数。证毕。

复杂度

设沙块数为 (S)，稀疏图边数 (E=O(S))。

满分算法时间复杂度为 (O(nm+S+E))，空间复杂度为 (O(nm+S+E))。