BJTU Tower of Hanoi

题面描述

变种汉诺塔问题和普通汉诺塔问题略有不同，规则描述如下：

1. 有三根柱子，在最左侧柱子上放置着若干圆盘。与传统汉诺塔不同的是，其中存在部分大小相同的圆盘。

2. 要求包括初始状态在内，每个圆盘上方放置的圆盘不得大于该圆盘，即圆盘上方只能放置小于自己或和自己相同大小的圆盘。

3. 每次移动只能将某柱子最顶部的一个圆盘移动到另一柱子的最顶部。

4. 需要注意的是，大小相同的圆盘具有的其他特征是不一样的，例如不同颜色。

最后需要保证 2 号柱子上的圆盘排列顺序，和开始时的 0 号柱子上的顺序完全相同。

求将初态 0 号柱子上的所有圆盘全部移到 2 号柱子上最优策略的步数 l 对 m 取模后的值。

输入数据

对于每组数据：

第一行有一个整数 t (1 ≤ t ≤ 100 ) ，表示有 t 组数据。

第一行包括 2 个数字 n,m (1≤n≤15000, 1≤m≤1000000) ，其中 n 代表圆盘种类的个数；

第二行包括 n 个数字 a1, … , an (1 ≤ ai≤ 99 )，其中 ai 代表大小为 i 的圆盘个数。

输出数据

对于每组数据，输出一行，若最优策略的步数为 l ，则输出 l mod m 。

样例输入

2
2 1000
1 2
3 1000
1 2 3

样例输出

7
21

 

解题思路

       这个变种汉诺塔是有规律可循的。先看一下传统的汉诺塔，具有 2 *（a[0] + a[1] + …… + a[n-1]）- 1 的规律，见如下代码。

#include <iostream>
using namespace std ;
int cnt = 0 ;// 记录次数  =  pow(2,n)-1
void move(char hanoi_A , char hanoi_C){
    cout << hanoi_A << "->" << hanoi_C << endl ;
    cnt++ ;
}
void hanoi(int n , char hanoi_A , char hanoi_B , char hanoi_C){// 数量、开始位置、媒介、最终位置
    if (n == 1)
        move(hanoi_A , hanoi_C) ;
    else{
        hanoi(n-1 , hanoi_A , hanoi_C , hanoi_B) ;// A先传到B上
        move(hanoi_A , hanoi_C) ;
        hanoi(n-1 , hanoi_B , hanoi_A ,hanoi_C) ;// B上的全部传到C上
    }
}
int main(){
    int n ;
    cin >> n ;
    hanoi(n , 'A' , 'B' , 'C') ;
    cout << cnt << endl ;
    return 0 ;
}

        对于变种汉诺塔，先统计好同种大小圆盘的移动数目，即不区分颜色。这种移动方式要比传统汉诺塔次数少的多。

        例如：3种圆盘的数量为1，2，3 。（结果是21次）

         第一步：temp[0] = 1 ；

                       temp[1] = 1 + 2 + 1 = 2 * 1 + 2 = 2 * temp[0] + a[1] = 4 ；

                       temp[2] = 1 + 2 + 1 + 3 + 1 + 2 + 1 = 2 * {1,2,1} + 3 = 2 * temp[1] + a[2] = 11 。

         第二步：//   假设，只有一种型号圆盘；可想可知，移动2遍前n-1个，最后一个移动一次

                       sum[0] = 2 * temp[0] - 1 = 1；

                       //   1_C > 21_B > 1_B > 22_C > 1_A > 21_C > 1_C     依据ABC传统汉诺塔，即为7次。

                       sum[1] = 2 * (1 + 2) + 1 = 2 * （temp[0] + a[1]）+1 = 7 ；

                       //   对于题目给出的规律，要包含传统汉诺塔的规律，就要分为某型号圆盘的数量是否为1。

                       传统的 Hanoi  ： 2 *（a[0] + a[1] + …… + a[n-1]）- 1

                       变种的 Hanoi ：  sum[2] = 2 * (7 + 3) + 1 = 2 * （temp[1] + a[2]）+1 = 21 ；

                       

 

全部程序代码如下