A - Erasing Vertices
给定大小为 \(n\) 的有向图，每次随机选择一个未删除的节点，将其与其可以到的的点全部删除，求总操作次数期望，\(n\leqslant 100\)。
考虑贡献，设能到达 \(i\) 的节点数为 \(d_i\)（包括自己），则其被操作的概率是 \(\dfrac{1}{d_i}\)，所以期望是每个点的和，求 \(d_i\) 建图跑或者直接 floyd 传递闭包。
B - Flip Digits
给定 01 序列 \(A,B\)，每次可以选一个 \(i>1\)，需保证 \(A_i=1\)，然后让 \(A_i\leftarrow 0\)，并反转 \(A_{i-1}\)，判断把 \(A\) 变成 \(B\) 的最小操作次数或判定无解，\(|A|\leqslant 5\times 10^5\)。
不开 long long 见祖宗。
一次操作可以看为向左移动某个 \(1\)，最多能移动到向前第一个 \(1\) 并把这俩一起消掉。于是开个队列维护 \(1\) 的位置然后扫 \(B\)，如果当前 \(1\) 多就消掉队内的前两个 \(1\)，\(1\) 不够就从下一个位置移过来，不能直接输出无解，不难发现这样是最优的。
C - Robots
数轴上从 \(0\) 到 \(10^{100}\) 每个位置有个机器人，现在给你 \(n\) 种操作，每种操作为让机器人 \(A_i\) 向前移动 \(1\) 个位置，如果前一个位置有机器人，则把那个机器人弄爆，每种操作有 \(B_i\) 个，问你最少修改多少个操作（让哪个机器人向前走）使得你可以安排某种操作顺序使得机器人 \(0\) 最终不会被弄爆。\(n\leqslant 2\times 10^5\)，\(0<A_i,B_i\leqslant 10^9\)。
先考虑答案何时为 \(0\)，我们发现如果某个机器人 \(i\) 满足 \(A_i\leqslant B_i\)，则其一定要被某个机器人弄爆，如果弄爆这个机器人的机器人 \(j\) 也满足 \(A_j\leqslant B_j\)，则 \(j\) 以后也一定要被弄爆，一直这么推下去最后一定有一个 \(A_k>B_k\) 的机器人 \(k\) 弄爆了上一个机器人，注意到这个机器人一定也都经过了递归栈中的所有机器人，所以我们可以认为一定是某个 \(A_k>B_k\) 的机器人弄爆了这个机器人。所以我们只需要判断每个 \(A_i\leqslant B_i\) 的机器人是否被某个 \(A_k>B_k\) 的机器人覆盖。
现在考虑一般情况，我们发现可以把修改操作改为删除或添加，删除好说就是把数改成超级大，添加就相当于选中一个对 \(A_i\leqslant B_i\) 的 \(i\) 的操作对其修改（如果没有显然不需要继续操作了）。若删除了 \(x\) 个操作，添加了 \(y\) 个操作，则代价为 \(\max(x,y)\)。考虑所有 \(A_i\leqslant B_i\) 且未被某个 \(A_k>B_k\) 的机器人覆盖的 \(i\)，我们考虑怎么把它弄爆：要不然添加一个 \(A_i+1\) 的操作，添加代价为 \(1\)；要不然删除一个能覆盖到 \(i\) 的 \(j\)，且\(A_j\leqslant B_j\) 的操作使得 \(A_j=B_j+1\)，删除代价为 \(B_j-A_j+1\)。我们发现，如果我们对两个不同的 \(j\) 都删除到了 \(A_j=B_j+1\)，最后两个机器人都会跑到 \(1\)，我们只需要保留 \(A\) 更大的那个机器人，所以我们枚举进行删除操作的机器人，然后求出还未被覆盖的机器人数量然后取 \(\min\) 即可，复杂度 \(O(n)\)。
D - Convex Sequence
发现是个凸包（题目名字说了），我们发现其导数单调，所以我们考虑每次增量构造，我们考虑这种序列这样的一种生成方法：
- 钦定最小值位置 \(i\)（如果有多个最小值，钦定下标最大的）及其值 \(v\)。
- 选择若干 \(j<i\)，分别把 \(a_j,a_{j-1},\dots a_1\) 加上 \(1,2,\dots,j\)。
- 选择若干 \(j>i\)，分别把 \(a_j,a_{j+1},\dots,a_n\) 加上 \(1,2,\dots,n-j+1\)，特别的，\(i+1\) 至少被选择一次。
我们可以发现，任何一个这样的凸包序列都可以和这样的生成方式一一对应。
注意到如果我们只需要考虑小于 \(i\) 的部分 ，那么这等价于跑一个物品大小为 \(n,1,3,6,10,\dots\) 的完全背包，注意不同的物品种类数是 \(O(\sqrt m)\) 的，我们可以在 \(O(m\sqrt m)\) 的时间解决该问题。
然后我们考虑大于 \(i\) 的部分，这等价于先强制添加一个大小为 \(1+2+\dots+n-i\) 的物品然后再跑完全背包。
现在我们考虑合并两边，先预处理出数组 \(f(i,j)\) 表示用前 \(i\) 个物品（不包含大小为 \(n\) 的那个）填满大小为 \(j\) 的背包的方案数，\(g(i,j)\) 表示用前 \(i\) 个物品和 \(n\) 填满大小为 \(j\) 的背包，且第 \(i\) 个物品至少被填一次的方案数，则答案为 \(\sum g(i,j)f(n-i-1,m-j)\)。总复杂度 \(O(m\sqrt m)\)，注意物品数开够了（大概要 460），不要像我没注意就开了 330（常用分块块长）。
咕咕咕