2025 CSP-S游记
Samxia12456 · · 生活·游记
突然意识到忘写游记了这里补一发
01.赛前2小时
中午和朋友们猜下午 S 组的题目难度，JHR 和 flf 不约而同地押了"绿—蓝—紫—紫"。
谁曾想，这个预感后来竟一语成谶。
不知是不是被 JHR 的情绪带动，考前我整个人都处在一种微妙的兴奋里。
如果非要形容，那大概是四分的紧张，六分的期待。
午睡只是浅浅眯了一会儿，眼看时间将至，便匆匆起身，背起包赶往考场。
一切仿佛在无声地宣告着——
CSP-S 2025已然启动！
02.赛中
在英才同学里，JHR,XZX和我在同一个考场
考前允许提前写代码 我将我所会的 快读快写，pbds平衡树 和 快速幂 模板 写了上去
然后就开始发题 本人做题的顺序是
以下内容均为本人场上的真实想法：
感觉就是个贪心？（其实研究一下题型分配就知道
CSP-S 的一题大概率就是贪心）考虑明显直接贪不行 但根据性质 只会有 至多一个人 不满足条件
优先队列维护
反悔贪心即可挺像
flareoj 比赛 CSP-S模拟赛13 T4 剪辑师 的弱化版
于是本人就去打了 显然的是 本人赛时想复杂了 返回贪心特判了
字符串题目？ 试试
Hash 暴力？时间复杂度
O(qL^2) 貌似只能过前2 个点且只有10pts欸疑似有点亏？ 但时间复杂度如何优化？ 是优化
q 的那一层还是L^2 的那一层呢？考虑优化
L^2 ，改成双指针干成O(L) 复杂度？显然假啊
O(L) 复杂度双指针没有错误性显然那
O(q) 能不能优化呢？一堆字符串的查询理论可以离线？ 那该怎么存储呢？
字典树啊！(其实和CSP 冲刺模拟赛 15-3 T3出思路过程相似)
没错 本人就这样神奇的场上推到了字典树
但之后的思想是一点未出了 这是场上时间已经过了
显然目前最大可得的分还是开始时秒出的难打的
看着像
最小生成树?观察特殊数据
k=0的前4 个点 直接最小生成树就行了 预期得分16pts(还好考前写了最小生成树板子:CSP 冲刺模拟赛 15-7 (板子大赛) T3)
那特性
A是不是可以类似的做呢？显然的想法是 点的开发既然不要钱 直接全部开发然后最小生成树就好了
能证明吗？
其实可以:因为特性
A既保证所有c_j=0 还保证存在1≤i≤n 满足a_{j,i}=0 那么直接连成一棵最小生成树显然不亏！
目前几分钟已经
48pts到手了 其他几个点的分还可以再获取些吗？仿照部份份的思路 考虑
k=5 可以直接二进制枚举所有情况 然后取价值的min 就好了时间复杂度
O(2^k\cdot m) 确实可过k=5 的点
于是本人就去打了 结果最后一组大样例神秘 Hack 了我的代码
吓得我赶紧加了个部分分分治保
此时已经过了
所以这里本人选择去完成
数据范围
n 这么小 一眼dp?先看看数据 有
n\leq 10 的点(8pts) 可以dfs完成再看特性 特性
A 看着像n!?先尝试实现 发现那个点的样例没过
看看数据 居然它的
c_i 可以为0 ? 那不奇怪了所以特性
A 应当也要用dp解决
于是本人就花了半个小时左右推式子 无果后立即玄学骗分:
其实你计算一下会发现 如果数据纯随机生成的话 应该得分率蛮高的 场上我也是如此想的
此时时间所剩不多 遗憾的是 本人
其实如果数据随机生成的话 这个期望分数也蛮高 但多测就有点悬了
至此
03.赛后估分
赛后用的绿蓝紫紫
我本以为这次我分已经估高了许多 结果碰见
具体如图:
(“不可以总司令”都有20pts的数据也是造的很神秘了)
我个人赛后最新估分相对综合我赛中的感受和
总之 不得不承认的是 我这次比赛其实槽点还是挺多的
至少而言 像
反思一下 你会发现这次
为了让每个题目反思的更为充分 本人打算每天在
可能简单的只有几句话 但或许都可以为下一次比赛的更高分做出贡献
“以史为鉴，可以知得失”，期望自己能够通过这次NOIP目标奋进！
最后的最后 我选择以