1. 理解核心概念

• 排列 (Permutation)：将数字1到n重新排列的顺序，如 [2, 3, 1]
• 逆排列 (Inverse Permutation)：记录每个数字在原排列中的位置
  • 例如原排列 [2, 3, 1] 的逆排列：
    • 数字1在原排列的第3位 → 逆排列第1个元素=3
    • 数字2在原排列的第1位 → 逆排列第2个元素=1
    • 数字3在原排列的第2位 → 逆排列第3个元素=2
    • 最终逆排列：[3, 1, 2]

2. 歧义排列的定义

当 原排列 = 逆排列 时，该排列是歧义的。例如：

• 原排列 [1, 4, 3, 2]
• 计算逆排列：
  • 数字1在第1位 → 逆[1]=1
  • 数字2在第4位 → 逆[2]=4
  • 数字3在第3位 → 逆[3]=3
  • 数字4在第2位 → 逆[4]=2
• 逆排列也是 [1, 4, 3, 2] → 歧义

3. 算法步骤

graph TD
    A[输入排列P] --> B[构建逆排列Q]
    B --> C[逐元素比较P和Q]
    C --> D{是否全部相等?}
    D -->|是| E[输出ambiguous]
    D -->|否| F[输出not ambiguous]

4. 关键实现细节

• 逆排列构建：

  for(int i = 1; i <= n; i++) {
      Q[P[i]] = i; // P[i]是数字，i是位置
  }
  

• 高效比较：

  bool is_ambiguous = true;
  for(int i = 1; i <= n; i++) {
      if(P[i] != Q[i]) {
          is_ambiguous = false;
          break; // 发现不匹配立即退出
      }
  }
  

5. 复杂度分析

6. 边界情况处理

• n=1：总是歧义（[1]的逆排列就是自己）
• 完全相同的排列：如 [1,2,3,...,n] 的逆排列就是自己
• 对称排列：如 [2,1,4,3] 也是歧义的

标程

#include <cstdio>
#include <vector>
using namespace std;

int main() {
    int n;
    while(scanf("%d", &n) == 1) {  // 明确检查返回值
        if(n == 0) break;
        
        vector<int> perm(n+1);  // 排列（1-based）
        vector<int> inv(n+1);   // 逆排列
        
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &perm[i]);
            inv[perm[i]] = i;  // 构建逆排列
        }
        
        bool is_ambiguous = true;
        for(int i = 1; i <= n; ++i) {
            if(perm[i] != inv[i]) {
                is_ambiguous = false;
                break;
            }
        }
        
        // C++98 兼容的输出方式
        if(is_ambiguous) {
            printf("ambiguous\n");
        } else {
            printf("not ambiguous\n");
        }
    }
    return 0;
}