【bzoj 4975】区间翻转（博弈论）_区间翻转c++

传送门biu~
考虑序列中顺序对的个数。
① 对于终止态，顺序对一定为0（偶数），此时先手必败。
② 对于翻转的区间[l,r]，可以视作将[l,r]内的顺序对数和逆序对数调换。
③ 因为区间长度为4x+2或4x+3，带入可知区间内的数对数（即顺序对数+逆序对数）为奇数。
综上可知，令当前序列顺序对数的奇偶性作为当前状态，那么对于一个奇状态，必定会转移到一个偶状态；反之，对于一个偶状态，必定会转移到一个奇状态。
所以奇状态为必胜态，偶状态为必败态。问题即转化为求序列顺序对数。

#include<bits/stdc++.h>
using namespace std;
int n,a[55],ans;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
        for(int j=1;j<i;++j)
            if(a[j]<a[i])    ans^=1;
    }   
    puts(ans?"Q":"T");
    return 0;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13