2026年山东省【信息学体验营】复赛真题及题解T3：城堡探险
题目描述
有一座神秘的城堡，里面共有n nn间密室，编号为1 11到n nn。
每间密室的墙壁上都刻着一个符文，符文上写着一个数字a i a_iai（表示从第i ii间密室出发，会被传送到第a i a_iai间密室，有可能a i = i a_i=iai=i，即传送到自己）。
现在有m mm位探险者前来挑战，每位探险者的探险过程如下：
- 从某间密室x xx出发；
- 连续进行y yy次传送，每次传送都严格按照当前密室符文上指示的目标移动。
每位探险者都想知道：自己最终会停留在哪一间密室？
请你编写程序，帮助所有探险者快速得到答案。
输入格式
第一行两个整数n , m n,mn,m，分别表示密室的数量和探险者的数量。
第二行n nn个整数a 1 , a 2 , … , a n a_1,a_2,\ldots,a_na1,a2,…,an，表示每个密室的符文数字。
接下来m mm行，每行两个整数x , y x,yx,y，表示一位探险者的起点和传送次数。
输出格式
共m mm行，每行一个整数，表示对应探险者最终所在的密室编号。
输入输出样例 1
输入 1
4 3 2 3 4 2 1 2 2 3 1 9输出 1
3 2 4输入输出样例 2
输入 2
8 5 2 3 4 5 1 7 8 6 1 1 1 2 6 4 7 1000000000 3 1000000000输出 2
2 3 7 8 3说明/提示
【样例1 11解释】
从1 11号密室出发，传送2 22次：1 → 2 → 3 1\to 2\to 31→2→3；
从2 22号密室出发，传送3 33次：2 → 3 → 4 → 2 2\to 3\to 4\to 22→3→4→2；
从1 11号密室出发，传送9 99次：1 → 2 → 3 → 4 → 2 → 3 → 4 → 2 → 3 → 4 1\to 2\to 3\to 4\to 2\to 3\to 4\to 2\to 3\to 41→2→3→4→2→3→4→2→3→4。
【数据范围】
对于所有的数据，保证：1 ≤ n , m ≤ 10 5 1\le n,m\le 10^51≤n,m≤105；1 ≤ a i ≤ n 1\le a_i\le n1≤ai≤n；1 ≤ x ≤ n 1\le x\le n1≤x≤n；0 ≤ y ≤ 10 9 0\le y\le 10^90≤y≤109。
| 测试点编号 | y yy | 特殊性质 |
|---|---|---|
| 1 ∼ 6 1\sim 61∼6 | ≤ 10 \le 10≤10 | 无 |
| 7 ∼ 14 7\sim 147∼14 | ≤ 10 9 \le 10^9≤109 | a i a_iai互不相同 |
| 15 ∼ 20 15\sim 2015∼20 | ≤ 10 9 \le 10^9≤109 | 无 |
思路分析
把每间密室看成图上的一个点，a[i]表示点i唯一的出边。
那么问题就是：从x出发，沿着出边走y步，最终停在哪个点。
如果直接模拟，y最大是10 9 10^9109，会超时。所以用倍增（二进制拆分）优化：
- 设
up[j][i]表示从点i出发，连续走2^j步后到达的点。 - 初始：
u p [ 0 ] [ i ] = a i up[0][i]=a_iup[0][i]=ai - 递推：
u p [ j ] [ i ] = u p [ j − 1 ] [ u p [ j − 1 ] [ i ] ] up[j][i]=up[j-1][up[j-1][i]]up[j][i]=up[j−1][up[j−1][i]]
意思是：先走2 j − 1 2^{j-1}2j−1步到中间点，再走2 j − 1 2^{j-1}2j−1步。
询问时，把y按二进制拆分。例如y=13=8+4+1，就从起点依次跳8步、4步、1步，最终位置就是答案。
时间复杂度：预处理O ( n log y ) O(n \log y)O(nlogy)，每个询问O ( log y ) O(\log y)O(logy)，可以通过。
代码实现
#include<bits/stdc++.h>usingnamespacestd;constintMAXN=100000+5;constintLOG=31;// 因为 y <= 1e9 < 2^30，多开一层更安全intup[LOG][MAXN];intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn,m;cin>>n>>m;// up[0][i] 表示从 i 走 1 步到达的点for(inti=1;i<=n;i++){cin>>up[0][i];}// 倍增预处理// up[j][i] 表示从 i 走 2^j 步到达的点for(intj=1;j<LOG;j++){for(inti=1;i<=n;i++){// 先走 2^(j-1) 步到中间点，再走 2^(j-1) 步up[j][i]=up[j-1][up[j-1][i]];}}while(m--){intx;longlongy;cin>>x>>y;intans=x;// 把 y 拆成二进制，依次跳跃for(intj=0;j<LOG;j++){if(y&(1LL<<j)){ans=up[j][ans];}}cout<<ans<<'\n';}return0;}更多内容请关注专栏：信奥赛C++普及组csp-j初赛&复赛真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转
【秘籍汇总】（完整csp信奥赛C++学习资料）：
1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：
https://edu.csdn.net/lecturer/7901 点击跳转
2、CSP信奥赛C++竞赛拿奖视频课：
https://edu.csdn.net/course/detail/40437 点击跳转
https://edu.csdn.net/course/detail/41081 点击跳转
3、csp信奥赛高频考点知识详解及案例实践：
CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转
CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转
信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转
4、csp信奥赛冲刺一等奖有效刷题题解：
信奥赛C++普及组CSP-J一等奖通关刷题题单及题解：
https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转
信奥赛C++普及组csp-j初赛&复赛真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转
信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转
5、GESP C++考级真题题解：
GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转
GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转
GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转
· 文末祝福 ·
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}
