解题思路

由于 $a$ 数组是一个 $1$ 到 $n$ 的一个排列，那么形成的一定是如下形式：

一定会构成几个点的循环，或者是几个单独的点。

从任意点开始，如果能进入一个循环，一定可以将整个循环的宝藏都拿走，因为不限进入传送门的次数。

那么，我们可以用并查集来维护点与点之间的关系，以及一个小团体里头点的数量。

由于我们可以使用一次从 $j$ 跳到 $j-1$ 或 $j+1$ 的位置，那么我们可以枚举所有的 $cnt[find(j)]+cnt[find(j+1)]$，其中 $find(j)\ne find(j+1)$。

时间复杂度约为 $O(n)$。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>using namespace std;const int N = 1e6 + 10;int n;
int p[N], cnt[N];int find(int x)
{if (x != p[x])p[x] = find(p[x]);return p[x];
}int main()
{cin >> n;for (int i = 1; i <= n; ++ i )p[i] = i, cnt[i] = 1;for (int i = 1; i <= n; ++ i ){int x;cin >> x;int a = find(i), b = find(x);if (a == b)continue;cnt[a] += cnt[b];p[b] = a;}int res = 0;for (int i = 1; i < n; ++ i ){int a = find(i), b = find(i + 1);if (a == b)res = max(res, cnt[a]);elseres = max(res, cnt[a] + cnt[b]);}cout << res << endl;return 0;
}

【在线测评】