CSP-S2025游记

· · 生活·游记

Day -？

SCP模拟赛VP，获得244pts，低于所有人qwq。

Day -4 ~ -1

感觉要打的板子太多于是开始严肃打板。

D-Day

今年出于一些原因并没有报-J，于是上午严肃复习数学部分，并祈祷千万不要没有签到。

13:46 抵达那个技术学院，感觉全世界都来这里考了，然后等待进考场。

不豪，考试之前肚子疼我服了，但问题不大。

14:15 左右在座位上坐好，并发现右边那个机子鼠标4了，还有对面的机子屏幕卡，祈祷自己的机子别出大问题。(伏笔)

14:30 并没有开题，因为密码还没有发布，大概14:35终于获得了密码。

开T1，第一眼三维dp，第二眼注意到肯定不可能有两个人数超过 n/2 的部门，坚信T1是签到，不会很难，于是想贪心，还好很快想出来了把差排个序直接做。火速写+调，等等，这个机子怎么不能分屏啊，需要我手动调到一个大小然后再挪过去，以及非常容易误触导致好不容易摆好的又乱了TAT。写写删删写写，过大样例，15:10。

开T2，完了这咋做，分层？不对。欸等下 k=10 ，那我可以 2^k 枚举，然后 O(m) 跑Kruskal，但肯定会T。为什么 n=10^4,m=10^6 不是一个量级？肯定有机密。想了一会儿之后肚子疼，紧急离场，然后15min左右缓过来了，15:45。平复了一下心情，手模了几个样例发现有效边应该在最小生成树上，于是原始边的量级减少至 10^4 。加上“乡村边”一共大概 10^5 条边，能过。

速写了一版 O(2^kkn\log kn)，不好，1s+。然后突然想到可以把排序放外面，于是复杂度降到 O(2^kkn) ，但还是擦边，于是火速开始卡常卡常卡常，优化优化优化，快读快读快读。最终自己造的满的样例卡到0.7s并提交，16:30。

但我仍非常不放心“有效边肯定在最小生成树上”的正确性，于是立刻开始对拍，但就拍了30组，16:45。

（前两题怎么做的这么慢）

开T3，串串题，完了怎么怕什么来什么，什么不会考什么，看看题，不会。算了先把暴力打了，获得25pts，17:15 左右。

不行，不能像去年一样T4连开都不开。于是决定先去看T4，然后再去想T3。完了怎么是排列阿，我就没会过这种排列的dp啊啊啊啊，这下只能打暴力了，于是写了个状压dp，我比较唐所以调了很久，获得20pts，火速提交，17:50。

等下好像可以求出一个最小区间，然后只要满足一些前后缀的限制就行，哈希一下应该能 O(nq) ，不好，感觉写不完了，于是先把暴力交了，大概18:05左右考场引起了轰动，因为回收系统好像炸了，但与我无关，至少目前我能交的都交了。啊啊啊我要疯了，真的要写不完了啊啊啊，还好18:13写完了，但直接段错误，调了一小会儿，未果，此时18:17。不行不行还是要留出时间检查一下，于是果断放弃，3min左右把暴力优化成 l \in [1,l'], r \in [r',len]并提交。diff了一下提交版本和理想版本，没问题；看了一遍文件，没问题；又测了一遍大样例，都过了。此时18:29:09。

期望得分：100+100+25+20=245pts。

罚坐时间仅有51秒，时间利用最充分的一集。这51秒光速思考了一下今年的配置，感觉感觉今年（上位）橙（下位）绿（上位）蓝（不知道什么东西）紫，但我不会T3，好难过，连50pts做法都写不完就是菜没边了。

完了我要垫底了，呜呜呜我的T3啊啊啊。往外走的时候根本不敢听别人的对话，生怕心态崩盘，回家也根本不敢复写或者上谷。

第二天还是没忍住上了谷，btw我也算放心T2的那条性质是真的了qwq，我还以为只有我一个人写的那种听上去像非正解做法的做法呢。晚上复写了一下T1～T3。WTF？不保证 |t_{j,1}|=|t_{j,2}| ？好好好，这下T3可能要保龄了，但民间数据仍通过了35pts，拜求ccf不要每个点都放一个长度不相等的阿。

所以大概是 100+100+[0,35]+20=[220,255]，求别挂分啊，本来就不多qwq。

后记：T3居然没卡串长不相等！？感谢出题人大大。官方分数：100+100+25+20=245pts。