题目链接

PEEK55 星球传送

题目描述

在一个包含 个星球的游戏中，每个星球 都有一个单向传送门，通往星球 （目标星球可能是自身）。你需要处理 个独立的查询，每个查询给定一个起始星球 和一个传送次数 。你需要计算出，从星球 出发，连续经过 次传送后，最终会到达哪个星球。

解题思路

由于传送次数 的值可能非常大（高达 ），对每次查询都进行 次模拟跳转是不可行的，会导致超时。

这个问题可以被看作是在一个功能图（functional graph，每个节点有且仅有一个出度）上寻找一个节点经过 步后到达的后继节点。这是一个可以使用倍增（Binary Lifting） 算法解决的经典问题。

算法的核心思想分为两步：预计算和查询。

  1. 预计算： 我们创建一个二维数组，通常记为 jump[p][i]，用于存储从星球 出发，连续传送 次后所到达的星球。

    • 基础状态 (): 从星球 传送 次，到达的星球就是输入中给定的 。所以，jump[0][i] = t_i。
    • 递推关系: 对于 ，从星球 传送 次，可以看作是先传送 次到达星球 jump[p-1][i]，然后再从这个新的星球继续传送 次。因此，递推公式为 jump[p][i] = jump[p-1][jump[p-1][i]]。

    我们可以通过这个公式，预先计算出所有需要的 jump 值。由于 ，所以 的范围大约是 到 。

  2. 查询：

    当我们需要处理一个查询 时，我们可以利用预计算好的 jump 表来快速找到答案。

    • 我们将传送次数 进行二进制分解。例如，如果 ，其二进制表示为 ，这意味着 。
    • 因此，从星球 开始传送 次，就等价于先传送 次，再传送 次，最后再传送 次。
    • 我们从 的最高位开始遍历。如果 的第 位是 ，我们就让当前位置 current_pos 跳转 次，即 current_pos = jump[p][current_pos]。
    • 通过这种方式，我们可以在 的时间内完成一次查询。

代码

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

const int LOGK = 30; // 2^30 > 10^9

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    long long q;
    cin >> n >> q;

    vector<vector<int>> jump(LOGK, vector<int>(n + 1));
    for (int i = 1; i <= n; ++i) {
        cin >> jump[0][i];
    }

    for (int p = 1; p < LOGK; ++p) {
        for (int i = 1; i <= n; ++i) {
            jump[p][i] = jump[p - 1][jump[p - 1][i]];
        }
    }

    for (long long i = 0; i < q; ++i) {
        int x;
        long long k;
        cin >> x >> k;

        for (int p = LOGK - 1; p >= 0; --p) {
            if ((k >> p) & 1) {
                x = jump[p][x];
            }
        }
        cout << x << "\n";
    }

    return 0;
}

import java.util.Scanner;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {
    private static final int LOGK = 30;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter writer = new PrintWriter(System.out);
        StringTokenizer st = new StringTokenizer(reader.readLine());

        int n = Integer.parseInt(st.nextToken());
        long q = Long.parseLong(st.nextToken());

        int[][] jump = new int[LOGK][n + 1];
        st = new StringTokenizer(reader.readLine());
        for (int i = 1; i <= n; i++) {
            jump[0][i] = Integer.parseInt(st.nextToken());
        }

        for (int p = 1; p < LOGK; p++) {
            for (int i = 1; i <= n; i++) {
                jump[p][i] = jump[p - 1][jump[p - 1][i]];
            }
        }

        for (long i = 0; i < q; i++) {
            st = new StringTokenizer(reader.readLine());
            int x = Integer.parseInt(st.nextToken());
            long k = Long.parseLong(st.nextToken());

            for (int p = LOGK - 1; p >= 0; p--) {
                if (((k >> p) & 1) == 1) {
                    x = jump[p][x];
                }
            }
            writer.println(x);
        }
        writer.flush();
    }
}

import sys

def solve():
    LOGK = 30
    
    # 使用 sys.stdin.readline 以提高大规模输入的读取效率
    input = sys.stdin.readline

    n_str, q_str = input().split()
    n, q = int(n_str), int(q_str)

    successors = [0] + list(map(int, input().split()))

    jump = [[0] * (n + 1) for _ in range(LOGK)]
    for i in range(1, n + 1):
        jump[0][i] = successors[i]

    for p in range(1, LOGK):
        for i in range(1, n + 1):
            jump[p][i] = jump[p - 1][jump[p - 1][i]]

    results = []
    for _ in range(q):
        x_str, k_str = input().split()
        x, k = int(x_str), int(k_str)

        for p in range(LOGK - 1, -1, -1):
            if (k >> p) & 1:
                x = jump[p][x]
        results.append(str(x))
    
    print("\n".join(results))

solve()

算法及复杂度

  • 算法：倍增 (Binary Lifting)
  • 时间复杂度：。其中 是星球数量， 是查询次数， 是最大传送次数。预处理倍增表需要 ，每次查询需要 。
  • 空间复杂度：。主要用于存储倍增表。