16哈理工新生赛 E Nine Digits (BFS+康拓展开) 妖狐艹你老母 2022-07-14 09:42 74阅读 0赞 <table> <tbody> <tr> <td><span style="font-size:18px">题目链接:<a href="http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=2297" rel="nofollow">点击打开链接</a><br> <br> Nine Digits</span></td> </tr> <tr> <td> <table> <tbody> <tr> <td><span style="font-size:18px">Time Limit: 3000 MS</span></td> <td><span style="font-size:18px">Memory Limit: 32768 K</span></td> </tr> </tbody> </table> <table> <tbody> <tr> <td><span style="font-size:18px">Total Submit: 69<span>(19 users)</span></span></td> <td><span style="font-size:18px">Total Accepted: 16<span>(12 users)</span></span></td> <td><span style="font-size:18px">Rating: <img src="http://acm.hrbust.edu.cn/Public/images/star-solid.png" alt=""><img src="http://acm.hrbust.edu.cn/Public/images/star-solid.png" alt=""><img src="http://acm.hrbust.edu.cn/Public/images/star-solid.png" alt=""><img src="http://acm.hrbust.edu.cn/Public/images/star-half2.png" alt=""></span></td> <td><span style="font-size:18px">Special Judge: <span> No</span></span></td> </tr> </tbody> </table> </td> </tr> <tr> <td><span style="font-size:18px">Description</span></td> </tr> <tr> <td><span style="font-size:18px"><img alt="" src="http://acm.hrbust.edu.cn/contests/attached/image/20161125/20161125122308_33369.jpg"></span></td> </tr> <tr> <td><span style="font-size:18px">Input</span></td> </tr> <tr> <td> <p style="text-indent:21pt"><span style="font-size:18px"><span style="font-family:宋体">多组数据,每组测试数据输入</span><span style="">9</span><span style="font-family:宋体">个整数,为</span><span style="">1-9</span><span style="font-family:宋体">的一个全排列。初始状态会被描述为</span><span style=""></span></span></p> <p style="text-indent:21pt"><span style="font-size:18px"><span style="">1 2 3 4 5 6 7 8 9</span></span></p> </td> </tr> <tr> <td><span style="font-size:18px">Output</span></td> </tr> <tr> <td> <p style="text-indent:21pt"><span style="font-size:18px"><span style="font-family:宋体">输出所需要的最小移动步数。</span><span style=""></span></span></p> </td> </tr> <tr> <td><span style="font-size:18px">Sample Input</span></td> </tr> <tr> <td> <p><span style="font-size:18px">1 2 3 4 5 6 7 8 9 </span></p> <p><span style="font-size:18px">9 8 7 6 5 4 3 2 1 </span></p> <p><span style="font-size:18px"><br> </span></p> </td> </tr> <tr> <td><span style="font-size:18px">Sample Output</span></td> </tr> <tr> <td> <p><span style="font-size:18px">0 </span></p> <p><span style="font-size:18px"><span style="color:#e53333">12</span> </span></p> <p><span style="font-size:18px"><br> </span></p> </td> </tr> <tr> <td><span style="font-size:18px">Source</span></td> </tr> <tr> <td><span style="font-size:18px">2016级新生程序设计全国邀请赛</span></td> </tr> </tbody> </table> 题解: 一看题目,我就想到BFS,就是把所有情况搜出来,也就是9的阶乘362880种情况。但是由于不能够建立一个九位数的数组来保存这些数据,因此这里需要用到康托展开。 康托展开的使用范围是对于n个数的排列进行状态的压缩和存储,例如要对9的全排列进行判重.没有必要开一个10的9次幂的数组,因此它有362880中情况。因此其思想就是相当于一个哈希函数。一个排列它所对应的位置就是它排的是第几大。比如321,对应的值就是6,因为前面有123,132,213,231,312比它小。下面的cantor( )函数就是。 做完康托展开后,就要实现四种情况的变换,这个也比较简单,使用四个函数来实现即可,但是写的过程需要特别小心。 AC代码: #include<iostream> #include<cstdio> #include<queue> using namespace std; const int MAX=362880; int s[9]={1,10,100,1000,10000,100000,1000000,10000000,100000000}; int jie[10]={0,1,2,6,24,120,720,5040,40320,362880}; int visit[MAX]; int len[MAX]; int four[4]; int lu(int num) { int result; result=num%s[4]; result+=((num/s[5])%10)*s[4]; result+=num/s[8]*s[5]; result+=((num/s[6])%10)*s[6]; result+=((num/s[4])%10)*s[7]; result+=((num/s[7])%10)*s[8]; return result; } int ru( int num ) { int result = num/s[5]*s[5]; result += num/s[1]%10; result += num/s[4]%10*s[1]; result += num/s[2]%10*s[2]; result += num%10*s[3]; result += num/s[3]%10*s[4]; return result; } int ld( int num ) { int result = num/s[6]*s[6] + num%10; result += num/s[2]%10*s[1]; result += num/s[5]%10*s[2]; result += num/s[3]%10*s[3]; result += num/s[1]%10*s[4]; result += num/s[4]%10*s[5]; return result; } int rd( int num ) { int result = num % s[3] + num/s[8]*s[8]; result += num/s[4]%10*s[3]; result += num/s[7]%10*s[4]; result += num/s[5]%10*s[5]; result += num/s[3]%10*s[6]; result += num/s[6]%10*s[7]; return result; } int cantor(int key) //康拓展开 { int result,temp[9]; for(int i=8;i>=0;i--) { temp[i]=key%10; key=key/10; } result=0; for(int i=0;i<8;i++) { int tot=0; for(int j=i+1;j<9;j++) if(temp[j]<temp[i]) tot++; result+=tot*jie[8-i]; } return result; } int key2[4]; int start=123456789; queue<int>que; int main() { int temp; int key1; len[0]=0; que.push(start); visit[0]=1; while(!que.empty()) { temp=que.front(); que.pop(); key1=cantor(temp); four[0]=lu(temp); four[1]=ru(temp); four[2]=ld(temp); four[3]=rd(temp); for(int i=0;i<4;i++) { key2[i]=cantor(four[i]); if(!visit[key2[i]]) { visit[key2[i]]=1; que.push(four[i]); len[key2[i]]=len[key1]+1; } } } int input[9]; while(~scanf("%d",&input[0])) { temp=input[0]; for(int i=1;i<9;i++) { scanf("%d",&input[i]); temp=input[i]+temp*10; } printf("%d\n",len[cantor(temp)]); } return 0; }
还没有评论,来说两句吧...