欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-06-16 11:17:46
...

传送门:点击打开链接

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

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

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

代码一:

#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;
}

相关标签: 逆序对