「JOI Open 2019」病毒实验

zhoujinchong2004 @ 2025-10-25 19:34:43

一、问题分析与数学建模

1.1 问题本质

这是一道BFS + 并查集 + 位运算 + 状态模拟的综合问题，核心在于理解病毒传播的长期稳定状态。

问题形式化

给定：

$R \times C$ 的网格，每个位置 $(i,j)$ 有抵抗力 $U_{i,j}$
一天有 $M$ 个时段，每个时段风向固定（周期性重复）
风向：N（北）、S（南）、W（西）、E（东）

感染规则：

如果位置 $(i,j)$ 连续 $U_{i,j}$ 个时段都满足"风从某个方向吹来，且该方向的邻居已感染"，则下一时段被感染
$U_{i,j} = 0$ 表示永远不会被感染

目标：

选择一个初始感染者
计算 $10^{100}$ 天后的最少感染人数
统计达到最少感染人数的初始选择方案数

1.2 核心数学观察

观察 1：时间的周期性

引理 1：由于风向按天周期循环，经过足够长时间后，病毒传播会达到一个稳定状态。

证明：

风向序列是周期为 $M$ 的循环
感染状态只能单调增加（已感染者不会恢复）
网格大小有限（最多 $R \times C$ 个状态）
因此必然在有限时间内达到稳定状态 ✓

推论： $10^{100}$ 天后的状态等价于"无限时间后的稳定状态"。

观察 2：方向掩码的概念

定义方向掩码 $\texttt{mask}$ ：一个 4 位二进制数，表示四个方向的组合。

$$\texttt{mask} = b_3 b_2 b_1 b_0 \quad (b_i \in \{0, 1\}) $$

其中：

$b_0 = 1$ ：北方向（N）有感染邻居
$b_1 = 1$ ：南方向（S）有感染邻居
$b_2 = 1$ ：西方向（W）有感染邻居
$b_3 = 1$ ：东方向（E）有感染邻居

例如： $\texttt{mask} = 0101_2 = 5$ 表示南方和北方都有感染邻居。

观察 3：最长持续时间的计算

定义： $\texttt{mxlen}[\texttt{mask}]$ 表示从某个时刻开始，连续满足掩码 $\texttt{mask}$ 中所有方向条件的最长时间。

关键问题：如何计算 $\texttt{mxlen}[\texttt{mask}]$ ？

算法思想：

将风向序列扩展为 $s + s$ （两个周期）
从右往左扫描，维护每个方向最后出现的位置
对于每个起始位置 $i$ 和每个掩码 $\texttt{mask}$ ，计算满足条件的最长时间

数学推导：

设 $\texttt{app}[d]$ 表示方向 $d$ 最后一次出现的位置（从右往左更新）。

对于起始位置 $i$ 和掩码 $\texttt{mask}$ ：

掩码中包含的方向： $d_1, d_2, \ldots, d_k$
这些方向最后出现位置：$\texttt{app}[d_1], \texttt{app}[d_2], \ldots, \texttt{app}[d_k]$
最晚出现的方向限制了持续时间： $\max(\texttt{app}[d_1], \ldots, \texttt{app}[d_k])$

算法：

按 $\texttt{app}$ 值排序方向： $q_1, q_2, q_3, q_4$ （从早到晚）
对于前缀掩码 $\{q_1\}, \{q_1, q_2\}, \{q_1, q_2, q_3\}, \{q_1, q_2, q_3, q_4\}$：
- 持续时间 = 下一个方向出现位置 - 当前位置
- 更新 $\texttt{mxlen}[\texttt{mask}]$

观察 4：可行感染条件

定义： $\texttt{okmask}[i][j]$ 表示位置 $(i,j)$ 可以被哪些方向掩码组合感染。

判断准则：掩码 $\texttt{mask}$ 可行当且仅当：

\texttt{mxlen}[\texttt{mask}] \ge U_{i,j}

直观理解：

如果某个方向组合能持续至少 $U_{i,j}$ 个时段
且这些方向的邻居都已感染
则该位置会被感染

观察 5：并查集的作用

关键洞察：在稳定状态下，某些位置会"最终连通"。

定义"最终连通"：

位置 $A$ $A$ 和 $B$ $B$ 最终连通，当且仅当：
- 从 $A$ 开始的感染可以传播到 $B$
- 从 $B$ 开始的感染可以传播到 $A$

并查集维护：

使用并查集 $\texttt{fa}[]$ 维护最终连通的等价类
迭代合并：反复尝试从每个连通分量代表扩散，找到可以相互到达的分量并合并
直到没有新的合并发生（达到稳定状态）

1.3 算法框架

阶段 1：预处理风向信息

计算 $\texttt{mxlen}[\texttt{mask}]$ 对于所有 $\texttt{mask} \in [0, 15]$

阶段 2：预计算可行掩码

对每个位置 $(i,j)$ ，计算 $\texttt{okmask}[i][j]$

阶段 3：并查集迭代合并

重复以下操作直到收敛：
1. 对每个未标记的连通分量代表，进行 BFS
2. 如果 BFS 能到达另一个分量，合并这两个分量
3. 如果 BFS 无法扩展，标记该分量

阶段 4：枚举答案

对每个已标记的连通分量代表，进行 BFS 计算感染人数
统计最小感染人数和方案数

二、算法设计与实现

2.1 方向掩码的数学性质

命题 1：对于任意两个掩码 $\texttt{mask}_1 \subseteq \texttt{mask}_2$ （集合包含关系），有：

$$\texttt{mxlen}[\texttt{mask}_1] \ge \texttt{mxlen}[\texttt{mask}_2] $$

证明：

$\texttt{mask}_1$ 包含的方向更少，条件更宽松
满足 $\texttt{mask}_2$ 的时间段必然满足 $\texttt{mask}_1$
因此 $\texttt{mask}_1$ 的最长持续时间至少和 $\texttt{mask}_2$ 一样长 ✓

2.2 BFS 感染模拟

函数：bool check(int x, int y)

功能：判断位置 $(x,y)$ 是否可以被当前已感染的邻居感染。

算法：

遍历该位置的所有可行掩码 $\texttt{mask} \in \texttt{okmask}[x][y]$
对于每个掩码，检查掩码中包含的所有方向：
- 该方向的邻居是否存在且已感染（ $\texttt{ison}[tx][ty] = \texttt{true}$ ）
如果存在某个掩码的所有方向都满足条件，返回 true

数学含义：

存在某个方向组合，该组合能持续足够长时间（ $\ge U_{x,y}$ ）
且该组合中所有方向的邻居都已感染
则位置 $(x,y)$ 会被感染

函数：pair<int, pair<int, int>> bfs(int sx, int sy)

功能：从 $(sx, sy)$ 开始 BFS，模拟病毒传播。

返回值：

first：感染人数
second：第一个遇到的属于不同连通分量的位置（用于合并），如果不存在则为 $(-1, -1)$

算法流程：

初始化：
    将 (sx, sy) 标记为已感染
    加入队列和路径记录

BFS 循环：
    对于队列中的每个位置 (x, y)：
        遍历四个方向的邻居 (tx, ty)：
            如果邻居满足感染条件（check(tx, ty)）：
                如果邻居属于不同连通分量：
                    记录该邻居，跳出循环
                否则：
                    标记邻居为已感染
                    加入队列

清理：
    恢复所有标记（ison[][] = false）
    
返回：
    (感染人数, 不同分量的位置)

关键细节：

使用 $\texttt{ison}[][]$ 临时标记当前 BFS 中的感染状态
BFS 结束后清理标记，不影响下次调用
如果遇到不同连通分量，立即停止（用于合并）

三、代码模块详解

模块 1：全局变量与常量定义

#define N 640010  // 最大节点数 (800*800)
#define M 810     // 最大网格大小
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};  // 北南西东
int d, n, m;
int a[M][M];           // 抵抗力
int fa[N];             // 并查集父节点
int mxlen[16];         // 每个掩码的最长持续时间
int app[4];            // 每个方向最后出现位置
bool vis[M][M];        // 是否已稳定（不会再扩展）
bool ison[M][M];       // BFS中的临时感染标记
vector<int> okmask[M][M];  // 每个位置的可行掩码
string s;              // 风向序列

设计说明：

dx[], dy[]：方向数组，顺序为北(0)、南(1)、西(2)、东(3)
mxlen[mask]：16 种掩码（ $2^4$ ）的最长持续时间
vis[i][j]：该位置所在连通分量已达到稳定状态
ison[i][j]：BFS 过程中的临时标记，使用后会清零

模块 2：并查集操作

int getf(int x) {
    return x == fa[x] ? x : fa[x] = getf(fa[x]);
}

路径压缩的并查集：

递归查找根节点
路径压缩优化：将路径上所有节点直接指向根

一维编号：位置 $(i,j)$ 的编号为 $i \times m + j$ 。

模块 3：预处理风向信息

cin >> d >> n >> m >> s;
s = s + s;  // 扩展为两个周期

// 初始化最后出现位置为无穷大
for (int i = 0; i < 4; i++)
    app[i] = INF;

// 从右往左扫描
for (int i = s.size() - 1; i >= 0; i--) {
    // 更新每个方向的最后出现位置
    if (s[i] == 'N') app[0] = i;
    if (s[i] == 'S') app[1] = i;
    if (s[i] == 'W') app[2] = i;
    if (s[i] == 'E') app[3] = i;
    
    // 只处理第一个周期
    if (i < s.size() / 2) {
        // 按出现位置排序方向
        vector<int> qwq = {0, 1, 2, 3};
        sort(qwq.begin(), qwq.end(), [](const int &x, const int &y) {
            return app[x] < app[y];
        });
        
        // 计算每个前缀掩码的持续时间
        for (int j = 0, mask = 0; j < 4; j++) {
            mask |= 1 << qwq[j];  // 加入第j个方向
            int next_pos = (j == 3 ? INF : app[qwq[j + 1]]);
            mxlen[mask] = max(mxlen[mask], next_pos - i);
        }
    }
}

算法解析：

步骤 1：扩展序列为 $s + s$

目的：处理跨越周期边界的情况
例如：NWSE 扩展为 NWSENWSE

步骤 2：从右往左扫描，维护 $\texttt{app}[]$

$\texttt{app}[d]$ 表示方向 $d$ 在位置 $i$ 右侧（包括 $i$ ）最近出现的位置

步骤 3：对于每个起始位置 $i$

将四个方向按 $\texttt{app}$ 值排序：越早出现的越靠前
计算前缀掩码的持续时间

数学推导：

假设排序后的方向为 $q_0, q_1, q_2, q_3$ ，对应最后出现位置 $a_0 < a_1 < a_2 < a_3$ 。

对于掩码 $\texttt{mask} = \{q_0, q_1, \ldots, q_k\}$ ：

从位置 $i$ 开始，这些方向都必须出现
限制因素是最晚出现的方向 $q_k$ ，位置为 $a_k$
但下一个方向 $q_{k+1}$ 出现在 $a_{k+1}$ ，会破坏条件
因此持续时间为 $[i, a_{k+1})$ ，长度为 $a_{k+1} - i$

正确性：

如果 $j = 3$ （所有方向都包含），持续时间为 $\infty - i$ （设为 INF）
对所有起始位置 $i$ 取最大值，得到 $\texttt{mxlen}[\texttt{mask}]$ ✓

模块 4：预计算可行掩码

for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) {
        cin >> a[i][j];
        fa[i * m + j] = i * m + j;  // 初始化并查集
        
        if (a[i][j]) {  // 抵抗力 > 0
            // 遍历所有掩码
            for (int x = 0; x < 16; x++)
                if (mxlen[x] >= a[i][j])
                    okmask[i][j].push_back(x);
        } else {  // 抵抗力 = 0
            vis[i][j] = true;  // 永远不会被感染
        }
    }

逻辑：

对于抵抗力 $U_{i,j} > 0$ 的位置，找出所有满足 $\texttt{mxlen}[\texttt{mask}] \ge U_{i,j}$ 的掩码
对于抵抗力 = 0 的位置，标记为稳定（不参与传播）

模块 5：check 函数实现

bool check(int x, int y) {
    for (auto &mask : okmask[x][y]) {
        bool ok = true;
        
        // 检查掩码中的每个方向
        for (int i = 0; i < 4; i++)
            if ((mask >> i) & 1) {  // 如果方向i在掩码中
                int tx = x + dx[i], ty = y + dy[i];
                
                // 检查该方向的邻居是否已感染
                if (tx < 0 || tx >= n || ty < 0 || ty >= m || (!ison[tx][ty])) {
                    ok = false;
                    break;
                }
            }
        
        if (ok) return true;  // 找到一个满足条件的掩码
    }
    
    return false;  // 所有掩码都不满足
}

算法细节：

只需要找到一个可行掩码即可
掩码的每一位对应一个方向
位运算 (mask >> i) & 1 检查第 $i$ 位是否为 1

复杂度：

最多 16 个掩码
每个掩码最多检查 4 个方向
总复杂度 $O(16 \times 4) = O(64) = O(1)$

模块 6：BFS 函数实现

pair<int, pair<int, int>> bfs(int sx, int sy) {
    vector<pair<int, int>> pth;  // 记录路径
    queue<pair<int, int>> qu;
    qu.push(make_pair(sx, sy));
    pth.push_back(make_pair(sx, sy));
    ison[sx][sy] = true;
    pair<int, int> ret = make_pair(-1, -1);
    
    while (!qu.empty()) {
        auto [x, y] = qu.front();
        qu.pop();
        
        for (int i = 0; i < 4; i++) {
            int tx = x + dx[i], ty = y + dy[i];
            
            if (tx >= 0 && tx < n && ty >= 0 && ty < m && 
                (!ison[tx][ty]) && check(tx, ty)) {
                
                // 检查是否属于不同连通分量
                if (getf(tx * m + ty) != getf(sx * m + sy)) {
                    ret = make_pair(tx, ty);
                    break;
                }
                
                ison[tx][ty] = true;
                pth.push_back(make_pair(tx, ty));
                qu.push(make_pair(tx, ty));
            }
        }
        
        if (ret.F >= 0) break;  // 找到不同分量，停止
    }
    
    // 清理标记
    for (auto &[x, y] : pth)
        ison[x][y] = false;
    
    return make_pair(pth.size(), ret);
}

关键点：

路径记录：pth 记录所有访问过的位置，用于最后清理标记
并查集判断：
```
if (getf(tx * m + ty) != getf(sx * m + sy))
```
如果邻居属于不同连通分量，说明可以合并
立即停止：找到不同分量后立即停止，返回该位置用于合并
清理标记：BFS 结束后恢复 ison[][]，确保下次调用的正确性

模块 7：并查集迭代合并

while (true) {
    vector<pair<int, int>> seq, ret;
    
    // 收集所有未标记的连通分量代表
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (getf(i * m + j) == i * m + j && (!vis[i][j]))
                seq.push_back(make_pair(i, j));
    
    if (seq.empty()) break;  // 所有分量都已稳定
    
    // 对每个代表进行 BFS
    for (auto &[x, y] : seq) {
        auto v = bfs(x, y);
        ret.push_back(v.S);  // 记录可达的不同分量
    }
    
    // 处理合并
    for (int i = 0; i < seq.size(); i++) {
        if (ret[i] == make_pair(-1, -1))
            vis[seq[i].F][seq[i].S] = true;  // 无法扩展，标记为稳定
        else
            fa[getf(seq[i].F * m + seq[i].S)] = getf(ret[i].F * m + ret[i].S);  // 合并
    }
}

算法流程：

步骤 1：收集未稳定的连通分量代表

连通分量代表： $\texttt{getf}(i \times m + j) = i \times m + j$
未稳定： $\texttt{vis}[i][j] = \texttt{false}$

步骤 2：对每个代表进行 BFS

尝试扩展感染范围
记录第一个遇到的不同分量位置

步骤 3：处理结果

如果 BFS 返回 $(-1, -1)$ ：无法再扩展，标记为稳定
否则：合并两个分量

步骤 4：重复直到所有分量都稳定

收敛性证明：

引理 2：算法一定会在有限步内终止。

证明：

连通分量数量只减不增（合并操作）
每次迭代至少有一个分量被标记为稳定或被合并
最多 $n \times m$ 个分量
因此最多迭代 $n \times m$ 次

模块 8：枚举答案

pair<int, int> ans = make_pair(INF, INF);

for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
        if (a[i][j] && vis[i][j]) {  // 可以作为初始感染者且已稳定
            auto v = bfs(i, j);
            
            if (v.F < ans.F)
                ans = make_pair(v.F, v.F);  // 更新最小值
            else if (v.F == ans.F)
                ans.S += v.F;  // 累加方案数
        }

cout << ans.F << '\n' << ans.S << '\n';

逻辑：

条件 1： $a[i][j] > 0$

只有抵抗力 $> 0$ 的位置可以作为初始感染者

条件 2： $\texttt{vis}[i][j] = \texttt{true}$

该位置所在连通分量已稳定
这是优化：未稳定的分量不需要枚举（它们最终会合并到稳定分量中）

计算：

对每个候选位置进行 BFS，计算感染人数
维护最小感染人数和方案数

关于方案数的特殊处理：

if (v.F < ans.F)
    ans = make_pair(v.F, v.F);  // 新的最小值，方案数 = 感染人数
else if (v.F == ans.F)
    ans.S += v.F;  // 累加方案数

这里有一个技巧：ans.S 不是直接计数，而是累加感染人数。这是因为同一个连通分量中的所有位置感染人数相同，所以用感染人数来表示方案数。

四、正确性证明

4.1 预处理的正确性

定理 1：算法正确计算 $\texttt{mxlen}[\texttt{mask}]$ 。

证明：

考虑任意掩码 $\texttt{mask}$ 和起始时刻 $t$ 。

设掩码包含方向集合 $D = \{d_1, d_2, \ldots, d_k\}$ 。

定义持续时间 $T(t, \texttt{mask})$ ：

从时刻 $t$ 开始，连续满足"对于所有 $d \in D$ ，风向为 $d$ "的最长时间

关键观察：

在时间区间 $[t, t')$ 内，所有方向 $d \in D$ 都必须出现
限制因素是最晚出现的方向

算法通过以下步骤计算：

扩展序列为两个周期，处理边界情况
从右往左维护每个方向的最后出现位置
对于每个起始位置，按出现顺序计算前缀掩码的持续时间

因此算法正确。

4.2 并查集合并的正确性

定理 2：并查集迭代后，同一连通分量中的任意两个位置"最终等价"。

定义"最终等价"：位置 $A$ 和 $B$ 最终等价，当且仅当：

从 $A$ 开始的无限时间传播可以到达 $B$
从 $B$ 开始的无限时间传播可以到达 $A$

证明：

归纳假设：每次迭代后， $\texttt{fa}[]$ 正确维护已知的等价关系。

归纳步骤：

如果 BFS 从 $A$ 可以到达 $B$ （不同分量），说明 $A \rightarrow B$ 传播可行
在后续迭代中，如果从 $B$ 可以到达 $A$ （或它们已经间接连通），则合并
最终，所有可以相互到达的位置都在同一连通分量中

4.3 答案枚举的正确性

定理 3：算法正确计算最小感染人数和方案数。

证明：

完备性：

算法枚举所有抵抗力 $> 0$ 的稳定位置
这些位置可以作为初始感染者
对每个位置计算感染人数，取最小值

正确性：

BFS 正确模拟从给定位置开始的传播
由于已经达到稳定状态，BFS 的结果就是无限时间后的结果

方案数计算：

同一连通分量中的所有位置感染人数相同
通过累加感染人数来统计方案数

五、复杂度分析

5.1 时间复杂度

预处理阶段：

扩展序列： $O(M)$
计算 $\texttt{mxlen}$ ： $O(M \times 16 \times 4) = O(M)$
计算 $\texttt{okmask}$ ： $O(RC \times 16) = O(RC)$

并查集迭代阶段：

外层循环：最多 $O(RC)$ 次
每次迭代：
- 收集代表： $O(RC)$
- BFS：每个位置最多访问一次， $O(RC)$
- 合并： $O(RC \times \alpha(RC))$ （ $\alpha$ 是反阿克曼函数）
总复杂度： $O((RC)^2 \alpha(RC))$

答案枚举阶段：

枚举位置： $O(RC)$
每次 BFS： $O(RC)$
总复杂度： $O((RC)^2)$

总时间复杂度： $O(M + (RC)^2)$

对于 $M \le 10^5$ ， $R, C \le 800$ ，约为 $10^5 + 6.4 \times 10^5 = 7.4 \times 10^5$ 次操作（实际会更少，因为并查集迭代通常很快收敛）。

5.2 空间复杂度

风向序列： $O(M)$
网格数组： $O(RC)$
并查集： $O(RC)$
$\texttt{mxlen}$ ： $O(16) = O(1)$
$\texttt{okmask}$ ： $O(RC \times 16) = O(RC)$

总空间复杂度： $O(M + RC)$

六、算法优化与扩展

6.1 关键优化技巧

位运算优化
- 用 4 位掩码表示方向组合，高效紧凑
- 位运算判断方向包含关系
并查集路径压缩
- 降低查询和合并的复杂度
提前终止
- BFS 遇到不同分量立即停止
- 避免不必要的扩展
状态清理
- ison[][] 使用后立即清零
- 避免状态污染

6.2 算法的创新点

传统思路 vs. 本题算法：

传统思路	本题算法
直接模拟 $10^{100}$ 天	利用周期性，计算稳定状态
每次完整模拟传播过程	预计算可行掩码，快速判断
独立计算每个初始位置	并查集合并等价位置，减少计算

核心创新：

将"无限时间后的稳定状态"转化为"并查集等价类"
用位运算和预处理加速感染条件判断
迭代合并而非直接模拟

6.3 相关问题与扩展

变种问题
- 不同的风向模式（非周期性）
- 不同的感染规则（需要多个方向同时满足）
- 动态添加/删除初始感染者
优化方向
- 更快的稳定状态检测
- 并行化 BFS
- 增量更新

七、知识点总结

7.1 核心算法技巧

✅ BFS
- 模拟病毒传播
- 计算连通分量大小
✅ 并查集
- 维护等价关系
- 迭代合并连通分量
✅ 位运算
- 紧凑表示方向组合
- 高效判断包含关系
✅ 状态模拟
- 利用周期性
- 计算稳定状态
✅ 预处理优化
- 预计算可行条件
- 减少重复计算

八、总结

8.1 算法精髓

本题采用的BFS + 并查集 + 位运算 + 状态分析算法的核心思想：

周期性利用：将 $10^{100}$ 天的模拟转化为稳定状态分析
位运算优化：用掩码高效表示和判断方向组合
并查集合并：找出最终会相互连通的等价类
迭代收敛：通过有限次迭代达到稳定状态
预处理加速：预计算可行条件，快速判断感染

8.2 学习价值

通过这道题，我们学习了：

如何处理具有周期性的长期模拟问题
位运算在组合优化中的应用
并查集维护动态等价关系的技巧
BFS 与并查集的结合使用
从直接模拟到状态分析的思维转变

ID

4102

时间

1000ms

内存

256MiB

难度

标签

递交数

已通过

上传者

zhoujinchong2004

1 条题解