题解 P1015 【回文数】

**upd：20200418** 这题是高精度加法和普通模拟的一道好题。 郑重声明：本题正解为高精度+模拟。利用数据范围模糊的题目漏洞而使用long long水过此题应当是一个应当坚决制止的行为。我本人刚学OI时做题经常只考虑局部正确性而忽视数据范围，然后稀里糊涂发了这篇题解。如今这篇题解截至此时因为利用数据范围漏洞而水过而成为第一高赞题解，但是我忽视了其影响力，**给后来的初学者开了一个很坏的头**，我做自我检讨。感谢评论区狂轰滥炸的督促，今天我这道题目和这篇题解重写。 请注意：我们应当认为，在任何时候利用题目数据、评测机器或其他漏洞而 **主观人为** 获取AC的行为与作弊行为性质上无异，应当坚决制止。**（这里的主观人为指你在A题前已经知道本题存在某些题面中没有说明的漏洞可以加以利用。这种漏洞不包括可以通过观察发现的特性。）** upd20230114:（ 对这句话必需补充的是，由于我2017年的那篇题解已经不再展示，所以这句话可能给了一些同学误解。这里的“坚决制止”是指由于我之前发了不符合题目要求的题解并且这篇题解点赞数量很多，导致许多人可能效仿那篇题解的做法从而水过此题。这在个人的训练提升当中是不提倡的做法。） 但是，由于本人已经升入大学且还是参加过不少场NOIP的，所以必须要说的是如果你在比赛当中通过合法的骗分方式得到了很多分甚至过了题，那么只要成绩有效，就不要有任何思想负担。 本题按照题目意思模拟即可。我们可以开两个数组来记录高精度数字，这样方便我们处理。判断“该数组是否回文”、“c翻转存入d再做c+d”可以写成两个单独的函数。然后主程序组织一下他们即可。注意好退出循环的条件。 ```cpp #include <cstdio> #include <cstring> const int S=303;//一次加法顶多多一位，所以顶多多30位，也就是130位左右。我开大一点，开到300. int n,a[S],l; char c[S],d[S]; inline void add() { for (int i=0;i<l;++i) d[l-i-1]=c[i]; l+=2;//可能有进位，所以我们干脆在前面先多空个两位 for (int i=0;i<l;++i) { c[i]+=d[i]; if (c[i]>=n) c[i+1]++,c[i]-=n; } while (!c[l-1]) --l;//大不了多余的前导0再减回来嘛~~简化思维~~ } inline bool pd() { for (int i=0;i<l;++i) if (c[i]!=c[l-1-i]) return false; return true; } int main() { scanf("%d%s",&n,c);l=strlen(c); for (int i=0;i<l;++i) { if (c[i]>='0' && c[i]<='9') c[i]-='0'; else c[i]=c[i]-'A'+10; } int step=0; while (!pd()) { ++step; if (step>30) break; add(); } if (step<=30) printf("STEP=%d\n",step); else puts("Impossible!"); return 0; } ``` 把不同的一些并不小的功能写成不同的函数再在主程序当中组织它们，是属于一种标准化、模块化编程的思维。这种思维在以后编程，尤其是像高精度这样主程序调用频繁的程序当中，可以大大简化思维和代码量。其特点就是函数间独立性较为明显，函数接口较为简单，函数调用方便。一个函数应当干完它所有的任务，如果把某些任务拖延到主程序或者是其他函数当中，将大大复杂编程思维复杂度和代码量。大家可以挑战一下[P1005 矩阵取数游戏](https://www.luogu.com.cn/problem/P1005)，这是我发现模块化极其优秀的起源。 ___ **20171029题解改：** 如果题目是int64整形范围内的话，那么将毫无必要转进制！ 一个小技巧：将n进制数反转，在十进制下即可翻转，无需转成字符数组。判断反转后的数（10进制）与原来的数（先把它转成10进制）是否相同即可。 代码： ```cpp bool pd(unsigned long long a)//判断a与其n进制下反转是否相等。 { unsigned long long s=0; for (unsigned long long i=a;i;i/=n) s=s*k+i%n;//用十进制，但是把它按照n进制操作 nex=s+a; return s==a; } ```