Csp-S 2025 邮寄

lrmlrm_ · 2025-11-04 08:22:52 · 生活·游记

考前偷溜到楼下看体艺节晚会，被班主任颗秒了/fn

筹集。

在一天上午抽了 deadshot,yorg,纸牌等。

中午吃饭得知上午 J 组异常简单，alan 和我声称下午必然不难，此时猜测难度是黄绿蓝紫（

其实是敷衍教练瞎写的总结，但是反正已经考成这样了，还是放上来吧。

一眼看出是贪心，尝试了几个做法过不去大样例。注意到最多只有 1 个部门可能超过 \frac{n}{2} 个人，则对于每个人，只会在满意度最大或第二大中选择一个。按照两者的差排序后贪心。

45min 左右过了大样例。

看完题目之后 10min 左右会了 O(2^k (m+kn) \log m) 左右的暴力。发现每次重新排序很浪费，用了 set，时间复杂度在 O(2^k nk \log m) 左右，但是大样例依然很慢。此时是 1h30min 左右。

一直在想怎么把 \log m 尝试消掉，发现不太可能，因为 set 的存在保底 \log m。

观察到每个村子能连哪些城市是固定的（只加入这一个村子，会和哪些城市连边），预处理出来，达到了一个玄学复杂度？

大样例跑了 1.5s ,极限数据 7s，只能安慰自己是本地机子比较慢。

在开完 t3 发现不会之后回来对拍了两组极限数据，发现全错了。但是大样例是对的。调了一会发现只剩 30min 了，只能跳了。

一眼想出了多串匹配，发现自己既不会 ac 自动机也不会字符串哈希。

打了个假做法，只能过小样例。只能放弃幻想打了朴素暴力。

但是并没有判 |t_1|\neq |t_2| :)

T4 employ

没时间了，只能打了阶乘暴力，甚至没有注意到 n=m 与 m=1。

估分：100+0+[0,10]+8=[108,118]

我去，这活什么啊，跳了。

怎么大家都 200+，要去不了 noip 了/ll