B3965 [语言月赛 202404] 神秘排列 题解

· · 题解

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;

视频讲解