P1365 这道题在洛谷的难度标签不高但每次点开题解区总能看到有人挂在同一个地方?的期望转移写错了。题目背景是 osu!玩法说到底就是统计连续o段的长度平方和可一旦出现?事情就从字符串模拟变成了期望 DP。这篇文章我把完整的推导过程、状态设计思路和常见错误一次性讲清楚适合刚学期望 DP 的同学也适合想搞明白“为什么这样转移”的老手。1. 从题目描述说起连续段平方得分为什么比看起来麻烦1.1 一个简单的得分计算例子先明确题目在算什么。你拿到一个长度为 n 的字符串里面只有三种字符o、x、?。所有连续的o会组成一段每段的长度平方计入总分然后全部相加。比如字符串oooxoo有两个连续o段第一段长度 3第二段长度 2得分就是 3² 2² 13。如果字符串里只有o和x这题就是个纯模拟扫一遍统计连续段长度就能过。难点全在?上每个?会以 1/2 的概率变成o以 1/2 的概率变成x。题目要求的不是某个具体字符串的得分而是所有可能展开结果的期望得分。如果?的数量是 m那么一共有 2^m 种展开方式每种等概率。别说 n 能到 10^6就算 m302^30 也已经超过十亿暴力枚举必死无疑。这就是题目第一个需要转化的点不能枚举必须直接用期望递推。1.2 “? ” 带来的组合爆炸暴力思路走不通之后很多人会想到另一个方向能不能计算每个位置的贡献o段得分的本质是长度平方不是简单的“每个o贡献 1 分”。如果只有一个连续段长度 l 的贡献是 l²。把 l² 拆开看可以理解成对每个位置 i贡献是 2i-1也就是“当前这个o作为段内第几个位置决定了它带来的增量”。但这样做的问题是一个位置到底是段内第几个取决于前面的字符而前面的字符在?存在时是不确定的。所以这题并不能简单地按位置独立贡献必须记录状态。而期望 DP 的价值就在这里它允许我们用一个标量描述“当前位置结尾的连续o段期望长度”从而把不确定的未来变成确定的递推。2. 期望DP的状态设计只需要两个标量背后是一个关键等式2.1 状态定义与转移依赖期望 DP 的状态设计核心是找清楚当前决策只依赖什么信息观察得分规则。假设已经处理完前 i 个字符正在考虑第 i1 个字符。如果第 i1 个字符是o它会让“以 i 结尾的连续o段”长度从 l 变成 l1这个段对总得分的贡献从 l² 变成 (l1)²总得分因此增加 (l1)² - l² 2l1。如果第 i1 个字符是x那它本身就是断点新增字符不会产生任何新得分原来的段也保持不变所以总得分增加 0。于是我们发现处理下一个字符时唯一需要知道的信息就是“当前以最后一个位置结尾的连续o段有多长”。这个长度 l 在某个具体字符串里是个确定整数但在期望问题里它是随机变量所以我们只需要维护它的期望值。定义f[i]前 i 个字符的期望得分。g[i]前 i 个字符中以第 i 个字符结尾的连续o段的期望长度。本质上这是两个标量的递推。f 负责答案g 负责为下一次转移提供“当前连续段长度”的期望信息。2.2 增量公式(l1)^2 - l^2 2l 1 为什么“恰好能用”这个公式是整个算法的基石。展开平方差(l1)² - l² l² 2l 1 - l² 2l 1它是一个关于 l 的线性表达式。就是因为线性才允许我们只维护 E[l]而不需要维护 E[l²]。在概率论里期望只满足线性性E[aX b] aE[X] b。E[l²] 这种东西并不等于 (E[l])²一旦维护“期望长度平方”就会出问题。但这里每次添加o的得分增量是 2l1是 l 的一次函数所以E[增量] E[2l1] 2E[l] 1这就是为什么状态里只需要 g E[l]不需要额外的二阶量。很多初学者在这里会绕进去觉得“得分和长度平方有关那肯定要维护期望长度平方吧”。实际上增量是线性的绕开了二次项。如果哪天题目把得分规则改成 l³增量是 (l1)³ - l³ 3l² 3l 1这时就真的需要额外维护 E[l²] 了而且维护 E[l²] 的递推还要用到 E[l]。这个变式会在文章后面细说。3. 三种字符的转移推导从 o、x 到 ? 的加权平均3.1 字符 o连续加分现在具体推导每一个字符的转移设当前处理到第 i 位上一状态用 f_old、g_old 表示更新后是 f_new、g_new。字符为o时新的连续段长度比原来多 1所以 g_new g_old 1。总得分的增量是 2 * g_old 1所以 f_new f_old 2 * g_old 1。注意这里 f 更新用的是旧 g。因为增量取决于“加这个 o 之前”的连续段长度。如果先更新 g 再用新 g 算增量结果会偏大。从另一个角度验证假设之前连续段长度是 l总得分里这个段贡献了 l²现在这个位置是 o段变成 l1贡献变成 (l1)²新增正是 2l1。3.2 字符 x断连清零字符为x时连续段断掉当前结尾没有o所以 g_new 0。新字符不产生任何得分所以 f_new f_old。这段简洁到很多人会忽略但它同样重要。很多错误代码在遇到x时只把 g 清零却忘了 f 保持不变是合理的——因为 x 不会破坏已经形成的段只是不增加新贡献。3.3 字符 ?两个分支各 1/2 的期望合并字符为?时它有一半概率变成o一半概率变成x。期望 DP 的处理方式就是把两个分支的结果做加权平均。先看 g 的更新变成o的概率是 1/2此时 g_new g_old 1。变成x的概率是 1/2此时 g_new 0。所以g_new (g_old 1) / 2 0 / 2 (g_old 1) / 2再看 f 的更新变成o时得分增量是 2 * g_old 1。变成x时得分增量是 0。所以f_new f_old (2 * g_old 1) / 2这里很容易写错的一个顺序问题是f 的增量必须基于旧 g_old也就是当前字符变成o之前连续段长度的期望。有人会因为手滑先更新了 g再拿新 g 去算 f 增量结果每次?都会多算一点最终答案偏大。为了验证这个递推拿个小例子手动展开。假设字符串是o?x只有一种?展开成两种等概率结果oox连续o段长度 2得分 4。oxx连续o段长度 1得分 1。期望得分是 (4 1) / 2 2.5。用递推跑一遍初始 f 0g 0。字符of 0 2×0 1 1g 0 1 1。字符?f 1 (2×1 1) / 2 2.5g (1 1) / 2 1。字符xf 2.5g 0。最后输出 2.5000和手动展开完全一致。4. 最容易踩的坑期望长度不是某段真实的长度4.1 错误写法的现场这个题最迷惑人的地方在于g 是一个实数而任何一个具体展开字符串里的连续段长度都是整数。把两者混在一起就会写出各种看起来很合理、实际上错的代码。比较常见的错误有两种。第一种把期望长度当真实长度去算平方// 错误示例 else { // ? g (g 1) / 2.0; f g * g; // 错E[g^2] ! (E[g])^2 }这样写的问题很明显。g 是“期望长度”不代表任何真实路径上的长度。真实情况下这个位置的连续段可能是一个整数长度 k概率是 pk² 的期望是 Σ p·k²而不是 (Σ p·k)²。直接 g*g 相当于把期望和平方交换了顺序答案自然不对。第二种用 g_new² - g_old² 来算 f 增量// 错误示例 else { // ? f ((g 1) * (g 1) - g * g) / 2.0; g (g 1) / 2.0; }这个例子有意思的地方在于(g1)*(g1) - g*g展开之后就是2g 1所以如果 g 没有被提前更新这个式子碰巧和正确式子一样。但如果把 g 先更新了再代入这个式子就会变成用新 g 算增量答案偏大。真正要避免的是忘了“期望的线性性只能用于线性表达式”这一条。得分增量2l 1是线性的所以可以用 E[l] 算但如果你试图构造任何含有 l² 的非线性表达式比如期望新增平方贡献那就必须额外维护二阶矩否则就是错的。4.2 为什么线性增量让这个状态成立往深一层想为什么只维护一个“期望长度”就能把整个 DP 跑通关键在于每一轮转移里f 的变化量都是旧状态连续段长度 l 的一次函数。我们把随机变量 l 替换成它的期望 E[l]代入增量公式结果不变。这是因为E[al b] aE[l] b?的转移本质上是在两个分支之间做加权平均这个操作也是线性的。所以整个 DP 过程中我们从来没有对非线性函数取期望所有地方都只需要一阶矩 E[l]。这其实也解释了为什么这题叫 Easy。如果把得分规则改成连续段长度三次方增量是(l1)^3 - l^3 3l^2 3l 1里面出现了 l²那就必须同时维护 E[l²] 和 E[l]状态从一个标量变成两个标量代码复杂度立刻上一个台阶。这就是 P1654 这类题和它的区别。4.3 推广到 l^3 时需要加一个状态顺着上面说如果得分是 l³怎么设计状态设 e1 E[l]e2 E[l²]。对于字符o新的 e1 e1 1。e2 E[(l1)²] E[l² 2l 1] e2 2*e1 1。得分增量 E[(l1)³ - l³] E[3l² 3l 1] 3e2 3e1 1。对于字符xe1 0e2 0得分增量 0。对于?两个分支各 1/2所以每个量的更新都是“o 分支结果 x 分支结果”除以 2。这里就可以看出规律平方得分需要维护 E[l] 和 E[l²]因为增量里有 l²增量公式里的最高次数决定了你要维护几阶矩。P1365 的增量最高是 l¹所以只维护 E[l] 就够。这个规律非常有价值。以后再见到“连续段长度 k 次方得分”的问题不必慌先写出增量多项式数一下最高次数就知道需要维护哪些矩了。5. 参考实现C 与 Python 的滚动数组版本5.1 C 实现与读入细节状态只依赖上一轮所以不需要开数组两个 double 滚动更新即可。#include bits/stdc.h using namespace std; int main() { int n; string s; cin n s; double f 0.0, g 0.0; for (char ch : s) { if (ch o) { f 2.0 * g 1.0; g 1.0; } else if (ch x) { g 0.0; } else { // ? f (2.0 * g 1.0) / 2.0; g (g 1.0) / 2.0; } } printf(%.4f\n, f); return 0; }读入方面n 最大 10^6普通cin n s在关闭同步之后问题不大但保险起见用scanf(%d%s, n, str)更快。下面是另一个版本#include cstdio const int MAXN 1000005; char s[MAXN]; int main() { int n; scanf(%d%s, n, s); double f 0, g 0; for (int i 0; i n; i) { if (s[i] o) { f 2 * g 1; g 1; } else if (s[i] x) { g 0; } else { f (2 * g 1) / 2; g (g 1) / 2; } } printf(%.4f\n, f); return 0; }注意f 2 * g 1这一行g是 double所以整行会自动转成浮点运算没有问题。5.2 Python 实现与输入输出Python 版同样很短注意读入字符串后去掉换行符。import sys def main(): data sys.stdin.read().split() n int(data[0]) s data[1] f 0.0 g 0.0 for ch in s: if ch o: f 2.0 * g 1.0 g 1.0 elif ch x: g 0.0 else: f (2.0 * g 1.0) / 2.0 g (g 1.0) / 2.0 print(f{f:.4f}) if __name__ __main__: main()Python 在 n10^6 的规模下单层循环跑完是没问题的。洛谷上 Python 过这题通常不卡但如果评测环境比较严格可以改用 PyPy读入用sys.stdin.buffer.read()更快。5.3 精度与规模分析有人会担心 double 的精度。我们来估算一下最坏情况。n 10^6如果所有字符都是o答案就是 n² 10^12。double 的 53 位尾数可以精确表示到 2^53 以内的所有整数2^53 大约是 9×10^15远大于 10^12。更关键的是全o情况下 f 和 g 每一步都是整数累加过程完全精确。如果字符串里有?g 会变成小数但只要有大量?连续段长度就会被打散答案不会接近 10^12 的规模。反过来如果字符串大部分是o只有一两个?那大部分中间结果仍是整数误差也很小。所以 double 在这题是安全的不需要 long double。输出保留 4 位小数直接printf(%.4f)即可。如果遇到极端数据仍然担心可以把 f 和 g 声明成long double输出用cout的setprecision(4)不过实测 double 版本已经能 AC。6. 从 P1365 延伸一道题带起的期望DP练习清单6.1 概率从 1/2 变成任意 pP1365 的?是等概率所以转移里直接除以 2。如果改成“每个位置有 p 的概率是 o1-p 的概率是 x”转移公式只需要把 1/2 全部替换成 pg_new p * (g_old 1) (1-p) * 0 p * (g_old 1)f_new f_old p * (2 * g_old 1)这种形式在 P1654 OSU! 里会出现只是那里的得分还是三次方状态数量不同。掌握了 P1365 的推导方法改概率也就是动几个系数的事。6.2 平方变三次方状态维度的变化规律前面推导过三次方的增量公式是3l² 3l 1需要维护 e1 E[l] 和 e2 E[l²]。很多人问为什么不能只维护 e2因为 e2 的更新公式是e2 e2 2 * e1 1这里出现了 e1。也就是说即使你只关心二阶矩的递推它也会依赖一阶矩。所以状态数量是由“增量多项式的最高次数 低次依赖关系”共同决定的并不是说最高次数是 2 就只需要维护 E[l²]。这类“连续段长度 k 次方得分”的期望 DP思路高度统一写出增量多项式 (l1)^k - l^k。展开成 l 的幂次和。确定需要维护哪些阶矩保证每一步递推都能闭环。对每个字符写分支转移遇到不确定字符就做加权平均。6.3 该往哪些题迁移做完 P1365建议按顺序刷这几道同源题感受同一套模板在不同得分规则下的变化P1654 OSU!得分是连续段长度三次方需要维护一阶矩和二阶矩。P3802 小魔女帕琪虽然背景不同但核心也是期望的线性叠加。Codeforces 上不少 EDP 题比如 235B Lets Play Osu!几乎就是把 P1365 换成 n 个独立概率 p_i 的版本。先刷 P1365再刷 P1654就能直观体会到“一个状态够不够用”这个问题是怎么随着得分规则变化而变化的。我自己做这类题的习惯是拿到题第一件事不写代码先在纸上把每个字符的转移公式列一遍重点检查 f 的增量用的是旧 g 还是新 g。这个习惯帮我避开了很多次?顺序写反导致的 WA。P1365 作为期望 DP 的入门题公式简单、状态少正是训练这套流程的好材料。
P1365 这道题在洛谷的难度标签不高但每次点开题解区总能看到有人挂在同一个地方?的期望转移写错了。题目背景是 osu!玩法说到底就是统计连续o段的长度平方和可一旦出现?事情就从字符串模拟变成了期望 DP。这篇文章我把完整的推导过程、状态设计思路和常见错误一次性讲清楚适合刚学期望 DP 的同学也适合想搞明白“为什么这样转移”的老手。1. 从题目描述说起连续段平方得分为什么比看起来麻烦1.1 一个简单的得分计算例子先明确题目在算什么。你拿到一个长度为 n 的字符串里面只有三种字符o、x、?。所有连续的o会组成一段每段的长度平方计入总分然后全部相加。比如字符串oooxoo有两个连续o段第一段长度 3第二段长度 2得分就是 3² 2² 13。如果字符串里只有o和x这题就是个纯模拟扫一遍统计连续段长度就能过。难点全在?上每个?会以 1/2 的概率变成o以 1/2 的概率变成x。题目要求的不是某个具体字符串的得分而是所有可能展开结果的期望得分。如果?的数量是 m那么一共有 2^m 种展开方式每种等概率。别说 n 能到 10^6就算 m302^30 也已经超过十亿暴力枚举必死无疑。这就是题目第一个需要转化的点不能枚举必须直接用期望递推。1.2 “? ” 带来的组合爆炸暴力思路走不通之后很多人会想到另一个方向能不能计算每个位置的贡献o段得分的本质是长度平方不是简单的“每个o贡献 1 分”。如果只有一个连续段长度 l 的贡献是 l²。把 l² 拆开看可以理解成对每个位置 i贡献是 2i-1也就是“当前这个o作为段内第几个位置决定了它带来的增量”。但这样做的问题是一个位置到底是段内第几个取决于前面的字符而前面的字符在?存在时是不确定的。所以这题并不能简单地按位置独立贡献必须记录状态。而期望 DP 的价值就在这里它允许我们用一个标量描述“当前位置结尾的连续o段期望长度”从而把不确定的未来变成确定的递推。2. 期望DP的状态设计只需要两个标量背后是一个关键等式2.1 状态定义与转移依赖期望 DP 的状态设计核心是找清楚当前决策只依赖什么信息观察得分规则。假设已经处理完前 i 个字符正在考虑第 i1 个字符。如果第 i1 个字符是o它会让“以 i 结尾的连续o段”长度从 l 变成 l1这个段对总得分的贡献从 l² 变成 (l1)²总得分因此增加 (l1)² - l² 2l1。如果第 i1 个字符是x那它本身就是断点新增字符不会产生任何新得分原来的段也保持不变所以总得分增加 0。于是我们发现处理下一个字符时唯一需要知道的信息就是“当前以最后一个位置结尾的连续o段有多长”。这个长度 l 在某个具体字符串里是个确定整数但在期望问题里它是随机变量所以我们只需要维护它的期望值。定义f[i]前 i 个字符的期望得分。g[i]前 i 个字符中以第 i 个字符结尾的连续o段的期望长度。本质上这是两个标量的递推。f 负责答案g 负责为下一次转移提供“当前连续段长度”的期望信息。2.2 增量公式(l1)^2 - l^2 2l 1 为什么“恰好能用”这个公式是整个算法的基石。展开平方差(l1)² - l² l² 2l 1 - l² 2l 1它是一个关于 l 的线性表达式。就是因为线性才允许我们只维护 E[l]而不需要维护 E[l²]。在概率论里期望只满足线性性E[aX b] aE[X] b。E[l²] 这种东西并不等于 (E[l])²一旦维护“期望长度平方”就会出问题。但这里每次添加o的得分增量是 2l1是 l 的一次函数所以E[增量] E[2l1] 2E[l] 1这就是为什么状态里只需要 g E[l]不需要额外的二阶量。很多初学者在这里会绕进去觉得“得分和长度平方有关那肯定要维护期望长度平方吧”。实际上增量是线性的绕开了二次项。如果哪天题目把得分规则改成 l³增量是 (l1)³ - l³ 3l² 3l 1这时就真的需要额外维护 E[l²] 了而且维护 E[l²] 的递推还要用到 E[l]。这个变式会在文章后面细说。3. 三种字符的转移推导从 o、x 到 ? 的加权平均3.1 字符 o连续加分现在具体推导每一个字符的转移设当前处理到第 i 位上一状态用 f_old、g_old 表示更新后是 f_new、g_new。字符为o时新的连续段长度比原来多 1所以 g_new g_old 1。总得分的增量是 2 * g_old 1所以 f_new f_old 2 * g_old 1。注意这里 f 更新用的是旧 g。因为增量取决于“加这个 o 之前”的连续段长度。如果先更新 g 再用新 g 算增量结果会偏大。从另一个角度验证假设之前连续段长度是 l总得分里这个段贡献了 l²现在这个位置是 o段变成 l1贡献变成 (l1)²新增正是 2l1。3.2 字符 x断连清零字符为x时连续段断掉当前结尾没有o所以 g_new 0。新字符不产生任何得分所以 f_new f_old。这段简洁到很多人会忽略但它同样重要。很多错误代码在遇到x时只把 g 清零却忘了 f 保持不变是合理的——因为 x 不会破坏已经形成的段只是不增加新贡献。3.3 字符 ?两个分支各 1/2 的期望合并字符为?时它有一半概率变成o一半概率变成x。期望 DP 的处理方式就是把两个分支的结果做加权平均。先看 g 的更新变成o的概率是 1/2此时 g_new g_old 1。变成x的概率是 1/2此时 g_new 0。所以g_new (g_old 1) / 2 0 / 2 (g_old 1) / 2再看 f 的更新变成o时得分增量是 2 * g_old 1。变成x时得分增量是 0。所以f_new f_old (2 * g_old 1) / 2这里很容易写错的一个顺序问题是f 的增量必须基于旧 g_old也就是当前字符变成o之前连续段长度的期望。有人会因为手滑先更新了 g再拿新 g 去算 f 增量结果每次?都会多算一点最终答案偏大。为了验证这个递推拿个小例子手动展开。假设字符串是o?x只有一种?展开成两种等概率结果oox连续o段长度 2得分 4。oxx连续o段长度 1得分 1。期望得分是 (4 1) / 2 2.5。用递推跑一遍初始 f 0g 0。字符of 0 2×0 1 1g 0 1 1。字符?f 1 (2×1 1) / 2 2.5g (1 1) / 2 1。字符xf 2.5g 0。最后输出 2.5000和手动展开完全一致。4. 最容易踩的坑期望长度不是某段真实的长度4.1 错误写法的现场这个题最迷惑人的地方在于g 是一个实数而任何一个具体展开字符串里的连续段长度都是整数。把两者混在一起就会写出各种看起来很合理、实际上错的代码。比较常见的错误有两种。第一种把期望长度当真实长度去算平方// 错误示例 else { // ? g (g 1) / 2.0; f g * g; // 错E[g^2] ! (E[g])^2 }这样写的问题很明显。g 是“期望长度”不代表任何真实路径上的长度。真实情况下这个位置的连续段可能是一个整数长度 k概率是 pk² 的期望是 Σ p·k²而不是 (Σ p·k)²。直接 g*g 相当于把期望和平方交换了顺序答案自然不对。第二种用 g_new² - g_old² 来算 f 增量// 错误示例 else { // ? f ((g 1) * (g 1) - g * g) / 2.0; g (g 1) / 2.0; }这个例子有意思的地方在于(g1)*(g1) - g*g展开之后就是2g 1所以如果 g 没有被提前更新这个式子碰巧和正确式子一样。但如果把 g 先更新了再代入这个式子就会变成用新 g 算增量答案偏大。真正要避免的是忘了“期望的线性性只能用于线性表达式”这一条。得分增量2l 1是线性的所以可以用 E[l] 算但如果你试图构造任何含有 l² 的非线性表达式比如期望新增平方贡献那就必须额外维护二阶矩否则就是错的。4.2 为什么线性增量让这个状态成立往深一层想为什么只维护一个“期望长度”就能把整个 DP 跑通关键在于每一轮转移里f 的变化量都是旧状态连续段长度 l 的一次函数。我们把随机变量 l 替换成它的期望 E[l]代入增量公式结果不变。这是因为E[al b] aE[l] b?的转移本质上是在两个分支之间做加权平均这个操作也是线性的。所以整个 DP 过程中我们从来没有对非线性函数取期望所有地方都只需要一阶矩 E[l]。这其实也解释了为什么这题叫 Easy。如果把得分规则改成连续段长度三次方增量是(l1)^3 - l^3 3l^2 3l 1里面出现了 l²那就必须同时维护 E[l²] 和 E[l]状态从一个标量变成两个标量代码复杂度立刻上一个台阶。这就是 P1654 这类题和它的区别。4.3 推广到 l^3 时需要加一个状态顺着上面说如果得分是 l³怎么设计状态设 e1 E[l]e2 E[l²]。对于字符o新的 e1 e1 1。e2 E[(l1)²] E[l² 2l 1] e2 2*e1 1。得分增量 E[(l1)³ - l³] E[3l² 3l 1] 3e2 3e1 1。对于字符xe1 0e2 0得分增量 0。对于?两个分支各 1/2所以每个量的更新都是“o 分支结果 x 分支结果”除以 2。这里就可以看出规律平方得分需要维护 E[l] 和 E[l²]因为增量里有 l²增量公式里的最高次数决定了你要维护几阶矩。P1365 的增量最高是 l¹所以只维护 E[l] 就够。这个规律非常有价值。以后再见到“连续段长度 k 次方得分”的问题不必慌先写出增量多项式数一下最高次数就知道需要维护哪些矩了。5. 参考实现C 与 Python 的滚动数组版本5.1 C 实现与读入细节状态只依赖上一轮所以不需要开数组两个 double 滚动更新即可。#include bits/stdc.h using namespace std; int main() { int n; string s; cin n s; double f 0.0, g 0.0; for (char ch : s) { if (ch o) { f 2.0 * g 1.0; g 1.0; } else if (ch x) { g 0.0; } else { // ? f (2.0 * g 1.0) / 2.0; g (g 1.0) / 2.0; } } printf(%.4f\n, f); return 0; }读入方面n 最大 10^6普通cin n s在关闭同步之后问题不大但保险起见用scanf(%d%s, n, str)更快。下面是另一个版本#include cstdio const int MAXN 1000005; char s[MAXN]; int main() { int n; scanf(%d%s, n, s); double f 0, g 0; for (int i 0; i n; i) { if (s[i] o) { f 2 * g 1; g 1; } else if (s[i] x) { g 0; } else { f (2 * g 1) / 2; g (g 1) / 2; } } printf(%.4f\n, f); return 0; }注意f 2 * g 1这一行g是 double所以整行会自动转成浮点运算没有问题。5.2 Python 实现与输入输出Python 版同样很短注意读入字符串后去掉换行符。import sys def main(): data sys.stdin.read().split() n int(data[0]) s data[1] f 0.0 g 0.0 for ch in s: if ch o: f 2.0 * g 1.0 g 1.0 elif ch x: g 0.0 else: f (2.0 * g 1.0) / 2.0 g (g 1.0) / 2.0 print(f{f:.4f}) if __name__ __main__: main()Python 在 n10^6 的规模下单层循环跑完是没问题的。洛谷上 Python 过这题通常不卡但如果评测环境比较严格可以改用 PyPy读入用sys.stdin.buffer.read()更快。5.3 精度与规模分析有人会担心 double 的精度。我们来估算一下最坏情况。n 10^6如果所有字符都是o答案就是 n² 10^12。double 的 53 位尾数可以精确表示到 2^53 以内的所有整数2^53 大约是 9×10^15远大于 10^12。更关键的是全o情况下 f 和 g 每一步都是整数累加过程完全精确。如果字符串里有?g 会变成小数但只要有大量?连续段长度就会被打散答案不会接近 10^12 的规模。反过来如果字符串大部分是o只有一两个?那大部分中间结果仍是整数误差也很小。所以 double 在这题是安全的不需要 long double。输出保留 4 位小数直接printf(%.4f)即可。如果遇到极端数据仍然担心可以把 f 和 g 声明成long double输出用cout的setprecision(4)不过实测 double 版本已经能 AC。6. 从 P1365 延伸一道题带起的期望DP练习清单6.1 概率从 1/2 变成任意 pP1365 的?是等概率所以转移里直接除以 2。如果改成“每个位置有 p 的概率是 o1-p 的概率是 x”转移公式只需要把 1/2 全部替换成 pg_new p * (g_old 1) (1-p) * 0 p * (g_old 1)f_new f_old p * (2 * g_old 1)这种形式在 P1654 OSU! 里会出现只是那里的得分还是三次方状态数量不同。掌握了 P1365 的推导方法改概率也就是动几个系数的事。6.2 平方变三次方状态维度的变化规律前面推导过三次方的增量公式是3l² 3l 1需要维护 e1 E[l] 和 e2 E[l²]。很多人问为什么不能只维护 e2因为 e2 的更新公式是e2 e2 2 * e1 1这里出现了 e1。也就是说即使你只关心二阶矩的递推它也会依赖一阶矩。所以状态数量是由“增量多项式的最高次数 低次依赖关系”共同决定的并不是说最高次数是 2 就只需要维护 E[l²]。这类“连续段长度 k 次方得分”的期望 DP思路高度统一写出增量多项式 (l1)^k - l^k。展开成 l 的幂次和。确定需要维护哪些阶矩保证每一步递推都能闭环。对每个字符写分支转移遇到不确定字符就做加权平均。6.3 该往哪些题迁移做完 P1365建议按顺序刷这几道同源题感受同一套模板在不同得分规则下的变化P1654 OSU!得分是连续段长度三次方需要维护一阶矩和二阶矩。P3802 小魔女帕琪虽然背景不同但核心也是期望的线性叠加。Codeforces 上不少 EDP 题比如 235B Lets Play Osu!几乎就是把 P1365 换成 n 个独立概率 p_i 的版本。先刷 P1365再刷 P1654就能直观体会到“一个状态够不够用”这个问题是怎么随着得分规则变化而变化的。我自己做这类题的习惯是拿到题第一件事不写代码先在纸上把每个字符的转移公式列一遍重点检查 f 的增量用的是旧 g 还是新 g。这个习惯帮我避开了很多次?顺序写反导致的 WA。P1365 作为期望 DP 的入门题公式简单、状态少正是训练这套流程的好材料。
