「POI2010」青蛙 Frog 题解

题目概述

在小溪上有 $n$ 个岩石，位置分别为 $p_1, p_2, ..., p_n$（按升序排列）。一只青蛙在某个岩石上，每次跳跃会选择距离它第 $k$ 近的岩石。如果存在多个这样的岩石，选择距离源头最近的那个。题目要求对每个可能的起始岩石，计算经过 $m$ 次跳跃后的位置。

解题思路

关键观察

1. 跳跃的确定性：对于每个位置 $i$，它的下一个跳跃位置是唯一确定的
2. 单调性：由于岩石位置是单调递增的，可以使用双指针技术高效计算每个位置的下一个跳跃位置
3. 大规模跳跃：$m$ 可以达到 $10^{18}$，必须使用倍增（二进制拆分）技术

算法步骤

1. 计算单次跳跃目标

对于每个位置 $i$，我们需要找到距离它第 $k$ 近的岩石。使用双指针维护一个窗口 $[l, r]$，使得：

• 窗口内包含 $k+1$ 个岩石（包括当前位置）
• 窗口覆盖距离当前位置最近的 $k$ 个岩石

具体实现：

• 初始化 $l = 1$, $r = k + 1$
• 对于每个 $i$ 从 $2$ 到 $n-1$：
  • 移动右指针直到 $p[i] - p[l] > p[r + 1] - p[i]$ 不再成立
  • 比较左右两端的距离，选择更近的一侧

2. 倍增处理

使用动态规划实现倍增：

• dp[0][i] 存储从位置 $i$ 跳跃 1 次后的位置
• 通过 dp[j][i] = dp[j-1][dp[j-1][i]] 计算跳跃 $2^j$ 次后的位置

3. 二进制拆分

将 $m$ 按二进制拆分，对于每个为 1 的位，应用对应的跳跃次数。

复杂度分析

• 预处理：$O(n)$，使用双指针计算每个位置的下一个跳跃目标
• 倍增预处理：$O(n \log m)$
• 查询：$O(n \log m)$
• 总复杂度：$O(n \log m)$，可以处理 $n \leq 10^6$, $m \leq 10^{18}$ 的数据规模

代码实现

#include <cstdio>
#define MAXN 1000005
using lli = long long;

int n, k, o, l, r;
lli m, p[MAXN], dp[2][MAXN], ans[MAXN];

int main() {
    scanf("%d %d %lld", &n, &k, &m);

    for (int i = 1; i <= n; ++i)
        scanf(" %lld", p + i);

    // 计算每个位置的下一次跳跃位置
    dp[0][1] = k + 1;
    l = 1, r = k + 1;

    for (int i = 2; i < n; ++i) {
        // 调整窗口，保持窗口内有k+1个点
        while (r < n && p[i] - p[l] > p[r + 1] - p[i])
            ++l, ++r;

        // 选择距离更近的一侧
        if (p[r] - p[i] > p[i] - p[l])
            dp[0][i] = r;
        else
            dp[0][i] = l;
    }

    dp[0][n] = n - k;

    // 初始化答案数组
    for (int i = 1; i <= n; ++i)
        ans[i] = i;

    // 使用倍增处理m次跳跃
    while (m) {
        if (m & 1LL) {
            for (int i = 1; i <= n; ++i)
                ans[i] = dp[o][ans[i]];
        }

        o ^= 1, m >>= 1;

        // 计算下一层倍增
        for (int i = 1; i <= n; ++i)
            dp[o][i] = dp[o ^ 1][dp[o ^ 1][i]];
    }

    // 输出结果
    for (int i = 1; i <= n; ++i)
        printf("%lld ", p[ans[i]]);

    putchar('\n');
    return 0;
}

样例解释

对于样例输入：

5 2 4
1 2 4 7 10

输出：

1 1 3 1 1

这表示：

• 从位置1开始，4次跳跃后仍在位置1
• 从位置2开始，4次跳跃后到达位置1
• 从位置4开始，4次跳跃后到达位置3
• 从位置7和10开始，4次跳跃后都到达位置1

总结

本题的关键在于：

1. 使用双指针高效计算每个位置的下一个跳跃目标
2. 使用倍增技术处理大规模的跳跃次数
3. 注意边界情况的处理（第一个和最后一个岩石）

这种结合了双指针和倍增的技巧在解决大规模跳跃类问题时非常有效。