COCI2025-2026#1 题解

Krugomet 扔球

有 $n$ 个人在玩游戏。第 $i$ 个人持有 $a_i$ 个球，她的暗恋对象为第 $s_i$ 个人（可能出现 $s_i=i$ ）。

进行 $k$ 轮游戏，每轮游戏中，所有人同时将自己手上的球抛给自己的暗恋对象，然后接住所有传给自己的球。

编程回答两个问题：

$k$ 轮后，持有球数量最多的人持有多少个球？
$k$ 轮后，谁持有的球数量最多？

对于第二问，若有多个答案，从小到大依次输出之。

基环树模型，把环视为一个点的话得到一棵树，每过一轮每个节点上的球向上移动一格，由此想到用倍增维护经过 $2^k$ 轮后，球所在的位置，可发现不必求环。

记 $f(i, j)$ 表示经过 $2^j$ 轮以后，第 $i$ 个位置的球移到到的位置，那么 $f(i, j) = f(f(i, j - 1), j - 1)$ 。

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

const int N = 1e5 + 10;
int f[N][31], n, k, A[N], S[N];
int sum[N], max_val;

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> A[i];
    for (int i = 1; i <= n; i++) cin >> f[i][0];

    for (int j = 1; j <= 30; j++)
        for (int i = 1; i <= n; i++) {
            f[i][j] = f[f[i][j - 1]][j - 1];
    }

    for (int i = 1; i <= n; i++) {
        int t = k, now = i;
        for (int j = 30; j >= 0; j--) {
            if (t >= (1 << j)) {
                now = f[now][j], t -= (1 << j);
            }
        }
        sum[now] += A[i]; 
    }
    for (int i = 1; i <= n; i++) max_val = max(sum[i], max_val);
    cout << max_val << '\n';
    for (int i = 1; i <= n; i++) {
        if (sum[i] == max_val) cout << i << " ";
    }
}

Krugomet 扔球​

Krugomet 扔球