P14467 [COCI 2025/2026 #1] 扔球 / Krugomet 题解

Satellite_system · 2025-11-20 12:54:11 · 题解

思路分析：

不难发现这些扔球的路径构成了一颗基环树森林，我们可以先倍增跳到环上，然后再在环上倍增跳。然后我们发现，既然都是倍增，二者完全相同啊！于是就不建图了，直接倍增求出第 i 个人传 2^j 次球传给了谁，就做完了。时间复杂度 O(n\log k)，事实上可以通过分开环和数优化为 O(n\log n)，但没有必要了。

AC Code:

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,k,mx,a[N],b[N],st[N][40],t[N];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)
        cin>>st[i][0],t[i]=i;
    for(int j=1;j<=30;j++)
        for(int i=1;i<=n;i++)
            st[i][j]=st[st[i][j-1]][j-1];
    for(int j=30;j>=0;j--)
        if(k>=(1<<j)){k-=(1<<j);
            for(int i=1;i<=n;i++)
                t[i]=st[t[i]][j];
        }
    for(int i=1;i<=n;i++)
        b[t[i]]+=a[i];
    for(int i=1;i<=n;i++)
        mx=max(mx,b[i]);
    cout<<mx<<'\n';
    for(int i=1;i<=n;i++)
        if(b[i]==mx)cout<<i<<' ';
    return 0;
}