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

#include<stdio.h>
#include<stdbool.h>
#define MAX 100000
int circle[MAX];//记录每个环大小
int parent[MAX];//记录每个传送阵所属的环
int m[MAX];
bool visited[MAX];
int circleIndex=0;//当前环的编号
//迭代实现换的查找void findcircle(int start){int current=start;int count=0;while(!visited[current]){visited[current]=true;parent[current]=circleIndex;count++;current=m[current]-1;}circle[circleIndex]=count;circleIndex++;} int main(){int n;scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d",&m[i]);}for(int i=0;i<n;i++){visited[i]=false;parent[i]=-1;}//遍历所有传送阵，查找环for(int i=0;i<n;i++){if(!visited[i]){findcircle(i);}} //最大访问数量int max=0;for(int i=0;i<n-1;i++){if(parent[i]!=parent[i+1]){int size1=circle[parent[i]];int size2=circle[parent[i+1]];if(size1+size2>max){max=size1+size2;}}} //如果没有相邻的环if(max==0){for(int i=0;i<circleIndex;i++){if(circle[i]>max)max=circle[i];}} printf("%d\n",max);return 0;}

• 有 n 个传送阵，编号从 1 到 n。

• 每个传送阵 i 会传送到 a[i]。

• 小蓝可以选择一个传送阵进入，然后连续进入传送阵。

• 小蓝可以使用一次魔法，从某个传送阵 j 走到相邻的传送阵（j-1 或 j+1）。

• 目标是计算小蓝最多能到达多少个不同的传送阵。

代码的核心思想是：

1. 找到所有的环：传送阵之间的关系会形成环（例如 1 → 2 → 1 是一个环）。

2. 记录每个环的大小：每个环中包含的传送阵数量。

3. 检查相邻的环：如果两个环相邻，则可以通过魔法将它们连接起来，从而访问更多的传送阵。

4. 计算最大访问数量：取最大的环大小，或者两个相邻环的大小之和。