CF1842
flower1
·
·
个人记录
CF1842
F
考虑钦定根节点为黑点重心，这样选每个点为黑点对答案造成的贡献是独立的。
如果计算答案时当前点不是黑点重心，那么会使答案更小，不会产生影响。
于是可以枚举黑点重心，O(n^2 \log n) 解决本问题，瓶颈在于排序。
G
非常神秘，考虑乘法分配率的每条路径，每次从 a_i 转移到 a_{i+1} 时。
- 选 a_i，贡献系数 a_i
- 选 v，贡献系数 v，并且还要求操作的位置在 i 前，由于 dp 时可能会选重复的 v，所以状态要记录以前钦定过位置的操作个数。
设 f_{i,j} 表示长度为 i 的前缀，钦定了 j 个操作的答案。
f_{i,j}(a_i+jv) \rightarrow f_{i+1,j}
f_{i,j}(m-j)iv\rightarrow f_{i+1,j+1}
答案为：
\frac{\sum_{j=0}^{m}f_{n,j}n^{m-j}}{n^m}
H
神秘 trick 题，有点过于人类智慧了。
首先设 y_i = x_i - 0.5，条件转化为 y_i + y_j \le 0 或 y_i + y_j \ge 0，这个式子只和绝对值较大的 y 有关。
因此我们状压 dp，钦定新加入的 y 绝对值更大，容易做到 O(2^nn)。