[POI 2010] ZAB-Frog

GitHub跳转原题关系图返回列表

双指针求每块石头的一跳终点，再对整个映射做二进制快速幂。

OJ: luogu

题目 ID: P3509

难度:省选/NOI-

标签:双指针倍增函数复合python

日期: 2026-07-16 18:28

目录

  1. 题意
  2. 思路
  3. Python 知识
  4. 代码
  5. 复杂度
  6. 总结

题意

石头坐标严格递增。青蛙每次跳到距离排名为 k 的石头，距离相同则选坐标较小者。对每个起点求跳 m 次后的终点。

思路

对当前石头 i，包含它在内的 k + 1 个最近点在有序坐标中一定构成连续窗口 [left, right]。窗口右侧下一个点比左端点更近时，就整体右移。指针只增不减，所以所有一跳终点可在线性时间求出。

窗口中离 i 更远的端点就是目标；两端距离相等时选择左端，恰好满足题目的平局规则。

得到一跳映射 transition 后，要计算它复合 m 次。像快速幂一样：

  • 当前二进制位为 1 时，把答案映射复合一次；
  • 每轮令 transition = transition o transition。

Python 知识

  • array("q") 保存最高可达 101810^{18} 的坐标，array("i") 保存下标，显著降低百万规模数据的内存。
  • 自定义 read_ints() 用 os.read 分块解析整数，避免 read().split() 为一百万个 token 创建大量 bytes 对象。
  • map(transition.__getitem__, answer) 表示把映射同时作用到所有当前答案上。
  • while moves: 与位运算实现“映射的快速幂”。

代码

python
import os
import sys
from array import array


def read_ints():
    number = 0
    reading = False
    while chunk := os.read(0, 1 << 20):
        for byte in chunk:
            if 48 <= byte <= 57:
                number = number * 10 + byte - 48
                reading = True
            elif reading:
                yield number
                number = 0
                reading = False
    if reading:
        yield number


data = iter(read_ints())
n, k, moves = next(data), next(data), next(data)
position = array("q", (next(data) for _ in range(n)))
transition = array("i", [0]) * n
left, right = 0, k

for i in range(n):
    while right + 1 < n and position[right + 1] - position[i] < position[i] - position[left]:
        left += 1
        right += 1
    transition[i] = right if position[right] - position[i] > position[i] - position[left] else left

answer = array("i", range(n))
while moves:
    if moves & 1:
        answer = array("i", map(transition.__getitem__, answer))
    moves >>= 1
    if moves:
        transition = array("i", map(transition.__getitem__, transition))

write = sys.stdout.write
for start in range(0, n, 8192):
    block = " ".join(str(x + 1) for x in answer[start:start + 8192])
    write(("" if start == 0 else " ") + block)
write("\n")

复杂度

双指针 O(n)O(n)，映射快速幂 O(nlog⁡m)O(n\log m)；空间 O(n)O(n)。

总结

倍增不一定要保存二维跳表。需要同时求所有起点且内存紧张时，可以像数值快速幂一样不断平方整个映射。