GESP2026年3月认证C++八级( 第三部分编程题（1、消息查找））精讲

GESP C 八级 第三部分编程题第一题《消息查找》——聊天记录里的秘密通道图压缩思想第一幕QQ群里的聊天记录1、同学们。1大家有没有在QQ群、微信群里面聊天过例如今天老师发了一条消息① 明天上午九点考试。2过了一会。小明回复② 引用① 老师我知道了。3又过了一会。小红回复③ 引用② 我也是。4后来。小军回复④ 引用① 需要带准考证吗5是不是像这样① 明天上午九点考试 ↑ ↑ ② ④ ↑ ③这里。出现了一种新的关系。除了消息按时间排列。还有引用关系。2、平时怎么看聊天记录1假设。你现在正在看③你想看看老师最开始说了什么。怎么办2第一种办法。一直往上翻。③ ↓ ② ↓ ①是不是需要两次。3还有一种办法。因为③引用了②。是不是可以直接跳过去③ ↓ ②然后②又引用①。于是③ ↓ ② ↓ ①还是两步。4但是。如果引用关系更多。例如① ② ③ ④ ⑤引用① ⑥引用⑤ ⑦引用⑥如果一直往上翻。⑦ ↓ ⑥ ↓ ⑤ ↓ ④ ↓ ③ ↓ ② ↓ ①需要6步。5但是利用引用。是不是⑦ ↓ ⑥引用 ↓ ⑤引用 ↓ ①引用只需要3步。是不是快了一半3、于是。今天这道题。其实就是怎样最快找到以前的一条消息。第二幕读懂题目1、我们先看看题目。题目给我们很多条消息。例如1 2 3 4 5 6 72、有些消息。没有引用。例如2就是普通消息。3、有些消息。引用了以前的一条消息。例如6 引用 3那么。从6开始。可以有两种操作。4、第一种。往上一条。例如6 ↓ 55、第二种。如果当前消息。引用别人。可以直接跳过去。例如6 ↓ 3这也算一步。6、现在。老师问6 ↓ 2最少几步这就是每一次查询。第三幕先做样例1、我们先来看一个简单例子。1假设共有6条消息。① ② ③引用① ④ ⑤引用② ⑥引用⑤2画成图。① ↑ ③ ② ↑ ⑤ ↑ ⑥ ④3注意除了引用。还有消息顺序。也就是说任何消息。都可以往上一条。4例如⑥ ↓ ⑤ ↓ ④ ↓ ③ ↓ ② ↓ ①5所以。真正能够走的路。其实有两种。例如⑥ ↓ ⑤这是上一条。还有⑥ ↓ ⑤引用②可以一下跳。6现在老师问。⑥ ↓ ①怎么走最快第一种。一直翻。⑥ ↓ ⑤ ↓ ④ ↓ ③ ↓ ② ↓ ①需要5步。第二种。利用引用。⑥ ↓ ⑤ ↓ ② ↓ ①只需要3步。是不是更快所以。引用。就是一条捷径。第四幕这到底是什么问题1、很多同学。做到这里。第一感觉这不像字符串。不像数组。更不像DP。那么。到底是什么2、我们把每一条消息。看成一个点。例如① ② ③ ④ ⑤ ⑥都是一个点。3、再把可以操作。画成边。例如上一条。⑥ ↓ ⑤ ↓ ④ ↓ ③ ↓ ② ↓ ①是不是很多边4、引用。也画成边。例如⑥ ↓ ⑤ ↓ ②是不是又多了一条边5、于是。整道题。其实变成一张图。例如⑥ ↙ ⑤ ↓ ② ↓ ① ↓ ……老师问⑥ ↓ ①最少几步。是不是就变成图上的最短路第五幕第一反应——BFS1、大家还记得。什么时候。用BFS2、当每一步代价都一样。今天上一条。一步。引用。也是一步。是不是所有边。都是1。3、所以很多同学。第一反应就是BFS。4、例如每一次询问。都起点 ↓ BFS ↓ 找到终点是不是完全正确5、我们甚至可以写出程序。每次询问 { BFS(); }很多同学。做到这里。都会觉得可以结束了。第六幕为什么 BFS 会超时1、汉克老师最喜欢说算法之前。先算复杂度。2、假设消息有100000条。查询也有100000次。那么。一次BFS。最坏。是不是可能把十万条消息。全部走一遍也就是100000步。3、现在。询问十万次。是不是100000 × 100000等于100亿4、所以。每次查询重新 BFS。一定超时。第七幕高手不会急着写算法1、真正的高手。看到一道题。第一件事。不是想算法。而是认真读题。因为很多时候。方法就藏在题目里。2、于是。我们发现。题目里面。有一句话。引用消息的数量非常少。题目限制引用消息总数远小于消息总数。3、老师问大家。这句话。为什么。要告诉我们如果一点用都没有。命题老师。为什么。专门写出来第八幕真正的突破口1、假设。1有100000条消息。2但是只有1800条。带引用。3也就是说剩下98200条。全部都是普通消息。4例如…… 1001 1002 1003 1004 1005 ……它们。没有引用。只能一直往上一条。5老师问这些消息。有没有自己的选择6没有。是不是只能1005 ↓ 1004 ↓ 1003 ↓ 1002永远只有这一条路。6那么。真正改变路线的。是谁是不是那些带引用的消息7例如1005 ↓ 1004 ↓ 1003 ↓ 200因为1003引用了200。一下跳过去。路线。立刻发生变化。8于是我们的结论真正影响答案的不是十万条消息而是那不到两千条会跳跃的消息。这就是整道题真正的突破口。第九幕为什么普通消息可以忽略1、很多同学。会觉得老师。十万条消息。怎么可能忽略我们来看一个例子。2、例如50 ↓ 49 ↓ 48 ↓ 47 ↓ 46中间。没有任何引用。3、老师问。从50到46。是不是永远只有一种走法50 ↓ 49 ↓ 48 ↓ 47 ↓ 46没有第二条。是不是那么。这一段。其实。没有任何决策。没有任何技巧。只是一直往前翻。4、因此。真正值得研究的。并不是这些普通消息。而是什么时候。会突然出现一条引用边。因为只有引用才能改变。最短路。第十幕如果只研究关键消息会发生什么1、我们已经发现真正影响路线的。只有引用消息。2、例如1 2 3引用1 4 5 6引用3 7 8 9引用2 103、请问大家。这里。真正重要的是谁是不是3 6 9因为只有它们。能够突然跳跃。4、其它消息。是不是永远只能10 ↓ 9 ↓ 8 ↓ 7一直往前。5、于是。我们提出一个大胆的想法。能不能。只保存这些关键消息很多同学。第一反应不能其它消息怎么办别急。我们继续研究。第十一幕普通消息真的重要吗1、例如现在20 ↓ 19 ↓ 18 ↓ 17 ↓ 162、中间没有任何引用。老师告诉你20 ↓ 16距离就是4。根本不用一步一步数了直接知道答案。3、于是。普通消息。其实可以压缩。第十二幕什么叫图压缩1、来看一个例子。原图100 ↓ 99 ↓ 98 ↓ 97引用30 ↓ 96 ↓ 95 ↓ 94引用10 ↓ 93是不是很长2、真正重要的是97 94因为只有它们。能够跳。3、于是。老师把中间普通消息。全部缩起来。4、变成100 ↓ 97 ↓ 94 ↓ 935、注意。不是真的删掉。而是把中间距离。记下来。6、例如100→97 距离 3以后。不用走100 ↓ 99 ↓ 98 ↓ 97直接知道花3步。7、是不是快很多这就叫图压缩。第十三幕怎样保存这些关键消息1、老师现在。重新编号。例如原来消息 97 94 30 102、现在我们变成① ② ③ ④3、为什么因为以后。程序里面。不用十万个编号。只研究关键点。4、于是程序中if(mark[i]) { p[cnt]i; pos[i]cnt; }什么意思就是发现引用消息。保存。重新编号。以后。整个程序。只研究这些点。第十四幕关键点之间怎么算距离1、现在。假设关键消息只有刚才的四个。① ② ③ ④2、请问。①到②。距离多少怎么办是不是直接数。3、例如100 ↓ 99 ↓ 98 ↓ 97一共3步。于是记录①→② 34、如果还有引用。例如97 引用 30是不是还能多一条边5、于是关键点之间。其实变成一张很小很小的图。原来十万个点。现在只有两千个。第十五幕为什么可以预处理1、查询有十万次。如果每次。重新算。是不是还是很慢2、但是关键点只有两千个。我们有没有办法。一次。全部算出来3、例如先算①→② ①→③ ①→④再算②→① ②→③……4、是不是以后查询。直接查表。根本不用重新搜索。这就叫预处理。第十六幕查询的时候怎么办1、例如题目问99999 ↓ 1002、第一步。找到最近关键消息。3、第二步。利用已经算好的关键点距离。4、第三步。最后。再补普通消息。5、整个过程。不用重新BFS。所以。一次查询。非常快。第十七幕参考程序#include cstdio #include algorithm using namespace std; const int N 1e5 5; const int C 2e3 5; const int oo 1e9; int n, q; int r[N], mark[N], pos[N]; int p[C], cnt; int d[C][C]; int pre[N], suf[N]; int main() { scanf(%d%d, n, q); for (int i 1; i n; i) { scanf(%d, r[i]); if (r[i]) mark[i] mark[r[i]] 1; } for (int i 1; i n; i) if (mark[i]) { p[cnt] i; pos[i] cnt; } for (int i 1; i cnt; i) { for (int j 1; j i; j) d[i][j] oo; d[i][i] 0; for (int j i; j 1; j--) { d[i][j - 1] min(d[i][j - 1], d[i][j] p[j] - p[j - 1]); if (r[p[j]]) { int k pos[r[p[j]]]; d[i][k] min(d[i][k], d[i][j] 1); } } } for (int i 1; i n; i) { pre[i] pre[i - 1]; if (mark[i]) pre[i] i; } suf[n 1] n 1; for (int i n; i; i--) { suf[i] suf[i 1]; if (mark[i]) suf[i] i; } while (q--) { int x, y; scanf(%d%d, x, y); if (pre[x] suf[y]) printf(%d\n, x - y); else printf(%d\n, x - pre[x] d[pos[pre[x]]][pos[suf[y]]] suf[y] - y); } return 0; }第十八幕为什么压缩预处理的算法能过1、我们来比较。普通做法。每次BFS。100000 × 100000约100亿。一定超时。2、压缩预处理的算法。真正处理的。只有两千个关键点。预处理一次。以后所有查询。几乎都是查表。3、复杂度立刻降下来。这就是命题老师。真正想考察的。不是BFS。而是发现数据特点。第十九幕完整算法流程1、整道题其实只有下面几个步骤。读入消息 │ ▼ 找到所有引用消息 │ ▼ 重新编号 │ ▼ 建立关键点之间的图 │ ▼ 预处理关键点最短路 │ ▼ 回答所有查询2、程序真正难点是想到为什么只研究关键点。第二十幕这道题真正考察什么它真正考察的是知识点是否重点本题作用图建模⭐⭐⭐⭐⭐把消息看成图BFS思想⭐⭐⭐发现暴力方法数据规模分析⭐⭐⭐⭐⭐判断算法是否超时图压缩⭐⭐⭐⭐⭐整题核心预处理思想⭐⭐⭐⭐一次计算多次查询查询优化⭐⭐⭐⭐快速回答十万次询问所以。它真正想训练大家的是看到数据特点主动寻找优化方法。课堂总结这道题最大的价值在于学会一种竞赛思维不要被十万个点吓住而要观察真正影响答案的是哪些点。很多 NOI、NOIP 提高组题目都不是靠更快的循环而是靠发现数据中的特殊结构。