D
E
F
D
题意 $n$个人, 第$i$个人$a_i$个饼干, 每次操作随机选一块饼干分给另一个人, 求一个人拥有所有饼干期望操作数
E
F
E
假设最终高度为$H$, 小于$H$要添加的和为$X$, 大于$H$要删除的和为$Y$
若$X>Y$, 答案为$Ymin(m,a+r)+(X-Y)a$
若$Y>X$, 答案为$Xmin(m,a+r)+(Y-X)r$
答案关于$H$是两段下凸曲线, 最优$H$要么是每段曲线最低点, 要么是两段曲线分界点
最低点一定是某个$h_i$, 分界点是$\lfloor\frac{sum}{n}\rfloor$和$\lceil\frac{sum}{n}\rceil$
F
F
最优方案一定是先选出$k-1$个, 按$b$从小到大添加, 然后其余依次添加删除, 最后留一个$a$最大的
先初始化每个人$b$值贡献为$(k-1)b_i$, 那么倒数第$j$个添加的人贡献就为$a_i-b_i\cdot j$
所以$O(nk)DP$即可求出最优方案
G
E
假设存在方案, 那么一定可以找到一个$\ge \lfloor\frac{n}{2}\rfloor$的方案
那么每个区间起始位置一定在$[1,\lceil\frac{n}{2}\rceil]$内, 一定以$x$结束
枚举起始位置, 算出向后延伸最大长度即可
F
F
F
题意 给定串$S,T$, 每次操作循环右移$S$中一个子串, 求$S$变为$T$的最少操作次数
原文：https://www.cnblogs.com/fs-es/p/13121586.html