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

UnionRE · 2025-04-14 13:59:34 · 题解

题解

题目理解

我们有 n 个传送阵排成一排，每个传送阵 i 会把你传送到第 a[i] 个传送阵。小蓝可以从任意传送阵开始，每次传送到指定的传送阵，也可以使用一次魔法跳到相邻的传送阵。目标是计算小蓝最多能访问多少个不同的传送阵。

思路

实际上，我们把这些传送阵看作几个不相连的环中，每个环的大小不一样。为了使到达的传送阵最多，选择最大的环。魔法使用就是跨越两个不相连的环。

时间复杂度：O(n)，我们只需要遍历传送阵两次（找环和检查相邻传送阵）。

Code

#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
bool vis[2000000];
int a[2000000],c[2000000];//c代表环的编号 
int main() {
    ios;
    int n;
    cin>>n;
    for(int i=1;i<=n;++i)cin>>a[i];
    vector<int>siz;//环的大小
    int k=0;
    // 找出所有环
    for(int i=1;i<=n;++i){
        if(!vis[i]){
            k++;
            int z=0,j=i;
            while(!vis[j]){
                vis[j]=1;
                c[j]=k;
                z++;
                j=a[j];
            }
            siz.push_back(z);
        }
    }
    int m=*max_element(siz.begin(),siz.end());//m代表单个环最大（即不使用魔法） 
    int t=0;//t代表相邻环的和的最大值，即使用魔法的情况 
    for(int i=1;i<n;++i){
        if(c[i]!=c[i+1]){//不在同一个环
            int u=siz[c[i]-1]+siz[c[i+1]-1];
            if(u>t)t=u;
        }
    }
    cout<<max(m,t);
    return 0;
}