F

E 太诡异了，来做做这题。

如果要求 \(f(z)\) 为 \(ans\ge z\) 的概率：

将 \([x_i,x_{i+1}]\) 变为 \([x_i-i*z,x_{i+1}-i*z]\) ，转化为选取 \(y_1 < y_2 ... < y_n\) 分别属于这些区间。

将端点排序一下变成 \(v\) 数组，然后 DP ，设 \(f(i,j,k)\) 为前 \(i\) 个，满足 \(v_j< y_{i-k+1}\sim y_i <v_{j+1}\) 的概率。

• \(f(i,j,k)\to f(i,j+1,0)\)
• \(f(i,j,k)\times \frac{1}{k+1} Prob(i,j) \to f(i+1,j,k+1)\) ， \(Prob(i,j)\) 为 \(i\) 的区间 \([x_i-i*z,x_{i+1}-i*z]\) 在 \([v_j,v_{j+1}]\) 的概率。

一个重要的性质： 当 v 数组与排序前的关系一样时，结果为关于 \(z\) 的多项式

于是可以 DP 求出每个情况的多项式，积分一下求个面积，复杂度 \(O(n^6)\) 。

代码写的基本不能看了..

E

神仙思维题。。。

需要各种分类讨论。

S 结尾为 a : 此时所有 b 能保留并放前面，用一个贪心策略，保留尽可能多的 a
S 结尾为 b ：

cnt(a) 偶数，删光 a
cnt(a) 奇数：

特判一下结尾为 ..ab,..aab 与全 S 为 aaaaabbbbb 的情况。
剩下的，找到一个 baa 与结尾 b 消除；或找一个 ba