Before noip2022
NOIP2022 考前脑洞打开ψ(｀∇´)ψ
大概是一个自己找的期望和容斥的小题单（也许会写）
然后杨爷给的一堆交互（全部口胡用来换换脑子）
可能会有 ARC076（和 hfy 一起打）。
考前可能还要复习一些板子。数学，图论的为主，哦，还有二分。
CF518D. Ilya and Escalatorψ(｀∇´)ψ
简单的期望 dp，考虑设 \(dp(i)\) 表示第 \(i\) 秒在电梯上的人的期望。
但是注意到 \(n\) 对结果是有影响的，所以再加一个维度：\(dp(i, j)\) 表示考虑第 \(i\) 个人在队头，第 \(j\) 秒的时候，电梯上的期望人数。
之前我做期望 dp 的时候一直是直接用定义和条件展开式子，然后从上一个状态的定义式子里面直接附带上新的决策的影响，然后合并同类项推出式子。
感觉这种做法比较蠢，可能是因为期望定义，概率的一些知识点有点忘了（whk 的概率，期望啥的都是差不多一年前这个时候学的了）。
- 合事件 \(A\cup B\) 发生的概率是 \(P(A) + P(B)\)。
- 积事件 \(A\cap B\) 发生的概率是 \(P(A) \times P(B)\)。
然后期望的本质实际上是一种加权平均数，所以我们在转移的时候可以把期望当成随机变量的一种取值，可以用来“代表”所有的情况。
嗯，然后推出状态转移方程：\(dp(i, j) = p \times (dp(i - 1, j - 1) + 1) + (1 - p) \times dp(i, j - 1)\)。
没了。
ARC101C(E)ψ(｀∇´)ψ
感觉也是很简单的套路，就是正难则反。
我考虑算不合法的方案数，这个东西容斥一下，就强制某条边不合法，枚举条件构成的子集然后乘上容斥系数。
这个东西可以用树上背包优化，但是具体的我不是很会，可能就是注意到不合法一定会造成一个个连通块的出现，用这个做 dp 算贡献。
具体的我咕掉了，以后再改。
ARC076ψ(｀∇´)ψ
这个见 ARC VP 集合。
话说这个集合里现在唯二的两次都是赛前打的，草。
最后更新:
September 14, 2023