CodeForces - 987E Petr and Permutations (思维+逆序对)

题意：初始有一个序列[1,2,...N]，一次操作可以将任意两个位置的值互换，Petr做3*n次操作；Alxe做7*n+1次操作。给出最后生成的新序列，问是由谁操作得到的。

分析：一个序列的状态可以归为：由原序列操作奇数次得到（简称奇序列）；和操作偶数次（偶序列）得到。显然奇序列中，逆序对的个数为奇数；偶序列中，逆序对的个数为偶。当n为奇数时，3*n为奇，7*n+1为偶；n为偶数时正好相反。

用树状数组或归并排序求逆序对即可。

#include<iostream>

#include<stdio.h>

#include<cstring>

#include<stack>

#include<algorithm>

#include<vector>

using namespace std;

typedef long long LL;

const int maxn = 1e6+;

LL bit[maxn];

int n;

inline int lowbit(int x){return x&(-x);}

void add(int pos,LL val){

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

        bit[i] +=val;

    }

}

LL sum(int pos){

    LL res=;

    for(int i=pos;i;i-=lowbit(i)) res+=bit[i];

    return res;

}

int main()

{

    #ifndef ONLINE_JUDGE

        freopen("in.txt","r",stdin);

        freopen("out.txt","w",stdout);

    #endif

    while(scanf("%d",&n)==){

        memset(bit,,sizeof(bit));

        LL res=;

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

            LL val; scanf("%lld",&val);

            add(val,);

            res+= i-sum(val);

        }

        if(res%==n%) printf("Petr\n");

        else printf("Um_nik\n");

    }

    return ;

}

巴特西

CodeForces - 987E Petr and Permutations (思维+逆序对)

最新文章

热门文章