文章目录

M × N Puzzle POJ - 2893

如果m-1 为偶数，则无论上下左右移动都不会影响逆序对数的奇偶性
如果m-1为奇数，上下移动会使得逆序对数的奇偶性改变，判断当前空格的行数和最后的行数的差值与逆序对数的奇偶性是否相同即可

树状数组求逆序数




const int maxn = 1e6+10;
int a[maxn];
int b[maxn];
int tree[maxn];
int n,m;
LL sum(int x){
    LL s = 0;
    while(x){
        s += tree[x];
        x -= x&(-x);
    }
    return s;
}
void Insert(int x,int dx){
    while(x < maxn){
        tree[x] += dx;
        x += lowbit(x);
    }
}

int main(void)
{
    
    while(cin>>n>>m&&n &&m){
        int t = 1;
        int index;
        for(int i = 1;i <= n; ++i)
            for(int j = 1;j <= m; ++j){
                int tt;scanf("%d",&tt);
                if(tt != 0) 
                    a[t++] = tt;
                else
                    index = i;
            }
        // assert(t == n*m);
        for(int i = 1;i <= n*m-1; ++i) tree[i] = 0;
        LL num = 0;
        for(int i = 1;i <= n*m-1; ++i){
            num += a[i]-sum(a[i])-1;
            Insert(a[i],1);
        }
        // cout<<num<<endl;
        bool yes = false;
        if((m-1) % 2 == 0 && num % 2== 0) yes = true;
        if((m-1) % 2 == 1 && num % 2== (n-index)%2 ) yes = true;
        if(!yes)
            puts("NO");
        else
            puts("YES");
    }
    

   return 0;
}

归并排序求逆序数



const int maxn = 1e6+10;
int a[maxn];
int b[maxn];
LL divide(int l,int r){
    if(l == r) return 0;
    int m = (l+r)/2;
    LL sum = 0;
    sum += divide(l,m);
    sum += divide(m+1,r);
    int t = l; 
    int L = l,R = m+1;
    while(L <= m && R <= r){
        if(a[L] < a[R]){
            sum += R-m-1;
            b[t++] = a[L++];
        }
        else 
            b[t++] = a[R++];
    }
    while(L <= m)
        b[t++] = a[L++],sum += r-m;
    while(R <= r)
        b[t++] = a[R++];
    for(int i = l;i <= r; ++i) 
        a[i] = b[i];
    return sum;
}

int main(void)
{
    int n,m;
    while(cin>>n>>m&&n &&m){
        int t = 1;
        int index;
        for(int i = 1;i <= n; ++i)
            for(int j = 1;j <= m; ++j){
                int tt;scanf("%d",&tt);
                if(tt != 0) 
                    a[t++] = tt;
                else
                    index = i;
            }
        // assert(t == n*m);
        LL num = divide(1,n*m-1);
        bool yes = false;
        if((m-1) % 2 == 0 && num % 2== 0) yes = true;
        if((m-1) % 2 == 1 && num % 2== (n-index)%2 ) yes = true;
        if(!yes)
            puts("NO");
        else
            puts("YES");
    }
    

   return 0;
}