欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！
专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。
适合人群：
- 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
- 希望系统学习C++/Python编程的初学者
- 想要提升算法与编程能力的编程爱好者
附上汇总帖：GESP认证C++编程真题解析 | 汇总
编程题
B4068 Recamán
【题目来源】
洛谷：B4068 [GESP202412 四级] Recamán - 洛谷
【题目描述】
小杨最近发现了有趣的 Recamán 数列，这个数列是这样生成的：
- 数列的第一项a 1 a_1a1是1 11；
- 如果a k − 1 − k a_{k−1}−kak−1−k是正整数并且没有在数列中出现过，那么数列的第k kk项a k a_kak为a k − 1 − k a_{k−1}−kak−1−k，否则为a k − 1 + k a_{k−1}+kak−1+k。
小杨想知道 Recamán 数列的前n nn项从小到大排序后的结果。手动计算非常困难，小杨希望你能帮他解决这个问题。
【输入】
第一行，一个正整数n nn。
【输出】
一行，n nn个空格分隔的整数，表示 Recamán 数列的前n nn项从小到大排序后的结果。
【输入样例】
5【输出样例】
1 2 3 6 7【算法标签】
《洛谷 B4068 Recamán》 #GESP# #2024#
【代码详解】
#include<bits/stdc++.h>usingnamespacestd;map<int,int>mp;// 用于记录已经生成的数值constintN=3005;// 定义数组的最大大小intn;// 输入的n值inta[N];// 存储生成的序列intmain(){cin>>n;// 输入n// 初始化序列的第一个元素为1，并记录到map中a[1]=1;mp[1]=1;// 生成序列的第2到第n个元素for(inti=2;i<=n;i++){// 尝试用前一个元素减去当前索引iif(a[i-1]-i>0&&mp[a[i-1]-i]==0){a[i]=a[i-1]-i;mp[a[i]]=1;// 标记该值已存在}else{// 如果不能减，则用前一个元素加上当前索引ia[i]=a[i-1]+i;mp[a[i]]=1;// 标记该值已存在}}// 对生成的序列进行排序sort(a+1,a+n+1);// 输出排序后的序列for(inti=1;i<=n;i++){cout<<a[i]<<" ";}cout<<endl;return0;}【运行结果】
5 1 2 3 6 7B4069 字符排序
【题目来源】
洛谷：[B4069 GESP202412 四级] 字符排序 - 洛谷
【题目描述】
小杨有n nn个仅包含小写字母的字符串s 1 , s 2 , … , s n s_1,s_2,…,s_ns1,s2,…,sn，小杨想将这些字符串按一定顺序排列后拼接到一起构成字符串t tt。小杨希望最后构成的字符串t tt满足：
- 假设t i t_iti为字符串t tt的第i ii个字符，对于所有的j < i j<ij<i均有t j ≤ t i t_j≤t_itj≤ti。两个字符的大小关系与其在字母表中的顺序一致，例如e < g < p < s e<g<p<se<g<p<s。
小杨想知道是否存在满足条件的字符串排列顺序。
【输入】
第一行包含一个正整数T TT，代表测试数据组数。
对于每组测试数据，第一行包含一个正整数n nn，含义如题面所示。
之后n nn行，每行包含一个字符串s i s_isi。
【输出】
对于每组测试数据，如果存在满足条件的排列顺序，输出（一行一个）1 11，否则输出（一行一个）0 00。
【输入样例】
3 3 aa ac de 2 aac bc 1 gesp【输出样例】
1 0 0【算法标签】
《洛谷 B4069 字符排序》 #GESP# #2024#
【代码详解】
#include<bits/stdc++.h>usingnamespacestd;constintN=105;// 定义最大字符串数量intT;// 测试用例的数量string s[N];// 存储输入的字符串intf[N*10];// 动态规划数组，用于计算最长非递减子序列intmain(){cin>>T;// 输入测试用例数量while(T--){// 处理每个测试用例intn;cin>>n;// 输入字符串数量// 输入所有字符串for(inti=1;i<=n;i++)cin>>s[i];// 对字符串进行字典序排序sort(s+1,s+n+1);// 将所有字符串拼接成一个长字符串str（前面加一个空格）string str=" ";for(inti=1;i<=n;i++)str+=s[i];intlen=str.size()-1;// 获取有效字符长度（去掉开头的空格）memset(f,0,sizeoff);// 初始化动态规划数组// 计算最长非递减子序列for(inti=1;i<=len;i++){f[i]=1;// 初始化为1（至少包含当前字符）for(intj=1;j<i;j++){if(str[j]<=str[i])// 如果前一个字符不大于当前字符f[i]=max(f[i],f[j]+1);// 更新最长子序列长度}}// 判断最长非递减子序列是否等于字符串长度if(f[len]==len)cout<<"1"<<endl;// 是，说明整个字符串是非递减的elsecout<<"0"<<endl;// 否，说明存在递减部分}return0;}【运行结果】
3 3 aa ac de 1 2 aac bc 0 1 gesp 0
