该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目类型

CSP-J 初赛风格高难度阅读程序题。本题共 5 小题，每题只有一个正确选项。

输入约定

第一行输入 n 和 q。第二行、第三行分别输入两个长度为 n 的整数序列；接下来 q 行每行输入 x 和 k。

其中 1 <= n,q <= 100000，第二行每个数均在 1 到 n 之间，第三行每个数的绝对值不超过 10^6，0 <= k <= 10^12。程序没有给出各函数和两个二维数组的实际意义，请根据函数之间的调用关系自行推断。

程序

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

const int N = 100005;
const int K = 41;

int n, q;
int to[N], go[K][N];
long long w[N], sum[K][N];

void seed() {
    for (int i = 1; i <= n; i++) {
        go[0][i] = to[i];
        sum[0][i] = w[i];
    }
}

void expand() {
    for (int j = 1; j < K; j++) {
        for (int i = 1; i <= n; i++) {
            int t = go[j - 1][i];
            go[j][i] = go[j - 1][t];
            sum[j][i] = sum[j - 1][i] + sum[j - 1][t];
        }
    }
}

pair<int, long long> ask(int x, unsigned long long k) {
    long long s = 0;
    for (int j = 0; j < K; j++) {
        if ((k >> j) & 1ULL) {
            s += sum[j][x];
            x = go[j][x];
        }
    }
    return {x, s};
}

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

    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> to[i];
    for (int i = 1; i <= n; i++)
        cin >> w[i];

    seed();
    expand();

    while (q--) {
        int x;
        unsigned long long k;
        cin >> x >> k;
        pair<int, long long> res = ask(x, k);
        cout << res.first << ' ' << res.second << '\n';
    }

    return 0;
}

选择区

第 1 题（20 分）

若输入为：

5 3
2 3 1 5 4
4 -1 6 3 8
1 5
4 4
3 2

程序依次输出三行。用“/”分隔三行，则正确输出是（　）。

{{ select(1) }}

• A. 3 12 / 4 20 / 2 10
• B. 2 12 / 4 22 / 1 10
• C. 3 12 / 4 22 / 2 10
• D. 3 13 / 5 22 / 2 9

第 2 题（20 分）

go[j][i] 的含义是（　）。

{{ select(2) }}

• A. 从位置 i 出发，连续执行 2^j 次转移后所在的位置
• B. 从位置 i 出发，连续执行 j 次转移后所在的位置
• C. 从位置 i 出发，在前 2^j 次转移中遇到的最大编号
• D. 从位置 i 出发，恰好能到达位置 j 所需的最少次数

第 3 题（20 分）

sum[j][i] 的含义是（　）。

{{ select(3) }}

• A. 从 i 出发执行 2^j 次转移后，终点位置的权值
• B. 从 i 出发能够到达的所有不同位置的权值和
• C. 从 i 出发前 j 次转移经过位置的权值和
• D. 从 i 出发执行 2^j 次转移时，每次转移前所在位置的权值和；包含起点，不包含最后的终点

第 4 题（20 分）

若只把 seed 函数中的 sum[0][i] = w[i] 改成 sum[0][i] = w[to[i]]，其余代码不变，则每次询问输出的第二个数变为（　）。

{{ select(4) }}

• A. 只统计起点和终点的权值
• B. 统计每次转移后到达位置的权值和；不包含起点，包含最后的终点
• C. 原答案的相反数
• D. 所有经过位置去重后的权值和

第 5 题（20 分）

把 K 看成能够覆盖 k 二进制位数的常量上界。该程序预处理、单次询问的时间复杂度以及额外空间复杂度依次为（　）。

{{ select(5) }}

• A. O(n^2)，O(1)，O(n)
• B. O(nK)，O(n)，O(K)
• C. O(nK)，O(K)，O(nK)
• D. O(K)，O(nK)，O(n)