07-30 题解
A
朴素的想法
$ dp(i, j, k) $ 表示考虑到第 \(i\) 位， 前 \(i\) 位的和为 \(j\)， 第 \(i\) 位的值为 \(k\)
然后咋转移？
重新定义移动小球的方式：
- 从自己右边的邻居拿过来正数个球
- 拿过来负数个球（即往右边的邻居放正数个球）
在第 2 种操作中， 我们拿走的球会被后面放过来的球补上， 所以只要最终状态下每个箱子里小球的个数都是非负整数即可
由于我们的转移方式都是从右边拿球， 所以考虑到第 \(i\) 位时， \(Sum_{i + 1}\) 是不变的（\(Sum_x\) 表示前缀和）， 所以第 \(i + 1\) 位的贡献就是 \(|j_{i + 1} - Sum_{i + 1}|\) （\(j\) 在前面定义过）
完结
B
鸽（我赛时用了个假的 \(O(n)\) BFS 过了， 你说 mxoj 牛不牛）
C
朴素想法
直接树形 DP 或者贪心地由底向上取链
但是这样对于每一个 \(k\) 都要计算一次， 显然 TLE （我第一次用显然啊）
然后经过观察：
发现可以根号分治解决
为什么呢？
- 对于所有 \(k \le \sqrt{n}\) ， 暴力计算总复杂度是 \(O(n \sqrt{n})\) 的
- 对于所有 \(k > \sqrt{n}\)， ans 的取值最多有 \(\sqrt{n}\) 种（\(ans \le \frac{n}{k} \le \frac{n}{k_{min}} = \sqrt{n}\)）， 所以暴力计算当前端点 \(l\) 的 DP 值， 二分最大的 \(r\) 使得 \(ans_r = ans_l\)， 总复杂度 \(O(n\sqrt{n}\ log\ n)\) （因为 \(ans_k\) 是单调不增的， 所以可以二分）
完结！
D
拆分贡献
对于 \(h_i\) ， 设小于他的 \(h\) 一共有 \(s\) 个， 大于等于的（包括自己）则有 \(n - s\) 个
在 \(\ge h_i\) 的 \(h\) 中任取一个都能与 \(h_i\) 组合并产生贡献， 方式有 \((n - s)!\) 种（\(h_i\) 在第一个也可以， 见题意）
剩下的 \(s\) 个数我们可以随便放
考虑 \(s\) 中的某一个数放到 \((pre_i, i)\) 的贡献：
首先会产生 1 的贡献， 剩下的 \(s - 1\) 个数随便放， 有 \(A_{n - s + 1 + s - 1}^{s - 1} = A_{n}^{s - 1}\) 种放法， 一共有 s 个等价的数， 所以总贡献是 \((n - s)!sA_{n}^{s - 1}\)
序列的总个数为 \(n!\)， 如果 \(i\) 和 \(pre_i\) 之间啥也不放， 还有 1 的贡献， 在每个排列中都有， 一共是 \(n!\) ， 所以总的期望为 \(\frac{(n - s)!sA_{n}^{s - 1} + n!}{n!} = \frac{s(n + 1)}{n - s + 1}\)
对于每个 \(h_i\) 都求一遍即可
E
贪心地考虑， 对于每一个 \(b\)， 我们选出最大的 \(b\) 个 \(a\) 来（不为 0）， 将他们都 -1， 这样肯定是不劣的
所以怎么动态地维护最大的几个 \(a\)， 并修改他们？
平衡树！
将模板《普通平衡树》的基本操作和《文艺平衡树》的 tag 操作结合起来， 就可以得到一棵带修的 Fhq Treap
修改后右根 R 中的所有元素不一定都大于左根中的， 再 Split 一次后合并即可
代码实现好像没那么难
F
很好的性质：有向无环图
定义 ‘贡献’ 为 A 比 B 多走的步数， 如果 A 想要赢， 那么 ‘贡献’ > 0
记 \(f(i)\) 为从第 \(i\) 个点开始走的贡献
这是一个对抗的过程， A 和 B 都会选择对自己最有利的结果
- 如果 i 为白点， 那么 \(f(i) = max(0ll, max(f(son_i)))\) ， （ 和 0 取 max ：如果白点对 A 的贡献非正， A 不会选择走到这里）
- 如果 i 为黑点， 那么 \(f(i) = min(0ll, max(f(son_i)))\) ， （和 0 取 min ： 如果黑点对 A 的贡献非负， B 也不会选择走到这里）
这时候有向无环图的优势就显露出来了： Dp 可以从每个入度为 0 的点开始， 类似拓朴排序， 且转移时不会出现环！
统计方案数的实质就是从 \(n\) 个点中选出一些， 使得 ‘贡献’ > 0， 直接 01 背包即可
注意过程中容量可能为负数
标签：max,frac,07,题解,30,sqrt,贡献,ans From： https://www.cnblogs.com/Bubblee/p/18333375