2024年3月GESP八级认证C组的编程题里有一道“接竹竿”我印象非常深。这题初看是个生活场景模拟但真正动手之后会发现它本质上是一道非常典型的区间连通性问题考察的是你把“题目描述”抽象成“数学模型”的能力。GESP八级作为最高等级考的就是这种区分度——题面包装得很朴素背后的算法却是实打实的排序贪心。这篇文章就把这道题的完整拆解写下来从题面还原、建模思路、C实现到考场上的易错点和扩展变体一次性讲透。适合正在备考GESP八级、或者想补一补区间类算法基础的同学参考。1. 先聊聊GESP八级在考什么1.1 八级的难度定位与考察范围GESP一共八个级别八级是顶格。到了这个级别考点已经不只是“会不会写循环”了而是要求考生具备一定的算法设计和建模能力。官方大纲里列出的内容大致包括树和图的基础操作、常见排序算法的复杂度分析、动态规划入门、贪心思想、以及STL的熟练使用。编程题通常有两道分值占比很大第一道往往偏模板题、考基本功第二道就是“接竹竿”这种需要多转一层弯的题。拿“接竹竿”来说它表面讲的是竹竿、跳跃、行走实际考的就是区间合并。这种出题风格近几年越来越常见不是在题目里写“给你n个区间求合并后的总长度”这种直白表述而是把区间藏在一个生活场景里让你自己把它挖出来。八级考生能不能从一堆文字描述里识别出“这是区间问题”直接决定了这道题能不能拿满分。1.2 “接竹竿”的考点映射这道题真正考察的东西我从高到低排一下第一层建模能力把竹竿抽象成数轴上的区间把“能否接上”抽象成区间是否相交。第二层贪心思想排序后按顺序合并区间维护当前可达的右边界。第三层代码基本功排序、扫描、二分查找用STL熟练实现。很多考生栽在第一层。他们盯着“竹竿”两个字试图模拟跳跃过程用一堆条件判断去处理每一根竹竿的位置关系结果把自己绕晕了。正确的做法恰恰相反——把竹竿全部画到数轴上问题瞬间就清晰了。这也是我想在文章开头就强调的信息学竞赛题不是读题而是拆题。1.3 为什么这道题区分度高“接竹竿”的题面信息量不大看起来也没什么吓人的术语但区分度恰恰来自这里。基础一般的同学能看懂题意但想不到区间化基础中等的同学能想到区间化却在边界条件上翻车只有真正吃透区间合并本质的同学才能又快又稳地拿下满分。这道题大概就是这种定位它不考偏门算法考的是你对经典算法的理解深度以及考场上的细心程度。2. 从题面到数学模型把竹竿变成区间2.1 题面关键条件还原先把我记忆中的题面还原一下。大约是这样地上水平放着若干根竹竿给定每根竹竿的左端点坐标 x 和长度 len那么这根竹竿就占据了数轴上 [x, xlen] 这么一段。你从某个位置 p 出发沿数轴正方向前进。规则是这样的遇到第一根竹竿时你必须跳上去然后可以沿着竹竿走到它的右端点如果下一根竹竿和当前竹竿在水平方向上有重合包括端点正好相接你就能直接跨过去继续走如果中间出现了空隙你掉到地上行程就结束了。问的是最远能到达哪个坐标。不同版本可能在起点上略有出入有的题目规定起点是 0有的会给多个询问起点。但无论哪种版本核心模型是一样的。只要你愿意多花两分钟把题面翻译成数学语言整道题的复杂度瞬间就从“模拟跳跃”降成了“区间处理”。2.2 区间化的三个关键推论第一竹竿的高度是没有用的。题面里竹竿横放在地面或同一水平面上你的跳跃实际上是水平投影上的衔接。所以每根竹竿只需要关心它在 x 轴上占据的闭区间 [L, R] 就够了完全不需要考虑“高度”“角度”这些干扰项。第二两根竹竿能“接上”的充要条件是后一根竹竿的左端点不超过当前一根竹竿的右端点。也就是说区间 [L1, R1] 和 [L2, R2] 满足闭区间相交或相接的条件即 L2 R1。不需要它们长度有多长也不需要位置完全重合只要存在一个 x 坐标你站在前一根竹竿的右端或某个位置能正好够到后一根竹竿的左端就能继续前进。第三这个问题最终会变成一个“找连通块右边界”的问题。把所有竹竿按区间画在数轴上互相之间有交叠的区间会连成一片。你不管从哪个点出发只要你跳上了某一根竹竿你能到达的最远位置就是你所在的这一片连通区间的最右端点。如果你从地面出发你会先遇到哪根竹竿是那根左端点大于等于 p 的最靠左的竹竿所以答案就是那根竹竿所在连通块的最右端点。2.3 边界条件到底用 还是 这是我在评论区看到讨论最多的问题没有之一。两根竹竿端点恰好重合时到底算不算“能接上”我的答案是算。请你想象一个画面——第一根竹竿的右端点在坐标 5第二根竹竿的左端点也在坐标 5。你沿第一根竹竿走到右端点原地笔直站定面前就是第二根竹竿的端点你只需要迈一小步或者轻轻一跳就能过去。这个动作在物理上完全成立。所以判断条件一定是 L2 R1而不是 L2 R1。这个细节在区间合并代码里就对应一行if (a[i].L curR)。很多同学写成结果边界测试点一跑就错非常可惜。闭区间就是闭区间这种地方不是题目坑你是你自己对“相接”这个概念的理解不够严谨。3. 排序与区间合并完整实现方案3.1 总流程设计整道题的做法分四步走输入每根竹竿的左端点 x 和长度 len计算右端点 R x len存成区间。把所有区间按照左端点从小到大排序。如果左端点相同就按右端点从小到大排保证扫描时顺序稳定。线性扫描一遍把互相接触的区间合并成一个个不相交的“连通块”。对每个询问起点 p用二分查找定位到它所在的或它前方第一个连通块输出这个连通块的最右端点。如果你只有单起点询问第4步可以直接在扫描过程中同步完成但写成“分组二分”的结构更通用多询问也不用改。考场上面临时间压力的时候我建议你直接用这个通用结构因为它的逻辑线性单一不容易在边界上出幺蛾子。3.2 关键代码区间合并这道题我用最标准的 C 写法来实现STL 的vector、sort、lower_bound都用上代码量并不大#include bits/stdc.h using namespace std; typedef long long ll; struct Node { ll L, R; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin n q; vectorNode a(n); for (int i 0; i n; i) { ll x, len; cin x len; a[i] {x, x len}; } // 1. 按左端点排序 sort(a.begin(), a.end(), [](const Node u, const Node v) { if (u.L ! v.L) return u.L v.L; return u.R v.R; }); // 2. 一次扫描合并出互不相交的连通块 vectorNode group; ll curL a[0].L; ll curR a[0].R; for (int i 1; i n; i) { if (a[i].L curR) { // 与当前连通块有接触扩展右边界 curR max(curR, a[i].R); } else { // 出现空隙当前连通块闭合 group.push_back({curL, curR}); curL a[i].L; curR a[i].R; } } group.push_back({curL, curR}); // 3. 提取所有连通块的左端点用于二分 vectorll Ls; for (auto g : group) Ls.push_back(g.L); // 4. 回答每个起点 while (q--) { ll p; cin p; int idx lower_bound(Ls.begin(), Ls.end(), p) - Ls.begin(); ll ans; if (idx 0 group[idx - 1].R p) { // p 落在了前一个连通块的范围内直接输出该块右端点 ans group[idx - 1].R; } else if (idx (int)group.size()) { // p 在空隙中或第一个块的左侧跳上第一个遇到的块 ans group[idx].R; } else { // p 右侧没有竹竿了 ans p; } cout ans \n; } return 0; }这里面最核心的是那个if (a[i].L curR)判断。它的含义就一句话只要下一根竹竿的左端没有超过当前可达的右边界我就能把右边界继续拓展。反之如果a[i].L curR说明中间出现了货真价实的空隙这一片连通块彻底结束后面的竹竿无论怎么排列都不可能跨过这个空隙被接上来因为它们的左端点只会更大不会更小。curR max(curR, a[i].R)这一步也值得多说一句。为什么不用curR a[i].R因为排序只保证了左端点有序不保证右端点有序。可能出现前面一个长竹竿覆盖到 100后面一根短竹竿左端点在 60、右端点在 70 的情况。如果直接赋值为 70右边界反而缩小了后面原本能接上的长竹竿就被错误地截断了。所以必须取两者的最大值。3.3 复杂度分析排序是 O(n log n)线性扫描合并是 O(n)每个询问做一次二分查找是 O(log n)。如果题意给的是单起点整个算法就是 O(n log n)如果给的是 q 个询问整体是 O(n log n q log n)。这个复杂度在 GESP 的题面数据范围下可以轻松跑过哪怕是 n 取到 10^6 量级排序 1e6 个数在现代评测机上也就是一瞬间的事。相比之下如果你真的去模拟每一根竹竿的跳跃路径最坏情况要 O(n^2)而且还要处理一堆无序的位置关系代码写得越长越容易出错。这就是建模的价值把问题形式化以后一个教科书级的贪心扫描就能解决问题。4. 回答查询的两种姿势4.1 单起点也可以直接扫描如果题目只给你一个起点你确实可以在扫描合并的同时计算出答案。基本流程是先定位到第一根左端点大于等于 p 的竹竿然后从它开始维护 curR一边扫描一边扩展直到遇到空隙为止。这样省掉分组后的二分查找代码可能更短一点。但我的建议是不要为了省这一点代码而牺牲通用性。因为 GESP 八级的题目偶尔会把“单起点”改写成“多行询问”你一上来看到q个询问如果只写了单起点的扫描版本就得现场重构。而分组二分的版本无论 q 是 1 还是 100000都能原地不动地直接通过。4.2 多起点二分定位连通块多起点的核心逻辑已经在上面代码里了我再把它拆开揉碎讲一遍。假设我们已经把竹竿合并成了若干个互不相交的连通块group每个块都有左端点 Ls[i] 和右端点 group[i].R情况一p 落在某个连通块内部。这时你跳上该块后能一直走到块的最右端答案是 group[i].R。情况二p 落在两个连通块之间的空隙。这时你从地面走到后方那个块也就是第一个左端点大于等于 p 的块的左端跳上去答案同样是那块的右端点。情况三p 在第一个连通块的左侧答案就是第一个连通块的右端点。情况四p 的右侧没有任何连通块也就是 p 大于所有竹竿的右端点那么答案就是 p 本身或者按题面要求的某个边界值。用lower_bound找到第一个Ls p的块下标 idx 之后只需要检查前一个块的右端点是否大于等于 p就能区分“p 在块内”还是“p 在空隙中”。这个检查极其关键漏掉它你的答案会在 p 恰好落进某个块时输出错误。4.3 如何构造样例自测不管是在考场上还是在平时练习我都强烈建议你至少手算三组小数据再提交。这个习惯能帮你拦住一大半低级错误。就拿这道题来说我通常会用下面几组第一组一根竹竿1 1 1 5 0竹竿覆盖 [1,6]起点 0从地面走到 1 跳上去最远到 6。答案 6。第二组两根竹竿有空隙2 1 1 2 4 2 1区间 [1,3] 和 [4,6]起点 1。你从 1 上杆到 3 时前面是空隙结束。答案 3。第三组两根竹竿端点相接2 1 1 2 3 2 1区间 [1,3] 和 [3,5]起点 1。端点重合能接上答案 5。第四组起点恰好在空隙里2 1 1 2 5 2 3区间 [1,3] 和 [5,7]起点 3。从 3 向前走遇到第一根竹竿是 [5,7]跳上去答案 7。把这些样例跑一遍你的二分逻辑和边界判断基本上就稳了。5. 现场最容易踩的坑5.1 坑一忘记排序这是我见过的最高频错误没有之一。有人以为输入数据就是按顺序给的直接不排序就扫描合并。这相当于赌命题人的数据善良但竞赛数据从来不善良。不排序你的“当前右边界”覆盖不到那些左端点更小却排在后面的区间合并结果必然出错。记住区间合并类问题的第一步永远是排序这是铁律。5.2 坑二int 类型溢出题目里 x 和 len 如果各是 10^9 量级右端点 xlen 就是 2*10^9已经超出 int 的表示范围了。我在网上看到不少同学用 int 存右端点本地样例全过提交后一两个测试点 WA半天找不到原因。这种题一律用long long不要有任何侥幸心理。排序、比较、答案输出全部用long long多打三个字母换来的是全场安心。5.3 坑三合并循环里提前 break另一种常见错误是扫描时遇到第一个空隙就 break然后直接输出。这在单起点且只关心第一个连通块的场景下勉强成立但如果你先整体分组、后面还要回答多组询问提前 break 会丢掉后面的所有区间导致分组不完整。正确做法是遇到空隙就把当前块收尾然后继续往后扫而不是跳出整个循环。5.4 坑四更新右边界时忘了 max前面分析过curR max(curR, a[i].R)和curR a[i].R是完全不同的两件事。排序不能让右端点有序所以你必须显式取最大值。这个错误特别隐蔽因为小数据很难测出来往往是在有“长区间包含短区间”的测试点才会暴露。5.5 坑五输入输出性能很多考生平时用cin/cout从不开加速到了大数据量的题就开始超时。GESP 八级的 n 通常不会特别大但既然把ios::sync_with_stdio(false); cin.tie(nullptr);写上就能白捡性能为什么不写考场时间有限不要在这种地方给自己添堵。我把这些坑整理成一张速查表方便你考前扫一眼坑点错误写法正确写法后果排序直接用输入顺序sort(a.begin(), a.end())合并结果随机大面积 WA类型溢出int存坐标long long全字段大数据点溢出隐蔽 WA接触判定L2 curRL2 curR端点相接数据点丢分右边界更新curR a[i].RcurR max(curR, a[i].R)长区间被短区间截断合并中断break收尾后继续扫描分组不完整后序询问错误输入输出未加速的cin/cout加ios::sync_with_stdio(false)大数据点可能 TLE6. 换个思路并查集版本选读6.1 为什么有时候想用并查集区间合并的扫描法已经足够简洁了那为什么还要提并查集因为“连通性”这个词一旦出现很多人的第一反应就是并查集。事实上这道题确实可以套并查集把所有互相接触的区间放到同一个集合里最后找出起点所在集合的最右端点。但我要提醒你对一维区间来说并查集是“杀鸡用牛刀”。区间在一维数轴上的连通性有一个非常好的性质——它是按顺序单向传播的只要左端点有序一次扫描就能合并完根本不需要维护复杂的树结构和路径压缩。只有在处理更高维的连通问题比如平面矩形连通、图上连通性并查集才真正发挥威力。6.2 并查集做法的思路大纲如果你就是想写并查集版本思路是这样的先按左端点排序用并查集把“和当前块有交叠”的区间连到同一个根上。具体实现要维护一个“当前最右端点”和“当前窗口”保证每个区间只和前面的一个代表元合并避免 O(n^2) 地枚举所有区间对。排序后可以做到接近 O(n log n) 的复杂度但代码比扫描法复杂不少。6.3 两种方案对比方案代码量易错点适用场景排序扫描二分短40 行内搞定边界判定、右端点更新一维区间的绝大多数变体并查集较长需要维护额外信息窗口维护、路径合并二维及以上连通问题我的看法是考场写扫描法就够了并查集可以作为思维拓展去理解。因为 GESP 八级考的是你在有限时间内稳定得分的能力不是炫技。最稳的算法就是最好的算法。7. 同类题与备考建议7.1 真题改编方向“接竹竿”这个模型太经典了命题人只要换层皮就能变成新题。我列举几个常见的改编方向你在备考时如果能把它们都想明白区间合并这一块就算彻底吃透了改成“最少需要多少根新竹竿才能从起点连通到终点”。这就变成了经典的区间覆盖问题做法是排序后贪心选择能覆盖当前右端点的最右区间。改成“给定一个目标点判断能否从起点到达”。答案就是判断可达右端点是否大于等于目标点。改成“求所有空隙中最长的那一段”。合并且分组完成后扫描所有相邻组之间的空隙取最大值。改成“每个区间有权值求从起点出发能获得的最大权值”。合并连通块的同时累加权值即可。你会发现这些变体全都建立在“区分区间、排序、合并、查询”这四个步骤之上。核心模型不变换的只是外壳。7.2 备考八级的刷题建议GESP 八级的区间类问题我建议你把三大经典题练透区间合并、区间覆盖、区间选点。这三类题分别对应了三种不同的贪心策略但它们有一个共同的起手式把题面抽象成数轴上的区间然后排序。我在备考阶段就是这么练的先花两周把这三个题型的模板写到闭眼能敲的程度再去做带场景包装的真题会发现自己识别模型的速度快了很多。另外一个很实用的建议是每次读题后先不要急着敲键盘拿笔画一下数轴。把竹竿画成线段把起点标出来眼睛看着图写代码边界条件会清晰得多。有时候你在纸上画完图代码的思路就已经自然而然地浮现出来了。最后再分享一个小技巧我实际做题时的习惯是提交之前一定会把代码里所有和“右端点”有关的变量名检查一遍确认每一处用的都是curR而不是a[i].R。这听起来很蠢但人在考场高压状态下最容易在自以为熟悉的地方犯低级错误。另一个习惯是写完后心里默念一遍那五个坑排序了吗long long 了吗边界是 吗更新用 max 了吗加速流开了吗五句话念完基本就能把低级的丢分点全部堵住。“接竹竿”这道题本身不难难的是在有限时间内不犯任何一个低级错误。把区间合并这个模板吃透你在八级考场上遇到它和它的所有变体都能从容应对。