蓝桥杯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. 计算最大访问数量：取最大的环大小，或者两个相邻环的大小之和。