自动搬运

查看原文

来自洛谷，原作者为

	Maxmilite **

搬运于2025-08-24 21:16:14，当前版本为作者最后更新于2024-04-24 09:23:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Source & Knowledge

2024 年 4 月语言月赛，由洛谷网校入门计划/基础计划提供。

题目大意

给定一个数列，求这个排列是否是神秘数列。

一个数列是神秘数列当且仅当满足下列条件：

1. 这个数列是一个排列。即，整数 $1 \sim n$ 均在这个数列中出现过，且其中的每种整数仅出现过一次（例如，当 $n=4$ 时，$1,2,4,3$ 是一个排列， $1,2,2,2$ 不是一个排列）；
2. 我们将一个数列中 $x$ 出现的位置（出现在第几个）记作 $p_x$（$1 \leq p_x \leq n$），神秘数列需要满足对于 $1 \sim n$ 中的任意一个整数 $i$，都有 $p_i=a_i$。

题目分析

考虑一下 $p_i = a_i$ 这个式子。将其左右对调，变为 $a_i = p_i$，即，$a_i$ 是元素 $i$ 出现的位置（出现在第几个），因此会有 $a_{a_i} = i$（$a$ 的第 $a_i$ 个位置上的元素是 $i$）。

因此遍历数组，逐个判断 $a_{a_i} = i$ 是否为真即可。

for (int i = 1; i <= n; ++i) {
  if (a[a[i]] != i) {
    cout << "NO" << endl;
    return 0;
  }
}
cout << "YES" << endl;

视频讲解