csp2024赛前集训

标签：11 le sum csp2024 times dfn 当前 集训 赛前

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. 当前这一位题目给出的字符不是 1

\[f_{i,j,k,0,0}=f_{i-1,j-1,k,0,0}+f_{i-1,j-1,k,1,0}+f_{i-1,j-1,k,1,1} \]

2. 当前这一位题目给出的字符不是 0

\[f_{i,j,k,1,0}=f_{i-1,j,k-1,1,1} \]

\[f_{i,j,k,1,1}=f_{i-1,j,k,0,0}+f_{i-1,j,k,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