【牛客小白月赛21】NC201605 Bits
题目描述
Nancy喜欢做游戏！
汉诺塔是一个神奇的游戏，神奇在哪里呢？
给出3根柱子，最开始时n个盘子按照大小被置于最左的柱子。
如果盘子数为偶数，则需要将她们全部移动到最右侧的柱子上，否则将她们移动到中间的柱子上。
那么，Nancy该怎样移动呢？请你输出汉诺塔游戏的过程叭！
输入描述:
共一行：一个整数n
输出描述:
共2^n组：每组n+2行，每行3×(2n+1)+4个字符，用.表示空白区域，用|表示柱子区域，用*表示盘子。组与组之间请输出3×(2n+1)+4个-。
具体输出方式请参看样例进行理解。
输入：2
输出：
................... ...|.....|.....|... ..***....|.....|... .*****...|.....|... ------------------- ................... ...|.....|.....|... ...|.....|.....|... .*****..***....|... ------------------- ................... ...|.....|.....|... ...|.....|.....|... ...|....***..*****. ------------------- ................... ...|.....|.....|... ...|.....|....***.. ...|.....|...*****.
解析
方法一：
一不小心拿了个运行时间最快qwq（8ms）（截至2020-01-28）
在别的题解中看到用二进制来解汉诺塔问题这个视频，又看大多数人都是用递归写的，便想试一试二进制做法。这个视频说的就是汉诺塔与二进制的关系（从视频的第6分钟开始）。
我对这个视频的大致理解就是，在二进制中，比如想从0000加到1111(其实就是f[n])，那就要先加111步(其实就是f[n-1])到0111，再加1步得1000，再加111步到1111，这与汉诺塔的递归策略很相似，想移动n个盘必须先用f[n-1]步移动n-1个到第二个柱，再用1步把第n个移到第三个柱，最后再用f[n-1]步移动n-1个到第三个柱，这显然是最优解，没有任何步数的浪费（其实这就得出了汉诺塔的递推式：f[n]=f[n-1]*2+1）。
所以根据这种二进制与汉诺塔的相似性，我们完全可以通过枚举二进制来模拟汉诺塔的移动，如有n个盘，那我们就要从1枚举到2^n-1（即n位二进制1，其实n盘汉诺塔的最少移动次数f[n]就等于2^n-1），对于每个数，我们看它最后一个1在第几位，如在第num位，也就是该移动第num
个盘了，就把编号为n的盘向右移动到下一个可行的柱子（柱子3的下一个柱子是柱子1）上。
你想操作二进制第n位的1，必须等第n位后没有1，也就是要把后面的1消除，这与汉诺塔的最优解规律是一致的：如果你想移动第n个盘，必须等这个盘子上没有其他盘，也就是移去上面的盘，所以这种移动的二进制规律肯定是最优解。
掌握了这个思路，接下来就是耐心考虑怎么输出图案了qwq
#include<math.h>
#include<string>
#include<iostream>
using namespace std;
int t[3][12],count[3],n,m,width;
//t[i][j]存储第i号柱的第j层的盘的编号（柱从0开始编号），count是柱上的盘子数，width=2*n+1，即最大盘的宽度
int order[6]= {0,1,2,0,1,2},number[11];
//order是塔的顺序，由于要向右移动到下一个可行的柱子上，柱子编号超过2要回到编号0，number[i]是编号为i的盘所在的柱子
string _begin,_str,str;
//_begin是每组图形的开头部分，_str是“...|.....|.....|...”，str用于输出每行的实际情况
inline void print() {
for (int floor=n,pos,len;floor;floor--){//从第n层向下依次输出
str=_str;//初始化为“...|.....|.....|...”
for (int i=0;i<3;i++){//画上每个柱此层的盘子
if (count[i]>=floor){//如果有盘子
len=2*t[i][floor]+1;//盘子宽
pos=width*i+i+1+(width-len)/2;//画盘子的起始位置，width最大盘的宽度，即柱子间的距离，注意柱子间还会多空出一位
for (int j=pos+1;j<=pos+len;j++)
str[j-1]='*';//画上盘子，由于是字符串，j减1
}
}
cout<<str<<"\n";
}
}
int main() {
ios::sync_with_stdio(false);
cin>>n,m=6*n+7;//m是行的长度
for (int i=1; i<=n; i++) t[0][i]=n-i+1;
count[0]=n;//把n个盘放在第0个柱上
for (int i=0; i<m; i++) _begin+='.',_str+='.';
width=2*n+1;
_str[width/2+1]=_str[width+2+width/2]=_str[width*2+3+width/2]='|';//画上中间的“|”
_begin+="\n"+_str+"\n";
cout<<_begin;
//这里的begin是“................... ...|.....|.....|...”两行，第一行没有“-------------------”
print();//输出第一组图形
string tmp;
for (int i=0; i<m; i++) tmp+='-';
_begin=tmp+"\n"+_begin;
//这里的begin是“------------------- ................... ...|.....|.....|...”三行
for (register int i=1,lim=(1<<n); i<lim; i++) {//从1枚举到2^n-1
int num=log2(i&-i)+1,_number=number[num];//i&-i是最后一位1加上后面的0所表示的数，用log2求出它的二进制位数，num即是要移动的盘子编号，_number是此盘所在柱子
cout<<_begin;
for (int j=1,k; j<3; j++) {//寻找移动到哪一个柱子上
k=order[_number+j];//k是柱子的编号
if (t[k][count[k]]>num || !count[k]) {//如果柱上最后一个盘大于num或柱上没有盘，则可行
number[num]=k,t[k][++count[k]]=num;
count[_number]--;//移动盘子，更新信息
break;
}
}
print();
}
}此外还有个小细节，就是用这种二进制规律做出来的结果正好符合题目要求：“如果盘子数为偶数，则需要将它们全部移动到最右侧的柱子上，否则将它们移动到中间的柱子上。”可是如果题目要求变换一下（比如把“偶数”换成“奇数”），对于递归做法很好改，但这个做法是不是还行呢？
然而，强大的二进制规律告诉我们：照样可以，只要把第50行换为“for (int j=2,k; j>0; j--)”，即从左开始找即可。
方法二：
由于菜鸡我没怎么写过汉诺塔递归，想试试大家喜闻乐见的递归写法qwq
一不小心又拿了个运行时间最快qwq（8ms）（截至2020-01-28）（逃
只要稍微改动一下即可，关于字符串输出和print()的注释请参照方法一
#include<string>
#include<iostream>
using namespace std;
int t[3][12],count[3],n,m,width;
string _begin,_str,str;
inline void print() {
for (int floor=n,pos,len;floor;floor--){
str=_str;
for (int i=0;i<3;i++){
if (count[i]>=floor){
len=2*t[i][floor]+1;
pos=width*i+i+1+(width-len)/2;
for (int j=pos+1;j<=pos+len;j++)
str[j-1]='*';
}
}
cout<<str<<"\n";
}
}
inline void move(int a,int b){//从a柱移动一个到b柱
t[b][++count[b]]=t[a][count[a]--];
cout<<_begin;
print();
}
void hanoi(int a,int b,int x){//从a柱移动x个到b柱
if (x==1) {
move(a,b);
return;
}
hanoi(a,3-a-b,x-1);//3-a-b是中转柱，注意柱子编号从0开始
move(a,b);
hanoi(3-a-b,b,x-1);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n,m=6*n+7;
for (int i=1; i<=n; i++) t[0][i]=n-i+1;
count[0]=n;
for (int i=0; i<m; i++) _begin+='.',_str+='.';
width=2*n+1;
_str[width/2+1]=_str[width+2+width/2]=_str[width*2+3+width/2]='|';
_begin+="\n"+_str+"\n";
cout<<_begin;
print();
string tmp;
for (int i=0; i<m; i++) tmp+='-';
_begin=tmp+"\n"+_begin;
n&1 ? hanoi(0,1,n):hanoi(0,2,n);//如果盘子数为偶数，则需要将它们全部移动到最右侧的柱子上，否则将它们移动到中间的柱子上。
}如果各位大佬有更好的理解或想法，欢迎提出改进和建议qwq！
京公网安备 11010502036488号