广告制作商_建设通查询中标_网络营销推广公司简介_百度指数批量获取

1.  P1760 通天之汉诺塔 题解

题目背景

直达通天路·小A历险记第四篇

题目描述

在你的帮助下，小 A 成功收集到了宝贵的数据，他终于来到了传说中连接通天路的通天山。但是这距离通天路仍然有一段距离，但是小 A 突然发现他没有地图！！！但是幸运的是，他在山脚下发现了一个宝箱。根据经验判断（小 A 有经验吗？），地图应该就在其中！

在宝箱上，有三根柱子以及在一根柱子上的 n 个圆盘。小 A 在经过很长时间判断后，觉得这就是 hanoi 塔！（这都要琢磨）。但是移动是需要时间的，所以小 A 必须要通过制造延寿药水来完成这项任务。现在，他请你告诉他需要多少步完成，以便他造足够的延寿药水。

输入格式

一个数 n，表示有 n 个圆盘。

输出格式

一个数 s，表示需要 s 步。

输入输出样例

输入 #1

31

输出 #1

2147483647

输入 #2

15

输出 #2

32767

说明/提示

数据范围及约定

对于所有数据，n≤15000。

代码：

#include <iostream>
#include <vector>using namespace std;int main() {int n;cin >> n;vector<int> digits;digits.push_back(1); // 初始为1，逆序存储for (int i = 0; i < n; ++i) {int carry = 0;for (int j = 0; j < digits.size(); ++j) {int temp = digits[j] * 2 + carry;digits[j] = temp % 10;carry = temp / 10;}if (carry != 0) {digits.push_back(carry);}}// 减一操作int borrow = 1;for (int i = 0; i < digits.size() && borrow != 0; ++i) {digits[i] -= borrow;if (digits[i] < 0) {digits[i] += 10;borrow = 1;} else {borrow = 0;}}// 去除前导零while (!digits.empty() && digits.back() == 0) {digits.pop_back();}if (digits.empty()) {cout << 0;} else {for (auto it = digits.rbegin(); it != digits.rend(); ++it) {cout << *it;}}cout << endl;return 0;
}

代码解释：

代码逻辑分析

1. 输入处理

• 读取整数 n，表示需要计算的次方数。

2. 初始化大数存储

• 使用动态数组 digits ​​逆序存储​​大数，初始值为 [1]（即 20=1）。
• 逆序存储意味着低位在前，高位在后。例如，数值 123 存储为 [3, 2, 1]。

3. 计算 

• 通过 ​​n 次循环​​，每次将当前数值乘以 2。
• ​​处理进位​​：
  • 遍历每一位数字，计算 当前位 × 2 + 进位。
  • 更新当前位为结果的个位，进位为十位。
  • 若所有位处理完仍有进位，将其作为新高位加入数组。

​​示例​​：初始为 1，计算 23=8：

• 第1次循环：1×2 → 2 → [2]
• 第2次循环：2×2 → 4 → [4]
• 第3次循环：4×2 → 8 → [8]

4. 减一操作

• 从最低位开始借位减一：
  • 若当前位减一后为负数，加 10 并设置借位。
  • 否则，直接减一并结束借位。

​​示例​​：=16 减一：

• 数值 16 存储为 [6, 1]。
• 减一后，低位 6 → 5，无借位，结果为 [5, 1]（即 15）。

5. 去除前导零

• 逆序存储中前导零位于数组末尾，需移除。
• 若所有位均为零，最终输出 0。

6. 输出结果

• 逆序输出数组，得到正确的高位到低位顺序。

代码示例解析（以 n=3 为例）

1. ​​计算 =8​​：
   • 初始 digits = [1]。
   • 3次循环后，digits = [8]（逆序存储 8）。
2. ​​减一​​：
   • 8 - 1 = 7 → digits = [7]。
3. ​​输出​​：
   • 逆序输出 7。

2. Problem D: 汉诺塔 题解

Description

        有三根柱A，B，C在柱A上有N块盘片，所有盘片都是大的在下面，小片能放在大片上面。现要将A上的N块片移到C柱上，每次只能移动一片，而且在同一根柱子上必须保持上面的盘片比下面的盘片小，请输出移动的步骤。

Input

        输入整数n，表示有n块盘片

Output

        输出移动的步骤

• Sample Input

3

• Sample Output

1 A->C
2 A->B
3 C->B
4 A->C
5 B->A
6 B->C
7 A->C

HINT

0 < n < 20

代码：

#include <cstdio>
#include <vector>
#include <string>
#include <cstring>using namespace std;vector<string> steps;
int step = 0;void hanoi(int n, char from, char to, char via) {if (n == 1) {step++;char buffer[20];snprintf(buffer, sizeof(buffer), "%d %c->%c", step, from, to);steps.emplace_back(buffer);} else {hanoi(n - 1, from, via, to);step++;char buffer[20];snprintf(buffer, sizeof(buffer), "%d %c->%c", step, from, to);steps.emplace_back(buffer);hanoi(n - 1, via, to, from);}
}int main() {int n;scanf("%d", &n);steps.reserve((1 << n) - 1); // 预分配足够内存hanoi(n, 'A', 'C', 'B');// 计算总输出长度size_t total_len = 0;for (const auto& s : steps) {total_len += s.size() + 1; // 每行加换行符}// 合并到缓冲区并一次性输出char* buffer = new char[total_len];char* ptr = buffer;for (const auto& s : steps) {size_t len = s.size();memcpy(ptr, s.c_str(), len);ptr += len;*ptr++ = '\n';}fwrite(buffer, 1, total_len, stdout);delete[] buffer;return 0;
}

代码解释：

1. ​​汉诺塔独特递归算法​​：

   • hanoi 函数递归地将 n 个盘子从起始柱 from 移动到目标柱 to，借助中间柱 via。
   • 当 n=1 时，直接将盘子从 from 移到 to，记录步骤。
   • 对于 n>1，分解为三步：
     • 将 n-1 个盘子从 from 移至 via（递归调用）。
     • 将第 n 个盘子从 from 移至 to。
     • 将 n-1 个盘子从 via 移至 to（递归调用）。

2. ​​记录步骤​​：

   • 使用全局变量 steps（vector<string>）存储每一步操作。
   • 每移动一个盘子，递增全局变量 step，并用 snprintf 格式化为字符串（如 "1 A->C"）存入 steps。

3. ​​性能优化​​：

   • ​​内存预分配​​：steps.reserve((1 << n) - 1) 预分配足够内存，避免 vector 动态扩容的开销。
   • ​​单次输出​​：计算所有步骤字符串的总长度，合并到连续内存缓冲区，通过 fwrite 一次性输出，减少频繁I/O操作的开销。

4. ​​代码结构​​：

   • ​​全局变量​​：steps 和 step 简化参数传递，但在多线程环境中不安全（此处单线程无问题）。
   • ​​递归实现​​：清晰体现汉诺塔问题分治思想，时间复杂度为 O(2ⁿ)。
   • ​​输入输出​​：scanf 读取盘子数 n，高效输出避免逐行打印。

​​总结​​：递归解决汉诺塔问题，记录每一步移动步骤，并通过内存预分配和单次输出优化性能，适合高效生成并输出大量步骤的场景。