2018AHU新生賽Panelatta與華容道題解

題目描述

Panelatta很喜歡玩益智游戲，今天，他又開(kāi)始玩一個(gè)古老的游戲：華容道！但是Panelatta不喜歡原版的華容道，所以他對(duì)此做了一些修改。給定一個(gè)由 n2n^{2}n
?2
?? ( n 為奇數(shù)）個(gè)方格組成的 n?n 方陣，在 n?n?1 個(gè)方格中填入數(shù)字 1 ~ n?n?1 ，并將剩下的一個(gè)方格留空。在游戲過(guò)程中，可以將空置的方格與其上下左右方向的任何一個(gè)數(shù)字交換。Panelatta將這個(gè)游戲稱為 n 階華容道。
現(xiàn)在給你兩個(gè) n 階華容道游戲的局面，請(qǐng)判斷是否存在一種移動(dòng)空置方格的方法，使得從其中一個(gè)局面可以變換成另一個(gè)局面？

輸入格式

多組數(shù)據(jù)，對(duì)于每組數(shù)據(jù)：
第1行一個(gè)奇數(shù) n ，(n < 500)
接下來(lái) n 行，每行 n 個(gè)整數(shù)，表示第一個(gè)局面。
接下來(lái) n 行，每行 n 個(gè)整數(shù)，表示第二個(gè)局面。
每個(gè)局面中用 0 表示空置方格，并保證每個(gè)局面都恰好用數(shù)字 0 ~ n?n?1填充滿。
輸出格式
對(duì)于每組數(shù)據(jù)，若兩個(gè)局面可達(dá)，輸出TAK，否則輸出NIE。

樣例

輸入樣例

3
1 2 3
0 4 6
7 5 8
1 2 3
4 5 6
7 8 0
1
0
0

輸出樣例

TAK
TAK

注：xls出的這個(gè)題沒(méi)點(diǎn)相關(guān)知識(shí)的話太難了，不愧是AHU全能王，出題就是有水平 ?
下面先介紹這道題所涉及到的相關(guān)知識(shí)點(diǎn)：

奇排列

下面是百度百科上對(duì)奇排列 先自行閱讀后再看下面的解釋

https://baike.baidu.com/item/奇排列/18881587?fr=aladdin

看完百度百科對(duì)奇排列的解釋后 不難知道以下結(jié)論：

定理1 ： 對(duì)換改變排列的奇偶性。（經(jīng)過(guò)一次對(duì)換，奇排列變成偶排列，偶排列變成奇排列。

例如：1 2 3 4 5 6是逆序?qū)? 所以為偶排列 若調(diào)換其中任意兩個(gè)位置的數(shù) 比如1 5 3 4 2 6 就變成偶排列

定理2 ：任意一個(gè)n級(jí)排列與排列 都可以經(jīng)過(guò)一系列對(duì)換互變，并且所作對(duì)換的個(gè)數(shù)與這個(gè)排列有相同的奇偶性。

定理2結(jié)合定理1也不難理解，偶排列換一次變成奇排列，再變化一次就變成了偶排列，以此類推得知：互變的次數(shù)的奇偶性與排列的奇偶性保持一致。

那么華容道是怎樣具有排列的性質(zhì)呢？
首先理解華容道不一定總是有解的，比如網(wǎng)上很火的一道數(shù)字華容道題
具體可以看下這個(gè)有關(guān)華容道里群論的視頻：華容道群論視頻
這種數(shù)字華容道是無(wú)解的，而原因就是因?yàn)樗且环N奇排列，而他要變成的1 2 3 4…… 14 15是一種偶排列，我們不難想到奇排列與偶排列在數(shù)字華容道中不能互相轉(zhuǎn)化。

了解了上面的知識(shí)再來(lái)看這道題 給出兩個(gè)數(shù)字華容道 問(wèn)第一個(gè)能否轉(zhuǎn)換成第二個(gè)，換個(gè)思路想，問(wèn)題可以轉(zhuǎn)化為第一個(gè)第二個(gè)是否都是同一種排列（比如都是奇排列和偶排列）。轉(zhuǎn)化為這個(gè)問(wèn)題后，我們又要想到如何判斷數(shù)字華容道的排列的奇偶性，那不妨找一個(gè)標(biāo)準(zhǔn)排列來(lái)與這兩個(gè)數(shù)字華容道作比較，看看這兩個(gè)數(shù)字華容道要互換幾次才能變成我們所規(guī)定的那個(gè)標(biāo)準(zhǔn)排列，若兩種變化次數(shù)為奇數(shù)或偶數(shù)，說(shuō)明這兩種排列具有相同的奇偶性，故可以相互轉(zhuǎn)化，輸出TAK。

不妨令標(biāo)準(zhǔn)排列為1 2 3 4 5 6 7 ……

此時(shí)問(wèn)題就轉(zhuǎn)化為了一個(gè)排列最少交換幾次才能變成1 2 3 4 5 6 7……這種升序排序。

由于數(shù)據(jù)為500*500=250000 數(shù)據(jù)很大 冒泡排序等方法很容易被卡超時(shí)

下面介紹一種復(fù)雜度o（n）的方法來(lái)處理這種問(wèn)題：

創(chuàng)建一個(gè)數(shù)組記錄一組數(shù) 然后再創(chuàng)建一個(gè)數(shù)組來(lái)記錄數(shù)所對(duì)應(yīng)的位數(shù) 比如第一組數(shù) 1 2 3 4 6 7 5 8 第一個(gè)數(shù)組叫a[1]=1 a[2]=2…a[5]=6 a[6]=7 a[7]=5 然另一個(gè)數(shù)組arem[1]=1 arem[2]=2 arem[6]=5 arem[7]=6 arem[5]=7 然后遍歷 如果a[i] ! =i 就讓arem[i]查到i值在第幾位 然后讓a[i]與a[arem[i]]交換數(shù)值 同時(shí)更新arem數(shù)組

注：更新arem數(shù)組的作用何在？
如果交換完位置后還用原來(lái)的數(shù)值記錄位置就會(huì)在后面調(diào)取某個(gè)數(shù)值的位置時(shí)產(chǎn)生錯(cuò)誤。
ac代碼

// An highlighted block #include<cstdio> #include<cstring> #include<queue> #include<algorithm> using namespace std; int a[250000],arem[250000]; int b[250000],brem[250000]; int main() {int t=10;while(t--){int n,cnta=0,cntb=0,tep;scanf("%d",&n);if(n==0){continue;};if(n==1){scanf("%d",&n);scanf("%d",&n);printf("TAK\n");continue;}for(int i=1;i<=n*n-1;i++){scanf("%d",&a[i]);if(a[i]==0){i=i-1;continue;}arem[a[i]]=i;}for(int i=1;i<=n*n-1;i++){scanf("%d",&b[i]);if(b[i]==0){i=i-1;continue;}brem[b[i]]=i;}int m,q;for(int i=1;i<=n*n-1;i++){if(a[i]!=i){m=arem[i];q=a[i];tep=a[arem[i]];a[arem[i]]=a[i];a[i]=tep;cnta++;arem[q]=m;}if(b[i]!=i){m=brem[i];q=b[i];tep=b[brem[i]];b[brem[i]]=b[i];b[i]=tep;cntb++;brem[q]=m;}}if(cnta%2==cntb%2){printf("TAK\n");}else{printf("NIE\n");}}return 0; }

幸運(yùn)的是這道題內(nèi)存限制沒(méi)什么要求，但是我們可以進(jìn)一步優(yōu)化下內(nèi)存，我們可以讓a和arem數(shù)組輸入完成后直接進(jìn)入運(yùn)算cnta的奇偶性，然后再把原來(lái)的b和brem直接輸入到a和arem，這樣就省去了b和brem所占有的內(nèi)存。

下面是改進(jìn)版本的代碼：

// An highlighted block #include<cstdio> #include<cstring> #include<queue> #include<algorithm> using namespace std; int a[250000],arem[250000]; int main() {//freopen("1.in","r",stdin);int t=10;while(t--){int n,cnta=0,cntb=0,tep;int m,q;scanf("%d",&n);if(n==0){continue;};if(n==1){scanf("%d",&n);scanf("%d",&n);printf("TAK\n");continue;}for(int i=1;i<=n*n-1;i++){scanf("%d",&a[i]);if(a[i]==0){i=i-1;continue;}arem[a[i]]=i;}for(int i=1;i<=n*n-1;i++){if(a[i]!=i){m=arem[i];q=a[i];tep=a[arem[i]];a[arem[i]]=a[i];a[i]=tep;cnta++;arem[q]=m;}}for(int i=1;i<=n*n-1;i++){scanf("%d",&a[i]);if(a[i]==0){i=i-1;continue;}arem[a[i]]=i;}for(int i=1;i<=n*n-1;i++){if(a[i]!=i){m=arem[i];q=a[i];tep=a[arem[i]];a[arem[i]]=a[i];a[i]=tep;cntb++;arem[q]=m;}}if(cnta%2==cntb%2){printf("TAK\n");}else{printf("NIE\n");}}return 0; }

內(nèi)存少了一半左右，且排序算法是o(n)的，現(xiàn)在應(yīng)該是優(yōu)化的很好的代碼啦。

下面再貼一種出題人Xls滴方法。

xls滴排序是o（nlogn）的方法。

// An highlighted block #include<iostream> #include<algorithm> #include<cstdio> #include<cstring> using namespace std; const int maxn=5e5+5;long long ans; int a[maxn]; int r[maxn];void msort(int s,int t){if(s==t)return;int mid=(s+t)/2;msort(s,mid);msort(mid+1,t);int i=s,j=mid+1,k=s;while(i<=mid&&j<=t){if(a[i]<=a[j]){r[k]=a[i];k++;i++;}else{r[k]=a[j];k++;j++;ans+=mid-i+1;}}while(i<=mid){r[k]=a[i];k++;i++;}while(j<=t){r[k]=a[j];k++;j++;}for(int i=s;i<=t;i++)a[i]=r[i]; } int main(){int n;int p;int val;while(~scanf("%d",&n)){p=1;for(int i=1;i<=n*n;i++){scanf("%d",&val);if(val!=0){a[p]=val;p++;}}ans=0;msort(1,p);long long t=ans;p=1;for(int i=1;i<=n*n;i++){scanf("%d",&val);if(val!=0){a[p]=val;p++;}}ans=0;msort(1,p);if(t%2==ans%2)printf("TAK\n");else printf("NIE\n");}return 0; }

問(wèn)題到此就解決了?

最后表白郭希賢同學(xué)！！！！

總結(jié)

以上是生活随笔為你收集整理的2018AHU新生赛Panelatta与华容道题解的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。