生活随笔
收集整理的這篇文章主要介紹了
108. 奇数码问题【思维 / 逆序对】
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
n為奇數，左右交換不改變逆序對數個數，上下交換不改變逆序對奇偶性。
結論就是，將其轉化成1維，將0去除掉，求逆序對的數量，看這兩個的逆序對的奇偶性是否相同即可。
#include<bits/stdc++.h>
using namespace std
;
typedef long long int LL
;
const int N
=1e5*3+10;
int n
,temp
[N
];
void merge_sort(int l
,int r
,vector
<int>&a
,LL
&ans
)
{if(l
>=r
) return;int mid
=l
+r
>>1;merge_sort(l
,mid
,a
,ans
),merge_sort(mid
+1,r
,a
,ans
);int i
=l
,j
=mid
+1,k
=0;while(i
<=mid
&&j
<=r
){if(a
[i
]<=a
[j
]) temp
[k
++]=a
[i
++];else ans
+=mid
-i
+1,temp
[k
++]=a
[j
++];}while(i
<=mid
) temp
[k
++]=a
[i
++];while(j
<=r
) temp
[k
++]=a
[j
++];for(int i
=l
,j
=0;i
<=r
;i
++,j
++) a
[i
]=temp
[j
];
}
int main(void)
{while(cin
>>n
){vector
<int>a
,b
;for(int i
=1;i
<=n
*n
;i
++){int x
; scanf("%d",&x
);if(!x
) continue;a
.push_back(x
);}for(int i
=1;i
<=n
*n
;i
++){int x
; scanf("%d",&x
);if(!x
) continue;b
.push_back(x
);}LL ans1
=0,ans2
=0;merge_sort(0,a
.size()-1,a
,ans1
);merge_sort(0,a
.size()-1,b
,ans2
);if( (ans1
&1)==(ans2
&1) ) puts("TAK");else puts("NIE");}return 0;
}
總結
以上是生活随笔為你收集整理的108. 奇数码问题【思维 / 逆序对】的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
