2024-09-24
开题顺序：ABDC
时间分配:A:20min，B:30min，C:1.5h，D:30min，其余时间打摆。
主观难度：绿蓝紫蓝
set
设 \(f_{i,j}\) 表示前 \(i\) 个数和为 \(j\) 的方案数，然后直接 01 背包，最后用快速幂把每种和的数量次方乘起来就行了。由于 \(f\) 最后要当指数，所以要 \(mod (kM-1)\)。
hire
设当前 \(i\) 位置上的人有 \(a_i\) 个，考虑到在合法时一定会有一些性质：
\[\forall l,r\in [1,n],l\le r, \sum_{i=l}^{r}a_i\le(r-l+1+d)\times k \]将其拆开：
\[\sum_{i=l}^{r}a_i\le r\times k-l\times k+k+d\times k \]\[\sum_{i=l}^{r} (a_i-k)\le k\times d \]然后直接用线段树维护每个位置的权值为 \(a_i-k\) 的序列的全局最大子段和就行。
block
这个题状态设计本质和 P6773 的状态设计一样，但赛时并没有看出来。
设 \(f_{i,j}\) 表示以 \(i\) 为根的子树中选择了的连通块中有限制的点的 \(dfn\) 最大值为 \(j\) (如果不存在有限制的点在连通块内 \(j\) 为 0)，转移找到前一个子树内 \(dfn\) 最大的点，然后与当前子树内的 \(dfn\) 最大的有限制点判断是否被限制到，没有就算上。
checkers
一开始看见是个数数题感觉是神仙题不太敢做，但看完题好像和 set 所用的大体思想差不多（？
首先考虑没有 ? 时怎么做。设字符串中有 \(x\) 个 0，有 \(y\) 个 11（比如 '001110' 就有 3 个 0 和 1 个 '11'，最后的那个 '1' 不算），那么方案数就是 \(\tbinom{x+y}{x}\)。那么就可以用 \(f_{i,j,k,0/1,0/1}\) 表示前 \(i\) 个字符有 \(j\) 个 0，\(k\) 个 11，当前这一位是 0/1，这一段 1 的数量有偶数/奇数个。那么就有转移：
- 当前这一位题目给出的字符不是
1
- 当前这一位题目给出的字符不是
0
这样时间复杂度是 \(\operatorname{O}(n^3)\)，带 7 倍常数，不过可以加一些减枝：\(j\le i,2\times k+j\le i\)，最后剪完好像是 \(\frac{1}{2}\) 倍常数的。
标签：11,le,sum,csp2024,times,dfn,当前,集训,赛前 From： https://www.cnblogs.com/caoshurui/p/18429497