Solutions CS101

Appearance

M30178: 数字华容道（Easy Version） ​

merge sort, binary indexed tree, http://cs101.openjudge.cn/practice/30178/

思路：容易猜到把二维数组展平后统计逆序对, 但充分性的证明还没想到. (看了群里的 Hard Version 的证明确实觉得优雅)

c++
#include <bits/stdc++.h>
using namespace std;

class BIT {
private:
    int n;
    vector<int> tree;

    int lowbit(int x) {
        return x & (-x);
    }
    
public:
    BIT(int n) : n(n), tree(n + 1, 0) {}

    void update(int i, int delta=1) {
        for (int j = i; j <= n; j += lowbit(j)) {
            tree[j] += delta;
        }
    }

    int query(int i) {
        int sum = 0;
        for (int j = i; j > 0; j -= lowbit(j)) {
            sum += tree[j];
        }
        return sum;
    }
};

bool is_solvable(const vector<int>& nums, int n, int blank_row) {
    int N = n * n - 1;
    int inverse = 0;
    BIT bit(N);
    vector<int> sorted_nums = nums;
    sort(sorted_nums.begin(), sorted_nums.end());

    for (int i = N - 1; i >= 0; i--) {
        int rank = lower_bound(sorted_nums.begin(), sorted_nums.end(), nums[i]) - sorted_nums.begin() + 1;
        inverse += bit.query(rank - 1);
        bit.update(rank);
    }
    
    if (n & 1) {
        return inverse % 2 == 0;
    } else {
        return (inverse + blank_row) % 2 == 0;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    int blank_row = 0;
    vector<int> nums;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int x;
            cin >> x;
            if (x == 0) {
                blank_row = n - i - 1;
            } else {
                nums.push_back(x);
            }
        }
    }
    cout << (is_solvable(nums, n, blank_row) ? "yes" : "no") << "\n";
    return 0;
}

35min

cpp
#include <iostream>
#include <vector>
using namespace std;

class Fenwick
{
private:
    int n;
    vector<int> tree;

public:
    Fenwick(int n) : n(n), tree(n + 1, 0) {}

    void update(int i)
    {
        while (i <= n)
        {
            ++tree[i];
            i = i + (i & -i);
        }
    }

    int query(int i)
    {
        int sum = 0;
        while (i > 0)
        {
            sum += tree[i];
            i &= i - 1;
        }
        return sum;
    }
};

int main()
{
    cin.tie(nullptr)->sync_with_stdio(false);

    int n;
    cin >> n;
    int sz = n * n;
    vector<int> matrix;
    int bottom_up;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
        {
            int x;
            cin >> x;
            if (x == 0)
                bottom_up = n - i;
            else
                matrix.push_back(x);
        }

    Fenwick bit(sz);
    long long cnt = 0;

    for (int i = matrix.size() - 1; i >= 0; --i)
    {
        cnt += bit.query(matrix[i] - 1);
        bit.update(matrix[i]);
    }

    bool flag = false;
    if (n % 2 != 0)
    {
        if (cnt % 2 == 0)
            flag = true;
    }
    else
    {
        if ((cnt + bottom_up) % 2 == 1)
            flag = true;
    }

    cout << (flag == true ? "yes\n" : "no\n");
    return 0;
}

共用时1h

【姚博骞 25物院】思路：方法是计算每行的逆序数然后分n奇数欧树讨论，这个证明还暂时不会，目前会先把这些相对偏组合数学一些的一些证明先放一放，但是像是kmp算法包括树状数组的证明这种直观上能理解的可以接受即可，严格证明以后可以一起写，现在还是主要提升代码能力。 目前写的是分治法计算逆序数组，需要变归并边排序，时间复杂度较高 还有一种方法是树状数组记录前缀和，考虑一个巨大的数组，从前向后读入，出现了的数字记作1，没出现的记作0，计算当前该数为下标的前缀和，即为前面出现的比该数小的元素个数，用树状数组可以O（logn）进行跟新和查询，故两种方法复杂度均为O(n^2logn),但是树状数组本身写起来比较简单故更快（记得加到cheatsheet上）

cpp
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int nixu(vector<int>& a,int p,int q)
{
    if(p==q) return 0;
    int mid=(p+q)/2;
    int ans=nixu(a,p,mid)+nixu(a,mid+1,q);
    vector<int>b(a.begin()+p,a.begin()+q+1);
    int s,r,nx,leiji;
    s=r=nx=leiji=0;
    int i=p;
    while(s<mid-p+1&&r<q-mid)
    {
        if(b[s]<=b[mid-p+1+r]){
            a[i]=b[s];
            s++;
            nx+=leiji;
        }
        else{
            a[i]=b[mid-p+1+r];
            r++;
            leiji++;
        }
        i++;
    }
    if(s==mid-p+1){
        for(int j=i;j<=q;j++){
            a[j]=b[mid-p+1+r];
            r++;
        }
    }
    else{
        for(int j=i;j<=q;j++){
            a[j]=b[s];
            s++;
            nx+=leiji;
        }
    }
    ans+=nx;
    return ans;
}
int main()
{
    int n;
    cin>>n;
    vector<vector<int>>a(n,vector<int>(n));
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++)
        {
            cin>>a[i][j];
        }
    }
    vector<int>c;
    int p;  // 记录空格所在行
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(a[i][j]!=0){
                c.push_back(a[i][j]);
            }
            else{
                p=i;  // 空格所在行
            }
        }
    }
    int ans=nixu(c,0,c.size()-1);  // 逆序对数
    if(n%2==1)  // 奇数列
    {
        if(ans%2==0) cout<<"yes";
        else cout<<"no";
    }
    else  // 偶数列
    {
        if((ans+n-p)%2==1) cout<<"yes";
        else cout<<"no";
    }
    return 0;
}

思路：化归到标准情形，然后统计逆序对数．时间复杂度为 O(n2log⁡n)．

一般地，在二分图 G=(L,R) 上可以利用逆序对给出（一个空位的）数字华容道可复原的一个必要条件：将左右部点交替排列 l1,r1,l2,r2,⋯,ln,rn（若 |L|≠|R|，只需增加一些棋子为 0 的孤点，使之参与逆序对数的统计），则忽略空位后长度为 2n−1 的序列的逆序对数奇偶性是一个操作不变量，从而当前局面与目标局面逆序对数奇偶性相同是复原的必要条件．然而，充分性似乎没有统一的解法，只能根据 G 的结构给出具体构造．

充分性其实很好证，因为n*n的盘面可以被降阶成 n-1*n-1的盘面

cpp
#include <bits/stdc++.h>
using namespace std;

const int N = 1000 * 1000 + 5;
int a[N];
struct BIT {
    void modify(int n) {
        for(; n < N; n += n & -n) c[n] ^= 1;
    }
    bool query(int n) {
        bool ans = 0;
        for(; n; n -= n & -n) ans ^= c[n];
        return ans;
    }
    bool c[N];
} B;
int main() {
    int n;
    cin >> n;
    bool ans = n % 2 == 0;
    for(int i = 0; i < n * n; i++) {
        int t;
        cin >> t;
        if(t == 0)
            ans ^= (n % 2 == 0) && ((n - 1 - i / n) % 2);
        else {
            ans ^= B.query(t);
            B.modify(t);
        }
    }
    cout << (ans ? "no" : "yes") << '\n';
    return 0;
}