CSP2025游记

做了好几次噩梦了，呜呜吓哭了。

为什么我模拟赛的场均挂分 >50 ？？

人家都 CSP 了，你得让让人家。

孩子们我判了 $|t_1|\not=|t_2|$，但是主播疑似 T4 暴力的数组开小了，可能会挂 [0,12] pts。

但是真的会有人45min会完前三题结果五点的时候才开始开T4的吗？

当然这里没有详细描写笔者的心理历程是害怕挂分之后变成joker，所以打算出分之后再来补。

upd：T4真挂了……

题解：

考虑一种反悔贪心，首先加入最大值，然后考虑如果此时某一列的选取个数超过了一半则选择一个代价最小的将其替换为次大值。由于 n 是偶数所以替换之后不会有新的列选的个数超过一半。

当然这么写是有些麻烦了，肯定存在更优的做法。

复杂度 $O(Tn\log n)$。

经典结论，考虑初始有n+k个点，$[1,n]$ 连向 $[n+1,n+k]$ 的边权值都为正无穷，我们可以选择一个 $k$ 的子集使得这个子集内的点连向 $[1,n]$，并且边权为输入的边权，并额外花费 $c_i$ 的代价。求MST。

那么考虑枚举对于 $k$ 的子集 $S$，$S/(lowbit(S))$ 中没有选择的边，在多选上一些边之后也不可能作为新的MST上的边，所以在枚举子集的时候我们只需要考虑 $O(n)$ 条边作为可能的MST上的边，注意 sort 常数很大，用归并或者手写个指针也可以。

复杂度 $O(2^kn\log n+m\log m)$，没写不带 $\alpha$ 的并查集是因为我觉得多记录一个 sz 数组的常数会比较大，和直接路径压缩实际上差不多。

（这个似乎是之前写一道双指针题的时候我偷懒写莫队 $O(n\sqrt m\alpha(n))$ 的时候怎么都卡不过去，然后换成直接路压还快了一点来着。）

一个类似匹配的问题，让我们转化到匹配问题上去。

考虑将 $s_1$ 和 $s_2$，$t_1$ 和 $t_2$ 交替插入在一起，则我们惊奇地发现可以计算结尾在偶数位置的匹配个数则可以统计出答案。

注意这个可以不用特判 $s$ 相等的情况。

然后还有一点问题，简单转化之后发现，因为我们匹配上的串需要满足其中一个端点 $<l$ 一个端点 $>r$。（也就是必须要覆盖了两个 $t$ 中不相等的位置构成的区间）

这个也是简单的，直接容斥一下，计算一定左端点 $\ge l$，右端点 $\le r$，以及两个条件都满足的匹配数。

直接 ACAM 上扫四遍即可，按寻思 $O(n+q+\Sigma L)$ 的东西不太会被卡吧？

然后在linux测 -fsanitize=undefined 的时候发现 $|t|$ 可以不相等。

赛场上策略比较保守，想着把暴力拼满即可，然后状态设的是对前 $i$ 小的元素dp，所以完全没有出路/kk

赛后简单口胡了一下，转移还没胡完……

设 $f_{i,j,k}$ 表示考虑了前 $i$ 个位置，此时有 $j$ 个元素落选，前边有 $k$ 个位置的值选择延后计算。

转移的时候考虑分讨这个位置填入 $\le j$ 还是 $>j$ 的值。也就是套路这一位是否选上。

对于后者，我们考虑延后计算，在 $j'>j$ 的位置上（注意，如果这个位置上 s=1，则下一个 j 一定变大，否则需要特判），我们枚举之前选择延后计算的位置，有多少个位置选择填入 $j'$ 这个值。这样可以使得任意两个转移过程中选择的值域区间要么是不交要么是包含的。转移系数是简单的组合数。

由于在每个 $j$ 至多只会枚举 $cnt_j$ 个数，所以总转移复杂度还是 $O(n^3)$ 的。

赛后这个思路大概花了半个小时不到就想出来了，不过写出来调出来就不知道要多久了。

17：00：

那我觉得，这么久以来的忍辱负重，我也应该迎来属于我的胜利了。

19：00：

我是joker