【游记】CSP 2025 游记
Day -9（2025.10.22）
本来想学高斯消元构造线性基，但是发现高斯消元忘得差不多了。复习一遍发现判断无解和无穷解那部分忘记了（而且让我有点难以理解）。遂放弃。
于是就做了一道作业题：P4570 [BJWC2011] 元素。看完题解很快打完了，意料之外啊。
感觉啥也没干。
写了个 NOI 大纲内知识点清单。\
注意到 1991 字符。
Day -5（2025.10.26）
我们似乎也没有什么天大的矛盾，只是滞留在了某个黄昏，从此没能再参与对方的日日夜夜。
今晚复习了：
-
-
-
-
- 纯入机
-
-
-
-
-
-
-
-
-
-
- 不会 Prim
-
-
通过数足足有
好吧发现还有好多没复习，数据结构、图论、初等数论
复习的话就没什么好说的了，虽然有点无聊但是过题就是爽啊！！
（滚去补 whk 作业了）
实际上没补作业，嘻嘻。
Day -3（2025.10.28）
呃呃，依旧 ACC。
你说得对，但是我怎么还是做不出来 DP？？
做到 20:40 跑路了。
复习了：
-
-
- normal，差分。
- 其实主要是差分要复习一下。
-
-
- 区修区查，不简单 tag 下传顺序
Day -2（2025.10.29）
复习了：
-
-
- 这个题单
-
-
- normal，01 Trie
-
-
- 其实就是背了一下。
发现脑子还挺好用，没有忘掉很多。
本来还想复习的但是时间好像不太够了。\
浅浅数了一下，发现还有
就剩两个晚上了，怎么办怎么办？
Day -1（2025.10.30）
复习了：
-
-
- FHQ_Treap(normal)，其它没复习
傍晚和某人去了图书馆，于是一个小时有半小时看水浒传、十几分钟看了一下哈希、剩下的是损耗。（本来打算直接来机房的）
Day 0（2025.10.31）
复习了：
-
-
- erfen+hash
-
-
- 用双哈希？
-
-
- ShuPou
-
-
- 懒得看
NOI 级：
-
-
- normal
中午打了哈希没打完。
傍晚搞了一下，然后发现效率不同，有一些地方：
- 这是一个算是比较常见的：map 能少用就少用，如果两个能压成一个就别用两个：1 & 2
- 比如二分函数里面定义了形如
unordered_map<long long,bool>mp的东西，但是由于调用很多次，时间会差很多：or1 & 2
复习得差不多了，看看明天能不能切 S 组 T2 吧，加油。希望别考没复习的。
Day 1（2025.11.01）
J 组
开题发现前两道一眼秒啊，T3 有点像数据结构。\ 8:52 T1。
为啥那么晚是因为前面在打
template.cpp，然后还是不敢用以auto为函数参数的快读快写（尽管只有 Warning）
8:54 注意到本次评测机升级为 Intel Core Ultra 9 285K CPU @ 3.70 GHz（关闭睿频与能效核），内存 96 GB。
9:01 T2。\
9:17 T3。\
观察到
9:22 这个时候发现读错题了，区间不用全部选完！\ 后面没直接想到正解的状态就先看 T4 了，（9:39）然后打 T3 DP。
转移错了调了好一会儿，打个暴力 DP 都这么费劲。。。
10:22 打出来 xor6 突然发现要循环大概
设的状态是：
f_{i,j} 表示当前选到i ，上一次选的区间的最后一位是j 时，能选出的区间数量的最大值。（嗯刷表法）
十点三十多开始改成 BIT（树状数组）维护。\ 10:53 意识到只是单点修改，单点查询。\ 糖丸了。那我浪费这么久时间？？\ 11:07 检查完。\
开始尝试优化、设一维状态、甚至把原来二维状态硬是去掉一维（尽管这样显然很假）
11:2? xor6，跑了几分钟以后发现答案是对的。还好。
11:33 做 T4。\ 11:41 没问题了。\
11:42:50 很好的，我就开了这么点窗口，jz 的电脑就给我卡死了。（这里是在用 VSCode 打开四个 .cpp 文件检查）\
11:44 好了，还好是在题目都打完了以后，而且比赛要结束了，不然肯定影响心态。（伏笔）
11:52 开了 Linux 系统测。\
g++ program.cpp -O2 -std=c++14 -static -Wall -Wextra -Wshadow -o program，但为何输-Wl会问我... you mean -W?。
11:57 极限啊，最后不到 freopen 和 scanf 的 Warning（之前在 HydroOJ 也见过，但是不知道什么意思）\
中午
出考场，听闻阿克声一片。\
观察到教练笑得嘴角都压不住了。怎么都这么牛？\
吃饭的时候统计了一下同校同级
这顿饭怎么可能
中午去了香山书房（好像是人就能进）。\ 神秘人怎么还没来？怎么还没来？\ 怎么来了 @Rannio 和 @Resss？
旁边 @Lame_Joke 在 lol，专注的神情让我很想笑。\ 神秘人终于来了，化身免费劳动力。感谢神秘人的冰红茶。
没睡着，但是可以了。
S 组
说实话开题我就觉得很【】，感觉药丸。\
嗯显然贪心。\
14:45 想到一个做法，具体是啥代码回来才记得起来，貌似是用 set 的假做法。\
15:16 认为做法错误。\
15:30 想半天毫无头绪啊，决定从特殊性质看起：
- 只有一个不为
0 的满意度，显然直接排序选前\frac{n}{2} 个。 - 两个呢？
15:36 看 T2。
15:41 （纸上写到）：
我会。 按 top 选（当然不重），若同种类超过 n/2 个，则直接把另外一个选完当时没仔细想，以为是对的。\ 15:48 （这里忘了发生了什么，应该是发现上面是错的）\
某个时候脑子里突然闪过“反悔贪心”这个词，但是因为做得很少，只记得暑假好像有一道题是：优先队列取出实现反悔还是什么的（嗯对具体也忘了）。\ 不过有什么用呢？。。。
16:48 哈哈哈哈，@BirdenT 电脑卡了。\
赛后据他所说，刚打完 T4 开始 T3，然后卡了。\
这是一段对话：
“你代码保存了吗？”\ “保存了”\ “人才”（在一旁小声说道）
被听见了哈哈哈哈，xswl 这监考员。\
16:28 开个虚拟机给我内存整到
17:19 看 T2。\
发现就是 MST（最小生成树）的改版。\
其实注意到了 T2 的
合着这 CSP-S 正赛被我打成了平时的 NOIP 模拟赛了是吧？全在拼暴力了。。。\
18:19 Linux。\ 18:23 测了，但没仔细看。没 CE 就行。
考后见到 zyl 和 lzx 在聊天，这就是高手的聚会吗。两个第一啊。
Day 2（2025.11.02）
下午和晚上干的事：复原代码、看游记、写游记。
估了分。
看后面，有更新。
J 组
洛谷：100+100+60+40=300
那实际应该就是：
T3 赛时跑了
xor6那个大样例，几分钟以后答案是对的。
又一点惊吓：T2 WA 85pts 了，发现是存答案的没开够。\ 体现出来数据有点水了。
S 组
洛谷：25+16+25+8=74
一点惊吓：WA 4pts，发现没开
long long。。。
看了一眼洛谷的难度：\ J 组：橙橙黄绿\ S 组：绿蓝紫紫
噢？绿吗？那是不是可以是一个做不出来的理由
Day 3（2025.11.03）
21:16 交到云斗的时候发现：在判断是否是暴力那一档分以后，我发现我没有和赛时代码一样对其它测试点都运行 MST()（也就是直接输出 MST 的答案，不考虑城镇化）。遂改，交了一发代码：1。\
“怎么还是 16 分？运气没那么好啊。”\
“诶不对？怎么 #4 没 A？？”\
“怎么 A 了一个 #15？”\
于是把昨天代码一交：2，果然只有
J 组
洛谷：100+100+60+40=300
云斗：100+100+60+40=300
综合：
S 组
洛谷：25+16+25+8=74
云斗：25+40+60+8=133
综合：
22:09 发现 -J T4 降黄了。
洛谷上的难度：\ J 组：橙橙黄黄\ S 组：黄蓝紫紫
22:11 哦哦，怎么黄都没切？。。。
反思
J 组
（粗略看了题解写的）
T3
先想了暴力然后优化，最后拿了 DP 的
解决方法：
去年 CSP 结束一直说要练贪心和 DP 的：都做过一些，贪心后面觉得不知道做什么题有用就没继续了。至于 DP？每次刷题想选 DP 的，都会想着下次再做吧。后来选拔考试以后就没有自己刷题了。。。
从最简单的 DP 开始练一下吧，然后可能要做一些有辅助数组的 DP。感觉这种有辅助数组的没做过几道啊（不包括什么前缀和之类的）
T4
经典先排序，嗯做过那种题（貌似就在今年），但是没想起来...赛时依照某网友总结的往年经验试图往图论想，不过显然不是图论。想了一下 DP 发现状态不好设（不排序当然了。。。）
解决方法：其实和上面差不多了。
S 组
做法全是暴力以及部分特殊性质啊。\ （还是粗略看了题解写的）
T1
没想出来哈哈哈哈！想到反悔贪心了，想到先按每个人最大的那个满意度先加了，但是因为没有对反悔贪心什么印象，只记得一道题的做法哈哈哈哈哈哈！！\ 11.3 早上听 @zhaomumu1218 口述就是：后面把超过长度的那个部门里面，最大与次大的差最小的人换到次大满意度的部门去。\ 哇哇！恍然大悟了是吗？？
这个问题是一直有的，之前在犇犇里提到过不知道多少次。\ 大概就是：贪心，我可以独立做出蓝题（当然就只是贪心题）、甚至想到紫的，但是我也可以在 CodeForces Div.2 中做不出来前面的简单贪心。（这导致我越打 CF 激情越少，一直掉分很多场，各种原因一起）\ 总之，贪心对我来说是个神秘东西。加练过但是发现没什么用，我也不知道该怎么练、练什么题。该找教练问问了。
T2
哈哈哈哈哈哈！！！哈哈哈哈！！！！你猜猜我赛时在干什么？我没有读错题，我读到了
为读错题的同学感到同情。
T3
我是纯按题意模拟打暴力的，但是因为有 break，所以得分靠抽奖。\
同学提出我那个做法可以用哈希再优化一下。呃呃，但是和 @BirdenT 讨论发现做法好像更劣。
好像在能力之外了？那个什么 合法的替换一定也是这种形式。但是呢赛时压根没想啊。