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

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，无法用内置整数类型存储。因此采用字符串存储每个数字。

判断一个数字是否为回文数，可以直接将该字符串反转，再与原串比较，若相等则为回文。

寻找最大回文数时，不能直接比较数值大小，因为字符串长度不同时，长度更长的数字更大；长度相同时，字符串的字典序与数值大小一致（所有数字无前导零）。故比较规则为：

• 优先比较字符串长度，长度大者数值大；
• 长度相同则比较字符串的字典序。

算法流程：

1. 读入整数n nn。
2. 初始化答案字符串ans为空。
3. 循环n nn次，读入一个数字字符串s ss：
   • 判断s ss是否为回文（反转后相等）。
   • 若是回文，则与当前答案比较：若ans为空或s ss更长或等长且字典序更大，则更新ans = s。
4. 输出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;}