题意分析

这道题目是关于汉诺塔问题的一个变种，要求计算在特定移动策略下解决汉诺塔问题所需的最少步数。题目给出了以下关键信息：

1. 汉诺塔规则：

   • 有三根柱子A、B、C，初始时所有圆盘按大小顺序叠放在柱子A上。
   • 每次只能移动一个圆盘，且不能将较大的圆盘放在较小的圆盘上。
   • 目标是将所有圆盘移动到柱子B或C上。

2. 移动策略：

   • 有6种可能的移动方式：AB、AC、BA、BC、CA、CB。
   • 输入会给出这6种移动的优先级顺序。
   • 每次选择优先级最高的合法移动，且不能连续两次移动同一个圆盘。

3. 问题要求：

   • 给定圆盘数量n（1 ≤ n ≤ 30）和移动策略，计算最少需要多少步才能完成游戏。
   • 步数可能非常大（不超过1e18），因此需要高效算法。

解题思路

1. 预处理步数：

   • 代码中预先计算了三种不同策略下的步数：
     • a[i]：传统汉诺塔的最少步数（2^i - 1）。
     • b[i]和c[i]：特定策略下的步数，通过递推公式计算。
   • 这些步数在程序开始时就已经计算好，存储在数组中。

2. 策略解析：

   • 输入6种移动策略后，将其转换为优先级编号。
   • 通过比较不同移动的优先级，确定当前策略属于哪种情况（对应a、b或c数组）。

3. 输出结果：

   • 根据策略的比较结果，选择对应的步数数组（a、b或c）并输出第n个元素。

代码示例

#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
ll a[40], b[40], c[40];
int num[10];
char s[10];
int main()
{
    int n, i, j, k;
    a[1] = b[1] = c[1] = 1;
    for (i = 2; i <= 30; i++)
    {
        a[i] = a[i - 1] * 2 + 1;
        c[i] = c[i - 1] * 3 + 2;
        b[i] = b[i - 1] + c[i - 1] + 1;
    }
    scanf("%d", &n);
    for (i = 1; i <= 6; i++)
    {
        scanf("%s", s);
        k = (s[0] - 'A') * 4 + s[1] - 'A';
        num[k] = i;
    }
    if (num[1] < num[2])
    {
        if (num[4] < num[6])
            printf("%I64d\n", c[n]);
        else if (num[9] < num[8])
            printf("%I64d\n", b[n]);
        else
            printf("%I64d\n", a[n]);
    }
    else
    {
        if (num[8] < num[9])
            printf("%I64d\n", c[n]);
        else if (num[6] < num[4])
            printf("%I64d\n", b[n]);
        else
            printf("%I64d\n", a[n]);
    }
}

关键点

1. 递推公式：

   • 传统汉诺塔的步数为a[i] = 2 * a[i-1] + 1。
   • 特定策略的步数通过更复杂的递推关系计算（如c[i] = 3 * c[i-1] + 2）。

2. 策略分类：

   • 通过比较6种移动的优先级，将策略分为三类，分别对应a、b、c三种步数数组。
   • 这种分类基于对汉诺塔移动规律的深入理解。

3. 高效计算：

   • 预处理步数数组使得查询时间为O(1)，适合大规模数据。