CSP2022
CSP2022考试总结
T1
先想到动态规划，但是想了下不好处理不相同的要求，发现只有 \(4\) 个点，考虑利用这个性质。
枚举中间的两个点，然后判断是否合法，然后对于每个点预处理到 \(1\) 可能的中间点，取值最大的 \(3\) 个，然后就可以直接合并两个点的信息得到一条路径。
T2
容易发现只会在 \(A,B\) 每个区间中的四个数中选，即负最大最小，正最大最小。
一共 \(16\) 种方案，直接拿个数据结构维护信息，暴力合并计算答案即可。
T3
考场暴力
不难发现充要条件是每个点有且仅有一条出边，这个条件相当严。
考虑只在边数为 \(n\)
时进行检查，其余情况显然是 NO，边数为 \(n\) 时，对所有被修改过的端点下放操作，此时
\(2,4\)
操作可能会叠加，只处理最后一次即可。
这样的暴力很难卡，实际上也可以通过。
正解1
充要条件是若干个类似的条件的叠加，考虑能不能一起检查。
参考这道题的思路，可以随机一个集合检查这个在集合里的所有点的边数和是否等于集合大小。
考虑不合法的 Case 通过判定的概率，显然不会超过 \(\frac{1}{2}\)，证明可以考虑一个不合法的元素所有能够通过判定的集合，如果包含它，那么删去它后就不合法，如果不包含它，那么对应加上它后就不合法，构造出等量的不合法集合，因此通过判定的概率低于
\(\frac{1}{2}\)，所以做 \(2\log_2(q)\)
次就能保证正确，如果还错了，快用你生成的第一个随机数去买彩票！
正解2
问题的本质是维护集合，你需要维护 \(n\) 个可重集，支持加入删除，填满和清空，问
\(n\)
个可重集的并是否等于某个集合，可以考虑 xor_hash。
随机点权的情况下，一个可重集的权值也是随机的，所以正确率为 \(1-\frac{1}{值域大小}\)，注意仍然需要特判边数是否为
\(n\)，因为可以构造不同大小的对于
xor_hash 来说权值相同的可重集——某一个元素出现 \(3\) 次，其余元素次数相同。
只有错误出现在不同元素之间互补构造时，xor_hash
的正确性才有保证
T4
考场暴力
可以把链提出来动态规划，期望 \(68\)，场上第一次写没考虑往一个点旁边走可以更优，只能过 \(k\le 2\)。
修了这个锅之后由于第一次写的时候限制了步数，但是走旁边会消耗步数，导致最开始没有办法走旁边，然后娶不到最优解。
正解
把暴力的动态规划改成倍增版即可。
有点难写，暂时没写。