CSP-S 2025 游记

OldDriverTree · 2025-09-14 20:52:26 · 生活·游记

\text{Day}\ -\infty

我在 \text{SCP-S}\ 2025 中获得了 51\text{pts} 的好成绩，你也来试试吧！

我在核桃编程 10\text{w} 选手模拟考第二轮中获得了 185\text{pts} 的好成绩，你也来试试吧！

赛时 \text{T1} 拼尽全力只有 10\text{pts}，\text{T4} 猫树，正着贪心，倒着反悔贪心，求 \text{kth} 都想到了，但是没想到怎么合并两边，怎么会是呢

看了一遍大纲，发现自己不会 ，怎么会是呢

\text{Day}\ -42

打模拟赛，然后发现自己不知道 x^b\equiv a\pmod m\land b\perp\varphi(m)\Rightarrow x\equiv a^{\frac 1b}\pmod m，怎么会是呢

\text{Day}\ -41

路上打新出的 \text{maimai} 精选集，\text{Komplexe} 的 \text{IN} 拼尽全力只有 98.50\%

补了一下擂台游戏、交通规划、树的重心和树上的数，感觉树上的数 < 树的重心 < 擂台游戏 <<<< 交通规划，交通规划对着题解瞪了三天才大概能懂，这真不是黑？？

打梦熊的 \text{CSP-S} 模拟赛，拼尽全力无法战胜 \text{T2}，如此实力，如何 \text{OI}？？？

\text{Day}\ 0

听了两天 -記憶-

下午与 WilliamFranklin 一起坐车，大概 15:30 到达酒店，摆了一会，然后与 Sgt_Dante 以及其他几位不认识的老哥一起去吃饭

晚上去试机，打了有向图 \text{Tarjan} 和 \text{FHQ}，并测了一下机子性能，试完机在小广场旗杆那里面基了 \text{Ag} 爷 Southern_Dynasty，但是我把徽章放到酒店里了，怎么会是呢

回酒店做了下 雪に咲く花，然后 11:40 做完了开始睡觉

\text{Day}\ 1

早上 6:55 起了，摆到了 7:40 然后去吃饭，吃完饭做了点 贪心，发现完全不会贪心，遂睡觉

吃完饭去考场，路上看见一位老哥穿着 不登校，赛前学校里的放的几首歌中只听出来 泪的告白，怎么会是呢，压缩包密码是人杰地灵的拼音，有点神秘

开 \text{T1}，发现没啥思路，于是把四道题题面都看了一下，发现一道都不会，于是继续想 \text{T1}，发现每个人一定不会取最小值，于是一开始让他们都取最大值，如果大于 \dfrac n2 就选择一些调整为次大值，做完了，在 15:06 过掉了所有大样例

开 \text{T2}，发现 k=0 和 \text{A} 性质就是直接跑最小生成树，扩展到 k>0，想了一会才猜到时间复杂度可以是 O(2^kn) 乘点东西，于是先对于原图只保留最小生成树，然后枚举改造哪些乡镇，跑 \text{kruskal} 就做到了 O(m\log m+2^knk\log nk)，在 15:52 过掉了大样例。然后发现大样例只有 n=10^3，造了一组 n=10^4 的随机数据发现跑了 3.5\text{s}，想到了排序可以改为归并但是以为只是把 \log nk 改为了 k，不太会卡于是直接去开 \text{T3}，唐完了

开 \text{T3}，很快想到了对 s_1 和 s_2 分别建一棵 \text{ACAM}，对于询问枚举右端点，然后转为查询第一维在 \text{A} 树上一条路径，第二维在 \text{B} 树上一条路径的点的个数，不难转为二维数点，但这是提高组，于是先去开了 \text{T4}，发现只会 O(2^nn^2) 和 m=n 的 24\text{pts}，遂开写 \text{T3}

细想了一下需要 4n 次前缀加和 2L_2 单点查，于是叠了四层值域分块，在 \text{17:25} 写完了，18:00 过掉了所有大样例，样例 4 跑了 1.4\text{s}，不想卡常了，于是写了下 \text{T4}，18:10 过掉了两个样例，开摆

期望得分 100+[0,100]+[0,100]+24=[124,324]\text{pts}

赛后发现大家分数都比我高，问了一下其他人发现 \text{T3} 只需要 \text{Trie}，怎么会是呢

Southern_Dynasty 和 KingPowers 怎么都想到正解但是没调出来，恐怖

\text{Day}\ (1,+\infty)

第二天上午云斗出分了，获得了 100+80+100+24=304\text{pts}，好像是第一次在正式比赛中切掉紫题