Codeforces 987E Petr and Permutations(数组的置换与复原、结论)

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目连接： Petr and Permutations

题意：给出一个1到n的序列，Petr打乱了3n次，Um_nik打乱了7n+1次，现在给出被打乱后的序列，求是谁打乱的。

题解：因为给出了一个3*n和一个7*n+1，发现这两个当一个为奇数另一个一定为偶数，所以可以联想和奇偶性质有关。但是这里面要算最短几步能把当前的序列变成1-n。这里我算错~~顺便学了一下如何将置换序列复原。

#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int> P;

typedef long long LL;

const int MAX_N = 1e6+;

const int INF =1e9+;

int N,M,T,S;

int vec[MAX_N];

int main(){

    while(cin>>N)

    {

        for(int i=;i<=N;i++) scanf("%d",&vec[i]);

        int num = ;

        for (int i = ; i <= N; i++)

        {

            while (vec[i] != i)

            {

                swap(vec[i], vec[vec[i]]);

                num++;

            }

        }

        if((*N - num) %  == ) cout<<"Petr"<<endl;

        else cout<<"Um_nik"<<endl;

    }

    return ;

}