蓝桥杯2024年第十五届省赛真题-传送阵

题目描述
小蓝在环球旅行时来到了一座古代遗迹，里面并排放置了 n 个传送阵，进入第 i 个传送阵会被传送到第 ai 个传送阵前，并且可以随时选择退出或者继续进入当前传送阵。小蓝为了探寻传送阵中的宝物，需要选择一个传送阵进入，然后连续进入之后的传送阵。小蓝希望尽可能多地进入传送门以便搜索宝物，同时他可以使用一次魔法，从某个传送阵 j 走到相邻的（第 j − 1 或第 j + 1 个）传送阵，请问小蓝最多能到达多少个不同的传送阵？一个传送阵可多次进入，但在计算答案时只算一个。
输入格式
输入的第一行包含一个正整数 n 。第二行包含 n 个正整数 a1, a2, · · · , an ，相邻整数之间使用一个空格分隔。
输出格式
输出一行包含一个整数表示答案。
样例输入复制
5
2 1 5 4 3
样例输出复制
4
提示
【样例说明】

小蓝的路径可以是：1 → 2 → 3 → 5 。其中 2 → 3 使用魔法。

【评测用例规模与约定】

对于 20% 的评测用例，1 ≤ n ≤ 1000 ；对于所有评测用例，1 ≤ n ≤ 106，且 a 是 1 至 n 的一个排列。

1.分析

        用并查集处理传送阵的关系，只用到了一个数组。

        1.初始化的时候按照题目的数组初始化fa[i]=a[i];

        2.遍历数组，把有关系的结点的父结点全部改为下标最小的结点。并且用一个数组记录个数。

2.代码

#include<iostream>
#include <cstring>
using namespace std;
const int MAX = 1e6+100;
int n,fa[MAX],num[MAX],a[MAX],re;int main()
{cin >> n;memset(fa, -1, sizeof fa);for (int i = 1; i <= n; i++) {         //输入，初始化cin >> a[i];fa[i] = a[i];}for (int i = 1; i <= n; i++) {if (fa[i] == i) num[i] = 1;      //自己单独的结点if (fa[i]>i) {            //因为从小到大遍历，如果父结点的下标比自己小，一定访问过int t=fa[i];          //最小下标为i  从小到大访问，第一次访问到的就是最小的fa[i] = i;num[i] = 1;           //初始化个数while (t != i) {      //判断是否到头int s = fa[t];fa[t] = i;num[i]++;t = s;}}}for (int i = 1; i < n; i++) {           //计算输出int x = fa[i],y=fa[i+1];if (x != y) re = max(re, num[x] + num[y]);else re = max(re, num[x]);}cout << re << endl;return 0;
}