5.18省选模拟

5.18 省选模拟

官方题解：https://www.docin.com/p-2212213554.html

总分数\(40+80+80\)，A没往AC自动机那边想，C数组开小了

A

给出m个串，求这些串至少出现一次的长度为n的串的个数

构建AC自动机，答案为在上面跑的方案数

矩阵优化转移就行了，最后加个容斥。

B

• 40 n^2dp


• 80 CDQ分治/splay维护动态凸包

一个数只会在一段区间被统计到，而且这个区间是在它之前，直接离线到线段树的log个区间上然后每个区间搞凸包求答案。注意到要在对一些点求凸包之前先把这些点的答案求出来，中序遍历即可。

C

先点分治，考虑计算连通块中经过每个点的答案。

按照一般套路，我们把这个点往下的路径搜出来，记录一下每条路径上权值的最小值、最大值和权值和。然后考虑把两条路径拼起来，显然对于一条最小值为 \(mi\) 的路径能匹配的路径的最大值应该在 \([0,mi+m]\)中，那么双指针就好了

然而最大值不能像普通点分治一样容斥，考虑再在每条路径上记录对应子树的编号，改用线段树查询最大值区间，然后同一子树内的不能匹配，那么再套一层bit记录前缀max和后缀max即可。注意总点数只有\(O(n)\)

总复杂度是\(log^2\) ，常数不大。

黄队说LCT可以做，不会(感觉不用)...