这道题看了半天没看出什么规律， 然后看到别人的博客， 结论是当n为奇数且逆序数为奇数的时候
无解， 否则有解。但是没有给出证明， 在网上也找到详细的证明……我也不知道是为什么……
求逆序对有两种方法， 树状数组和归并排序， 当然这道题数据很小可以直接暴力， 我三种都写了。
暴力
#include<cstdio>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;const int MAXN = 512;
int a[MAXN];int main()
{int T, n;scanf("%d", &T);while(T--){int cnt = 0;scanf("%d", &n);REP(i, 0, n) {scanf("%d", &a[i]);REP(j, 0, i)if(a[j] > a[i])cnt++;}printf("%s\n", (n & 1 && cnt & 1) ? "impossible" : "possible");}return 0;
}
归并排序
#include<cstdio>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;const int MAXN = 512;
int a[MAXN], t[MAXN], cnt;void merge_sort(int l, int r)
{if(l + 1 >= r) return;int m = (l + r) >> 1;merge_sort(l, m); merge_sort(m, r);int p = l, q = m, i = l;while(p < m || q < r){if(q >= r || p < m && a[p] < a[q]) t[i++] = a[p++];else t[i++] = a[q++], cnt += m - p;}REP(i, l, r) a[i] = t[i];
}int main()
{int T, n;scanf("%d", &T);while(T--){cnt = 0;scanf("%d", &n);REP(i, 0, n) scanf("%d", &a[i]);merge_sort(0, n);printf("%s\n", (n & 1 && cnt & 1) ? "impossible" : "possible");}return 0;
}
树状数组
#include<cstdio>
#include<cstring>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;const int MAXN = 512;
int a[MAXN], f[MAXN], n;int lowbit(int x)
{return x & (-x);
}void add(int x)
{while(x <= n){f[x]++;x += lowbit(x);}
}int sum(int x)
{int ret = 0;while(x){ret += f[x];x -= lowbit(x);}return ret;
}int main()
{int T;scanf("%d", &T);while(T--){int cnt = 0;memset(f, 0, sizeof(f));scanf("%d", &n);REP(i, 0, n) {scanf("%d", &a[i]);cnt += sum(n) - sum(a[i]-1);add(a[i]);}printf("%s\n", (n & 1 && cnt & 1) ? "impossible" : "possible");}return 0;
}