专栏文章

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

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

文章操作

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

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

题目大意

题目题意清楚不做过多概述。

思路

先考虑普通按照题目意思模拟的思路，每一次都让一次球，但是 1≤n≤1051 \le n \le 10^5 而 1≤k≤1091 \le k \le 10^9，所以直接模拟肯定不行。现在考虑减少操作次数，只要我们将某几轮合并成一次来计算那么时间复杂度就肯定会减少。因为每一个正整数都可以被分解成若干个 22 的正整数次幂的和，所以我们可以提前算出出从每一个人传球的第 2n2^n 次会传到谁，然后在每一次处理的时候直接跳加上当前已经有的步数后小于 kk 的最大的 2n2^n 这么多步。

预处理

在之前我们学习过倍增法，定义 si,js_{i,j} 代表第 ii 个人开始传球的第 2j2^j 次会传到哪个人，那么根据题目的模拟意思可以得出：
si,j=ssi,j−1,j−1s_{i,j}=s_{s_{i,j-1},j-1}
意思：就是第一次传 2j−12^{j-1} 次，再传 2j−12^{j-1}。一共就是 2j2^j 次。

时间复杂度验证

时间复杂度为 O(Nlog⁡k)O(N \log k)，可以通过本题。

关键代码

CPP
for(int j = 1; (1<<j) < k; j++)//预处理部分
		for(int i = 1; i <= n; i++)
			s[i][j] = s[s[i][j-1]][j-1];
	for(int j = __lg(k)+1; j >= 0; j--) {//压缩完成后进行计算
		if(st+(1<<j) < k) {
			st += (1<<j);
			for(int i = 1; i <= n; i++)t[i] = 0;
			for(int i = 1; i <= n; i++)t[s[i][j]] += a[i];
			for(int i = 1; i <= n; i++)a[i] = t[i];
		}
	}

评论

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

正在加载评论...