题解：P12123 [蓝桥杯 2024 省 B 第二场] 传送阵

Deakin · 2025-04-16 20:48:35 · 题解

题目传送门

前言

本蒟蒻是初一学生，第一篇题解，我会尽可能用通俗易懂的语言来讲。 求通过 QAQ。

思路

第 i 个传送门会传送到第 a_i 个传送门。

根据题目对传送门的解释，我们发现这样就会形成一个循环（即经过一定次数的传送后会回到原点）的一条路径，这里统称为“环”。 （以例题来说，五个传送门 2, 1, 5, 4, 3 可以形成三个环：1→2、3→5、4）。 当进入到某一个环中，则可以到这个环中的任意一个传送门，且不用魔法。

同时他可以使用一次魔法，从某个传送阵 j 走到相邻的（第 j−1 或第 j+1 个）传送阵。

其实本质上来说：从传送阵 j 走到第 j-1 个传送阵就相当于从第 j-1 个传送阵走到传送阵 j。

所以，我们只需要从第 1 个传送阵对应的环遍历到第 n 个传送阵对应的环中找到相邻且不为同一个环的两个环和最多的传送阵数量。

到这里题目意思就很明确了，找出所有的独立环，并统计每个环的大小。找到传送门数量最多的两个相邻且不同的环。并输出这两个环中传送门数量之和。（注意有个坑：可能只有一个环）。 ‌

算法

思路实现

例题：

5
2,1,5,4,3

按照思路，先找出所有独立环，并统计大小。

预处理环结构

分析

继承的条件：在之前的某个环中有出现过。用数组 id 的值的变化来表示有无出现过（出现过对 id 做标记）。

判断继承：找对应环时对环中的数的 id 进行处理。当处理过的数要找对应环时，找处理它 id 的环的 size。

代码

先建立两个数组，帮助我们快速处理环结构。

int id[1000001];//id[]数组‌：标记每个节点所属的环编号(索引)。
‌int size[1000001];//size[]数组‌：记录每个环的节点数量。

找对应环

方法： 模拟传送，标记每个节点的所属编号和环节点数。

模拟传送： 遍历每个节点，若未被处理过，则通过模拟传送过程 i = a[i] 找到整个环，并标记其 id 和计算 size‌。

int id[1000001]={0};//环的编号
int size[1000001]={0};//每个数对应环中传送阵的数量
//预处理每个环的id和size（类并查集）
for(int i=1;i<=n;i++){
  //如果i已经被处理过，直接取对应环的size
  if(id[i]!=0)size[i]=size[id[i]];
  else {
  int x=i;//环起点
  do{
      if(id[x]==0)id[x]=i;//标记环id
      size[i]++;//增加环的大小
      x=a[x];//模拟传送
    }while(x!=i);//当回到起点时结束循环
  }
}

求相邻环最大值

按照思路，找到传送门数量最多的两个相邻且不同的环。

继续以例题来说，先将预处理过的不同下标的环分开（比较直观）。