我的思路：本质还是dfs，但是用m的值来指引方向，每搜一层确定第i个盘子在哪个塔，o（n）的算法，看图说明：
#include<iostream>
#include<vector>
using namespace std;
char get[65]; //记录I号盘子在哪个塔
long long f[65]; //2^i次的值
void got() //预处理的f[i]; 注意点：用1<<i会爆int。
{
f[1]=2;
for(int i=2;i<65;i++)
f[i]=f[i-1]*2;
}
void dfs(char fl,char fr,char now,int lev,long long x) //同汉若塔第七代理，LVE是层数，x是目前的值
{
get[lev]=now;
if(lev==1)return; //出口
char temp;
if(fl=='A'&&fr=='B'||fl=='B'&&fr=='A')temp='C';
else if(fl=='A'&&fr=='C'||fl=='C'&&fr=='A')temp='B';
else temp='A';
lev--;
long long tx=(f[lev]-1)/2;
if(x<=tx) //小于它的
{
if(now==fl) //左边的下来
dfs(fl,temp,fl,lev,x);
else
dfs(temp,fr,temp,lev,x);
}
else
{
if(now==fl)
dfs(fl,temp,temp,lev,x-tx-1); //减一，那一步是最下面的塔的移动
else
dfs(temp,fr,fr,lev,x-tx-1);
}
}
int main()
{
got();
int T;
cin>>T;
while(T--)
{
long long n,m;
cin>>n>>m;
if(m<=(f[n]-1)/2)
dfs('A','C','A',n,m);
else
dfs('A','C','C',n,m-(f[n]-1)/2);
vector<int>a,b,c;
for(int i=n;i>=1;i--)
{
if(get[i]=='A')a.push_back(i);
else if(get[i]=='B')b.push_back(i);
else c.push_back(i);
}
cout<<a.size();
for(int i=0;i<a.size();i++)
cout<<" "<<a[i];
cout<<endl;
cout<<b.size();
for(int i=0;i<b.size();i++)
cout<<" "<<b[i];
cout<<endl;
cout<<c.size();
for(int i=0;i<c.size();i++)
cout<<" "<<c[i];
cout<<endl;
}
return 0;
}
汉若塔IX hdu2175，经典汉若塔问题上问第M次移动的是几号盘。
思路：同理，第n个盘之前，必先移动前n-1个，再移动第n号，再移动前n-1个，依次。所以二分法查找，在“中间”那个移动的酒在那一个盘了。
#include<iostream>
using namespace std;
long long f[65]; //2^i次的值
void got() //预处理的f[i]; 注意点：用1<<i会爆int。
{
f[0]=1;f[1]=2;
for(int i=2;i<65;i++)
f[i]=f[i-1]*2;
}
int main()
{
got();
long long n,m;
while(cin>>n>>m&&(n||m))
{
while(m!=f[n-1])
{
if(m<=f[n-1]-1)
;
else
m=m-f[n-1];
n--;
}
cout<<n<<endl;
}
return 0;
}
汉若塔X hdu2511 求第m次移动是把几号盘从哪个塔到哪个塔移动。第九代的扩展。
思路：做到这里，每步的移动已经一清二楚了，还是那颗树，“左中右”遍历序列便是所有状态。由于一共就6种可能移动法。每次移动后知道下一步的移动。
依旧采用二分寻根法，详见代码：
#include<iostream>
#include<string>
using namespace std;
long long f[65]; //2^i次的值
void got() //预处理的f[i]; 注意点：用1<<i会爆int。
{
f[0]=1;f[1]=2;
for(int i=2;i<65;i++)
f[i]=f[i-1]*2;
}
string getnext(string s,int id) //状态转移
{
if(s=="AC")
{
if(id==0)return "AB";
else return "BC";
}
else if(s=="AB")
{
if(id==0)return "AC";
else return "CB";
}
else if(s=="CB")
{
if(id==0)return "CA";
else return "AB";
}
else if(s=="CA")
{
if(id==0)return "CB";
else return "BA";
}
else if(s=="BA")
{
if(id==0)return "BC";
else return "CA";
}
else if(s=="BC")
{
if(id==0)return "BA";
else return "AC";
}
}
int main()
{
got();
int T;
cin>>T;
long long n,m;
while(T--)
{
cin>>n>>m;
string s="AC";
while(m!=f[n-1])
{
if(m<=f[n-1]-1)
{
s=getnext(s,0);
}
else
{
s=getnext(s,1);
m=m-f[n-1];
}
n--;
}
if(s=="AB")
cout<<n<<" 1 2"<<endl;
if(s=="BA")
cout<<n<<" 2 1"<<endl;
if(s=="AC")
cout<<n<<" 1 3"<<endl;
if(s=="CA")
cout<<n<<" 3 1"<<endl;
if(s=="BC")
cout<<n<<" 2 3"<<endl;
if(s=="CB")
cout<<n<<" 3 2"<<endl;
}
return 0;
}