专栏文章

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

SSatellite_system
P14467题解参与者 1已保存评论 0

文章操作

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

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

思路分析：

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

AC Code:

CPP
#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;
}

评论

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

正在加载评论...