CSP邮寄

Rem_CandleFire · 2025-11-03 20:09:35 · 生活·游记

也是没有一点包袱地来写邮寄了，说起来默认的输入法是真难用。

考前进行了半学半抽的体艺节，和许多同学合影非常愉悦。

快进到进入考场。慢悠悠地解压缩看题，准备打 T_1 保卫战。看题，一眼发现先对最大值排序选，写写写欸怎么样例过不了，手玩一下发现很像之前做过的一道三种硬币的反悔贪心，开了几个优先队列并回忆反悔贪心是什么模式。

进入地狱模式。

调了一会发现调不出来，只能过性质 B，尝试了一下合理地把两个的反悔贪心扩展到三个，发现不知道怎么反悔，尝试了各种标记调整总感觉是个环想不清楚。过了两个小时去看 T_2。

发现 T_2 似乎是个 Prim 状物，欸 Prim 不会写，先来个朴素 Kruskal 过掉 k=0，发现没有什么思路。考虑了半个小时后注意到 c_i 是升级第 i 个乡镇的费用，而不是升级编号为 c_i 的乡镇。奇怪玩样例是对的。先看性质 A，糊了个东西上去发现过不了？奇怪，看一眼 T_3,T_4 发现一个串串一个计数，不看了。

回来想 T_1，注意到 \frac{n}{2} 这个条件似乎不同于一般的限制，先默认取第一个然后反悔balabala，似乎可以但是总感觉很奇怪。

样例过不掉。此时已三个小时。

黑化，决定写暴力，注意到 n\le200 有许多分，写了一个 DP 看起来很可做，调了十几分钟发现这玩意有后效性（大雾）。那没办法了枚举跑路了。

瞪一眼 T_2 发现只有“原来的城市”需要被链接，哇去结合 k\le10 发现应该是 O(2^km\log m) 状物，写了一个 map 存边欸不对我边怎么炸了，这是为什么呢？

此时还有最后十分钟。注意到性质 A 激活城市不需要费用，直接加 nk 条边跑个最小生成树，啊哈性质 A 的样例过不掉无敌了。

那没什么好说的了，几十分跑路。

说起来对这成绩也并没有特别遗憾的感觉，虽然连 NOIp 线都达不到，无所谓了，大不了滚回去学文。

诶呀，动量怎么这么难。