联合省选2026游记

· · 生活·游记

省流：[64,100]+15+12+[40,100]+[12,20]+0=[143,247]

前情提要：https://www.luogu.com.cn/article/qmtma6wo

非常令人气愤的是cq的noip1=要208分，作者因为没打暴力导致差八分1=。

day 0

找教练要了周末作业可以迟交，针不戳。

day 1

带了一堆面包以及经典尖叫加士力架。

开题！

扫了一眼题，确定策略：尝试优先把T1ac了。

想了一个很符合直觉的树形dp，写写写，啊这样例怎么过不去。

可恶，哪里错了，想想想。

不对，这玩意要撤销带常数的树形背包，没救了。

重新想想想，诶对，这玩意可以处理前缀和后缀再跑合并。

对了对了，赶紧写写写，怎么大样例1.7秒啊，稍微卡一下，1.3秒，发现只有1.5h了，赶紧跑了。

开T2，什么抽象题，想了一小会无果打了个n2^m暴力跑了。

开T3，当时急了，先把前三个点的暴力打了，想了想发现性质B似乎可做，于是开始打，结果没来得及打完。

day1刚考完的时候看起来还是比较欢乐的，有100+15+12，结果出来一对才发现T1写的是n^3，一下子变成64+15+12，这个时候就哭泣了。

day2

还是通读体面，一看，这啥鬼，两交互，还有T3那个神经滚木比大小？？？

那么策略依旧不变，还是先考虑切T1。

一看，这个限制6e5带log不是随便做吗，反应了一下又发现要线性还不能有多余的次数。

想想想，考虑我们二分的过程，尝试把这个东西刻画到线段树上，发现并没有什么帮助。

再想想想，考虑我们二分的过程，尝试把这个东西刻画到笛卡尔树上，发现重要的点只有笛卡尔树最左链的点和最右链的点。

不对，这不就是前缀后缀最小值吗，这个时候可以2n做了，即查找[0,n-2],[0,n-3]……和[1,n-1],[2,n-1]……这些总共2n-2个的区间。

稍微考虑一下发现遇到0之后的所有区间都没有用了，可以简单的优化到n次询问。

好，但是发现要输出方案，不会构造，但是考虑到每个数都对应着一段区间，于是写了个匈牙利跑了。

开T2，发现是个假的交互题，思考暴力，发现似乎有点太难打了，考虑乱搞。

想了一下，发现n(n-1)/2\le p，决定每次随机一个举行仪式的方案，然后如果会亏就重新随机，由于p很大不会出现被次数卡的问题。

写写写，写完了，大样例开测，发现只有k=3和n,m\le8的部分成功概率高，但是k=3的部分如果要保证正确率就会跑得很慢。

考虑增加选中能赚的点集的概率，想了想，加了个数组存跟当前选了的点之间没有边的点，优先从这个数组里面选点，好好好，跑得很快，跑了。

开T3，什么goes东西，一堆滚木比大小？？？？？

看到只剩下不到10min，决定开摆。

结果后来他加了15min，我想想别的不好实现就写个菊花性质分讨吧，结果没写出来。

后话

555，要面临中考了，快救救孩子。