2022年CSP-X复赛真题及题解（T1：最大回文数）

2022年CSP-X复赛真题及题解（T1：最大回文数）

题目描述

回文数指的是一个数字，从左到右读和从右到左读都一样。例如，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。

思路分析

• 输入的数字最大可达10 32 10^{32}1032，已经超过long long范围，所以用字符串存储每个数。
• 判断回文：用左右双指针从字符串两端向中间扫描，只要出现不同字符就不是回文数。
• 找出最大回文数：
  • 空字符串先直接更新；
  • 长度更长的数字更大；
  • 长度相同时，字典序更大的数字更大。
• 输出最终答案。

代码

#include<bits/stdc++.h>usingnamespacestd;boolcheck(string s){// 回文判断intl=0,r=s.size()-1;// 左右指针while(l<r){// 未相遇if(s[l]!=s[r])returnfalse;// 不对称l++;r--;// 移动指针}returntrue;// 是回文}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;// 输出最大回文数return0;}

功能分析

• check函数：判断一个字符串是否为回文串，时间复杂度 O(len)。
• 主函数：读入所有数字，只保留回文数，并按照“长度优先、相同长度字典序优先”的方式更新最大值。
• 由于每个数最多只有 33 位，n ≤ 10 4 n \le 10^4n≤104，总时间非常小。

更多内容请关注专栏：信奥赛C++普及组csp-j初赛&复赛真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

【秘籍汇总】（完整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;}