「POI 2020/2021 R1」Gra platformowa 题解

算法思路分析

关键观察

1. 洞的处理顺序

vector<pair<int, int>> holes;
for (int i = 1; i <= n; i++) {
    int k; cin >> k;
    while (k--) {
        int x; cin >> x;
        holes.push_back({-x, i});  // 存储负值便于从右向左排序
    }
}
sort(holes.begin(), holes.end());

• 将洞按位置从右向左排序（通过存储负值实现）
• 这样处理时能保证先处理靠近终点的洞

2. 状态定义与转移

vector<int> f(n + 1);
for (auto [x, i] : holes) {
    f[i]++;  // 遇到洞，该层跳跃次数+1
    
    if (i + 1 <= n) {
        int z = min(f[i], f[i + 1]);
        f[i] = f[i + 1] = z;  // 合并相邻层的答案
    }
}

状态含义：

• $f[i]$ 表示从第 $i$ 层平台当前处理位置到达终点所需的最小跳跃次数

转移逻辑：

1. 遇到洞时：$f[i] = f[i] + 1$
   • 因为必须用一次跳跃来通过这个洞
2. 合并相邻层：$f[i] = f[i+1] = \min(f[i], f[i+1])$
   • 利用 $\texttt{B}$ 操作可以在相邻层间转移
   • 取最小值保证最优性

算法正确性证明

为什么从右向左处理？

• 终点在位置 $X$，从右向左处理确保每个洞的处理都基于其后继状态的最优解
• 符合动态规划的"后效性"消除原则

为什么合并相邻层？

考虑相邻的两层平台 $i$ 和 $i+1$：

• 通过 $\texttt{B}$ 操作，可以从第 $i$ 层跳到第 $i+1$ 层
• 反之，从第 $i+1$ 层也可以通过某种方式影响第 $i$ 层
• 取最小值确保了两层之间的最优连通性

复杂度分析

• 时间复杂度：$O(\sum k \cdot \log(\sum k) + z)$
  • 排序洞：$O(\sum k \cdot \log(\sum k))$
  • 处理洞：$O(\sum k)$
  • 回答查询：$O(z)$
• 空间复杂度：$O(n + \sum k)$

完整代码解释

#include <bits/stdc++.h>
using namespace std;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, X, z;
    cin >> n >> X >> z;
    vector<pair<int, int>> holes;

    // 读取所有洞，存储为(负位置, 层号)
    for (int i = 1; i <= n; i++) {
        int k;
        cin >> k;
        while (k--) {
            int x;
            cin >> x;
            holes.push_back({-x, i});  // 负号实现从右向左排序
        }
    }

    // 按位置从右向左排序
    sort(holes.begin(), holes.end());
    
    // f[i]: 从第i层当前处理位置到终点的最小跳跃次数
    vector<int> f(n + 1);

    // 从右向左处理每个洞
    for (auto [x, i] : holes) {
        f[i]++;  // 遇到洞，需要一次跳跃

        // 合并相邻层的答案
        if (i + 1 <= n) {
            int z = min(f[i], f[i + 1]);
            f[i] = f[i + 1] = z;
        }
    }

    // 回答查询
    while (z--) {
        int p;
        cin >> p;
        cout << f[p] << "\n";  // 输出从第p层起点到终点的答案
    }
}

算法优势

1. 简洁高效：代码非常简短，但正确解决了问题
2. 利用题目性质：充分利用了"洞不相邻"的条件
3. 线性复杂度：相对于平台长度 $X$ 是 $O(1)$ 的
4. 支持多查询：预处理后可以 $O(1)$ 回答每个查询

适用场景

这种方法特别适用于：

• $X$ 很大（达到 $10^9$）的情况
• 洞的总数 $\sum k$ 在可接受范围内
• 需要支持大量查询