题目：
把1~n(n≤500)放到一个圆盘里，每个数恰好出现一次。每次可以选4个连续的数字翻转顺序。问能不能变成1.2.3....n的顺序。
思路：
这样的题的规律真的是一点都不好推，看了网上的博客知道只有n为奇数且给出的序列的逆序数为奇数的时候，这种情况下是不能完成的，其余的情况都可以。
如果n为偶数，那么在这个环中总有4个连续的数字的逆序数是偶数，假设4个数的逆序数是x，翻转之后逆序数变成了6-x（为什么是6-x自己还没有搞懂），逆序数的变化为6-2x为偶数。最后升序的逆序数是0为偶数。根据偶数+(-)偶数=偶数,奇数+(-)偶数=奇数，可以得知当序列的逆序数为偶数时，那就可以通过翻转是逆序数变为0.
代码：
树状数组求逆序数
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define MAX 1e3
#define FRE() freopen("in.txt","r",stdin)
#define FRO() freopen("out.txt","w",stdout)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int maxn = ;
int a[maxn],n,tree[maxn]; int lowbit(int x){
return x&(-x);
} void add(int x){
while(x<=n){
tree[x]++;
x += lowbit(x);
}
} int getSum(int x){
int res = ;
while(x>){
res+=tree[x];
x -= lowbit(x);
}
return res;
} int main(){
//FRE();
int kase;
scanf("%d",&kase);
while(kase--){
memset(tree,,sizeof(tree));
scanf("%d",&n);
int cnt = ;
for(int i=; i<n; i++){
scanf("%d",&a[i]);
add(a[i]);
cnt += i+-getSum(a[i]);
}
if(cnt%== && n%==){
printf("impossible\n");
}else{
printf("possible\n");
}
}
return ;
}
暴力求逆序数
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define MAX 1e3
#define FRE() freopen("in.txt","r",stdin)
#define FRO() freopen("out.txt","w",stdout)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int maxn = ;
int a[maxn],n; int main(){
int kase;
scanf("%d",&kase);
while(kase--){
scanf("%d",&n);
for(int i=; i<n; i++){
scanf("%d",&a[i]);
}
int cnt = ;
for(int i=; i<n; i++){
for(int j=; j<i; j++){
if(a[j]>a[i]){
cnt++;
}
}
}
if(cnt%== && n%==){
printf("impossible\n");
}else{
printf("possible\n");
}
}
return ;
}