首页 > 代码库 > POJ 2470 Ambiguous permutations(简单题 理解题意)
POJ 2470 Ambiguous permutations(简单题 理解题意)
However, there is another possibility of representing a permutation: You create a list of numbers where the i-th number is the position of the integer i in the permutation. Let us call this second possibility an inverse permutation. The inverse permutation for the sequence above is 5, 1, 2, 3, 4.
An ambiguous permutation is a permutation which cannot be distinguished from its inverse permutation.The permutation 1, 4, 3, 2 for example is ambiguous,because its inverse permutation is the same. To get rid of such annoying sample test cases, you have to write a program which detects if a given permutation is ambiguous or not.
【分析】:看我加红的部分。就是说假设叫做ambiguous permutation的话,就要通过这种变换方式后还是same.否则的话就是not ambiguous。
这样的方式就是例如以下:
数字的新旧位置互换,即是数组的下标是所谓旧位置。而这个数列本身的数字又代表一种新的位置。我们依照数字所显示的。将该数字所相应的下标变成序列中的值,便形成了新的序列。
如: 2 3 4 5 1 // 原序列
[1] [2] [3] [4] [5] // 数组下标
经过变换后:
[5] [1] [2] [3] [4] // 此时新的序列就是 5 1 2 3 4。由于与原序列 2 3 4 5 1不同,所以就是not ambiguous
1 2 3 4 5
见代码:
注:c++的输入输出会超时!
// 524K 219Ms #include<iostream> using namespace std; int a[100005]; int main() { int i,j,n; while(scanf("%d",&n)&&n!=0) { int flag=1; for(i=1;i<=n;i++) scanf("%d",&a[i]); for(i=1;i<=n;i++) { if(a[a[i]]!=i) { flag=0; break; } } if(flag==0) printf("not ambiguous\n"); else printf("ambiguous\n"); } return 0; }
POJ 2470 Ambiguous permutations(简单题 理解题意)