专栏文章

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

NNostopathy
P14467题解参与者 5已保存评论 4

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
4 条
当前快照
1 份
快照标识符
@minbmpn6
此快照首次捕获于
2025/12/01 23:45
3 个月前
此快照最后确认于
2025/12/01 23:45
3 个月前
查看原文

题意

有 nn 个点，每个点权值为 aia_i，与 sis_i 有一条单向边。进行 kk 次操作，每次每个点的权值都移动到 sis_i。问最后哪些点权值最大。

分析

kk 的范围很大，考虑优化到 log⁡\log。定义 sti,jst_{i,j} 表示第 ii 个节点进行 2j2^j 轮操作后，他的权值移动到了哪个点，转移是 sti,j=ststi,j−1,j−1st_{i,j}=st_{st_{i,j-1},j-1}。然后遍历每个点，将操作次数拆分，找到最终传给了哪个节点。
时间复杂度 Θ(nlog⁡k)\Theta(n \log k)。

代码

CPP
#include<bits/stdc++.h>
using namespace std;
using LL=long long int;
const int N=1e5+5;
int n,k,a[N],cnt[N],st[N][35];
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;++i)cin>>a[i];
    for(int i=1,crush;i<=n;++i)cin>>crush,st[i][0]=crush;
    int m=__lg(k);
    for(int j=1;j<=m;++j)for(int i=1;i<=n;++i)st[i][j]=st[st[i][j-1]][j-1];
    for(int i=1;i<=n;++i){
        int num=i,now=m,round=k;
        while(round){
            if(round>=(1<<now))round-=(1<<now),num=st[num][now];
            --now;
        }
        cnt[num]+=a[i];
    }
    int mx=0;
    for(int i=1;i<=n;++i)mx=max(mx,cnt[i]);
    cout<<mx<<"\n";
    for(int i=1;i<=n;++i)if(cnt[i]==mx)cout<<i<<" ";
}

结语

这个游戏一定很好玩。

评论

共 4 条评论，欢迎与作者交流。

正在加载评论...