Oct31==Dec25?

点亮花火 · 2026-11-01 10:13:30 · 个人记录

总结

感觉游记其实写心态的东西挺多的，所以写一下总结吧。

比赛

进场前先洗了个脸，调整了一下，到自己座位上发现电脑是黑的，于是找监考修，监考给换了一台。

比赛刚开始感觉场内很吵，大家都在找监考问问题，监考也在讲话，感觉有一点被影响到。刚开始比较急躁，感觉这是不对的，所以通读题的时候其实后两题没有完全看明白，但这个其实影响不是很大。

听到旁边人已经开始写代码，但没有受到任何影响，感觉这是很对的行为。

感觉 T1 好像不好做，没有慌读了一下题，发现读错了，过了一小会会了，觉得没有什么细节，并且我一般习惯做两题之后开始写代码，至少也要半小时左右开始写代码，于是去看了 T2。

读完题感觉不太能做，但看了数据范围这个 n\le 500 显然很不对，想了一下把路线看作点，过了一会发现同一条路线坐车怎么不需要花费时间，那就好做了，直接建图跑 Floyd 就好了，算了一下复杂度也挺对的，大概都是 10^8 的级别，应该是可以过的。

这时候大概过了 20min 多一点，开始写代码，首先写了 T1，发现二分其实不好写而且可以直接双指针，于是改成了双指针，感觉花费了比较久的时间写这个 T1，出现了一些细节上的问题，感觉写代码太少导致的。

然后开始写 T2，几乎没有遇到任何困难，发现有边权所以修了一下，检查了一下连边是否取 \min，然后很快做完了。

这个时候其实觉得完全有能力做出这个 T3，因为这种对点对计数的题我觉得是比较可做的，同时这个 T4 感觉限制并不是很会转化，因为是对两个集合的限制，所以评估了一下感觉 T3 < T4，其实赛后感觉 T4 不一定是难题，两个题可能都是可做题，而且 T4 明显细节会少一些。

于是策略是尝试思考 T3，然后 T4 拼包，首先思考了如何做到最短路，发现只需要一直跳最远能够到达的点，推导了一会，首先想出了一个非常错的做法，大概是总连通点对数量 - 距离为 1 的点对数量，还需要去掉在同一条链上的数量，但手玩样例后发现这个会有问题，并且只能算 \ge 2 的情况，于是被否了，这个时候其实还剩下不到 2.5h，由于发现了一些性质，临场决策还是选择开 T3。

发现对于点对 u,v，首先显然存在最短路分别从 u 和 v 开始不断跳到最远能跳到的地方，考虑了一会发现两个点跳这样的链，必须恰好有 1 个不同点，否则要么唯一要么 > 2。

其实这个结论是很对的，但后来画了一个图来尝试证明这件事，然后莫名其妙把自己的结论叉了，大概就是这样的图。

叉掉的原因在于画出图之后，认为绿色边的最短路是多一条边的，但实际上绿色是不多边的，所以当时没有考虑绿色边的情况，从而把结论叉掉，并且得到一个想法是，需要区分 u,v 对应的链的起点终点，并根据他们之间的距离做一些判断。

其实根据这个做法在后来也想出来了另一个做法，但这个确实太麻烦了，而且想出来已经来不及了，感觉这个做法完全没有任何美感，就是纯发现各种各样的性质，然后发现只需要保留每一层的右端点，然后做 dp 合并，但这都是后话。

这个时候应该就只有不到 2h 了，这个时间是非常紧的，因为其实还没有思考 T4 的一些部分分，并且也没有写什么暴力。此时觉得 T3 可能有救，评估了一下 T3 和 T4 的部分分，认为 T4 也是一个需要一步步发现性质的题，并且应该部分分也需要一些性质，于是认为可能可做的只保留了 2^n \times n 以及 k=2，特殊性质可能可做，然后决定冲一把 T3。

叉掉结论后开始做 T3，首先有一些显然的性质，比如最短路每一层是区间，转移是一段前缀/后缀，于是只需要保留最右端的一些位置，推了一会转移发现很麻烦。

这个时候其实已经大概 17:15 了，去了一下洗手间，决定要冲这个题，如果在 17:40 没做出来那就只能认了写点暴力了。后来发现了只需要暴力右边两个位置，并且处理好了 A 和 C 的转移，但是 B 的转移里面有一部分是不合法的，应该直接扔掉，但已经没时间了而且当时只能做到平方，并没有思考怎么把一些重复的状态合并起来，然后就草草开始写，写完显然是不对的。

大概只剩下 40min 了，时间是非常紧的，花了几分钟写了三方的 BFS，然后认为应当去做 T4 的纯暴力，然后从 k=2 与这个题的性质 A,B 选出一个来做，因为这题性质 A 其实在第一个结论是不存在我以为的非法情况的。

比较顺利的写了 T4 的暴力，其实看到时间 18 开头的时候就知道已经没救了，因为确实后面需要至少十多分钟用来检查，考虑了一下 T3 的 A 性质还是需要处理边界的一些细节，于是写 k=2 的暴力，哎这个 k=2 怎么这么难，好像会的只有平方，大概是枚举一个点，对于另一个点贡献为子树内最长链以及子树外一条长链，但脑子已经糊了，甚至没有处理出来如何存出来最长链上的点，最后放弃抵抗了，去了个厕所平复了一下心情，检查了文件，然后开始思考这场比赛的失误。

出场想了一会 T3，发现 B 的转移其实是对的，但是需要去掉其中不合法的一部分，然后只需要最外层套一个 dp，记录合法的起点数量，对于可以合并的起点同一处理即可。

对于比赛？

首先评价一下这场的题吧，场上预估 T1 不评价，T2 我的感觉是和去年一样难度的题，T3 和 T4 难度差不多，并且都是需要找性质的题，性质是环环相扣的。

由于还不会做 T4，我觉得还不太好评价，但绝对是一个发现性质就做完了的题，T3 其实也是这样，但两种不同做法之间需要处理的细节是完全不一个量级的。

• 感觉最大的失误就是没有想明白画的东西吧，然后叉掉了结论这样。

• 其次的话，可能是临场的决策有很大问题，其实 CSP 和 NOIP 的很多题，部分分都是具有启发性并且不简单的，但我可能错误估计了自己做出部分分的效率。

• 第三个可能就是，写代码能力，确实有问题。平时写的比较少，可能代码实现能力是很弱的，影响就是，首先在 T1 写错了很多的位置，甚至于写错了离散化，虽然就是没有耽误很多时间；然后 T2 其实还好，T3 并没有能力去花费很短的几分钟写出来一个暴力验证结论，并且对自己写代码时没有信心的。

• 但感觉写代码，本质上就是有没有想清楚细节，感觉很多时候很多题，正解的做法是很优美的，而在模拟赛里可能，过于追求能过题，而没有用心的写暴力，并且很多题没有写代码，导致根本没有办法处理好一些细节吧。

所以就是，模拟赛就是要，当成正赛来打吧，是有道理的，而不应该是，当成题单来，想要花时间做一些好题。然后尽量，以后做题写代码吧，我觉得如果代码能力上来，其实也并不需要花费很多的时间，否则正赛其实，也很难搞。

理性分析一下，可能场上的发挥就是自己的下限了，说实话可能只给一个半小时，写出来的同样是这些分，就是想要的太多了吧。

上限的话，可能是 100 + 100 + [40,100] + 50 这样子，感觉 T4 可能要独立做确实需要很久，当然好像这个 T3 也要很久，但 T4 的 50 肯定是非常好做的，也就是平方的做法吧，只需要枚举一条边然后暴力剥叶子就好了。

做了一下 T4，感觉就是，其实也是可做的，写代码太唐了，因为弱智错误一个小时才修出来，原因是 cnt - m 和 m-cnt 写反了，感觉如果场上也要这么久，那可能，也就是 all in T4 才能做出来，所以其实就是拼包好像就是最好的。

反正 CSP 无所谓吧，NOIP 好好打，干回来就好了。

但，越想其实越觉得可能，唉，比较菜，干不回来了。

薄弱点？

• 读题，想出做法后实现出来的能力。
• 对自己写代码速度的评估能力。
• 场上判断一个东西是否正确的能力。

要做啥？

感觉首先是，实现一个题的时候，估计一下自己要用多久，以及看一下实际用了多久。然后可能对于每个卡住的题，多想一下自己卡在了哪个地方，哪些东西暗示了这个性质，以及这个性质有什么用。

总之就是，做好复盘，然后模拟赛养成一些好习惯吧。

模拟赛要干啥？

• 首先 10 分钟读一下题吧，稍微感觉一下。
• 然后开题，得到结论要尝试写出适用的范围，以及尝试证明。
• 写代码前估计时间。
• 写完前两题之后给后两题都留出一定思考时间。
• 大概每半个小时想一下这段时间里干了啥。
• 记录一下比较关键的时间点。
• 最后一个半小时的时候就要考虑一下手里还拿着多少没写的东西。

如何复盘？

• 得分：T1 / T2 / T3 / T4，总分。
• 时间分配：各题大致用时，关键换题节点。
• 场上进展：后两题分别想到哪里，具体卡在哪里。
• 可避免的失分：读错题、实现错误、会做没写、没有及时换题等。
• 决策反思：根据当时已知的信息，哪次选择值得保留，哪次应该调整。

最后我觉得，终有一日吧，总有一天，我想，希望，会是那一天吧，我想，希望，美好的事情，希望，那一天，会如期而至，希望，活下去，希望，希望。