CSP模拟赛记录
落下了好多慢慢补qwq
2023.10.16
A. 魔力子串
直接vector 扔 map里面 没什么好说的
警示后人: 能用map就不要哈希
B. 吃树
结论题
-
当正好存在 \(\frac{n}{k}\) 个节点的子树大小为 \(k\) 的倍数时, \(k\) 作为块的大小是合法的
-
对于每种合法的块的大小，有且仅有 \(1\) 种构造方案
C. 弹弹床
想不到状态的可爱 \(dp\) 题捏~~~
对于 \([1,i]\) 这个区间, 必然被从右侧进入再出来一定次数， 所以令 \(dp_{i,j}\) 表示区间 \([1,i]\) 在若干步以后, 剩下 \(j\) 个向右的没有确定终点
\[dp_{i,j}=\begin{cases}
dp_{i-1,j} \times j + dp_{i-1,j-1}, S_i=R\\
dp_{i-1,j}\times j +dp_{i-1,j+1} \times (j+1) \times j, S_i=L
\end{cases}
\]
可以获得60分的好成绩
考虑怎么处理中间的数值， 发现上述dp可以反过来再做一次, 算出区间 \([i,n]\) , 剩下 \(j\) 个向左的方案数
然后枚举终点， 左右匹配即可