BZOJ4975 区间翻转

　　这个范围给的很像区间dp之类的，想了半天没一点思路，滚去看了一眼status被吓傻了。然后瞎猜了一发结论就过掉了。

　　求出逆序对数，判断是否为奇数即可。因为翻转区间会把将这段区间的逆序对取反，而长度为4x+2和4x+3的区间的数对数量是奇数，所以每次增加或减少的逆序对个数是奇数。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 55

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<''||c>'')) c=getchar();return c;}

int gcd(int n,int m){return m==?n:gcd(m,n%m);}

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

int n,a[N],ans;

int main()

{

#ifndef ONLINE_JUDGE

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

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

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read();

    for (int i=;i<=n;i++) a[i]=read();

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

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

        ans+=a[i]<a[j];

    if (ans&) cout<<'Q';else cout<<'T';

    return ;

}

巴特西

BZOJ4975 区间翻转

最新文章

热门文章