这里会显示出您选择的修订版和当前版本之间的差别。
两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
2020-2021:teams:intrepidsword:2020.07.24-2020.07.30_周报 [2020/07/31 17:13] 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 等复杂度和如何优化查询 | ||
行 100: | 行 101: | ||
让 $u = \tan{\theta} \in \mathbb{R}$,改写一下函数 $g_{x, y}(u) = x + y u$,题目需要的就是在投影之间不相交情况下,最小化所有线段上的点的函数值的最大值和最小值的差,相当于线段端点的函数值的最大最小差。 | 让 $u = \tan{\theta} \in \mathbb{R}$,改写一下函数 $g_{x, y}(u) = x + y u$,题目需要的就是在投影之间不相交情况下,最小化所有线段上的点的函数值的最大值和最小值的差,相当于线段端点的函数值的最大最小差。 | ||
- | 一个显然的想法是取线段投影没有相交、但是存在几个投影恰好相切时候的 $u$ 来对答案进行更新。因为在投影之间完全不相交也不相切的情况下,角度逐渐偏左或偏右会让投影之间变化到恰好相切,根据函数的定义容易知道在取恰好相切的时候是能够取到极值点的(极大或极小都有可能,但总有一个点会比没有相切的情况要好)。 | + | 一个显然的想法是取线段投影没有相交、但是存在几个投影恰好相切时候的角度来对答案进行更新。 |
- | 好,接下来需要处理的是,在计算存在有投影相切的时候,如何知道其它的投影是没有相交情况的。容易发现一对高度不同的线段,会在某个特定的角度区间出现投影相交的情况,而求出来区间的左右端点刚好是这两个线段投影相切时候的角度。那我们 $\mathcal{O}(n^2)$ 处理出来所有的区间(可以用分数类),让端点为关键点,排个序 $\mathcal{O}(n^2 \log n)$,然后在扫描线过程中不计算存在有投影相交情况下的关键点即可。 | + | 因为在投影之间完全不相交也不相切的情况下,角度逐渐偏左或偏右会让投影之间变化到恰好相切,根据 $g_{x, y}(u)$ 容易知道在取恰好相切的时候是能够取到答案的局部极值点的(极大或极小都有可能,但总有一个极值点比所有没有相切的情况要优)。 |
+ | |||
+ | 好,接下来我们需要能够知道,在什么情况下,才不会有投影相交。 | ||
+ | |||
+ | 容易发现一对高度不同的线段,会在某个特定的角度区间出现投影相交的情况,而求出来区间的左右端点刚好是这两个线段投影相切时候的角度。那我们 $\mathcal{O}(n^2)$ 处理出来所有的区间(可以用分数类),让端点为关键点,排个序 $\mathcal{O}(n^2 \log n)$,然后在扫描线过程中不计算存在有投影相交情况下的关键点即可。 | ||
你会想说单关键点计算时间复杂度 $\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)$。 |