P1015 [NOIP 1999 普及组] 回文数

记录141#includebits/stdc.h using namespace std; int n; // 进制数 N int a[200],len; // a数组用来倒序存储大数len记录当前大数的长度 // 判断当前数组 a 是否是回文数 bool f(){ for(int i0;ilen/2;i){ if(a[i]!a[len-1-i]) return false; } return true; } // 高精度 N 进制加法将数组 a 与它的倒序相加 void add(){ int b[200]; // 用来存 a 的倒序 // 1. 先把 a 倒序存入 b for(int i0;ilen;i) b[i]a[len-1-i]; // 2. 模拟竖式加法 for(int i0;ilen;i){ a[i]b[i]; // 对应位相加 a[i1]a[i]/n; // 处理进位 a[i]%n; // 保留当前位的余数 } // 3. 如果最高位产生了进位长度要加1 if(a[len]0) len; } int main(){ // 主函数入口 ios::sync_with_stdio(false); // 关闭同步加速IO cin.tie(0); string s; // 用来读入初始的 N 进制数 M cinns; // 将字符串倒序转换成数字存入数组 a方便从个位开始加 lens.size(); for(int i0;ilen;i){ char cs[len-1-i]; // 倒着取字符 if(c0c9) a[i]c-0; // 数字字符转数字 else a[i]c-A10; // 字母 A-F 转 10-15 } int step0; // 记录步数 while(step30){ if(f()){ // 如果已经是回文数 coutSTEPstep\n; return 0; // 直接结束程序 } add(); // 执行一次高精度加法 step; // 步数加1 } // 如果循环跑完30步还没找到 coutImpossible!\n; return 0; }题目传送门https://www.luogu.com.cn/problem/P1015前言我是一名专注信奥赛CSP-J/S、NOIP的教练。如果你觉得这篇题解对你有帮助欢迎点击关注我的CSDN账号我会持续更新高质量算法解析。我深知算法思维的构建远比单纯通过题目更重要本系列题解不局限于AC代码的堆砌而是致力于拆解题目背后的逻辑链条与核心知识点备赛路上若遇瓶颈欢迎随时评论或私信我将甄选典型疑难问题通过视频讲解或撰写专项文章的形式为你提供深度答疑。核心解题思路这道题是一道非常经典的高精度运算与字符串处理结合的问题。数据规模分析题目中给出的 N 进制数 M 长度不超过 100 位。在 C 等语言中普通的整数类型如long long最多只能存储 19 位左右的十进制数。因此我们必须使用高精度算法即用数组来模拟大数的每一位进行运算。算法设计高精度加法 模拟题目要求我们不断执行“将当前数与其倒序数相加”的操作直到结果变为回文数。我们可以按照以下步骤模拟数据存储将输入的字符串倒序存入一个整型数组中数组下标 0 对应个位方便处理进位。回文判定每次加法前检查当前数组表示的数是否是回文数。高精度 N 进制加法模拟竖式加法将数组与它的倒序对应位相加并处理 N 进制的进位。步数限制题目限制最多 30 步如果超过 30 步仍未得到回文数则输出Impossible!。代码分块详细解释1. 头文件、全局变量与回文判定函数#includebits/stdc.h using namespace std; int n; // 进制数 N int a[200], len; // a数组用来倒序存储大数len记录当前大数的长度 // 判断当前数组 a 是否是回文数 bool f(){ for(int i0; ilen/2; i){ if(a[i] ! a[len-1-i]) return false; } return true; }详细分析a[200]是高精度运算的核心容器因为初始长度最多 100 位经过最多 30 次加法后长度翻倍也远小于 200所以数组大小足够。f()函数通过双指针思想从数组的两端向中间遍历只要有一对对应位置的数字不相等就说明不是回文数。2. 核心逻辑高精度 N 进制加法// 高精度 N 进制加法将数组 a 与它的倒序相加 void add(){ int b[200]; // 用来存 a 的倒序 // 1. 先把 a 倒序存入 b for(int i0; ilen; i) b[i] a[len-1-i]; // 2. 模拟竖式加法 for(int i0; ilen; i){ a[i] b[i]; // 对应位相加 a[i1] a[i] / n; // 处理进位除以进制数 n a[i] % n; // 保留当前位的余数对进制数 n 取模 } // 3. 如果最高位产生了进位长度要加1 if(a[len] 0) len; }详细分析这是本题最核心的部分。倒序备份由于我们要将a和它的倒序相加而a本身在加法过程中会被修改所以必须先用一个临时数组b把a的倒序存起来。竖式加法与进位从个位下标 0开始将a[i]和b[i]相加。因为是 N 进制所以满 N 就要进 1。a[i] / n得到进位的值加到下一位a[i1]上a[i] % n得到当前位保留的数字。长度更新如果最高位a[len-1]相加后产生了进位这个进位会落在a[len]上此时大数的实际长度就需要增加 1。3. 主函数输入处理与倒序转换int main(){ ios::sync_with_stdio(false); cin.tie(0); string s; // 用来读入初始的 N 进制数 M cin n s; // 将字符串倒序转换成数字存入数组 a方便从个位开始加 len s.size(); for(int i0; ilen; i){ char c s[len-1-i]; // 倒着取字符 if(c 0 c 9) a[i] c - 0; // 数字字符转数字 else a[i] c - A 10; // 字母 A-F 转 10-15 }详细分析由于输入的数可能包含字母如 16 进制中的 A-F且长度很长必须用string读入。为了符合人类做竖式加法的习惯从个位开始算我们将字符串倒序存入数组a。例如输入 87a[0]存 7a[1]存 8。同时通过 ASCII 码的运算将字符完美转换为对应的十进制数值。4. 主循环模拟步进与结果输出int step 0; // 记录步数 while(step 30){ if(f()){ // 如果已经是回文数 cout STEP step \n; return 0; // 直接结束程序 } add(); // 执行一次高精度加法 step; // 步数加1 } // 如果循环跑完30步还没找到 cout Impossible!\n; return 0; }详细分析这里采用了while循环来模拟题目要求的操作步骤。每次循环开始时先判断当前数是否已经是回文数注意初始输入的数本身可能就是回文数此时步数为 0。如果不是就调用add()执行一次加法并将步数加 1。如果循环正常结束即step超过了 30说明在限制步数内无法得到回文数输出Impossible!。核心逻辑总结表代码模块核心变量/操作精炼作用解决的痛点高精度存储int a[200]用整型数组倒序存储大数突破了普通整数类型的位数限制能够处理 100 位以上的超大数字符转换c-0与c-A10将 N 进制字符转换为对应数值完美兼容了 2-10 进制以及 16 进制包含字母的输入回文判定f()函数双指针比对数组两端快速判断当前高精度数是否满足题目要求的终止条件竖式加法a[i1] a[i]/n模拟 N 进制的进位操作实现了任意进制下的大数加法是本题的核心算法动态长度if(a[len]0) len处理最高位进位导致的长度增加保证了在多次加法后数组的有效长度始终是正确的步数模拟while(step30)限制最大操作次数并模拟过程严格按照题目要求在 30 步内寻找答案或判定无解