日记

上午#

昨天晚上打了 codeforces 当然不会考试了

改 NOIp 的题。

P11362 [NOIP2024] 遗失的赋值 solution#

因为二元限制限制的是 $x_i$ 和 $x_{i + 1}$ ，所以它不可能越过那些一元限制限制的数，所以就以 $c_{i - 1}$ 和 $c_i$ 作为分界，划分 $114514$ 个区间。
设一个能塞下 $x$ 个二元限制的区间方案数是 $dp_x$，如果第 $i$ 个二元限制的第一个数与区间左端点的数一样，那么第二个数就有 $v$ 种取值，就有 $v \times dp_{x - 1}$ 种方案， $dp_{x - 1}$ 是因为少了一个二元限制。
而如果没有重合的话，那么除第一个以外的二元限制就有 $(v^2)^{x - 1}$ 种方案。
而第一个二元限制的第一个数因为不能和区间左端点相同，所以就只有 $v \times (v - 1)$ 种方案。
以上三种方案合起来就是 $dp_x = v \times (v - 1) \times (v^2)^x + v \times dp_{x - 1}$ 。这是一个递推式。但是，我们经过一番推导，成功的把他从递推式推成了通项公式：$dp_x = v^{2x} - v^x + v^{x - 1}$ ，然后就用快速幂就可以了。答案就是每个区间的答案乘起来。
注意：第一个区间，没有左端点的限制，所以方案数就是 $v^{2x}$ 。对于最后一个区间，因为没有右端点的限制，随便填一定填的出来，所以方案数也是 $v^{2x}$ 。

然后上午就只做了这一题。

下午#

写了点题，但是十分的颓废

P11361 [NOIP2024] 编辑字符串#

纯纯大模拟+贪心，我的做法没假。但是码力不行。

然后就把另一个小站弄好了，花了我 $\frac{1}{3}$ 个下午，也是十分的颓废。

CF2028E Alice’s Adventures in the Rabbit Hole#

对于每一个点 $u$ ，设 $dp_u$ 表示在 $u$ 点逃脱的概率。那么有弱智都看得出来的转移：$dp_u = \frac{1}{2}dp_f + \frac{1}{2}dp_v$ 。其中，$f$ 表示 $u$ 的父亲，$v$ 表示 $u$ 的子节点。但是，我们的dp方程要么是从 $f$ 推过来，要么是从 $v$ 推过来，怎么可能两边一起推呢？这个时候，我们就需要召唤劳张之力：待定系数法。设 $dp_u = k_u \times dp_f + b_u$。那么有：

解得：

我们就可以盯真定出来 $b_u$ 恒为 $0$ 。然后我们就可以在深搜的时候处理 $k_u$ 。然而AC代码并没有在深搜的时候处理
最后我们就得到了 $dp_u$ 的递推式。注意：初始化的时候 $dp_1 = 1$ 。