csp信奥赛C++高频考点专项训练之字符串 --【回文字符串】：最大回文数

csp信奥赛C高频考点专项训练之字符串 --【回文字符串】最大回文数题目描述回文数指的是一个数字从左到右读和从右到左读都一样。例如1221 12211221和1234321 12343211234321是回文数1234 12341234不是回文数。现有n nn个正整数a i ( i 0 , 1 , 2 , 3 , … , n − 1 ) a_i(i0,1,2,3,\dots,n-1)ai​(i0,1,2,3,…,n−1)请找出其中最大的回文数。输入格式输入文件的第一行只有一个正整数n nn代表正整数a i a_iai​的个数。接下来的n nn行每行包含一个正整数a i a_iai​。输入保证一定有回文数。输出格式输出文件一行一个正整数即最大的回文数。输入输出样例 1输入 13 4718 1221 121输出 11221输入输出样例 2输入 25 3944 953 8 75739 46输出 28说明/提示【输入输出样例 1 说明】回文数有1221 12211221和121 121121最大的回文数是1221 12211221。【输入输出样例 2 说明】回文数只有一个8 88因此最大的回文数就是8 88。【数据说明】对于30 % 30\%30%的数据1 ≤ n ≤ 100 1\leq n\leq 1001≤n≤1001 ≤ a i ≤ 10 8 1\leq a_i \leq 10^81≤ai​≤108。对于60 % 60\%60%的数据1 ≤ n ≤ 1000 1 \leq n \leq 10001≤n≤10001 ≤ a i ≤ 10 16 1 \leq a_i \leq 10^{16}1≤ai​≤1016。对于100 % 100\%100%的数据1 ≤ n ≤ 10 4 1 \leq n \leq 10^41≤n≤1041 ≤ a i ≤ 10 32 1 \leq a_i \leq 10^{32}1≤ai​≤1032。思路分析题目要求从n nn个正整数中找出最大的回文数其中数值最大可达10 32 10^{32}1032无法用内置整数类型存储。因此采用字符串存储每个数字。判断一个数字是否为回文数可以直接将该字符串反转再与原串比较若相等则为回文。寻找最大回文数时不能直接比较数值大小因为字符串长度不同时长度更长的数字更大长度相同时字符串的字典序与数值大小一致所有数字无前导零。故比较规则为优先比较字符串长度长度大者数值大长度相同则比较字符串的字典序。算法流程读入整数n nn。初始化答案字符串ans为空。循环n nn次读入一个数字字符串s ss判断s ss是否为回文反转后相等。若是回文则与当前答案比较若ans为空或s ss更长或等长且字典序更大则更新ans s。输出ans。时间复杂度O ( n × L ) O(n \times L)O(n×L)L LL为数字最大长度不超过 33完全可行。代码实现#includebits/stdc.husingnamespacestd;boolcheck(string s){// 判断回文string ts;// 拷贝原串reverse(t.begin(),t.end());// 反转字符串returnst;// 比较是否相等}intmain(){intn;cinn;// 读入数字个数string ans;// 当前最大回文数空串表示未找到while(n--){// 循环 n 次string s;cins;// 读入一个数字字符串if(check(s)){// 如果是回文数if(ans||s.size()ans.size()||(s.size()ans.size()sans))anss;// 更新最大值}}coutansendl;// 输出最大回文数return0;}功能分析输入处理使用cin读取整数n nn随后循环读取n nn个字符串形式的数字。回文判断函数check接收一个字符串的副本利用reverse将其反转然后与原串比较若相等返回true否则返回false。此方法简单直观但每次判断会多一次拷贝和反转操作由于字符串长度很小效率足够。最大值维护在main函数中对于每个回文数按规则更新ans若ans为空直接赋值否则先比较长度长度更大则更新长度相等时比较字符串的字典序s ans因无前导零字典序等价于数值大小。输出最终输出ans即为最大回文数。【完整系列请查看专栏】信奥赛C普及组CSP-J一等奖通关刷题题单及题解https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}【秘籍汇总】完整csp信奥赛C学习资料1、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转2、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转https://edu.csdn.net/course/detail/41081 点击跳转3、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转4、csp信奥赛冲刺一等奖有效刷题题解信奥赛C普及组CSP-J一等奖通关刷题题单及题解https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转信奥赛C提高组csp-j初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转5、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转GESP(C 七级八级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}