记录一道 GESP 2024年9月 的模拟真题。这类题在考试里属于必得分项核心就那几行代码关键是别在小细节上丢分。题目来源ACGO A46123 2024年9月 四级赛事场次2024年9月 四级一、题目信息题目名称区间排序赛事场次2024年9月 四级难度定位四级涉及知识点模拟 基础排序题目链接https://www.acgo.cn/problemset/info/46123坑点这题失分基本都在这排序的稳定性冒泡/插入/选择三种排序的复杂度与适用场景。排序题先明确排序关键字与优先级再选 sort 比较器。题意简述小杨有一个包含 n 个正整数的序列 a。小杨计划对序列进行多次升序排列每次升序排序小杨都会选择一个区间 l,r 并对区间内所有数字即 aₗ,aₗ₊₁,…,aᵣ 进行升序排序。每次升序排序会在上一次升序排序的结果上进行。小杨想请你计算出多次升序排序后的序列。前置知识做题之前我们先把几个关键概念说清楚这样后面的代码才好理解。模拟题的解法把题目描述的操作流程一步一步翻译成代码。关键是不要漏掉题目里的任何条件建议先把流程在纸上走一遍再写码。二、思路分析先看清楚题目要我们做什么把题目读两遍我们提取出关键信息输入是什么、要输出什么、有哪些约束条件。这道题考查的是模拟属于这类题里比较基础的一道把题目要求一步步翻译成代码逻辑就能解决。我的思考过程读完题之后我的第一反应是这样的定义足够大的数组存储数据后按题目要求获取区间后对指定区间进行排序。需要提前准备自定义排序函数或使用sort排序注意限制进行排序的范围。样例中描述的下标是从下标1开始存储的注意检查自己的存储情况对应的下标是否正确。需要说明的是上面这个思路是把题目要求直译成代码得到的没有用到什么高级技巧。对于这类基础题读准题意加写对边界比追求巧妙解法更重要因为考试里这种题是必须拿满分的。三、完整代码 逐行注释#include iostream #include algorithm using namespace std; int n,q,l,r; int a[110]; void f(int x,int y){ //sort(ax,ay1); //冒泡排序,可自由选择其他排序方法 int flag1; while(flag){ flag0; for(int il;ir;i){ // 遍历 if(a[i]a[i1]){ // 判断 flag1; swap(a[i],a[i1]); } } } } int main() { cinn; // 读入 for(int i1;in;i){ // 遍历 cina[i]; // 读入 } cinq; // 读入 for(int i1;iq;i){ // 遍历 cinlr; // 读入 f(l,r); } for(int i1;in;i){ // 遍历 couta[i] ; // 输出 } return 0; }四、代码分段拆解为了看得更清楚我们把代码按功能分成几段解释。第一步引入头文件#include iostream #include algorithm using namespace std;#include iostream提供输入输出功能using namespace std;让我们能直接写cin、cout而不用加前缀。这两行是几乎所有 C 程序的开头照写即可。第二步读入数据cinn; cina[i]; cinq;注意变量的类型要能装下题目的数据。数据可能超过 21 亿时要改用long long。第三步核心处理逻辑while(flag){ for(int il;ir;i){ for(int i1;in;i){ for(int i1;iq;i){这一段是整道题的关键也是模拟的体现。看循环的三个要素从哪里开始、什么时候结束、每次怎么变化。这三个要素任何一个写错结果都会不对。第四步按要求输出couta[i] ;输出格式必须和题目要求的完全一致。很多同学算法完全正确却因为少了一个换行或者空格多寡不对而 WA这种分丢得最可惜。五、实例模拟把样例代进去手动模拟一遍思路会更清晰。以题目的第一组样例为例样例输入5 3 4 5 2 1 3 4 5 3 4 1 3样例输出1 3 4 5 2把这份输入代进代码程序会先把数据依次读入然后进入循环逐个判断把满足条件的值累积起来最后按格式输出。建议你对照着代码在纸上走一遍前两次循环确认自己对每一步的理解都和程序一致。六、踩坑总结下面是做这道题时最容易出错的地方对照自己的代码检查一下变量类型选错虽然本题范围不大但养成习惯——凡是不确定范围时累加变量一律用long long成本为零但能保命。区间边界取错题目说「L 到 R 之间包括两端」循环就要写for (int i L; i R; i)。写成i R会漏掉最后一个数这是最常见的失分点。循环起点搞错题目说的是「正整数」循环要从 1 开始而不是从 0 开始差一个数就是 WA。输出格式不符题目要求输出几行就输出几行行末换行、数字之间的空格都要严格对齐算法对了但格式错了同样判 WA这种分丢得最冤。特殊情况没特判把最小数据、最大数据、答案恰好等于 0 的情况各测一遍。特别是边界输入出题人最喜欢在这里设陷阱。七、知识点拓展把这题的经验提炼一下以后遇到同类题可以直接套用本题考查模拟的基本写法这类题在考试中属于必得分项要练到能默写。写完代码后建议自己造几组边界数据测试特别是最小值和最大值。同一知识点在不同场次反复出现把这道题的写法吃透后面遇到同类题可以直接套用。八、适用人群刚学完模拟、正在准备 四级 考试的同学适合用这道题检验掌握程度。如果这篇题解对你有帮助欢迎点赞收藏。后续我会继续按场次整理 2024年9月 四级 的真题关注我可以第一时间看到更新。有更好的写法也欢迎在评论区交流。