题解 P2730 【魔板 Magic Squares】

没看过题的童鞋请去看一下题-->[P2730 魔板 Magic Squares](https://www.luogu.org/problemnew/show/P2730) 不了解康托展开的请来这里-->[我这里](https://rpdreamer.blog.luogu.org/p2524) ## 广告： [安利blog](https://www.luogu.org/blog/RPdreamer/#) 至于这题**为什么可以用康托展开**?~~(瞎说时间到.~~ 因为只有8个数字,且只有1~8这8个数字,所以我们可以算出最多情况有8！=40320个. 所以我们完全可以开数组记录这些状态并且记录这些答案. 康托展开的作用就是**把这些排列映射成一个排名**. 如果我们存储排列,那极限情况应该是87654321,很容易就炸掉的. 而映射成排名的话,我们开的极限只有40320,大约是1/2173的空间. 因此我们就可以这样去存储状态. 即 vis[i]代表排名为i的排列存在 to[i]代表从初状态到达排名为i的状态的操作序列.//要开成string类型. **求解：** 那么如何求解呢？ 对于初状态{1,2,3,4,5,6,7,8}是不变的,因此我们可以用bfs预处理出来其他状态. 而要满足字典序最小,我们可以先尝试进行A操作,B操作,C操作即可。其他操作就和普通的bfs差不多了。 对操作之后的序列,我们去求一下他的排名,那我们就可以得到 变成他的操作序列.把操作序列存储进to[]数组即可。 **ps:字符串string类型支持拼接操作** 而我们**不要忘记把序列还原**。 即改变一个序列有三种操作,我们不能连续进行A,B,C操作,需要对当前的序列操作. 因此就预处理出来了。 **解决：** 然后我们如何输入？(这里卡了好久的QwQ getchar()可以读一切字符~~(应该是~~ 所以我们就可以**每次放一个getchar()**! 而去一位一位的存储读入的字符串。 所以说我们就可以完美的解决这个题啦！ 部分代码参考-->[ @qiqi_starsky](https://blog.csdn.net/qiqi_skystar/article/details/49493357) -------------------代码--------------------- ``` #include<bits/stdc++.h> #define IL inline #define RI register int using namespace std; const int fac[]={1,1,2,6,24,120,720,5040,40320,362880};//阶乘 struct code { string st,step; }s,ss; string to[666666]; bool vis[666666]; IL int Contor(string &s)//这里本应该不加&就可以正确的. //但不加会Wa //应该是你谷评测机的锅. //已经尝试过在bzoj提交,不加&是可以过的 { int ans=0; for(RI i=0;i<8;i++) { //std::cout<<ans<<std::endl; int smaller=0; for(RI j= i+1 ;j<8;j++) { if(s[i] > s[j])smaller++; } ans += smaller*fac[8-i-1]; } return ans+1; } IL void A(string &s) { for(RI i=0;i<4;i++) swap(s[i],s[8-i-1]); } IL void B(string &s) { int t=s[3]; for(RI i=3;i>=1;i--) s[i]=s[i-1]; s[0]=t; int tt=s[4]; for(RI i=4;i<=6;i++) s[i]=s[i+1]; s[7]=tt; } IL void C(string &s) { int t=s[6]; s[6]=s[5]; s[5]=s[2]; s[2]=s[1]; s[1]=t; } /* 1 2 3 4 5 6 7 8 ↓ ↓ ↓ ↓ 1 7 2 4 8 6 3 5 */ IL void bfs() { std::queue<code>q; s.st="12345678"; s.step=""; q.push(s); vis[Contor(s.st)]=true; while(!q.empty()) { s=q.front();q.pop(); ss=s; A(ss.st);//A操作 int cnt=Contor(ss.st);//对于改变的操作序列求出他的排名 if(!vis[cnt]) { ss.step+="A"; to[cnt]=ss.step;//字符串可以直接整个赋过去 q.push(ss);//把一个新的字符串放过去,接下来扩展 vis[cnt]=true;//标记 } ss=s;//还原的操作！！！很重要！ B(ss.st);//B操作 cnt=Contor(ss.st); if(!vis[cnt]) { ss.step+="B"; to[cnt]=ss.step; q.push(ss); vis[cnt]=true; } ss=s; C(ss.st);//C操作 cnt=Contor(ss.st); if(!vis[cnt]) { ss.step+="C"; to[cnt]=ss.step; q.push(ss); vis[cnt]=true; } } } int main() { bfs(); string str; cin>>str[0];getchar();cin>>str[1];getchar(); cin>>str[2];getchar();cin>>str[3];getchar(); cin>>str[4];getchar();cin>>str[5];getchar(); cin>>str[6];getchar();cin>>str[7];getchar(); //这输入厉害不厉害！ int cnt=Contor(str); cout<<to[cnt].length()<<endl;//字符串用.length() cout<<to[cnt]<<endl; } ``` **后话** 如果给定的初始序列不是{1,2,3,4,5,6,7,8}怎么办? 把初始序列看成{1,2,3,4,5,6,7,8}即可 ## Upd **2018.09.03** **回来填坑** 当我们的初始序列不是{1,2,3,4,5,6,7,8}该怎么做？ 例如： 瞎出的例子emmmm 初始状态：65783241——>12345678 对应位置得到这种状态↓ 终止状态：13486572——>85741236 更详细一点↓ 看好如何对应。 初状态 6 5 7 8 3 2 4 1 ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ 对应为 1 2 3 4 5 6 7 8 即我们要把想得到的状态 1 3 4 8 6 5 7 2 用上面的对应关系转化 **过程↓** 1 发现 1->8 3 发现 3->5 4 发现 4->7 8 发现 8->4 6 发现 6->1 5 发现 5->2 7 发现 7->3 2 发现 2->6 最终得到8 5 7 4 1 2 3 6 如果不理解,请仔细再看一下。 这样我们求解{6,5,7,8,3,2,4,1}到{1,3,4,8,6,5,7,2}的操作, 就转变为了{1,2,3,4,5,6,7,8}到{8,5,7,4,1,2,3,6}的操作. 代码实现转化↓(尝试理解一下,~~懒得码字了 emmm~~ ```cpp for (int i=0; i<8 ; i++) num[s[i]-'0']=i+1; //看看我们的枚举,所以需要i+1得到1,2,3.....8 //get关系↑.s存储初状态 //转化关系↓.str存储末状态 for (int i=0; i<8 ; i++) str[i]=num[str[i]-'0']+'0'; ``` 如果有新的知识,我还会来Upd的 **~~(逃~~** ## Upd: **2018.09.05** 关于**康托展开那里的字符串是否需要加&**不知道是否会有疑问? 感谢[@cellur925](https://www.luogu.org/space/show?uid=60124) 的提问 已经在bzoj尝试不加&,是可以AC的. 并通过在我谷下载数据并尝试debug,发现输出是一样的. Contor函数并没有涉及到修改原串,因此不加&应该是正确的. ~~感觉应该是你谷评测机的锅~~ 而其他A,B,C操作是需要修改原串的,需要加&. PS：加&是可以引用变量的.