每日c/c++题 备战蓝桥杯（洛谷P1015 [NOIP 1999 普及组] 回文数）
洛谷P1015 [NOIP 1999 普及组] 回文数 题解
题目描述
P1015 回文数 是NOIP 1999普及组的经典模拟题。题目要求如下：
给定一个数N（十进制）和进制K（2≤K≤16），将N转换为K进制表示后，通过以下操作使其变为回文数：
- 将当前数与其逆序数相加
- 重复操作直到得到回文数或超过30次操作
输入格式：
- 第一行输入进制K（2≤K≤16）
- 第二行输入十进制数N（1<N≤1e9）
输出格式：
- 若30步内得到回文数，输出
STEP=步数 - 否则输出
Impossible!
解题思路
本题是典型的进制转换+模拟操作问题，核心在于：
- 正确实现大数的K进制转换
- 高效处理大数加法与进位
- 准确判断回文数
关键算法步骤
- 进制转换：将十进制数N转换为K进制表示
- 回文判断：检查当前数是否为回文
- 加法模拟：实现大数与其逆序数的加法运算
- 进位处理：处理不同进制下的进位逻辑
代码解析（附用户代码讲解）
以下是用户提供的代码的逐层解析：
#include<bits/stdc++.h>
#include<string>
using namespace std;int N; // 目标进制
int step = 0; // 操作步数
int len = 0; // 当前数位长度
int ans[205] = {0}; // 存储K进制数（低位在前）
int tem[205] = {0}; // 临时反转数组
int re[205] = {0}; // 未使用（可忽略）// 回文数检查函数
int Check() {for(int i=0; i<len/2; ++i) {if(ans[i] != ans[len-i-1]) return -1;}return 1;
}// 加法操作函数
void play() {// 反转数组到temfor(int i=0; i<len; ++i) tem[i] = ans[len-i-1];// 执行加法for(int i=0; i<len; ++i) ans[i] += tem[i];// 进位处理for(int i=0; i<len; ++i) {if(N != 16) { // 非16进制通用处理if(ans[len-1] >= N) len++;ans[i+1] += ans[i] / N;ans[i] %= N;} else { // 16进制特殊处理if(ans[len-1] >= 16) len++;ans[i+1] += ans[i] / 16;ans[i] %= 16;}}
}int main() {ios::sync_with_stdio(false);cin.tie(0);string s;cin >> N >> s;len = s.length();// 初始化K进制数（注意低位存储方式）for(int i=0; i<len; ++i) {if(isdigit(s[len-i-1]))ans[i] = s[len-i-1] - '0';elseans[i] = s[len-i-1] - 'A' + 10;}if(Check() == 1) { // 初始即为回文cout << "STEP=0";} else {while(step <= 30) {play();step++;if(Check() == 1) break;}if(step <= 30)cout << "STEP=" << step;elsecout << "Impossible!";}return 0;
}
代码特点分析
- 低位优先存储：使用数组
ans[]的低位在前方式存储，简化进位操作 - 双模式进位处理：通过
N != 16判断统一处理不同进制 - 动态长度维护：通过
len变量动态跟踪当前数位长度
优化方案与注意事项
优化方向
- 预分配数组空间：可预先分配200位空间，避免频繁扩容
- 提前终止判断：在加法操作前即可判断是否已产生回文
- 进制处理统一化：将16进制特殊处理合并到通用逻辑中
关键细节说明
-
输入处理：
- 使用
len-i-1实现字符串反转初始化 - 正确处理字母A-F（10-15）的转换
- 使用
-
进位逻辑：
- 从低位到高位处理进位
- 每次加法后检查最高位是否需要扩容
-
回文判断：
- 只需检查前半部分与对应后半部分是否相等
测试样例分析
示例1
输入：
9
87
输出：
STEP=4
过程：
87(10) = 106(9)
106 + 601 = 707（回文，4步）
示例2
输入：
10
196
输出：
Impossible!
（著名的回文数猜想反例）
复杂度分析
- 时间复杂度：O(30*L)，其中L为最大数位长度（≤200）
- 空间复杂度：O(L)，使用固定大小数组存储
总结
- 本题核心是掌握大数运算在模拟题中的应用
- 关键点在于：
- 正确实现进制转换
- 高效处理大数加法与进位
- 准确判断回文结构
- 实际编程时需特别注意：
- 数组越界问题（动态维护len变量）
- 不同进制的字符处理（0-9和A-F）
- 步骤计数器的初始值与终止条件
通过本题可以巩固：
- 进制转换的双向实现
- 大数运算的基本技巧
- 模拟算法的优化策略