CodeForces 986B Petr and Permutations
原题链接
Petr 要打乱排列。他首先有一个从 1 到n的顺序排列，然后进行 3n 次操作，每次选两个数并交换它们。
Alex 也要打乱排列。他与 Petr 唯一的不同是他进行 7n+1 次操作。
给定一个 1 到n的排列。问是由谁打乱的。如果是 Petr，输出 "Petr"，否则 输出 "Um_nik"（不是 Alex）。
（by AKEE）
题解
首先我们考虑怎么快速还原这个序列。
很显然的一个贪心策略就是假设序列为 {ai}，不断把aai 与ai交换直到ai=i。
这样做我们发现交换次数是 O(n) 级别的，因为 aai 最多被选 n 次。
然后我们发现要一个序列交换后形成交换前的序列交换次数只能是偶数。所以该交换次数与 Petr 或Alex的奇偶性相同。
于是只要判一下奇偶即可。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| #include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1000005;
int aa[maxn];
int main()
{
int n;
scanf("%d", &n);
for(int i = 1; i <= n; ++i)
scanf("%d", &aa[i]);
int ans = 0;
for(int i = 1; i <= n; ++i)
{
while(aa[i] != i)
{
swap(aa[aa[i]], aa[i]);
ans++;
}
}
if((n & 1) == (ans & 1))
puts("Petr");
else
puts("Um_nik");
return 0;
}
|
