2023.1.30 整理

$\mathcal{Let’s\ roll.}$

谨以此博文，纪念 L_fire。

没想到 2023 年一个月过去了才重新开始写（

之前断更的有点厉害啊。

考的还算说的过去吧。

T1 签到题，T2 概率期望，T3 是奇妙的数据结构，T4 是模拟接高精。

问题就是一些学过的东西复习不够及时，一些套路还不是很会。

想期望的能力还是太烂了，多学学吧。

码力倒提升了点，至少模拟能敲出来了。（

T1 不写了，有手就行。

Analysis

T2

这一堆颜色……考虑期望是具有可加性的，我们就分别考虑每个颜色的贡献。

考虑该颜色时，其余颜色都可以视为一种颜色，毕竟都要变成该颜色，因此只要不一样就是异教徒（

设当前颜色为白色，其余皆为黑色。

然后我们开始想状态：

阶段是什么？发现到了第 i 个球并不能很好的表示状态（因为不好算），那么我们就转而去设有 i 个白球的状态。

来一手疯狂的 push 柿子就得到了下边的方程：

$dp[i] = \dfrac{C^2_n}{i(n - i)} + \dfrac{1}{2} * dp[i - 1] + \dfrac{1}{2} * dp[i + 1]$

好像还是蛮对的，但是有破绽!

破绽就是，你有没有想过一个问题，$dp[0]$ 有意义吗？

一个白球都没有，岂不是正无穷次操作？

太妙了，然后你每个状态都成了正无穷，直接爆炸。

发觉这东西是个少一个限制的东西，我们必须要限制向能成功的方向去做。

$dp[i]$ 应该是有 i 个白球，在能全变成白球的条件下的期望步数。

我们先来一手概率，设 $g[i]$ 表示当前有 i 个白球全变成 n 个的概率。

易得：

$g[i] = \dfrac{1}{2}g[i - 1] + \dfrac{1}{2}g[i + 1]$。

初始化是：$g[0] = 0, g[n] = 1$。（wljss 这里打错了 TwT）

根据上边那个式子，移项，乘 2，然后发现这是个等差数列。

公差就可以弄出来，得出 $g[i] = \dfrac{i}{n}$。

根据期望的定义，我们可以用 $g[i]$ 来弄出新的 dp 的两个新的系数。

然后我们弄出：

$dp[i] = \dfrac{C^2_n}{i(n - i)} + \dfrac{(i - 1)}{2i} * dp[i - 1] + \dfrac{i + 1}{2i} * dp[i + 1]$

然后发现这个东西是可以高斯消元的，可以用 $\mathcal{O}(n^3)$ 的复杂度通过 80 pts 的数据。

但是我们发现一个问题，这个矩阵它并不满，而且几乎全在对角线附近。

然后我们就可以改的少亿点，这样就可以 $\mathcal{O}(n)$ 过了。

T3

我说这是个国家集训队的题你信吗？

我说这是个 CTSC 选拔的模拟赛的题你信吗？

不过赛时还是拿到了 64pts 的成绩，不是太高但也说得过去。（可能只是 wljss 的数据太善良了？）

赛场上我是看出了一些端倪的，就是存在一个等差数列，正序逆序都行，序列就可以了，满足这个序列长度至少为 3 即可。

然后我直接一手 DP（

正解当然不是 DP，毕竟我想了很长时间也想不出来这东西怎么优化（

考虑这是一个全排列的问题，所以先一手转换成桶来做。

当我们处理到 i 时，将 $t[a[i]]$ 标记为 1。

如果此时以 $a[i]$ 为中心，我们将左右边界尽可能地扩展，直到有一边顶到了边界，然后拿出这一段，这会是一个 01 串，1 表示这个数在 $a[i]$ 之前出现过，0 表示未出现过，如果发现这并不回文，也就是满足 $t[a[i] -j] \ne t[a[i] + j]$

那么是不是说明此时满足的题目的条件？

那我们该如何快速判断回文串呢？

我们用树状数组维护一个动态 Hash 就可以了。