P10454

niu_zh · 2024-06-14 15:10:31 · 题解

思路

首先将两个表格每行首尾相接连成一个序列，然后对操作分别讨论。

• 当空格左右移动时，序列不会发生变化。

• 当空格上下移动时，会与其前或后 n-1 个数进行交换。如果其中一个数比它大，那么会增加一个逆序对；如果比它小，那么减少一个；如果相等，那么不变。

由于 n-1 是偶数，所以逆序对的总数的奇偶性不变。

所以考虑用归并排序求逆序对的数量，再判断奇偶性。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2500+10;
int a[N],b[N],t[N];
ll cnta,cntb;
void msort(int a[],int l,int r,ll &cnt)
{
    if (l>=r)
    {
        return;
    }
    int mid=(l+r)>>1;
    msort(a,l,mid,cnt);
    msort(a,mid+1,r,cnt);
    int i=l,j=mid+1,k=0;
    while (i<=mid&&j<=r)
    {
        if (a[i]<=a[j])
        {
            t[k++]=a[i++];
        }
        else
        {
            t[k++]=a[j++];
            cnt+=mid-i+1;
        }
    }
    while (i<=mid)
    {
        t[k++]=a[i++];
    }
    while (j<=r)
    {
        t[k++]=a[j++];
    }
    for (int i=l; i<=r; i++)
    {
        a[i]=t[i-l];
    }
}
int main()
{
    int n;
    while (cin>>n)
    {
        cnta=0,cntb=0;
        n*=n;
        for (int i=1,idx=0,x; i<=n; i++)
        {
            cin>>x;
            if (x!=0)
            {
                a[++idx]=x;
            }
        }
        for (int i=1,idx=0; i<=n; i++)
        {
            cin>>x;
            if (x!=0)
            {
                b[++idx]=x;
            }
        }
        msort(a,1,n-1,cnta);
        msort(b,1,n-1,cntb);
        if ((cntb%2)==(cnta%2))
        {
            cout<<"TAK\n";
        }
        else
        {
            cout<<"NIE\n";
        }
    }
    return 0;
}