csp信奥赛C++高频考点专项训练之字符串 --【回文字符串】：最大回文数
题目描述
回文数指的是一个数字，从左到右读和从右到左读都一样。例如，1221 12211221和1234321 12343211234321是回文数，1234 12341234不是回文数。现有n nn个正整数a i ( i = 0 , 1 , 2 , 3 , … , n − 1 ) a_i(i=0,1,2,3,\dots,n-1)ai(i=0,1,2,3,…,n−1)，请找出其中最大的回文数。
输入格式
输入文件的第一行只有一个正整数n nn，代表正整数a i a_iai的个数。
接下来的n nn行，每行包含一个正整数a i a_iai。输入保证一定有回文数。
输出格式
输出文件一行，一个正整数，即最大的回文数。
输入输出样例 1
输入 1
3 4718 1221 121输出 1
1221输入输出样例 2
输入 2
5 3944 953 8 75739 46输出 2
8说明/提示
【输入输出样例 1 说明】
回文数有1221 12211221和121 121121，最大的回文数是1221 12211221。
【输入输出样例 2 说明】
回文数只有一个8 88，因此最大的回文数就是8 88。
【数据说明】
对于30 % 30\%30%的数据，1 ≤ n ≤ 100 1\leq n\leq 1001≤n≤100，1 ≤ 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≤1000，1 ≤ 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≤104，1 ≤ 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），完全可行。
代码实现
#include<bits/stdc++.h>usingnamespacestd;boolcheck(string s){// 判断回文string t=s;// 拷贝原串reverse(t.begin(),t.end());// 反转字符串returns==t;// 比较是否相等}intmain(){intn;cin>>n;// 读入数字个数string ans="";// 当前最大回文数，空串表示未找到while(n--){// 循环 n 次string s;cin>>s;// 读入一个数字（字符串）if(check(s)){// 如果是回文数if(ans==""||s.size()>ans.size()||(s.size()==ans.size()&&s>ans))ans=s;// 更新最大值}}cout<<ans<<endl;// 输出最大回文数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 点击跳转
各种学习资料，助力大家一站式学习和提升！！！
#include<bits/stdc++.h>usingnamespacestd;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++标准模板库STL：
https://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 点击跳转
· 文末祝福 ·
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}
