題目鏈接：點(diǎn)擊查看

題目大意：給出一個(gè)長(zhǎng)度為 n 的序列，可能打亂過 3 * n 次，也可能打亂過 7 * n + 1 次，問到底打亂過多少次

題目分析：首先看出，3 * n 和 7 * n + 1 的奇偶是不同的，如此根據(jù)逆序?qū)Χɡ?#xff0c;可以根據(jù)逆序?qū)Φ钠媾紒?lái)判斷對(duì)換次數(shù)，直接用樹狀數(shù)組求出逆序?qū)Φ膫€(gè)數(shù)就好了

代碼：
?

//#pragma GCC optimize(2) //#pragma GCC optimize("Ofast","inline","-ffast-math") //#pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e6+100;int n,c[N];int lowbit(int x) {return x&(-x); }void add(int x) {for(int i=x;i<=n;i+=lowbit(i))c[i]++; }int ask(int x) {int ans=0;for(int i=x;i>0;i-=lowbit(i))ans+=c[i];return ans; }int main() { #ifndef ONLINE_JUDGE // freopen("data.ans.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);scanf("%d",&n);int ans=0;for(int i=1;i<=n;i++){int x;scanf("%d",&x);ans=(ans+ask(n)-ask(x))%2;add(x);}if(ans^(3*n%2))puts("Um_nik");elseputs("Petr");return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 987E Petr and Permutations(树状数组+逆序对定理)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。