当前位置：首页 > news >正文

【逆序对】N*M Puzzle / Simple Puzzle

news 来源：原创 2024/5/6 4:34:19

HDU P3600 Simple Puzzle

POJ P2893 N*M Puzzle

（咕在前面，这是两道基本一样的题，我都没有A掉，但我觉得我写的十分正确！！！不想改了先放上来orz

思路：这个题真是妙啊qwq我特意新建了一个“妙啊”分类给它qwq（然而A不掉

将二维转化为一维，从左往右从上至下，遇到0（空格）跳之~
可知空格左右移动对一维序列无影响，上下移动会向前或向后移动，跳过（m-1）个格子//这里n行m列
如果列数为奇数，（m-1）为偶数，则无论移动的数与跳过的数的大小关系如何，逆序对数奇偶性不变；
也就是说具有同奇偶性的逆序对数的数列是可以互相转化的，初始数列逆序对数为0，只要逆序对数为偶数，即可输出“YES”
如果列数为偶数，（m-1）为奇数，则无论移动的数与跳过的数的大小关系如何，逆序对数奇偶性一定改变；
同理，空格移动行数若为奇数，逆序对数奇偶性发生改变
（太乱了！！！！贴个讲的清楚地QAQ

贴上我可怜的无助的至今在两大oj还是wa的代码！（输入格式附和POJ

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 using namespace std;
 5 const int sz = 1000;
 6 int n, m, flag, num = 0, cnt = 0, x, a[sz*sz], b[sz*sz];
 7 void merge_sort(int l, int r) {
 8     if(r - l > 0) {
 9         int mid = (l + r) >> 1;
10         int i = l, p = l, q = mid + 1;
11         merge_sort(l, mid);
12         merge_sort(mid+1, r);
13         while(q <= r|| p <= mid) {
14             if(q > r || (p <= mid && a[p] <= a[q])) 
15                 b[i++] = a[p++];
16             else b[i++] = a[q++], cnt = cnt + mid - p + 1;
17         }
18         for(int i = l; i <= r; i++)
19             a[i] = b[i];
20     }
21 }
22 int main() {
23     while(1) {
24         scanf("%d%d", &n, &m);
25         if(n==0&&m==0) break;
26         num = 0;
27         memset(a, 0, sizeof(a));
28         memset(b, 0, sizeof(b));
29         for(int i = 1; i <= n; i++) {
30             for(int j = 1; j <= m; j++) {
31                 scanf("%d", &x);
32                 if(x==0) {
33                     flag = i;
34                     continue;
35                 }
36                 a[++num] = x;
37             }
38         }
39         cnt = 0;
40         merge_sort(1, num);
41         if(m%2==1) {
42             if(cnt%2==1) {
43                 if((n-flag)%2==1) printf("YES\n");
44                 else printf("NO\n");
45             }
46             else {
47                 if((n-flag)%2==1) printf("NO\n");
48                 else printf("YES\n");
49             }
50         }
51         else {
52             if(cnt%2 == 0) printf("YES\n");
53             else printf("No\n");
54         }
55     }
56     return 0;
57 }