生活随笔
收集整理的这篇文章主要介绍了
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. 奇数码问题【思维 / 逆序对】的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。
