HDU 汉诺塔系列

一、经典汉诺塔

题意

有三根柱子 A,B,C，柱子 A 上放着 n 个大小不同的盘子，从上往下，盘子大小依次增大。要把所有盘子都移到柱子B上，且移动的过程中，同一根柱子不能出现大盘子在小盘子上方的情况，问至少需要多少次移动。

分析

设 F[n] 为将 n 个盘子从柱子A移动到柱子B的最少移动次数。

当 n = 1 时，F[n] = 1

当 n > 1 时，分三步

①将柱子A上的 n - 1 个盘子，依靠柱子B，移动到柱子C上，这个过程至少需要 F[n - 1]步

②将柱子A上最大的那个盘子放到柱子B上，需要 1 步

③将柱子C上的 n - 1 个盘子，依靠柱子A，移动到柱子B上，这个过程至少需要 F[n - 1]步

所以移动完 n 个盘子，至少需要的步数 F[n] = 2 * F[n - 1] + 1；

其中 F[1] = 1，那么就有 F[n] = 2^n - 1；

二、HDU 1207 汉诺塔Ⅱ （传送门）

题意

有四根柱子 A,B,C，D，柱子 A 上放着 n 个大小不同的盘子，从上往下，盘子大小依次增大。要把所有盘子都移到柱子B上，且移动的过程中，同一根柱子不能出现大盘子在小盘子上方的情况，问至少需要多少次移动。（1 <= n <= 64）

分析

设 F[n] 为将 n 个盘子从柱子A移动到柱子B的最少移动次数。

当 n = 1 时，F[n] = 1；

当 n = 2 时，F[n] = 3；

当 n > 2 时，分三步

①将柱子A上的 x (1 <= x < n) 个盘子，依靠柱子B,C移动到柱子D上，这个过程至少需要 F[x] 步

②将柱子A上剩下的 n - x 个盘子，依靠柱子C移动到柱子B上，这个过程相当于经典汉诺塔问题，则需要 2^(n-x) - 1 步

③将柱子D上的 x 个盘子，依靠柱子A,C移动到柱子B上，这个过程至少需要 F[x] 步。

那我们可以枚举这个 x，对所有可能的答案取最小值

当 n = 64 时，x = 0 时，2^64 就很大了，会爆 long long，所以我特判掉了这种情况

#include <bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define UI unsigned int
#define mem(i, j) memset(i, j, sizeof(i))
#define rep(i, j, k) for(int i = j; i <= k; i++)
#define dep(i, j, k) for(int i = k; i >= j; i--)
#define pb push_back
#define make make_pair
#define INF 0x3f3f3f3f
#define inf LLONG_MAX
#define PI acos(-1)
#define fir first
#define sec second
#define lb(x) ((x)h & (-(x)))
#define dbg(x) cout<<#x<<" = "<<x<<endl;
using namespace std;

const int N = 1e6 + 5;

const LL mod = 1e9 + 7;

LL ksm(LL a, LL b) {

    LL res = 1LL;

    while(b) {

        if(b & 1) res = res * a;

        a = a * a;

        b >>= 1;

    }

    return res;

}

LL f[N];

void solve() {

    f[1] = 1;

    f[2] = 3;

    rep(i, 3, 64) {

        f[i] = inf;

        rep(j, 0, i - 1) {

            if(i - j >= 63) continue;

            f[i] = min(f[i], 2 * f[j] + ksm(2, i - j) - 1);

        }

    }
    
    int n;
    
    while(~scanf("%d", &n)) printf("%lld
", f[n]);

}



int main() {

//    int _; scanf("%d", &_);
//    while(_--) solve();

    solve();

    return 0;
}
View Code

三、HDU 1995 汉诺塔Ⅴ（传送门）

题意

有三根柱子 A,B,C，柱子 A 上放着 n 个大小不同的盘子，从上往下，盘子大小依次增大，我们将其依次编号为 1 2 ...... n，即编号越大，大小越大。要把所有盘子都移到柱子B上，且移动的过程中，同一根柱子不能出现大盘子在小盘子上方的情况，问按照最优的方式移动 n 个盘子，编号为 k 的盘子需要移动多少次。（1 <= n <= 60, 1 <= k <= n）

分析

画一画就能发现规律了，答案是 2^(n - k)；所有盘子需要移动 2^n - 1 次，2^n - 1 二进制形式就是 n 个 1，最大的那个盘子只需要移动 1 次，倒数第二个需要移动 2 次，倒数第 3 个需要移动 4 次........

#include <bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define UI unsigned int
#define mem(i, j) memset(i, j, sizeof(i))
#define rep(i, j, k) for(int i = j; i <= k; i++)
#define dep(i, j, k) for(int i = k; i >= j; i--)
#define pb push_back
#define make make_pair
#define INF 0x3f3f3f3f
#define inf LLONG_MAX
#define PI acos(-1)
#define fir first
#define sec second
#define lb(x) ((x)h & (-(x)))
#define dbg(x) cout<<#x<<" = "<<x<<endl;
using namespace std;

const int N = 1e6 + 5;

const LL mod = 1e9 + 7;

LL ksm(LL a, LL b) {

    LL res = 1LL;

    while(b) {

        if(b & 1) res = res * a;

        a = a * a;

        b >>= 1;

    }

    return res;

}

void solve() {

    int n, k;
    
    while(~scanf("%d %d", &n, &k)) printf("%lld
", ksm(2, n - k));
    

}



int main() {

    int _; scanf("%d", &_);
    while(_--) solve();

//    solve();

    return 0;
}
View Code

四、HDU 1997 汉诺塔VII （传送门）

题意

这题是经典汉诺塔改版，问的是，将 n 个盘子（第 i 个盘子编号为 i，编号越大，盘子越大）从 a 移动到 c，按照步数最少策略移动，现在给你三个序列，分别代表柱子 a, b, c 上的盘子的编号，问你这三个序列是不是将 n 个盘子从 a 移动到 c 这个过程中的一种情况。

思路

参考博客

这个题呢，可以用递归的方式去求解，要理解经典汉诺塔盘子是怎么移动的。

若要将 n 个盘子从 a 移动到 c，首先，先将 n - 1 个盘子，从 a 移动到 b，然后再将第 n 个，移动到 c 上。

这个过程中，第 n 个盘子只能出现在柱子 a 和 柱子 c 上，若出现在柱子 b 上，则不正确。

那就接着分类

若第 n 个盘子出现在 a 上，则表示第 n 个盘子还没有移动到 c，则这种情况就是，将 n - 1 个盘子，从柱子 a 移动到柱子 b 上。

若第 n 个盘子出现在 c 上，则表示第 n 个盘子已经移动到柱子 c 上了，这种情况就是将 n - 1 个盘子从 b 移动到 c 上。

就这样一直递归下去若全部盘子都满足条件，则是正确的。

#include <bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define UI unsigned int
#define mem(i, j) memset(i, j, sizeof(i))
#define rep(i, j, k) for(int i = j; i <= k; i++)
#define dep(i, j, k) for(int i = k; i >= j; i--)
#define pb push_back
#define make make_pair
#define INF 0x3f3f3f3f
#define inf LLONG_MAX
#define PI acos(-1)
#define fir first
#define sec second
#define lb(x) ((x)h & (-(x)))
#define dbg(x) cout<<#x<<" = "<<x<<endl;
using namespace std;

const int N = 1e6 + 5;

bool judge(int n, int a[], int c[], int b[]) {

    if(a[0] == n) return judge(n - 1, a + 1, b, c);

    else if(c[0] == n) return judge(n - 1, b, c + 1, a);

    else if(b[0] == n) return 0;

    else return 1;

}

int a[N], b[N], c[N];

void solve() {

    int n, m, p, q;

    scanf("%d", &n);

    scanf("%d", &m);

    rep(i, 0, m - 1) scanf("%d", &a[i]);

    scanf("%d", &p);

    rep(i, 0, p - 1) scanf("%d", &b[i]);

    scanf("%d", &q);

    rep(i, 0, q - 1) scanf("%d", &c[i]);

    a[m] = b[p] = c[q] = -1;

    if(judge(n, a, c, b)) puts("true");

    else puts("false");

}



int main() {

    int _; scanf("%d", &_);
    while(_--) solve();

//    solve();

    return 0;
}
View Code

五、HDU 2064  汉诺塔III （传送门）

题意

经典汉诺塔问题再加一个条件：最左边柱子上的盘子不能直接移动到最右边的柱子，最右边柱子上的盘子也不能直接移动到最左边的柱子。问将 n 个盘子，从最左边的柱子 a，经过柱子 b，移动到最右边的柱子 c 上的最少移动步数。

思路

设 dp[n] 表示将 n 个盘子从 a 经过 b 移动到 c 的最少移动步数。

则，将 n 个盘子从 a 经过 b 移动到 c 上，可以分为几个过程：

1、将 n - 1 个盘子从 a 经 b 移动到 c 上，需要 f[n - 1]

2、将第 n 个盘子从 a 移动到 b 上，需要 1 步

3、将 n - 1 个盘子从 c 经 b 移动到 a 上，需要 f[n - 1]

4、将第 n 个盘子从 b 移动到 c 上，需要 1 步

5、将 n - 1 个盘子从 a 经 b 移动到 c，需要 f[n - 1]

则有

f[n] = 3 * f[n - 1] + 2

其中 f[1] = 2

#include <bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define UI unsigned int
#define mem(i, j) memset(i, j, sizeof(i))
#define rep(i, j, k) for(int i = j; i <= k; i++)
#define dep(i, j, k) for(int i = k; i >= j; i--)
#define pb push_back
#define make make_pair
#define INF 0x3f3f3f3f
#define inf LLONG_MAX
#define PI acos(-1)
#define fir first
#define sec second
#define lb(x) ((x)h & (-(x)))
#define dbg(x) cout<<#x<<" = "<<x<<endl;
using namespace std;

const int N = 1e6 + 5;

LL dp[N];

void solve() {

    dp[1] = 2;

    rep(i, 2, 35) dp[i] = 3LL * dp[i - 1] + 2LL;

    int n;

    while(~scanf("%d", &n)) printf("%lld
", dp[n]);

}



int main() {

//    int _; scanf("%d", &_);
//    while(_--) solve();

    solve();

    return 0;
}
View Code

六、HDU 2077 汉诺塔IV （传送门）

题意

五、HDU 2064  汉诺塔III 的题意再加一个条件：允许最大的盘子在小的盘子上面。

思路

跟五、HDU 2064  汉诺塔III 的思路也类似：

将 n - 1 个盘子从 a 经过 c, 移动到 b 上，再将第 n 个盘子移动到 c 上，再将 n - 1 个盘子从 b 经过 a 移动到 c 上。

其中，将 n - 1 个盘子从 a 经过 c, 移动到 b 上 和 将 n - 1 个盘子从 b 经过 a 移动到 c 上 可以合并为 将 n - 1 个盘子从 a 经过 b 移动到 c 上（满足只能移动到相邻的柱子上）。

那么答案就是 dp[n - 1] + 2

其中 dp[1] = 2, dp[i] = 3 * dp[i - 1] + 2

#include <bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define UI unsigned int
#define mem(i, j) memset(i, j, sizeof(i))
#define rep(i, j, k) for(int i = j; i <= k; i++)
#define dep(i, j, k) for(int i = k; i >= j; i--)
#define pb push_back
#define make make_pair
#define INF 0x3f3f3f3f
#define inf LLONG_MAX
#define PI acos(-1)
#define fir first
#define sec second
#define lb(x) ((x)h & (-(x)))
#define dbg(x) cout<<#x<<" = "<<x<<endl;
using namespace std;

const int N = 1e6 + 5;

LL dp[N];

void solve() {

    int n;

    scanf("%d", &n);

    printf("%lld
", dp[n - 1] + 2LL);

}



int main() {

    dp[1] = 2;

    rep(i, 2, 35) dp[i] = 3LL * dp[i - 1] + 2LL;

    int _; scanf("%d", &_);
    while(_--) solve();

//    solve();

    return 0;
}
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/Willems/p/12916770.html