2023.02.15 模拟赛小结
目录更好的阅读体验戳此进入
啥正经人会在模拟赛用仨小时将普及难度的期望DP转换成枚举调和级数中选数然后写一个脑子正常的人都写不出来的奇怪2D0D啊。。。。。。
赛时思路
T1
初始位置为 $ 0 $，计数器为 $ 0 $，给定 $ n $。假设当前在 $ p $，若 $ p = n $ 则停止，反之随机生成一个 $ [p + 1, n] $ 的数到达该位置并使计数器 $ +1 $，求计数器期望数值。
正解算是一个普及难度的很裸的期望 DP，反向设状态令 $ dp(i) $ 表示从 $ n - i $ 到 $ n $ 的期望，则转移显然为 $ dp(i) = \dfrac{1}{i}\sum_{j = 0}^{i - 1}dp(j) + 1 $，前缀和优化一下就是 $ O(n) $ 的，可以获得 $ 80\texttt{pts} $，向后打表预处理一下就可以过 $ 90\texttt{pts} $，对于最后 $ n \le 10^{18} $，考虑推理过程中有些奇妙，尝试推式子：
\[\begin{aligned} dp(i) &= \dfrac{1}{i}\sum_{j = 0}^{i - 1}dp(j) + 1 \\ &= \dfrac{1}{i}(\sum_{j = 0}^{i - 2}dp(j) + dp(i - 1)) + 1 \\ &= \dfrac{1}{i}(\sum_{j = 0}^{i - 2}dp(j) + \dfrac{1}{i - 1}\sum_{j = 0}^{i - 2}dp(j) + 1) + 1 \\ &= \dfrac{1}{i}(\dfrac{i}{i - 1}\sum_{j = 0}^{i - 2}dp(j) + 1) + 1 \\ &= \dfrac{1}{i - 1}\sum_{j = 0}^{i - 2}dp(j) + \dfrac{1}{i} + 1 \\ &= dp(i - 1) + \dfrac{1}{i} \end{aligned} \]则 $ H_n = \sum_{i = 1}^n \dfrac{1}{i} $。
又有：
\[\sum_{i = 1}^n \dfrac{1}{i} = \ln n + \varepsilon(n) + \gamma \]其中 $ \varepsilon \approx \dfrac{1}{2n}, \lim\limits_{n \to +\infty} \varepsilon(n) = 0 $，且 $ \gamma $ 为欧拉-马歇罗尼常数，$ \gamma \approx 0.57721566\cdots $。
赛时不知道脑子怎么想的，肝了将近三个小时最终推导出从调和计数中枚举选择 $ k \in [0, n - 2] $ 个数求积并将积求和后分别乘上 $ n $ 到 $ 2 $ 这些数再乘上 $ \dfrac{1}{n} $ 然后枚举记录答案，这个东西能想到的就是一个 $ \texttt{2D0D} $ 的 DP，感觉不咋好优化，也就是因为这个后三道题基本都没咋看。。。一直在肝这个奇怪的东西。
T2
大概就是个树剖和维护 “换根” 树剖。。
T3
暴力分是建线性基然后直接枚举长度即可，正解有点阴间，暂时咕了。
T4
哥德巴赫猜想：任意大于 $ 2 $ 的偶数，都可以表示成两个素数之和。
对原题差分一下就行了，具体不想细说了，更深入地说，就是如果是 $ 2, 4 $ 这种可以拆成 $ 5 - 3 $ 的形式，而更大的偶数一定是两个奇数，或者说奇素数组成的，跑一下二分图匹配就行了。
有一说一这篇模拟赛小寄写的亿点水。。。
UPD
update-2023_02_15 初稿
标签：15,dfrac,2023.02,枚举,小结,sum,dp From： https://www.cnblogs.com/tsawke/p/17124388.html