标签：记录 -- times 模拟 端点 区间 CSP dp

CSP模拟赛记录

落下了好多慢慢补qwq

2023.10.16

A. 魔力子串

直接vector 扔 map里面 没什么好说的

警示后人: 能用map就不要哈希

B. 吃树

结论题

1. 当正好存在 \(\frac{n}{k}\) 个节点的子树大小为 \(k\) 的倍数时, \(k\) 作为块的大小是合法的

2. 对于每种合法的块的大小，有且仅有 \(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\) 个向左的方案数

然后枚举终点， 左右匹配即可

D. 数星星

小丑了 上次补这题是ACV的

这道题去年做过 我记得 x–r--z- 去年还补过 可惜没有什么用 --zc

将查询按照右端点排序，可以考虑把所有贡献算在当前节点的最后一次出现上

那么，当处理到当前右端点时，直接查询左端点即可

然后用一个set去维护每个区间的覆盖情况，用树状数组维护每个时刻的值，树剖做链上修改

标签：记录,--,times,模拟,端点,区间,CSP,dp
From： https://www.cnblogs.com/xiaruize/p/17768600.html