题解

本题是汉诺塔问题的一个变种，僧侣们已经把圆盘弄乱，现在要找到一种方案，将所有圆盘以最少的移动次数整齐地堆叠到某一根柱子上。

思路分析

数据读取：首先需要从输入中读取圆盘的总数 N，以及三根柱子上各自的圆盘数量和每个圆盘的大小。 枚举目标柱子：分别假设将所有圆盘移动到柱子1、柱子 2、柱子 3，计算每种情况下的最少移动次数。

计算移动次数：对于每种目标柱子的情况，使用递归或动态规划的思想来计算从当前状态移动到目标状态所需的最少移动次数。这里可以利用汉诺塔问题的经典结论：将$n$ 个圆盘从一根柱子移动到另一根柱子需要$2^n - 1$次移动。

取模运算：由于移动次数可能非常大，题目要求只保留移动次数对$1000000$取模的结果。

选择最优方案：比较三种目标柱子情况下的移动次数，选择移动次数最少的方案，并输出目标柱子编号和最少移动次数。

cpp

#include #include #include using namespace std;

const int MOD = 1000000;

// 计算 2^n % MOD int powerOfTwoMod(int n) {

int result = 1;
for (int i = 0; i < n; ++i) {
    result = (result * 2) % MOD;
}
return result;

}

// 计算将所有圆盘移动到目标柱子所需的最少移动次数 int calculateMoves(const vector<vector>& pegs, int targetPeg) {

int n = 0;
for (const auto& peg : pegs) {
    n += peg.size();
}
vector<int> currentPeg(n + 1);
for (int i = 0; i < 3; ++i) {
    for (int disk : pegs[i]) {
        currentPeg[disk] = i + 1;
    }
}

int moves = 0;
for (int disk = n; disk >= 1; --disk) {
    if (currentPeg[disk] != targetPeg) {
        // 计算需要移动的圆盘数量
        int otherPeg = 6 - targetPeg - currentPeg[disk];
        int smallerDisks = 0;
        for (int i = 1; i < disk; ++i) {
            if (currentPeg[i] == otherPeg) {
                ++smallerDisks;
            }
        }
        moves = (moves + powerOfTwoMod(smallerDisks)) % MOD;
        
        // 更新当前圆盘的位置
        currentPeg[disk] = targetPeg;
    }
}
return moves;

}

int main() {

int N;

cin >> N;

vector<int> pegSizes(3);
for (int i = 0; i < 3; ++i) {
    cin >> pegSizes[i];
}

vector<vector<int>> pegs(3);
for (int i = 0; i < 3; ++i) {
    pegs[i].resize(pegSizes[i]);
    for (int j = 0; j < pegSizes[i]; ++j) {
        cin >> pegs[i][j];
    }
}

int minMoves = MOD;
int bestPeg = 0;
for (int targetPeg = 1; targetPeg <= 3; ++targetPeg) {
    int moves = calculateMoves(pegs, targetPeg);
    if (moves < minMoves) {
        minMoves = moves;
        bestPeg = targetPeg;
    }
}

cout << bestPeg << endl;
cout << minMoves << endl;

return 0;

}