HDU 汉诺塔系列

做了这一系列题，表示对汉诺塔与这一系列递推理解加深了

经典汉诺塔：1,2,...,n表示n个盘子，数字大盘子就大，n个盘子放在第１根柱子上，按照从上到下 从小到大的顺序排放，过程中每次大盘都不能放在小盘上． 把n个盘子移动到第３根柱子．每次只能移动１个盘子，求把第１根柱子上的盘子全部移动到第3根柱子上需要的最少步数

解法：我们使用dp[n]表示移动前n个盘子从第1根柱子到第3根柱子需要的步数，则我们需要这么做：首先移动前n-1个盘子从1到2，接着移动第n个盘子从1到3，最后我们移动前n-1个盘子从2到3。则我们的步骤就是递推算法：dp[n]=dp[n-1]+1+dp[n-1]，化简就是dp[n]=2^n-1

HDU 1207 汉诺塔II

题意：将基础汉诺塔的三根柱子换成四根，其他不变

题解：http://www.cnblogs.com/fanzhidongyzby/archive/2012/07/28/2613173.html

dp(n)=min(2*dp(n-r)+2^r-1)，（1≤r≤n）

#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<string>
#include<cstdio>
#include<cstring>
#include<iomanip>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define eps 1E-8
/*注意可能会有输出-0.000*/
#define Sgn(x) (x<-eps? -1 :x<eps? 0:1)//x为两个浮点数差的比较,注意返回整型
#define Cvs(x) (x > 0.0 ? x+eps : x-eps)//浮点数转化
#define zero(x) (((x)>0?(x):-(x))<eps)//判断是否等于0
#define mul(a,b) (a<<b)
#define dir(a,b) (a>>b)
typedef long long ull;
typedef unsigned long long ll;
const int Inf=1<<28;
const ll INF=1ll<<60;
const double Pi=acos(-1.0);
const int Mod=1e9+7;
const int Max=350;
ll dp[Max];
ll Mtp(ll num,ll mul)
{
    ll sum=1ll;
    while(mul)
    {
        if(mul&1ll)
            sum*=num;
        num*=num;
        mul>>=1ll;
    }
    return sum;
}
void Init(int n)
{
    dp[1]=1,dp[2]=3;
    for(int i=3; i<n; ++i)
    {
        dp[i]=2ll*dp[i-1]+2ll-1ll;
        for(int j=2; j<=i; ++j)
            dp[i]=min(dp[i],2ll*dp[i-j]+Mtp(2ll,(ll)j)-1ll);
    }
    return;
}
int main()
{
    Init(65);
    int n;
    while(~scanf("%d",&n))
    {
        printf("%llu
",dp[n]);
    }
    return 0;
}

HDU 2064 汉诺塔III

 题意：标准汉诺塔，接着不允许直接从最左(右)边移到最右(左)边(每次移动一定是移到中间杆或从中间移出)，输出移动最小的次数

题解：与标准汉诺塔一样移动但有限制，所以就是dp[n]=3dp[n-1]+2

#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<string>
#include<cstdio>
#include<cstring>
#include<iomanip>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define eps 1E-8
/*注意可能会有输出-0.000*/
#define Sgn(x) (x<-eps? -1 :x<eps? 0:1)//x为两个浮点数差的比较,注意返回整型
#define Cvs(x) (x > 0.0 ? x+eps : x-eps)//浮点数转化
#define zero(x) (((x)>0?(x):-(x))<eps)//判断是否等于0
#define mul(a,b) (a<<b)
#define dir(a,b) (a>>b)
typedef long long ll;
typedef unsigned long long ull;
const int Inf=1<<28;
const ll INF=1ll<<60;
const double Pi=acos(-1.0);
const int Mod=1e9+7;
const int Max=350;
ull dp[Max];
void Init(int n)
{
    dp[1]=2ull;
    for(int i=2;i<n;++i)
    {
        dp[i]=3ull*dp[i-1]+2;
        //printf("%llu
",dp[i]);
    }
}
int main()
{
    Init(36);
    int n;
    while(~scanf("%d",&n))
        printf("%llu
",dp[n]);
    return 0;
}

HDU 2077 汉诺塔IV

题意：在III的基础上，添加了可以将最大的一块放到其他的上面

题解：特判1，接着前n块就是前n-1块再移动第n块的两次就好

#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<string>
#include<cstdio>
#include<cstring>
#include<iomanip>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define eps 1E-8
/*注意可能会有输出-0.000*/
#define Sgn(x) (x<-eps? -1 :x<eps? 0:1)//x为两个浮点数差的比较,注意返回整型
#define Cvs(x) (x > 0.0 ? x+eps : x-eps)//浮点数转化
#define zero(x) (((x)>0?(x):-(x))<eps)//判断是否等于0
#define mul(a,b) (a<<b)
#define dir(a,b) (a>>b)
typedef long long ll;
typedef unsigned long long ull;
const int Inf=1<<28;
const ll INF=1ll<<60;
const double Pi=acos(-1.0);
const int Mod=1e9+7;
const int Max=350;
ull dp[Max];
void Init(int n)
{
    dp[1]=2ull;
    for(int i=2;i<n;++i)
    {
        dp[i]=3ull*dp[i-1]+2;
    }
    return;
}
int main()
{
    Init(21);
    int t,n;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        if(n==1)
            printf("2
");
        else
        printf("%llu
",dp[n-1]+2);
    }
    return 0;
}

HDU 1995 汉诺塔V

题意：标准汉诺塔计算n个盘子的第m个盘子移动的次数

题解：打表找规律：2^(n-m)

#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<string>
#include<cstdio>
#include<cstring>
#include<iomanip>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define eps 1E-8
/*注意可能会有输出-0.000*/
#define Sgn(x) (x<-eps? -1 :x<eps? 0:1)//x为两个浮点数差的比较,注意返回整型
#define Cvs(x) (x > 0.0 ? x+eps : x-eps)//浮点数转化
#define zero(x) (((x)>0?(x):-(x))<eps)//判断是否等于0
#define mul(a,b) (a<<b)
#define dir(a,b) (a>>b)
typedef long long ll;
typedef unsigned long long ull;
const int Inf=1<<28;
const ll INF=1ll<<60;
const double Pi=acos(-1.0);
const int Mod=1e9+7;
const int Max=350;
ull dp[Max][Max];
ull Mtp(ull num,ull mul)
{
    ull sum=1ull;
    while(mul)
    {
        if(mul&1ull)
            sum*=num;
        num*=num;
        mul>>=1ull;
    }
    return sum;
}
void Init(int n)
{
    for(int i=1;i<n;++i)
    {
        for(int j=i;j>=1;--j)
        {
            dp[i][j]=Mtp(2ull,(ull)i-j);
            //printf("%d %d %llu
",i,j,dp[i][j]);
        }
    }
    return;
}
int main()
{
    Init(61);
    int t,n,m;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d %d",&n,&m);
        printf("%llu
",dp[n][m]);
    }
    return 0;
}

HDU 1996 汉诺塔VI

题意：三根柱子上按照汉诺塔的规则放盘子（注意不是最小次数移动的排列数），输出所有可能性的总个数

题解：排列组合：3^n

#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<string>
#include<cstdio>
#include<cstring>
#include<iomanip>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define eps 1E-8
/*注意可能会有输出-0.000*/
#define Sgn(x) (x<-eps? -1 :x<eps? 0:1)//x为两个浮点数差的比较,注意返回整型
#define Cvs(x) (x > 0.0 ? x+eps : x-eps)//浮点数转化
#define zero(x) (((x)>0?(x):-(x))<eps)//判断是否等于0
#define mul(a,b) (a<<b)
#define dir(a,b) (a>>b)
typedef long long ll;
typedef unsigned long long ull;
const int Inf=1<<28;
const ll INF=1ll<<60;
const double Pi=acos(-1.0);
const int Mod=1e9+7;
const int Max=110;
ll dp[Max];
void Init(int n)
{
    dp[1]=3ll;
    for(int i=2;i<n;++i)
        dp[i]=dp[i-1]*3ll;
    return;
}
int main()
{
    Init(31);
    int n,t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n); printf("%lld
",dp[n]);
    }

    return 0;
}

HDU 1997 汉诺塔VII

题意：给定三根柱子上放盘子的顺序，判断是否是最小移动过程中会产生的顺序

题解：我们看汉诺塔移动的规则：n-1个盘子A->B，第n个盘子A->C:这时可看做A,B柱子交换的顺序

因此我们可以看第n个盘子放在哪个柱子上，如果放在B柱子上，则可以判断答是否。

如果放在A柱子上，则交换B,C柱子，如果放在C柱子上，则交换A,B柱子，接着换后再看第n-1个盘子，递归到第1个盘子

#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<string>
#include<cstdio>
#include<cstring>
#include<iomanip>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define eps 1E-8
/*注意可能会有输出-0.000*/
#define Sgn(x) (x<-eps? -1 :x<eps? 0:1)//x为两个浮点数差的比较,注意返回整型
#define Cvs(x) (x > 0.0 ? x+eps : x-eps)//浮点数转化
#define zero(x) (((x)>0?(x):-(x))<eps)//判断是否等于0
#define mul(a,b) (a<<b)
#define dir(a,b) (a>>b)
typedef long long ll;
typedef unsigned long long ull;
const int Inf=1<<28;
const ll INF=1ll<<60;
const double Pi=acos(-1.0);
const int Mod=1e9+7;
const int Max=350;
int x,y,z,flag;
void dfs(int now,int *a,int *b,int *c)//当a或者c的值为now时，可看做a->c,然后b与a柱子交换
{
    if(!now)
        return;
    if(*a==now)
    {
        dfs(now-1,a+1,c,b);
    }
    else if(*c==now)
    {
        dfs(now-1,b,a,c+1);
    }
    else
        flag=0;
    return;
}
int num[3][Max];
int main()
{
    int t,n;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        scanf("%d",&x);
        for(int i=0; i<x; ++i)
        {
            scanf("%d",&num[0][i]);
        }
        num[0][x]=0;
        scanf("%d",&y);
        for(int i=0; i<y; ++i)
        {
            scanf("%d",&num[1][i]);
        }
        num[1][y]=0;
        scanf("%d",&z);
        for(int i=0; i<z; ++i)
        {
            scanf("%d",&num[2][i]);
        }
        num[2][z]=0;
        flag=1;
        dfs(n,num[0],num[1],num[2]);
        if(flag)
            printf("true
");
        else
            printf("false
");
    }
    return 0;
}

HDU 2184 汉诺塔VIII

题意：汉诺塔移动m次后的情况

题解：找到dp[n],再二分找到第n个盘子放的柱子，接着模拟上一个汉诺塔进行柱子交换

#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<string>
#include<cstdio>
#include<cstring>
#include<iomanip>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define eps 1E-8
/*注意可能会有输出-0.000*/
#define Sgn(x) (x<-eps? -1 :x<eps? 0:1)//x为两个浮点数差的比较,注意返回整型
#define Cvs(x) (x > 0.0 ? x+eps : x-eps)//浮点数转化
#define zero(x) (((x)>0?(x):-(x))<eps)//判断是否等于0
#define mul(a,b) (a<<b)
#define dir(a,b) (a>>b)
typedef long long ll;
typedef unsigned long long ull;
const int Inf=1<<28;
const ll INF=1ll<<60;
const double Pi=acos(-1.0);
const int Mod=1e9+7;
const int Max=350;
void dfs(int now,int *a,int *b,int *c,ll m,ull sum)
{
    if(!now)
        return;
    if(sum/2ull>m)//左边
    {
        *a=now;
        *(a+1)=0;
        dfs(now-1,a+1,c,b,m,sum/2);
    }
    else
    {
        *c=now;
        *(c+1)=0;
        dfs(now-1,b,a,c+1,m-sum/2,sum/2);
    }
    return;
}
int num[3][Max];
ull Mtp(ull dig,ull mul)
{
    ull sum=1ull;
    while(mul)
    {
        if(mul&1)
            sum*=dig;
        dig*=dig;
        mul>>=1ull;
    }
    return sum;
}
void Solve(int n,ll m)
{
    int a,b,c;
    ull sum=Mtp(2ull,(ull)n);
    dfs(n,num[0],num[1],num[2],m,sum);
    for(a=0; num[0][a]; ++a);
    for(b=0; num[1][b]; ++b);
    for(c=0; num[2][c]; ++c);
    printf("%d",a);
    for(int i=0;i<a;++i)
        printf(" %d",num[0][i]);
    printf("
");
        printf("%d",b);
    for(int i=0;i<b;++i)
        printf(" %d",num[1][i]);
    printf("
");
        printf("%d",c);
    for(int i=0;i<c;++i)
        printf(" %d",num[2][i]);
    printf("
");
    return ;
}
int main()
{
    int t,n;
    ll m;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d %I64d",&n,&m);
        Solve(n,m);
    }
    return 0;
}

HDU 2077 汉诺塔IX

题意：标准汉诺塔求第m次移动的是那一个盘子

题解：求出移动m-1次后情况与移动m次后的情况，通过三个柱子上最上面的盘子的情况来看

#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<string>
#include<cstdio>
#include<cstring>
#include<iomanip>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define eps 1E-8
/*注意可能会有输出-0.000*/
#define Sgn(x) (x<-eps? -1 :x<eps? 0:1)//x为两个浮点数差的比较,注意返回整型
#define Cvs(x) (x > 0.0 ? x+eps : x-eps)//浮点数转化
#define zero(x) (((x)>0?(x):-(x))<eps)//判断是否等于0
#define mul(a,b) (a<<b)
#define dir(a,b) (a>>b)
typedef long long ll;
typedef unsigned long long ull;
const int Inf=1<<28;
const ll INF=1ll<<60;
const double Pi=acos(-1.0);
const int Mod=1e9+7;
const int Max=350;
void dfs(int now,int *a,int *b,int *c,ull m,ull sum)
{
    if(!now)
        return;
    if(sum/2ull>m)//左边
    {
        *(a+1)=now;
        *(a+2)=0;
        dfs(now-1,a+1,c,b,m,sum/2);
    }
    else
    {
        *(c+1)=now;
        *(c+2)=0;
        dfs(now-1,b,a,c+1,m-sum/2,sum/2);
    }
    return;
}
int num[2][3][Max];
ull Mtp(ull dig,ull mul)
{
    ull sum=1ull;
    while(mul)
    {
        if(mul&1)
            sum*=dig;
        dig*=dig;
        mul>>=1ull;
    }
    return sum;
}
int Solve(int n,ull m)
{
    int dig[10];
    memset(num,0,sizeof(num));
    dfs(n,num[0][0],num[0][1],num[0][2],m-1ull,Mtp(2ull,(ull)n));
    dfs(n,num[1][0],num[1][1],num[1][2],m,Mtp(2ull,(ull)n));
    int a1,a2,b1,b2,c1,c2;
    for(a1=1;num[0][0][a1];++a1);
    for(a2=1;num[1][0][a2];++a2);
    for(b1=1;num[0][1][b1];++b1);
    for(b2=1;num[1][1][b2];++b2);
    for(c1=1;num[0][2][c1];++c1);
    for(c2=1;num[1][2][c2];++c2);
    int coun=0;
    if(num[0][0][a1-1]!=num[1][0][a2-1])
    {
        dig[coun++]=num[0][0][a1-1];
        dig[coun++]=num[1][0][a2-1];
    }
    if(num[0][1][b1-1]!=num[1][1][b2-1])
    {
        dig[coun++]=num[0][1][b1-1];
        dig[coun++]=num[1][1][b2-1];
    }
    if(num[0][2][c1-1]!=num[1][2][c2-1])
    {
        dig[coun++]=num[0][2][c1-1];
        dig[coun++]=num[1][2][c2-1];
    }
        sort(dig,dig+coun);
    for(int i=0;i<coun-1;++i)
    {
        if(dig[i]==dig[i+1]&&dig[i])
        {
                return dig[i];
        }
    }
}
int main()
{
    std::ios::sync_with_stdio(false);
    int n;
    ull m;
    while(cin >> n >> m)
    {
        if(!n&&n==0ull)
            break;
            cout << Solve(n,m) << endl;
    }
    return 0;
}

HDU  2511 汉诺塔X

题意：标准汉诺塔求第m次移动的是那一个盘子，并且求出是从哪个柱子移到哪个柱子

题解：与前一个汉诺塔一样

#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<string>
#include<cstdio>
#include<cstring>
#include<iomanip>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define eps 1E-8
/*注意可能会有输出-0.000*/
#define Sgn(x) (x<-eps? -1 :x<eps? 0:1)//x为两个浮点数差的比较,注意返回整型
#define Cvs(x) (x > 0.0 ? x+eps : x-eps)//浮点数转化
#define zero(x) (((x)>0?(x):-(x))<eps)//判断是否等于0
#define mul(a,b) (a<<b)
#define dir(a,b) (a>>b)
typedef long long ll;
typedef unsigned long long ull;
const int Inf=1<<28;
const ll INF=1ll<<60;
const double Pi=acos(-1.0);
const int Mod=1e9+7;
const int Max=350;
void dfs(int now,int *a,int *b,int *c,ull m,ull sum)
{
    if(!now)
        return;
    if(sum/2ull>m)//左边
    {
        *(a+1)=now;
        *(a+2)=0;
        dfs(now-1,a+1,c,b,m,sum/2);
    }
    else
    {
        *(c+1)=now;
        *(c+2)=0;
        dfs(now-1,b,a,c+1,m-sum/2,sum/2);
    }
    return;
}
int num[2][3][Max];
ull Mtp(ull dig,ull mul)
{
    ull sum=1ull;
    while(mul)
    {
        if(mul&1)
            sum*=dig;
        dig*=dig;
        mul>>=1ull;
    }
    return sum;
}
void Solve(int n,ull m)
{
    int dig[10];
    memset(num,0,sizeof(num));
    dfs(n,num[0][0],num[0][1],num[0][2],m-1ull,Mtp(2ull,(ull)n));
    dfs(n,num[1][0],num[1][1],num[1][2],m,Mtp(2ull,(ull)n));
    int a1,a2,b1,b2,c1,c2;
    for(a1=1;num[0][0][a1];++a1);
    for(a2=1;num[1][0][a2];++a2);
    for(b1=1;num[0][1][b1];++b1);
    for(b2=1;num[1][1][b2];++b2);
    for(c1=1;num[0][2][c1];++c1);
    for(c2=1;num[1][2][c2];++c2);
    int coun=0;
    if(num[0][0][a1-1]!=num[1][0][a2-1])
    {
        dig[coun++]=num[0][0][a1-1];
        dig[coun++]=num[1][0][a2-1];
    }
    if(num[0][1][b1-1]!=num[1][1][b2-1])
    {
        dig[coun++]=num[0][1][b1-1];
        dig[coun++]=num[1][1][b2-1];
    }
    if(num[0][2][c1-1]!=num[1][2][c2-1])
    {
        dig[coun++]=num[0][2][c1-1];
        dig[coun++]=num[1][2][c2-1];
    }
    int temp;
        sort(dig,dig+coun);
    for(int i=0;i<coun-1;++i)
    {
        if(dig[i]==dig[i+1]&&dig[i])
        {
                cout << dig[i] << " ";
                temp=dig[i];
                break;
        }
    }
    if(num[0][0][a1-1]==temp)
        cout << "1 ";
        if(num[0][1][b1-1]==temp)
        cout << "2 ";
            if(num[0][2][c1-1]==temp)
        cout << "3 ";

        if(num[1][0][a2-1]==temp)
        cout << "1" << endl;
        if(num[1][1][b2-1]==temp)
        cout << "2" << endl;
            if(num[1][2][c2-1]==temp)
        cout << "3" << endl;
    return;
}
int main()
{
    std::ios::sync_with_stdio(false);
    int n,t;
    ull m;
    cin >> t;
    while(t--)
    {
        cin >> n >> m;
            Solve(n,m);;
    }
    return 0;
}