2020-2021:teams:intrepidsword:2020.07.24-2020.07.30_周报
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:intrepidsword:2020.07.24-2020.07.30_周报 [2020/07/31 17:18] chielo [jsh] |
2020-2021:teams:intrepidsword:2020.07.24-2020.07.30_周报 [2020/08/07 18:17] (当前版本) chielo 已恢复为旧版 (2020/07/31 17:46) |
||
|---|---|---|---|
| 行 73: | 行 73: | ||
| Atcoder M-SOLUTIONS Programming Contest 2020 problem E | Atcoder M-SOLUTIONS Programming Contest 2020 problem E | ||
| - | https://atcoder.jp/ | + | https://img.atcoder.jp/m-solutions2020/editorial.pdf |
| **Tags**：search | **Tags**：search | ||
| - | **题意**：见链接 | + | **题意**：平面上若干个点 已在x轴，y轴建设道路。定义点权重为点上的人数和到任意一条道路的最小距离之积。问假设可以再增加k条平行于x或y轴的道路。求最小点权和。 |
| - | **题解**：见链接 | + | **题解**： 一个简单的想法是暴力枚举在哪些点上建设道路 然后check。这样的复杂度是2^n * n^3的。其实预存一张表来记录每个点建设道路后的对其他点的更新，这样check的复杂度是n^2的。 |
| + | 实际上可以3^n去枚举所有可能的情况(无道路，平行x轴，平行y轴。这样是3^n * n的。 | ||
| **Comment**：考虑清楚3^n,2^n * n^2 等复杂度和如何优化查询 | **Comment**：考虑清楚3^n,2^n * n^2 等复杂度和如何优化查询 | ||
| 行 110: | 行 111: | ||
| 你会想说单关键点计算时间复杂度 $\mathcal{O}(n)$ 不就爆了吗。 | 你会想说单关键点计算时间复杂度 $\mathcal{O}(n)$ 不就爆了吗。 | ||
| - | 会发现 $g_{x, y}(u)$ 都是些直线，应用一下 [[https://codeforces.com/blog/entry/63823|Convex Hull Trick]]，我们就能在 $\mathcal{O}(\log n)$ 的时间内计算 $\mathcal{O}(n)$ 个线性函数在某个自变量下的最大值啦。 | + | 会发现 $g_{x, y}(u)$ 都是些直线。应用一下 [[https://codeforces.com/blog/entry/63823|Convex Hull Trick]]，我们就能在 $\mathcal{O}(\log n)$ 的时间内计算 $\mathcal{O}(n)$ 个线性函数在某个自变量下的最大值啦。开两个表，一个 $g$，一个 $-g$，在关键点各自取最大值求和即可。 |
| 时间复杂度 $\mathcal{O}(n^2 \log n)$。 | 时间复杂度 $\mathcal{O}(n^2 \log n)$。 | ||
2020-2021/teams/intrepidsword/2020.07.24-2020.07.30_周报.1596187119.txt.gz · 最后更改: 2020/07/31 17:18 由 chielo
