记本次GESP八级
2024-07-07 19:26:25
发布于：上海
提示：本文没有正解！！！
总体来说海星。
首先是选判题，这次还是挺简单的。几何题只考了勾股定理 ，不会三角函数的六年级生狂喜。代数题套一下组合数和二项式的公式就行了。语法算法题也还行。
重头戏当然是编程题。我先把自己回忆的题面放一下（可能与原题有出入，但不影响理解）。
题面
T1
给定一棵 个节点的无根树（无边权），每个节点是黑色或白色，求这棵树中相距最远的不同色节点的距离。
%： 且树的形态是一条链。
另外 %：。
所有：。
T2
给定一个二维平面，上面有 个水平于 轴的挡板。第 个挡板的左端点 坐标为 ，右端点 坐标为 ， 坐标为 。保证所有挡板两两无交点。你初始在第 个挡板的左端点处，目标是移到第 个挡板上。在挡板上左右移动 单位需要 秒。当你在挡板的左右端点时，你可以下坠直到下面的挡板（下坠过程中不能左右移动）。下坠 单位同样需要 秒。求最短时间花费，无解输出 。
%：对于所有 ，。
另外 %：对于所有 ，。
所有：。
思路
T1
容易发现我太弱了。我想不出正解，就先把 Task 2 打了暴力。从每个点开始广搜记录答案，时复 。
然后是 Task 1，链式图只需要从两头开始搜就行了，时复 。
不过我还不知道正解。好像比较接近的是只搜叶子节点？不过最坏时复依然是 （菊花图）。好像又有点像要求 LCA 的节奏，不过又不完全像 （我连 LCA 的板子都没背）。
后面想着随机化拼人品骗 Task 3（GESP 可以 次测试），然后 Task 3 拿到了 的好成绩。
考场上 （即 ），拿了前两个部分分。
T2
好像要 dp，但我连状态都不会设，一看部分分有 ，果断地去骗部分分了。
Solution 0
学习⑨，输出 。
预计得分 。
考场实测 ，比我旁边那个辛辛苦苦打了半天的老哥还高 2.5pts hhh。
Solution 1
首先有一个好想的无解情况：，毕竟你总不可能往上跳或者跨过空隙吧。
那么排除这种情况，我们直接去想 Task 1。既然所有挡板左端点都在 ，开局直接从左端点跳下去就行了。到达第 个挡板的左端点只需要 秒。答案即为 。
剩下情况，传承⑨的优良品德，输出 。
预计得分 。
考场实测 ，看来对 CCF 来说，学习⑨还是有用的。
Solution 2
在 Solution 1 的基础上，我们拼命地想 Task 2。
容易发现 Task 2 有解的前提是 至 单调（严格）递减，因为你只能往下跳。
那么有解的情况答案是怎样的呢？画一张图：（可能有点丑，见谅）
红线是实际要走的路径。把它们移补一下就变成了等长的绿线。我们发现，绿线的长度就是 与 的差加上上下高度差！形式化地说，答案为 。
剩下情况，继续传承⑨的优良品德，输出 。
预计得分 。
考场实测 ，看来对 CCF 来说，有时学习⑨是没用的。
考场上实现了 Solution 2，得到 （即 ），同样拿了前两个部分分。
总结
暑假真的来了，祝大家暑假快乐！
奶嘴可爱捏，所以奶嘴来镇文了。
后记： 分，我真逊。
有帮助，赞一个