2020年山东CSP-X复赛真题解析

​欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！

专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。

适合人群：

• 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
• 希望系统学习C++/Python编程的初学者
• 想要提升算法与编程能力的编程爱好者

附上汇总帖：历年CSP-X复赛真题解析 | 汇总

B4088 最大回文数

【题目来源】

洛谷：B4088 [CSP-X2020 山东] 最大回文数 - 洛谷

【题目描述】

回文数指的是一个数字，从左到右读和从右到左读都一样。例如，1221 12211221和1234321 12343211234321是回文数，1234 12341234不是回文数。现有n nn个正整数a i ( i = 0 , 1 , 2 , 3 , … , n − 1 ) a_i(i=0,1,2,3,…,n−1)ai​(i=0,1,2,3,…,n−1)，请找出其中最大的回文数。

【输入】

输入文件的第一行只有一个正整数n nn，代表正整数a i a_iai​的个数。

接下来的n nn行，每行包含一个正整数a i a_iai​。输入保证一定有回文数。

【输出】

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

【输入样例】

3 4718 1221 121

【输出样例】

1221

【算法标签】

《洛谷 B4088 最大回文数》 #模拟# #循环结构# #字符串（入门）# #CSP-X小学组# #2020# #山东#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;intn;// 字符串数量string s;// 临时存储输入的字符串string ans;// 存储满足条件的最优字符串// 检查字符串是否为回文boolcheck(string x){for(inti=0;i<x.size();i++){if(x[i]!=x[x.size()-1-i])// 比较对称位置的字符{returnfalse;}}returntrue;}// 自定义比较函数：先比长度，再比字典序boolcmp(string x,string y){if(x.size()>y.size())// 长度更长{returntrue;}if(x.size()<y.size())// 长度更短{returnfalse;}returnx>y;// 长度相同时，字典序更大}intmain(){cin>>n;// 输入字符串数量while(n--){cin>>s;// 输入一个字符串// 如果是回文且比当前最优字符串更优if(check(s)&&cmp(s,ans)){ans=s;// 更新最优字符串}}cout<<ans;// 输出最优字符串return0;}

【运行结果】

3 4718 1221 121 1221

B4089 勇敢的津津

【题目来源】

洛谷：[B4089 CSP-X2020 山东] 勇敢的津津 - 洛谷

【题目描述】

津津是个勇敢的孩子，总是做一些挑战自己的事情。一天津津来到一条宽为L LL米的小河边，河道的一边到另一边需要途径N NN块较大的石墩，每块石墩到这一边岸边之间距离d i d_idi​米（石墩不占距离，只考虑石墩的中间点到这一边岸边之间距离）。津津想踩着这些石墩从小河的这一边跳到另一边（不落入水中），一次可以跳过几块石墩。已知津津每次最多跳M MM米的距离，那么津津最少跳几次就能从这一边跳到另一边？

【输入】

第一行包含三个整数L , N , M L,N,ML,N,M，分别小河的宽度、石墩数和津津跳的最远距离。

接下来N NN行，每行一个整数，第i ii行的整数d i ( 0 < d i < L ) d_i(0\lt d_i \lt L)di​(0<di​<L)，表示第i ii块石墩与这一边岸边的距离，保证石墩之间的距离和最靠边的石墩到这一边岸边的距离小于等于M MM。这些石墩按与起点距离从小到大的顺序给出，且不会有两个石墩出现在同一个位置。

【输出】

一个整数，即最少的跳跃次数。

【输入样例】

10 4 2 2 4 6 8

【输出样例】

5

【算法标签】

《洛谷 B4089 勇敢的津津》 #动态规划DP# #贪心# #CSP-X小学组# #2020# #山东#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=505;// 定义常量N，最大数组大小intL,m,n;// L: 跳跃长度上限, m: 最小跳跃距离, n: 石头数量inta[N],dp[N];// a: 存储石头位置, dp: 动态规划数组intmain(){cin>>L>>n>>m;// 输入跳跃长度上限、石头数量和最小跳跃距离for(inti=1;i<=n;i++)// 输入n个石头的位置cin>>a[i];a[n+1]=L;// 在终点位置添加一个虚拟石头sort(a+1,a+n+1);// 对石头位置进行排序memset(dp,0x3f,sizeof(dp));// 初始化dp数组为最大值dp[0]=0;// 起点位置（0位置）需要0次跳跃// 动态规划：计算到达每个石头的最少跳跃次数for(inti=1;i<=n+1;i++)// 遍历每个石头（包含终点）for(intj=0;j<i;j++)// 尝试从之前的石头j跳到石头i{if(a[i]-a[j]<=m)// 如果从石头j到石头i的距离不超过mdp[i]=min(dp[i],dp[j]+1);// 更新到达石头i的最少跳跃次数}// 调试用：输出每个石头的dp值// for (int i = 1; i <= n + 1; i++)// cout << dp[i] << " ";// cout << endl;cout<<dp[n+1]<<endl;// 输出到达终点的最少跳跃次数return0;}

【运行结果】

10 4 2 2 4 6 8 5