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

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

题目描述

回文数指的是一个数字，从左到右读和从右到左读都一样。例如，

1221

1221

1221 和

1234321

1234321

1234321 是回文数，

1234

1234

1234 不是回文数。现有

n

n

n 个正整数

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

n

n，代表正整数

a

i

a_i

ai​ 的个数。

接下来的

n

n

n 行，每行包含一个正整数

a

i

a_i

ai​。输入保证一定有回文数。

输出格式

输出文件一行，一个正整数，即最大的回文数。

输入输出样例 1

输入 1

3
4718
1221
121

输出 1

1221

输入输出样例 2

输入 2

5
3944
953
8
75739
46

输出 2

8

说明/提示

【输入输出样例 1 说明】

回文数有

1221

1221

1221 和

121

121

121，最大的回文数是

1221

1221

1221。

【输入输出样例 2 说明】

回文数只有一个

8

8

8，因此最大的回文数就是

8

8

8。

【数据说明】

对于

30

%

30\\%

30% 的数据，

1

≤

n

≤

100

1\\leq n\\leq 100

1≤n≤100，

1

≤

a

i

≤

10

8

1\\leq a_i \\leq 10^8

1≤ai​≤108。

对于

60

%

60\\%

60% 的数据，

1

≤

n

≤

1000

1 \\leq n \\leq 1000

1≤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^4

1≤n≤104，

1

≤

a

i

≤

10

32

1 \\leq a_i \\leq 10^{32}

1≤ai​≤1032。

思路分析

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

代码

#include <bits/stdc++.h>
using namespace std;

bool check(string s){ // 回文判断
int l=0,r=s.size()–1; // 左右指针
while(l<r){ // 未相遇
if(s[l]!=s[r]) return false; // 不对称
l++; r—; // 移动指针
}
return true; // 是回文
}

int main(){
int n;
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; // 输出最大回文数
return 0;
}

功能分析

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

更多内容请关注专栏：信奥赛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>
using namespace std;
int main(){
cout<<"跟着王老师一起学习信奥赛C++";
cout<<" 成就更好的自己！ ";
cout<<" csp信奥赛一等奖属于你! ";
return 0;
}