Codeforces Round #485 (Div. 2) - E - Petr and Permutations

传送门：点击打开链接

题意：给出一个1-n的随机排列，问这个序列是交换3*n次形成的，还是交换7*n+1次形成的。

分析：首先，3*n和7*n+1的奇偶性一定不同，线性代数中学过，交换序列中任意两个元素，会使序列逆序对的奇偶性发生改变一次，所以只需快速求出逆序对就行。用归并、树状数组、线段树都行。另外负数取余，取余的结果与被取余的数保持一致，如果不确定正负，就先使用绝对值再取余。也可以直接求出最少交换次数，用一个辅助数组存储每个数的位置，从前往后对应排好。

代码一：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6+5;
ll ans,n;
int a[N],tp[N];

void mg(int arr[],int l,int r){
    int m=(l+r)/2,i=l,j=m+1,k=1;
    while(i<=m&&j<=r){
        if(arr[i]<=arr[j]){
            tp[k++]=arr[i++];
        }else {
            ans+=(m-i+1);
            tp[k++]=arr[j++];
        }
    }
    while(i<=m) tp[k++]=arr[i++];
    while(j<=r) tp[k++]=arr[j++];
    for(int i=1;i<k;i++)
        arr[l++]=tp[i];
}

void mgsort(int arr[],int l,int r){
    if(l>=r) return ;
    else {
        int m=(l+r)/2;
        mgsort(arr,l,m);
        mgsort(arr,m+1,r);
        mg(arr,l,r);
    }
}

int main(){
    cout<<(-5)%2<<endl;
    ios::sync_with_stdio(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    mgsort(a,1,n);
    if( (3*n-ans) % 2 == 1)cout<<"Um_nik"<<endl;
    else cout<<"Petr"<<endl;
    //if( (3*n-ans) % 2 == 0)cout<<"Petr"<<endl;
    //else cout<<"Um_nik"<<endl;
}

代码二：

#include <bits/stdc++.h>
const int MAXN = 1e6 + 10;
int n;
int a[MAXN], p[MAXN];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++){
        scanf("%d", a + i);
        p[a[i]] = i;
    }
    int cnt = 0;
    for (int i = 1; i <= n; i++){
        if (a[i] != i){
            cnt++;
            a[p[i]]=a[i];
            p[a[i]]=p[i];
        }
    }
    if ((3 * n - cnt) % 2 == 0) printf("Petr");
    else printf("Um_nik");
    return 0;
}