csp-s2025邮寄

· · 生活·游记

2025，又是一个悲伤的11月，坐标JS，估计还是太蒟了。

去程

不得不说，来的时候，这次因为高速被封，原本11:30就能到的，延迟了1h才到，我坐在车的最后，给我整的，在车上昏迷了2h。

试机

没啥好说的，打了个线段树，lca,dij就结束了，但是考试文件的密码竟然发错了，这真太有CCF的风格了

T1

一开始以为是一道dp，想了15min,发现没法正确转移，有些难受，又去想了一下贪心，先觉得按每个岗位的大小分别排序，发现是完全错误的，于是我又仔细看了一下题面，发现n/2的条件非常特殊，仔细想了一下，发现可以让每个人都先去选他最喜欢的部门，然后看哪一个部门人数超过n/2的，就看如何能让其以最低代价转到其他部门就行，只需对转移的代价进行排序即可，复杂度O(T2nlog2n)可以通过，将代码写出来，过了大样例，时间已过去1h10min

T2

仔细观察了数据范围，发现k竟然小于等于10，我的思路便来了，先将原图跑一遍最小生成树，但是我竟然发现我的并查集写炸了，一直段错误，我一气之下没用递归写，用while写的，发现这样写就不会段错误了，不知道会不会增加常数，然后用2进制枚举k，分别计算每一种情况的最小生成树，注意不要在原图上跑，一定要在原来的最小生成树上跑，转换成本等跑过最小生成树后再加上就行了，在每种情况求出来后求最小的ans即可(包括一开始的最小生成树)，复杂度O(mlogm + 2^kknlog(nk))应该可以拿到80分，但是我不知道为什么写挂了，大样例死活过不去，只能拿到最低档的k=0的部分分了，我还是把3kb的丑陋代码交了上去，不知道能拿几分，时间已经过了3h25min，我得喷一下南航的电脑，中途死机了不说，死机之后还死卡死卡的，得换电脑了呀。

T3、T4

打了个T3的第一档的暴力分，没来及测小样例，希望能过吧。

闲话

收代码时，我的代码始终的交不过去，6点30分就结束的比赛，我一直等到7点10分才将代码交了上去，整个学校等我等了40min，南航真得换设备了……

总结

估分=100+[16,?]+[0,10]+0=[116,?]还是有进步的，不像去年连T1都没写出来，但还是得练啊，T2的思路大概没问题，却没写出来，足以证明我的代码能力得多加练习，希望明年可以加油吧！