CSP-S2025又寄

这篇是11月14号写的，回来懒得写咕咕到现在才打开typora（）我还以为截止了呢。

进考场前在等朋友，但有两位懒货等我都进去了才到，导致进考场前没有面基到，~~这为我下文的惨败埋下了伏笔~~。

开题，人杰地灵是什么鬼，第一眼看成人机了。

先想T1，首先马上写了按最大排序再按顺序取的贪心，然后假了，于是仔细思考。

然后又想到钦定某个俱乐部满员，又假了。

结合贪心1贪心2，还错。

急死我了，~~贪心太坏了~~。

这个时候开始认真思考不再猜结论，首先可以想到，这个题一定是贪心而不是dp。什么你问我原因？~~因为直觉~~

总之就是毫无怀疑地去想贪心，思考了一下反悔贪心，但被我马上舍弃掉了，因为我没怎么写过这个东西。

对着大样例瞪眼半天，已经过去了快1个小时。。。

突然灵机一动：显然每个人肯定不去价值最小的俱乐部，那么我们可以假定所有人都去了价值最大的，再把因为人数问题去了次大俱乐部看做损失，贪心就变成了让损失最小。

那么很自然的想法是，因为每个人都要选，所以我们应该尽量让损失最大的人先选，也就是按每个人的最大-次大进行排序。

然后就做完了，耗费1h，我怎么这么菜。

开T2，读错题面了。

一直以为乡村和城市是连在一起的，都是最小生成树的必须点，然后想了半天换根还有转移集合什么玩意的东西，耗时忘了，总之当我意识到乡村是独立点的时候把自己气笑了。

这警示我们要好好读题不要急！！！

首先对城市最小生成树，那些已经被删掉的边就不要了，显然没有任何用处。

一看时间剩2.5h，去做T3T4

T3：这不AC自动机吗？？但我不会写！于是准备敲个哈希暴力，考虑到23年单哈希可能会死掉，选择了双哈希，然后写成了史，脑子也给我写浑了，直接导致后续T2没调出来

T4：一看计数还是T4直接暴力了，O(n!)。

回到T2

首先特殊性质A的意思其实是，乡村可以跟原图那些边权为0的城市点合并，这样就变成了在原图上加边后最小生成树，先敲了这个特殊性质保底。

注意到k很小，可以2^k枚举，每次再kruskal，时间复杂度O(m\log m+2^kkn\log(kn))，是个64pts（？其实忘了多少）的做法，然后，我！没！调！完！

气死我了。

赛后被lzc大神鞭打（？）后发现只要在枚举状态前先排序边然后再双指针加边进行kruskal就可以做到O(m\log m+kn\log(kn)+2^kkn)。这个优化感觉是个人都能看出来，然而我没看出来，真服了。

复杂度忘了，差不多这个东西吧。赛后重敲代码30minAC。

回顾往年CSP生涯，常伴遗憾

最后喜提100+56+5+12=173pts

倒是混了个1=。。。。

恭喜YCH脑婆也获得了1=！

赛后见到了朋友，合照，开心。

总算终结了连着两年2=，也算是个新的开端吧。

机房全员进入NOIP（废话25分分数线），可喜可贺

NOIP2025RP++！