CF1852E Rivalries
首先，我们只关心每种数 \(x\) 出现的第一个位置和最后一个位置 \(l_x,r_x\)。
此时，若有两个数 \(x<y\)，满足 \(l_x<l_y\leq r_y<r_x\)，那么 \(x\) 就一点用没有，去除掉这些 \(x\) 之后，剩下的每种数一定至少在端点处是有用的，我们先把这些位置填了。
此时，对于有用的数 \(x\)，其只能在 \([l_x,r_x]\) 内填数。
此时对于剩下的位置，一个显然的想法是，位置 \(i\) 填上所有 \(i\in [l_x,r_x]\) 的 \(x\) 最大值，记为 \(b_i\)。
但是事实上，我们还可以填一些没有用的数，但是要满足他们不影响现在的权重。
注意到若填了两种及以上不同的没用的数，我们不妨换成最大的一个，这样不仅和变大了，而且其也更不容易被计算到权重里，因此最多有一种没用的数，设为 \(c\)。
那么，一定存在一种有用的数 \(x\)，满足 \(c<x\) 且 \(l_c<l_x\leq r_x<r_c\)，我们不妨枚举 \(x\)。
此时贪心地，\(c\) 一定是填小于 \(x\) 的最大的 \(c\) 最好，我们先把 \(b_i>c\) 的先填上 \(b_i\) ，剩下的位置填上 \(c\) 。但是这样不一定合法 ，因为我们要保证 \(l_x,r_x\) 两侧各有至少一个 \(c\) ，如果已经有了就不用管了，否则选择 \(b\) 最小的一个换成 \(c\) 即可。
实现不是难点。
CF1835E Old Mobile
首先，因为我们可以记住按过的键，所以串里的字符只有第一次出现是有用的，所以我们去重之后求出 额外按键次数，然后加 \(n\) 就好了，去重之后字符之间没有区别，我们记作 \(1\to k\)。
我们把 \([1,k]\) 的字符称为 有用字符，\([k+1,m]\) 的字符称为无用字符。
考虑我们的策略是什么：
很明显这个删除键非常重要，因此我们分是否知道删除键的位置讨论：
知道删除键的位置
记 \(f_{i,j}\) 表示已经按出了 \(i\) 种无用字符， \(j\) 种有用字符的概率，\(F_{i,j}\) 为其期望次数。
- 串中下一个字符我们已知，此时不需要额外按键次数，不转移
- 串中下一个字符未知，那么我们就需要随机按一个
- 按中一个无用的字符 需要先删掉，然后转移到 \(f_{i+1,j}\)，花费的次数是 \(2\) 。
- 按中一个有用的字符，但是不是串中下一个 需要先删掉，然后转移到 \(f_{i,j+1}\) 花费次数是 \(2\)
- 按中一个有用的字符，且是串中下一个 不需要删掉，转移到 \(f_{i,j+1}\)，花费次数 \(0\)
概率都是很好算的。
不知道删除键的位置
那么我们可能会打出一个不符合原串的后缀，并且一旦打出来第一个不符合原串的字符，我们接下来唯一的目的就是寻找删除键，然后把这些不符和的都删除。
记 \(g_{i,j}\) 表示已经按出了 \(i\) 种无用字符，\(j\) 种有用字符，且当前打出的字符完全符合原串的概率，\(G_{i,j}\) 为其期望。
记 \(h_{i,j}\) 表示已经按出了 \(i\) 种无用字符，\(j\) 种有用字符，且当前打出的字符至少有一个不符合原串的概率，\(H_{i,j}\) 为其期望。
\(g:\)
- 串中下一个字符我们已知，此时不需要额外按键次数
- 串中下一个字符未知，此时需要随机按一个
- 按中删除键 转移到 \(f_{i,j}\)，需要 \(2\) 的额外花费，因为需要把不小心删的打回来
- 按中无用字符/有用但不对的字符 转移到 \(h\) 并且我们迟早会删掉这个字符，所以一定有 \(2\) 的代价
- 按中有用且对的字符 转移到 \(g\)，无额外代价。
\(h:\)
- 串中下一个字符我们已知，此时不需要额外按键次数
- 串中下一个字符未知，此时需要随机按一个
- 按中删除键 转移到 \(f_{i,j}\) 并且误删的那个代价算过了，所以代价为 \(0\)
- 按中别的字符 转移到 \(h\) 并且我们迟早会删掉这个字符，所以一定有 \(2\) 的代价
特殊注意一下\(i=j=0\) 时删除键不需要补代价。
最终的贡献，我们很明显一旦知道了其他 \(m\) 个键剩下的是什么也很清楚了，因此有不止一种合法终态。