首页 > 代码库 > UVa 1620 懒惰的苏珊（逆序数）
UVa 1620 懒惰的苏珊（逆序数）
https://vjudge.net/problem/UVA-1620
题意：给出一个序列，每次可以翻转4个连续的数，判断是否可以变成1,2,3...n。
思路：考虑逆序数，通过计算可以得出每次翻转4个连续的数，如果这4个数原来的逆序数为x，那么翻转之后逆序数会变为6-x。
1.n为偶数时，总会有序列的逆序数为偶数
2.当n为奇数时，并且这个所给的序列的逆序数为奇数，不管怎么变换 他的逆序数不能变为 偶数。
这两个结论是别人博客看来的，不过我不太清楚怎么推导来着。有人懂得话希望能告诉我一下。
1 #include<iostream> 2 using namespace std; 3 4 const int maxn = 505; 5 int n; 6 int a[maxn]; 7 8 int main() 9 {10 //freopen("D:\\txt.txt", "r", stdin);11 int t;12 cin >> t;13 while (t--)14 {15 cin >> n;16 for (int i = 0; i < n; i++)17 cin >> a[i];18 int cnt = 0;19 for (int i = 0; i < n-1; i++)20 {21 for (int j = i + 1; j < n; j++)22 {23 if (a[i]>a[j]) cnt++;24 }25 }26 if (cnt % 2 && n % 2) cout << "impossible" << endl;27 else cout << "possible" << endl;28 }29 return 0;30 }
UVa 1620 懒惰的苏珊（逆序数）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。