乘风原创程序

  • CH0503 奇数码问题(逆序对)
  • 2020/8/10 9:52:08
  • 题面:奇数码问题

    思路:

    找了好久,没有找到奇数码问题和 n?mn*m 数码问题的详细证明。先记个结论。

    奇数码游戏两个局面可达,当且仅当两个局面下网络中的数依次写成不含零的 11n?n?1n*n-1 的序列后,逆序对个数的奇偶性相同。

    结论必要性证明:空格(即 00 )左右移动的时候,我们列出出来的序列是不变的;空格上(下)移动时,相当于某个数与它后(前)边 n?1n-1 个数交换了位置,因为 n?1n-1 是偶数,所以逆序对数的变化也是一个偶数。

    拓展到 nn 为偶数的情况,此时两个局面可达,当且仅当两个局面对应的网络写成序列之后,逆序对数之差两个局面下空格所在的行数之差奇偶性相同。
    n?mn*m 数码问题也是根据上面两个结论来进行判定有解性的。具体的,慢慢找。

    代码:

    #include <bits/stdc++.h>
    #define sc scanf
    #define pf printf
    using namespace std;
    const int N = 250010;
    
    int a[N], b[N], w[N];
    
    //归并排序求逆序对数
    int merge(int l, int r, int x[])
    {
        if(l == r)    return 0;
        int mid = l + r >> 1;
        int res = merge(l, mid, x) + merge(mid + 1, r, x);
        
        int i = l, j = mid + 1, k = 0;
        while(i <= mid && j <= r) {
            if(x[i] <= x[j])    w[k++] = x[i++];
            else {
                res += mid - i + 1;
                w[k++] = x[j++];
            }
        }
        while(i <= mid) w[k++] = x[i++];
        while(j <= r)   w[k++] = x[j++];
        for(i = l, j = 0; i <= r; i++, j++) x[i] = w[j];
        return res;
    }
    
    void read(int *x, int len)
    {
        int k = 0;
        for(int i = 0; i < len; i++) {
            int num; sc("%d", &num);
            if(num != 0)    x[k++] = num;
        }
    }
    
    int main()
    {
        int n;
        while(cin >> n) {
            read(a, n * n);
            read(b, n * n);
            int cnt_a = merge(0, n * n - 1, a);
            int cnt_b = merge(0, n * n - 1, b);
            //要使得两个局面可达
            //当且仅当两个局面的不含空格的序列的逆序对个数的奇偶性一致
            if((cnt_a & 1) == (cnt_b & 1))  puts("TAK");
            else    puts("NIE");
        }
    }
    

    本文地址:https://blog.csdn.net/qq_45371462/article/details/107876269