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

· · 题解

题目大意

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

思路

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

预处理

在之前我们学习过倍增法，定义 s_{i,j} 代表第 i 个人开始传球的第 2^j 次会传到哪个人，那么根据题目的模拟意思可以得出：

s_{i,j}=s_{s_{i,j-1},j-1}

意思：就是第一次传 2^{j-1} 次，再传 2^{j-1}。一共就是 2^j 次。

时间复杂度验证

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

关键代码

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];
        }
    }