1952E - 扫线 详细题解（官方标程版）

题意规范化翻译

有一个一维扫雷游戏，只有一行格子。 给定长度为 $n$ 的数组 $a$，满足 $0\le a_i\le 2$。 每个 $a_i$ 表示第 $i$ 格左右相邻格子的地雷总数（不含自身）。

设 $x_i\in\{0,1\}$ 表示第 $i$ 格是否有地雷：

• $x_i=1$：有地雷
• $x_i=0$：没有地雷

则对每个 $i$ 必须满足：

$$a_i = x_{i-1} + x_{i+1}$$

边界约定： $x_0 = 0,\ x_{n+1} = 0$（最左、最右外都没有地雷）。

求合法地雷布局 $x$ 的方案数，答案对 $20240401$ 取模。 （标程指出：答案只会是 $0,1,2$，取模无实际意义。）

---

核心结论（标程原话）

整个数组 $x_2,\dots,x_n$ 由 $x_1$ 唯一确定。 $x_1$ 只有 $0$ 或 $1$ 两种可能，因此总方案数 $\le 2$。

---

严格推导（标程逻辑）

由约束：

$$a_i = x_{i-1} + x_{i+1}$$

移项得到递推式：

$$x_{i+1} = a_i - x_{i-1}$$

第一步：由 $a_1$ 直接得 $x_2$

$i=1$ 时：

$$a_1 = x_0 + x_2 = x_2$$

所以：

$$x_2 = a_1$$

第二步：递推推出全部 $x$

对 $i=2,3,\dots,n-1$：

$$x_{i+1} = a_i - x_{i-1}$$

每一步必须满足：

$$x_i\in\{0,1\}$$

否则该 $x_1$ 对应的方案非法。

第三步：最终校验（关键）

$i=n$ 时：

$$a_n = x_{n-1} + x_{n+1} = x_{n-1}$$

所以必须满足：

$$a_n = x_{n-1}$$

不满足则方案非法。

---

算法流程（标准 $O(n)$）

1. 枚举 $x_1\in\{0,1\}$
2. 对每个 $x_1$：
   • 令 $x_2 = a_1$
   • 若 $x_2\notin\{0,1\}$，非法
   • 递推 $x_3\sim x_n$：$x_{i+1}=a_i-x_{i-1}$
   • 若任意 $x_i\notin\{0,1\}$，非法
   • 最后检查 $a_n = x_{n-1}$
3. 统计合法的 $x_1$ 数量即为答案。

---

特殊情况：$n=1$

此时：

$$a_1 = x_0 + x_2 = 0$$

只有 $a_1=0$ 时有 $1$ 种方案，否则 $0$。

---

标程风格可AC代码（极简、无冗余）

#include <iostream>
#include <vector>
using namespace std;

const int MOD = 20240401;

int test(int n, vector<int>& a, int x1) {
    vector<int> x(n + 2, 0);
    x[1] = x1;
    x[2] = a[1];
    if (x[2] < 0 || x[2] > 1) return 0;

    for (int i = 2; i <= n - 1; ++i) {
        x[i+1] = a[i] - x[i-1];
        if (x[i+1] < 0 || x[i+1] > 1)
            return 0;
    }

    return (a[n] == x[n-1]) ? 1 : 0;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    vector<int> a(n+1);
    for (int i=1; i<=n; ++i) cin >> a[i];

    if (n == 1) {
        cout << (a[1] == 0) << endl;
        return 0;
    }

    int ans = test(n,a,0) + test(n,a,1);
    cout << ans % MOD << endl;
}

---

复杂度

• 时间：$O(n)$
• 空间：$O(n)$（可优化到 $O(1)$，标程常用）

---

答案为什么最多是 2？

因为只有两个可能：

$$x_1 = 0 \quad \text{或} \quad x_1 = 1$$

每个唯一确定整个布局，最多两个合法。