百练百会 bestWit

Appearance

20260214：AtCoder Beginner Contest 445 ​

百会（bestWit）| 百炼成钢，融会贯通，助力GESP备考

哈喽，备战GESP的同学们～ 百会（bestwit）AtCoder题解来啦！每周1次更新，聚焦竞赛高频题型，贴合GESP入门难度，帮大家拆解解题思路、掌握解题技巧，夯实编程基础，为GESP考试做好准备。

题目 ​

题目编号：C ：Sugoroku Destination  题目难度：★★★☆☆（贴合GESP 4-5级难度） 题目链接：C - Sugoroku Destination

本题属于ABC赛制中经典的“路径循环+记忆化”题型，难度适中（300点），核心考察对“无限次操作”的规律捕捉，以及大数据量下的效率优化，非常适合入门选手巩固基础、进阶选手练手。

题目大意 ​

有 N 个格子排成一列，编号从 1 到 N。每个格子 i 上都写着一个整数 A_i（满足 i ≤ A_i ≤ N，也就是说，数字不会比格子编号小）。

请针对每个起始格子 s（s 从 1 到 N），解决以下问题： 一开始，把棋子放在格子 s 上。重复执行一个操作 10^100 次（这个次数极大，远超 N）：读取当前棋子所在格子上的数字 x，然后把棋子移动到格子 x 上。操作结束后，输出棋子最终所在的格子编号。

限制条件： ​

  • 1≤N≤5×105
  • i≤Ai​≤N (1≤i≤N)
  • 所有输入均为整数

输入输出 ​

输入为如下格式：

N
A1​ A2​ … AN​

输出为如下格式：

一行输出 N 个整数，依次表示从格子 1~N 出发，经过 10^100 次操作后，棋子最终所在的格子编号，用空格分隔。

输入样例：

7
2 4 7 5 5 6 7

输出样例：

5 5 7 5 5 6 7

解释：s=1的情况下、如下图所示，是这样移动的：移动示意图

解题思路 ​

解题核心：破解“10^100次操作”的关键。

拿到题目，首先会被“10^100次操作”吓到——这个次数太大了，不可能真的模拟每次移动，否则一定会超时（哪怕 N=1e5，模拟一次都要超时，更别说1e100次）。

所以，核心是找到「操作的规律」，跳过所有重复循环，直接找到最终位置。结合题目给出的约束（i ≤ A_i ≤ N），我们可以推出两个关键结论：

结论1：最终一定会停在“自环格子”上 ​

因为每次移动，棋子都是从格子 i 移动到 A_i，而 A_i ≥ i（格子编号不会变小）。格子总数是有限的（N个），根据「鸽巢原理」，棋子移动若干次后，一定会重复到达某个格子——此时就进入了循环。

但因为 A_i ≥ i，循环只能是「自环」（即 A[x] = x）。试想：如果进入一个非自环的循环（比如 x→y→x），那么 x < y（因为 A[x] ≥ x），但 A[y] = x < y，这和 A[y] ≥ y 的约束矛盾。所以，最终棋子一定会停在某个 A[x] = x 的格子上，再也不动。

结论2：反向计算 + 记忆化，效率最优 ​

既然 A_i ≥ i，那么格子编号越大，越先到达最终的自环格子（比如格子 N，A[N] 只能等于 N，因为 A[N] ≤ N 且 A[N] ≥ N）。

基于这个特点，我们可以「从后往前计算」（从 N 到 1），用一个数组 sn[i] 存储「从格子 i 出发，最终到达的自环格子编号」。这样，计算 sn[i] 时，sn[A[i]] 可能已经计算完成，可以直接复用，避免重复计算，实现 O(N) 时间复杂度。

解题步骤 ​

  1. 初始化数组：a[] 存储每个格子 i 上的数字 A_i，sn[] 存储每个格子 i 的最终位置，初始化为 0。
  2. 初始化边界：sn[N] = N（格子 N 一定是自环格子，直接确定）。
  3. 反向计算（从 i = N-1 到 1）：
    1. 如果 sn[A[i]] 已经计算完成（sn[A[i]] ≠ 0），那么 sn[i] = sn[A[i]]（直接复用结果）。
    2. 如果 sn[A[i]] 未计算，就沿着移动路径查找（i → A[i] → A[A[i]] → ...），直到找到某个已计算 sn 值的格子，或者找到自环格子（A[s] = s），此时 sn[i] = 找到的那个格子编号。
  4. 输出结果：按顺序输出 sn[1] 到 sn[N]，用空格分隔。

代码 ​

C++
#include <bits/stdc++.h>
using namespace std;

// a[i]：格子i上写的数字（指向的格子编号）
// sn[i]：从格子i出发，最终到达的自环格子编号（记忆化数组）
int a[500005], sn[500005];

int main(){
    // 关键优化：关闭cin/cout与stdio的同步，加速输入输出（大数据量必备）
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n; // 读入格子总数N

    // 读入每个格子i上的数字A_i（注意：格子编号从1开始）
    for(int i=1;i<=n;i++){
        cin >> a[i];  
    }

    // 初始化：格子n一定是自环（A[n]只能等于n），所以sn[n] = n
    sn[n] = n;

    // 反向计算：从n-1往1推导，复用已计算的结果
    for(int i=n-1;i>=1;i--) {
        int s = i;    临时变量，记录当前查找的格子

        // 优化1：如果a[s]的最终位置已计算，直接复用，不用继续查找
        if(sn[a[s]] != 0){
            sn[i] = sn[a[s]];
            continue;
        }

        // 沿着移动路径查找，直到找到自环或已计算的位置
        while(a[s] != s){
            // 优化2：如果当前指向的格子已有结果，直接跳转，减少循环次数
            if(sn[a[s]] != 0){
                s = sn[a[s]];
                break;
            }else{
                // 优化3：每次移动两步，进一步减少循环迭代次数
                s = a[a[s]];              }          }
        // 记录当前格子i的最终位置
        sn[i] = s;
    }

    // 按要求输出结果（1~n的最终位置，空格分隔）
    for(int i=1;i<=n;i++){
        cout << sn[i] << " ";       }
       return 0;
}

总结 ​

1. 本题核心收获 ​

这道题的本质是「路径压缩+记忆化」，核心是抓住两个关键点：

  • 利用题目约束（A_i ≥ i），推出“最终停在自环格子”的规律，避免模拟无限次操作；
  • 反向计算+记忆化，复用已计算结果，将时间复杂度降到 O(N)，适配大数据量。

2. 同类题推荐（巩固练习） ​

如果想进一步巩固这类“路径循环+记忆化”的题型，可以练习以下AtCoder ABC真题，难度相近，思路相通：

  • ABC 300 C - Cross
  • ABC 312 C - Invisible Hand
  • ABC 326 C - Max MEX

3. 小提醒 ​

在ABC比赛中，300点的C题通常是“规律捕捉+基础优化”的题型，不会有太难的算法，重点在于：

① 不要被“极大值”（比如本题的10^100）吓到，学会找规律；

② 注意大数据量的输入输出优化；

③ 善用记忆化，避免重复计算。

最后，祝大家在后续的AtCoder比赛中，顺利AC每一道C题，稳步提升！后续我们会逐步更新难度更高的题解，贴合GESP进阶考点，陪大家一起“百炼成钢”。

下期预告：AtCoder Beginner Contest 446，经典的 300 点模拟类题目，提供两种不同的解法。记得关注公众号，第一时间获取更新通知～

百炼成钢，融会贯通

© 2026 百练百会（bestwit）GESP备考一站式平台 | 京ICP备16040576号-5