2026年山东省【信息学体验营】复赛真题及题解T3城堡探险题目描述有一座神秘的城堡里面共有n nn间密室编号为1 11到n nn。每间密室的墙壁上都刻着一个符文符文上写着一个数字a i a_iai表示从第i ii间密室出发会被传送到第a i a_iai间密室有可能a i i a_iiaii即传送到自己。现在有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输入 14 3 2 3 4 2 1 2 2 3 1 9输出 13 2 4输入输出样例 2输入 28 5 2 3 4 5 1 7 8 6 1 1 1 2 6 4 7 1000000000 3 1000000000输出 22 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≤1051 ≤ a i ≤ n 1\le a_i\le n1≤ai≤n1 ≤ x ≤ n 1\le x\le n1≤x≤n0 ≤ 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≤109a 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按二进制拆分。例如y13841就从起点依次跳8步、4步、1步最终位置就是答案。时间复杂度预处理O ( n log y ) O(n \log y)O(nlogy)每个询问O ( log y ) O(\log y)O(logy)可以通过。代码实现#includebits/stdc.husingnamespacestd;constintMAXN1000005;constintLOG31;// 因为 y 1e9 2^30多开一层更安全intup[LOG][MAXN];intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn,m;cinnm;// up[0][i] 表示从 i 走 1 步到达的点for(inti1;in;i){cinup[0][i];}// 倍增预处理// up[j][i] 表示从 i 走 2^j 步到达的点for(intj1;jLOG;j){for(inti1;in;i){// 先走 2^(j-1) 步到中间点再走 2^(j-1) 步up[j][i]up[j-1][up[j-1][i]];}}while(m--){intx;longlongy;cinxy;intansx;// 把 y 拆成二进制依次跳跃for(intj0;jLOG;j){if(y(1LLj)){ansup[j][ans];}}coutans\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标准模板库STLhttps://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 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}