Codeforces 986B. Petr and Permutations（没想到这道2250分的题这么简单，早知道就先做了）

这题真的只能靠直觉了，我没法给出详细证明。

解题思路：

　　1.交换3n次或者7n+1次，一定会出现一个为奇数，另一个为偶数。

　　2.用最朴素的方法，将n个数字归位，计算交换次数。

　　3.判断交换次数是否与3n的奇偶性相同，相同输出Petr；

　　　　不相同则一定与7n+1的奇偶性相同，输出Um_nik。

代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int a[];

int idx[];

int main(){

    ios::sync_with_stdio(false);

    int n;

    cin >> n;

    for(int i = ;i <= n; ++i) cin >> a[i],idx[a[i]] = i;

    int cot = ;

    for(int i = ;i <= n; ++i){

        if(a[i] != i){

            a[idx[i]] = a[i];

            idx[a[i]] = idx[i];

            cot++;

        }

    }

    if((cot+*n)&){

        cout << "Um_nik" << endl;

    }else{

        cout << "Petr" << endl;

    }

    return ;

}

巴特西

Codeforces 986B. Petr and Permutations（没想到这道2250分的题这么简单，早知道就先做了）

最新文章

热门文章