专栏文章

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

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

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@minbnn6g
此快照首次捕获于
2025/12/01 23:46
3 个月前
此快照最后确认于
2025/12/01 23:46
3 个月前
查看原文
首先，暴力的复杂度为 O(nk)O(nk)，只能获得 14pts。
考虑为什么暴力抛这么慢。原因是暴力抛一个一个抛，太慢了，应该一段一段抛。
一段一段跳，就可以想到倍增，记 pu,jp_{u,j} 为 uu 开始抛 2j2^j 次抵达的位置，转移显然：pu,j=ppu,j−1,j−1p_{u,j}=p_{p_{u,j-1},j-1}。
然后最后求 uu 抛 kk 次的结果跟倍增求 kk 级祖先是类似的，就是“抵挡诱惑”，只有当 k≥2pk \ge 2^p 时再跳 2p2^p 步，代码很简单，二十多行。
CPP
#include<bits/stdc++.h>
using namespace std;
const int N=100009;
int p[N][32],a[N],s[N],ans[N],n,k,L;
int go(int x,int y){
	int u=x;
	for(int i=30;i>=0;i--)
		if(y>=(1<<i)) y-=(1<<i),u=p[u][i];
	return u;
}
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) cin>>s[i],p[i][0]=s[i];
	L=log2(k);
	for(int j=1;j<=L;j++)
		for(int u=1;u<=n;u++)
			p[u][j]=p[p[u][j-1]][j-1];
	for(int i=1;i<=n;i++) ans[go(i,k)]+=a[i];
	int mx=0;
	for(int i=1;i<=n;i++) mx=max(mx,ans[i]);
	cout<<mx<<endl;
	for(int i=1;i<=n;i++)
		if(ans[i]==mx) cout<<i<<" ";
	cout<<endl;
	return 0;
}

评论

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

正在加载评论...