CSP-S 2025 邮寄

· · 生活·游记

CSP-S 2025 邮寄

邮寄也可以有头图。

DAY -43-eps

复习初赛。SCP-S 2025 只拿了 <65 pts /oh

乱做初赛模拟/历年初赛。

在核桃编程的某套神秘题目中拿到了 14+9+3+9+15+15=70 pts。何意味。

怎么 2024、2023 年的成绩都比去年低😭

不管了。

DAY -43

上午乱做题。去做了 Typical 90-051。

然后 J 组有神秘的交互题？来自 AGC 神秘黑题？？？？

下午快忘记干了啥了。

欸怎么有 Meet in the Middle。这不是上午刚做过。但是似乎一点加成也没有

感觉挺简单。但是最后 20 min 检查时查出来 inf 个错误，至少 10pts。

直接把答案抄下来回机房开对。不到 10min 直接出答案，这就是 Luogu 速度！

91 pts。恭喜接广

DAY [-43+eps,-1]

开始停课。

国庆前的这个星期选择了选择性停课（VP UCup 不做，VP AT 也不做）。但是桦加沙小朋友有点打乱这个星期了。

不过幸好还能打 CF。+80 Rating。

然后就是全体停课了。每周一半时间都在神秘模拟赛。

不想详写了。

在这些模拟赛中，你将可以看到：

DAY 0

最后一场模拟赛 && 试机赛。怒挂 110pts。

T1

直接将 A 上的点与 B 上 x 坐标前继、后继点连线，再连直线上的相邻点，跑 MST 即可。

为什么没有看出性质向左右各连了 30 条边直接 MLE 了😡

T2

令到某个节点的路径上的 w 积为 preW，a 和为 preA。

线段树只维护叶子节点上的答案和，节点直接维护区间的 \sum preW 和 \sum preA 并算出 \sum ans。

但是下传标记的时候你不能更改 preW 和 preA 之后拿它们去重算 ans，只能根据其变化去给 ans 乘/加系数。

为什么赛时在线段树节点全为叶子时才 return 啊，这样会被菊花卡掉的😭

本地菊花为啥过了啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊

T3

Waiting to be updated.当然这里不会再更新了

T4

首先观察到答案一定是某条连接不同颜色的点的边的最小长度。这个性质可助你轻松拿下 40pts。

然后，有性质：仅保留原图的最小生成树答案不变。因为对于一条边权更大且两端异色的边 (u,v)，最小生成树上定有路径 (u,v) 且其上定有一个两端颜色不同的边比原边更优。

考虑原图的 Kruskal 重构树，对于一个虚点，其可能成为答案的条件为：

因此，对于一棵子树，任何一个点都能代表其颜色。

重构该图为一条链。初始时每个点为自身。Kruskal 合并时，将左子树的链尾和右子树链头连边。

修改时用两个优先队列维护哪些边要删去，哪些边要保留/新加。互相抵消掉之后剩下的边权最小值即为答案。

别慌。仔细检查。计算空间。虚拟机测时间、空间（/usr/bin/time -v ./A）。写拍子。多造数据多跑跑。

不要想当然。ZSKOI2024。数据删除。

此外这几天一直在疯狂乱做题。详见 做题纪录。

DAY 1

上午没有 J 组。7:40 才来机房。

自由看题。怒写 猫娘 和 数论分块入门。

中午直接变成大胃袋，这样下午就不会饿了。😋

学弟都说 CSP-J 难度 = ABC 前 4 题，人均 1h 内 AK，这样的吗？（Thinking）

宿舍有人提出总难度恒定理论。那我们不炸缸了？

fydj 跟我说评测机更新了。原话：25什么K。

以及几个人 yy 了一场比赛。我说 T4 是极小 MEX 区间+大数据结构。lnw 说 T3 是全局平衡二叉树DDP。锌钯钴说 T2 大模拟，T1 构造。怎么我的反而成最简单的一个了（雾）

睡大觉。但是化竞的有人乱跑导致宿管发出尖锐爆鸣 20min /oh

来到机房泡了杯浓茶。喝完瞬间 感 觉 好 极 了🦸

看到 CSP-J 自测。全国统一评测时采用的机器配置为：

WTF Ultra 9 285K？？？？？？96GB？？？？？据传 0.8s 1e9？？

原来多的报名费全部拿去买新评测机了，边评测边玩原神完全不是梦，CCF 的恩情根本还不完😭😭😭😭😭😭

进场。一键快进到看题。

先看 T1。嘶哈。不太会做啊。

但是旁边的老哥怎么开始键盘威慑了。不管了先打完输入再说😡😡😡

看了 15min。先把朴素贪心丢上去。毫无悬念地爆炸了。

但是不急。去看看 T2。先简单注意到 k \le 10。

一开始读成在 n 个城市里选 k 个了。差点联想到 Himitsu。

再读题。挖去这不是简单题吗。

写写写。测测大样例。颗秒！

较困难地注意到大样例并没有卡满。随手造了个极限数据，本地 CPU R7-5700G，Windows 下只跑了 0.6s。这不稳了？

此时是 14:56。

再回去看 T1。草稿纸上乱写了几个思路：DP、反悔贪心、图论建模（不是为啥有这个）。

这个形式不是很能 DP。遂去想贪心。

考虑先除去 cnt_{i \in \{1,2,3\}} \le \frac{n}{2} 咋做。此时我们可以直接排序解决。

然后就有点像 exchange argument 了。考虑一个 (id,from) 转移到 (id,to) 的增加的代价（可能为负）。其中 id 为学生编号，from,to \in \{1,2,3\}。将这个东西作为一个转移，按代价从大到小排。直接做就行了。

大约 15:20。拍一下。

欸我草怎么挂了。调试一下。就错了多测中的一部分。挑出来也是错的，不是多测没清空......

哦想起来 n 为偶数了。自己 吓 自己。改 maker.cpp。

15:40 拍了 3000+ 组。

然后开始看 T3、T4。

感觉这个 T3 不是很可做，T4......我不会计数啊！

不过我们有前两题还是没啥大问题的。

怎么左边的老哥一直在跟我举行别样的键盘吵闹大战，拼尽全力无法战胜。

把 T4 的状压写了。写了 20min，F5 了至少 5 次。还是不够仔细。

然后想其特殊性质。但是 AB 都不会啊啊啊。输出 0 跑路。

此时忘记啥时候。感觉身体是夹紧的好难受。奖励自己去了趟厕所。

回来 T1 已经拍了 8000+ 组了（中间中断了一次），懒得继续了。给代码最后加了个 //freopen("Club.in","r",stdout);。

来到 T3。

先胡个暴力。然后给暴力加了个不可以总司令状物。

单次查询不会一点。弃掉 A 性质。

看 B 性质着实听特别。本质就是 b 的左右移动。先按变化量把 s 存起来。

但是，我一开始只存了 s_{i,1} 的前缀 a 个数，并且只按这个判断是否合法，显然过不了大样例2。

改成前缀和后缀 a 个数，这时就是一个二维偏序。但是此时只剩 30min，不是很能打。/oh

只能暴力遍历了。相信少爷机。相信水数据。

最后检查了 \infty 遍自己的代码。

估分 100+100+(25+eps)+20=(245+eps)。

18:27。全体起立！

P_HOK 大帝说自己 T3 正解没调完。考场内周围一圈都问了一下，感觉 200+ 还行了。

优化2 说自己不会 T1，爆炸了。？？？

问了一圈好像 300+ 不是很多。今年盲估绿绿紫紫。

晚上把 T2 默出来并 AC。睡觉。

DAY 2

把 T1 默了。也没问题。T3 T4 不想写不写了。

DAY 3

完成这篇邮寄。

UPD：Luogu 加了数据把我的 T2 卡成了 88pts，生死未卜。

DAY 5

使用申诉方式找到了 100+80+5+24=209。无言。

为什么 puts('0') 有 40。为什么一车暴力拿高分。为什么 |t_1|=|t_2|（笔者在代码里先判了这个再跑的暴力）。CCF yo mo di .