2020-2021:teams:wangzai_milk:atcoder_beginner_contest_127_vp
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:wangzai_milk:atcoder_beginner_contest_127_vp [2020/07/21 11:11] wzx27 |
2020-2021:teams:wangzai_milk:atcoder_beginner_contest_127_vp [2020/07/21 11:14] (当前版本) wzx27 |
||
|---|---|---|---|
| 行 15: | 行 15: | ||
| === 题解 === | === 题解 === | ||
| - | 考虑两个格子 $(x_i,y_i)$ 和 $(x_j,y_j)$ 对答案的贡献为 $(|x_i-x_j|+|y_i-y_j|){nm-2 \choose k-2}$，所以只要求一遍两两 $|x_i-x_j|+|y_i-y_j|$ 的值即可。 | + | 考虑两个格子 $(x_i,y_i)$ 和 $(x_j,y_j)$ 对答案的贡献为 $(|x_i-x_j|+|y_i-y_j|){k-2 \choose nm-2}$，所以只要求一遍两两 $|x_i-x_j|+|y_i-y_j|$ 的值即可。 |
| <hidden code> <code cpp> | <hidden code> <code cpp> | ||
| 行 64: | 行 64: | ||
| return 0; | return 0; | ||
| } | } | ||
| - | </hidden> </code> | + | </code> </hidden> |
| + | \\ | ||
| ==== F - Absolute Minima ==== | ==== F - Absolute Minima ==== | ||
| 行 83: | 行 84: | ||
| 最后的函数都是形如 $f(x) = \sum |x-a_i| + B$ 的，于是最小值的 $x$ 在这些$a_i$的中间取得，即对 $a_i$ 排序后，如果有奇数个则为 $a_{\frac {n+1}2}$ ,否则为 $a_{\frac n2}$。 | 最后的函数都是形如 $f(x) = \sum |x-a_i| + B$ 的，于是最小值的 $x$ 在这些$a_i$的中间取得，即对 $a_i$ 排序后，如果有奇数个则为 $a_{\frac {n+1}2}$ ,否则为 $a_{\frac n2}$。 | ||
| - | 比赛的时候做法比较复杂，离线离散化 $a_i$ 后维护两棵线段树，一棵是权值线段树，另一棵是区间求和的线段树。每次查询时，通过权值线段树得到 $x = argmin \; f(x)$ ,然后通过区间求和得到 $\sum_{a_i<=x}a_i$ 和 $\sum_{a_i>x}a_i$，再结合 $B = \sum b_i$ 就可以得到 $f_{min}(x)$ 。 | + | 比赛的时候做法比较复杂，离线离散化 $a_i$ 后维护两棵线段树，一棵是权值线段树，另一棵是区间求和的线段树。每次查询时，通过权值线段树得到 $x = argmin \; f(x)$ ,然后通过区间求和得到 $\sum_{a_i \le x} a_i$ 和 $\sum_{a_i>x} a_i$，再结合 $B = \sum b_i$ 就可以得到 $f_{min}(x)$ 。 |
| <hidden code> <code cpp> | <hidden code> <code cpp> | ||
| 行 195: | 行 196: | ||
| return 0; | return 0; | ||
| } | } | ||
| - | </hidden> </code> | + | </code> </hidden> |
| + | \\ | ||
2020-2021/teams/wangzai_milk/atcoder_beginner_contest_127_vp.1595301112.txt.gz · 最后更改: 2020/07/21 11:11 由 wzx27
