AtCoder Beginner Contest竞赛题解 | 洛谷 AT_abc438_e Heavy Buckets

​欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！

专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。

适合人群：

• 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
• 希望系统学习C++/Python编程的初学者
• 想要提升算法与编程能力的编程爱好者

附上汇总帖：AtCoder Beginner Contest竞赛题解 | 汇总

【题目来源】

洛谷：[AT_abc438_e ABC438E] Heavy Buckets - 洛谷

【题目描述】

有N NN人和N NN桶。人和水桶的编号都是1 , 2 , … , N 1, 2, \ldots, N1,2,…,N。

最初，人i ii只持有水桶i ii，而水桶i ii是空的。

从现在起，将执行以下操作10 9 10^9109次：

• 同时在i = 1 , 2 , … , N i = 1, 2, \ldots, Ni=1,2,…,N中，i ii将i ii个单位的水添加到自己手中的每个水桶中，并将这些水桶递给A i A_iAi​。

在这里，水桶中的水量没有限制。

对于i = 1 , 2 , … , Q i = 1, 2, \ldots, Qi=1,2,…,Q，请回答下列问题：

• 求第T i T_iTi​次操作后，水桶B i B_iBi​中的水量。

【输入】

输入内容由标准输入法提供，格式如下

N NNQ QQ
A 1 A_1A1​A 2 A_2A2​… \ldots…A N A_NAN​
T 1 T_1T1​B 1 B_1B1​
T 2 T_2T2​B 2 B_2B2​
⋮ \vdots⋮
T Q T_QTQ​B Q B_QBQ​

【输出】

输出Q QQ行。第i ii行应包含第i ii次查询的答案。

【输入样例】

5 6 3 4 2 2 5 4 3 6 5 1 4 10 1 10 2 1000000000 1

【输出样例】

11 30 4 28 30 2999999998

【算法标签】

《洛谷 AT_abc438_e Heavy Buckets》

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong// 将int定义为long long，处理大数constintN=200005;intn,Q;// n: 数组长度，Q: 查询次数inta[N];// 原始数组// f[j][i]: 从位置i开始，走2^j步到达的位置// v[j][i]: 从位置i开始，走2^j步经过的值的和intf[30][N],v[30][N];signedmain()// 因为#define int long long，所以用signed main{// 输入数据cin>>n>>Q;for(inti=1;i<=n;i++){cin>>a[i];// 初始化：走2^0=1步f[0][i]=a[i];// 从i走1步到a[i]v[0][i]=i;// 经过的值是起始位置i}// 预处理倍增表for(intj=1;j<30;j++)// 2^30 > 1e9，足够大{for(inti=1;i<=n;i++){// 从i走2^j步 = 从i走2^(j-1)步，再走2^(j-1)步f[j][i]=f[j-1][f[j-1][i]];// 经过的值的和 = 前半段的和 + 后半段的和v[j][i]=v[j-1][i]+v[j-1][f[j-1][i]];}}// 处理查询while(Q--){intt,b;// t: 走的步数，b: 起始位置cin>>t>>b;intans=0;// 存储经过值的和// 从高位到低位处理t的二进制表示for(inti=29;i>=0;i--){// 如果t的第i位是1if(t&(1<<i)){// 累加从b开始走2^i步经过的值的和ans+=v[i][b];// 更新当前位置b=f[i][b];}}cout<<ans<<endl;}return0;}

【运行结果】

5 6 3 4 2 2 5 4 3 11 6 5 30 1 4 4 10 1 28 10 2 30 1000000000 1 2999999998