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的奇偶性一定不同,线性代数中学过,交换序列中任意两个元素,会使序列逆序对的奇偶性发生改变一次,所以只需快速求出逆序对就行。用归并、树状数组、线段树都行。另外负数取余,取余的结果与被取余的数保持一致,如果不确定正负,就先使用绝对值再取余。也可以直接求出最少交换次数,用一个辅助数组存储每个数的位置,从前往后对应排好。
代码一:
#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;
}
推荐阅读
-
Educational Codeforces Round 71 (Rated for Div. 2)E. XOR Guessing
-
Codeforces Round #670 (Div. 2) E. Deleting Numbers(交互,素数构造)
-
Codeforces Round #423 (Div. 2, rated, based on VK Cup Finals) E. DNA Evolution(多颗树状数组+思维)
-
Codeforces Round #648 (Div. 2) E、Maximum Subsequence Value
-
Codeforces Round #566 (Div. 2) E(矩阵快速幂)
-
Educational Codeforces Round 98 (Rated for Div. 2) A-E 题解
-
Codeforces Round #670 (Div. 2) (A~E题解)
-
Codeforces Round #485 (Div. 2) - E - Petr and Permutations
-
Codeforces Round #175 (Div. 2)-A. Slightly Decreasing Permutations_html/css_WEB-ITnose
-
Codeforces Round #274 (Div. 2) E. Riding in a Lift(DP)_html/css_WEB-ITnose