NOIP 提高组初赛 · NOIP 2018 提高组初赛试题 第 19 题

阅读程序写结果：

#include <stdio.h>

int n, d[100];
bool v[100];

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", d + i);
        v[i] = false;
    }
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        if (!v[i]) {
            for (int j = i; !v[j]; j = d[j]) {
            	v[j] = true;
            }
            ++cnt;
        }
    }
    printf("%d\n", cnt);
    return 0;
}

输入：10 7 1 4 3 2 5 9 8 0 6

这道题考的是置换环分解。拿到题先别急着跑代码，把输入序列当成一个函数 f(i)=d[i]，从每个未访问的 i 出发沿着 f 跳，直到回到起点，这就是一个环。把 n 个元素全部分解成若干互不相交的环，答案就是环的个数。

很多学生容易把‘循环节’和‘前缀和/子段和’混淆，或者认为只要相邻两个数相等才算环。其实这里的环是函数迭代形成的：从 i 跳到 d[i]，再跳到 d[d[i]]，直到再次遇到已经标记过的点，这一串就构成一个环。另外，v 数组的作用是关键，它防止同一个环被多次计数——外层循环遇到 i 时如果 v[i] 已经是 true，说明 i 所在的环已经被处理过了，直接跳过即可。

考点概念：程序阅读（置换环）

这道题的核心在于理解置换环分解（Cycle Decomposition）。在组合数学和图论中，一个长度为 n 的置换（即一个由 0 到 n-1 组成的排列）可以唯一地分解成若干个互不相交的环。本题的程序正是模拟了这个分解过程，统计环的个数。

命题视角：为什么考这个？

NOIP 提高组初赛喜欢考这种‘看似简单实则需要理解数据结构逻辑’的程序阅读题。命题人不会让你直接问‘什么是置换环’，而是把算法封装在几行代码里，考察你是否能透过语法看本质。这类题目在历年考频中属于中等偏上难度，尤其在 2018 年、2024 年、2025 年这类年份出现频率较高，说明命题组对‘算法思维’的考察越来越重视，不再局限于死记硬背的知识点。