CSP 梦游记。

· · 生活·游记

CSP 梦游记。

由于作者在经历完 CSP 后去备考期中考试了，所以这篇文章的发布时间较晚。

注：为了提升阅读体验，在发布这篇文章时有删改。原文可以在我的专栏里看。

\texttt{2025-10-29 \& Day -3}

在首师北^1集训的最后一天。

今天打了信心赛（大约 CSP-J 至 CSP-S 之间），但是还是考得很差。T1 博弈论看错题虚空调试 30min，T2 组合数学写了正解但是忘取模，还没调出来，遂写暴力但是依旧忘取模，(190, 260] \rightarrow 160 喜提倒数第二。

洛谷我谢谢你给我的大凶。

下午不知道怎地就开始颓 2048 了，肝了 600 行的 C++ 控制台版，居然成功合成出 8192。现在越临近考试、压力越大，就越想颓，信心也大不如前了。我这是怎么了。

回家后开始做老师发的数学小练习，然后被飞了，现在 whk 也不行了。

肖岱恩我想你了。

\texttt{2025-10-30 \& Day -2}

回到本部集训了。

本部有世界上最好的 NOI Linux 实体机，比首北的 Ubuntu 虚拟机流畅多了、好用多了。

其实 Ubuntu 真的很好用。但是所有人都在用 Windows，我实在不能理解。

\texttt{2025-10-31 \& Day -1}

最后一天了。不知道该复习什么，所以就来补游记了。

考成什么样就什么样了。我发觉我的 OI 水平真是越来越差了。

上周六考 CF *1600 题目（但是 OI 赛制 + CF hacks），全是做过的，但是思路全部是现想，一共 6 道有 2 道没做完，做出的 4 道又有 2 道被 hack 了。说实话题目真的简单，但是我的代码能力真的堪忧了。

我觉得我应该做一个好梦。

\texttt{2025-11-1 \& Day 1}

我似乎进入了梦境。

我恍恍惚惚地到了人大附，然后忘了发生了什么就已经坐在座位上了。

全考场的人都在用 Code::blocks，只有我一个人在用 VSCode。

上善若水。

打开题面，四道题都扫一眼，怎么前两题都这么简单，感觉好不真实。

30min 切掉前两题。第三、四题懒得想了，省一省 RP 别用完了。

于是打了第三题的 O(n^2) 部分分，但是我的代码在随机数据下跑得飞快，预期时间复杂度接近 O(n \log n)，但是大概也只能多拿十几分。

第四题一眼组合数、二眼 DP、三眼背包，但是不会写，打了部分分就跑路了。

预期得分：100 + 100 + [60, 90] + 64 = [324, 354]。

人杰地灵。

摆烂了，打成什么样就什么样吧。

T1 看起来就不简单。一眼想到一个贪心就是先选最大，再贪心地把多余的分到其他组。但是我伪证了贪心的证伪，所以我以为它是假的。

于是想到了 O(n^3) 的 DP，设 f_{i, j, k} 表示第一组选了 i 个、第二组选了 j 个、第三组选了 k 个的最大满意度，然后暴力转移。

再搞搞特殊性质，于是拿到了 70 分。

Upd：后来才知道贪心就是正解。但是好像很多人都和我一样没做出来。 :::align{right} ——亏麻了。 :::

再来开 T2。用最少的代价连通整个图，明显要求最小生成树。但是怎么处理乡镇呢，假如把开乡镇结点的代价加进它所连接的边，那多条边连接同一个乡镇又怎么处理呢？明显不可行。

注意到 k 很小，有 0, 5, 10 三个梯度，那么我们为什么不能暴力枚举改造的乡镇，再跑 Kruskal 呢？提前排好序，时间复杂度能达到 O(2^k m + m \log m)，能通过 k \le 5 的数据，大概能拿到 64 分。体会到了部分分的魅力。 :::align{right} ——出题人设计的每个部分分都是有用的。 :::

T3 暴力不会，跳过。T4 只打了 8 分的暴力。

Upd：后来才知道 T3 暴力很好打，而且能拿 20 分。 :::align{right} ——亏麻了。 :::

考试快结束了，连 T1 都没做出来，已经准备好被嘲讽了。感觉我的水平还是太差了，考成这样已经尽力了。不挂分就好。 :::align{right} ——明天要努力了。今天要原神了。 :::

预期得分：70 + 64 + 0 + 8 = 142。

结束了。但是没有碰到肖岱恩。回来吧我的肖岱恩。

白色的路灯下，人大附中校门静默，金黄的树叶在风中翻飞，像无数破碎的梦，飘散在夜色里。路灯的光晕里，叶片旋转、坠落，仿佛时间被拉长，又突然凝固。风掠过，树叶沙沙作响，却听不清它们在说什么。夜色渐深，路灯的光晕模糊了轮廓，只剩下金黄与白交织的碎片，在空气中游荡……

梦醒了。