NOIP 普及组初赛 · NOIP 2018 普及组初赛试题 第 21 题

阅读程序写结果:

#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

这题考的是排列的环分解。拿到程序先别急着跑，把d数组画成箭头图：每个位置i指向d[i]。然后从0开始顺着箭头走，走到哪里标记哪里，直到回到起点就是一个环。每发现一个没标记过的位置，就说明又找到一个新环，计数器加1。数数看一共几个圈，答案就出来了。

最容易栽跟头的就是读题粗心：第一个数是n（数组长度），后面才跟d[0]到d[9]的值，千万别把n当成d[0]去画图。其次就是自环，像d[i]=i这种，很多学生觉得“没动”就不算环，其实只要走一步就回到自己，也算一个环。还有内层循环条件!v[j]，当j走到已经标记过的位置时循环自动结束，这时候刚好走完一个环，千万别以为没走完或者多走了一步。最后注意输出的是环的个数，跟环里元素个数无关，不管是大圈还是自环都只计1个。

这道题考查的是排列的环分解，以及用标记数组（visited）来统计环的个数。这是信息学竞赛里非常经典的算法模型，本质就是图论里的“有向图每个点出度为1，分解成若干个不相交的环”。

先说说知识点： 1. 排列的环分解：任意一个长度为n的排列，如果把每个位置i看成指向d[i]的箭头，整个图一定会被分解成若干个互不相交的环。比如n=3，d=[1,2,0]，就是0→1→2→0一个大环；d=[0,1,2]就是三个自环。不管环里元素多，每个环只算一个。 2. 标记数组v：v[i]为false表示i还没被访问过，true表示已经访问过。每次从一个新的未访问点i出发，沿着j=d[j]一直走，把经过的点都标记为true，直到遇到一个已经标记过的点，说明已经走完一个环，这时候cnt++。 3. 时间复杂度：每个点只会被访问一次，所以整体是O(n)，非常高效。

命题人为什么考这个？ 这类题在NOIP普及组和GESP里出现频率不低，因为代码很短，但逻辑很精妙：外层循环找起点，内层循环沿箭头走，v数组控制终止条件。命题人喜欢在输入格式上挖坑（第一个数是n，后面才是d），也喜欢在自环上设陷阱（d[i]=i），或者在内层循环条件上偷换概念（比如把!v[j]写成!v[i]就全错了）。这道题就是典型的“代码很短，但细节很多”的题。

思考心法：拿到这种“阅读程序写结果”的题，别急着一行行翻译，先问自己三个问题：

• 这段代码在干什么？（统计环的个数）
• 输入是什么？（n=10，后面10个数是d[0]~d[9]）
• 怎么手算？（画图，从0开始走，标记，数几个圈）

具体推演： 输入是：10 7 1 4 3 2 5 9 8 0 6 第一行10是n，后面10个数依次是d[0]到d[9]： d[0]=7, d[1]=1, d[2]=4, d[3]=3, d[4]=2, d[5]=5, d[6]=9, d[7]=8, d[8]=0, d[9]=6

现在画图，每个i指向d[i]： 0→7→8→0 （这是一个环，包含{0,7,8}） 1→1 （自环，包含{1}） 2→4→2 （环，包含{2,4}） 3→3 （自环，包含{3}） 5→5 （自环，包含{5}） 6→9→6 （环，包含{6,9}）

一共6个环，所以输出6。

避坑提醒：

• 别把n=10当成d[0]，画图时d[0]应该是7，不是10。
• 自环d[i]=i也要算一个环，比如d[1]=1，d[3]=3，d[5]=5，这三个都是环。
• 内层循环条件!v[j]，当j走到已经标记过的位置时循环自动结束，这时候刚好走完一个环，千万别以为没走完或者多走了一步。
• 输出的是环的个数，跟环里元素个数无关，不管是大圈还是自环都只计1个。

考频与趋势： 从题库数据看，循环结构是出现频率最高的考点（609题），其中2026年有161题，2025年158题，2024年128题，2023年77题，呈现明显上升趋势。分支结构（181题）和输入输出（253题）也都很常见。这类“阅读程序写结果”的题在NOIP普及组初赛里每年都占一席之地，尤其是涉及标记数组和环分解的，最近三年（2023-2026）在GESP二级、一级和NOIP普及组中都有多次出现，说明命题人很偏爱这种“代码短但逻辑精妙”的类型。

预测： 基于2024-2026年的数据，循环结构和标记数组的考查频率在持续上升，未来几年这类题很可能继续作为“阅读程序”或“完善程序”的必考内容。命题人可能会在输入格式、自环判断、或循环终止条件上继续挖坑，比如把d数组的输入顺序打乱，或者在内层循环里加入额外判断（如只统计大小为k的环）。但核心逻辑——用v数组标记、沿d[i]跳跃、数环的个数——应该不会变。

总结： 这道题的关键就是读懂代码逻辑，把d数组画成箭头图，然后数几个圈。记住输入格式、自环也算环、内层循环条件，就能稳稳拿分。