差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:intrepidsword:2020.07.24-2020.07.30_周报 [2020/08/07 18:15]
chielo [jsh]
+++ 2020-2021:teams:intrepidsword:2020.07.24-2020.07.30_周报 [2020/08/07 18:17] (当前版本)
chielo 已恢复为旧版 (2020/07/31 17:46)
@@ 行 1: / 行 1: @@
 ===== 团队 =====
-.08.03 [[2020-nowcoder-multi-8|2020牛客暑期多校训练营（第八场）]] ''pro: 5/7/11'' ''rk: 10/685''
+.07.30 [[xvi-open-cup-ukraine|XVI Open Cup named after E.V. Pankratiev. GP of Ukraine]] ''pro: 11/11/13'' ''rk: 35/409''
-.08.01 [[2020-nowcoder-multi-7|2020牛客暑期多校训练营（第七场）]] ''pro: 8/8/10'' ''rk: 5/1090''
+.07.27 [[2020-nowcoder-multi-6|2020牛客暑期多校训练营（第六场）]] ''pro: 7/8/11'' ''rk: 27/1019''
+.07.25 [[2020-nowcoder-multi-5|2020牛客暑期多校训练营（第五场）]] ''pro: 6/10/11'' ''rk: 24/1116''
 ===== 个人 =====
 ==== zzh ====
 === 专题 ===
+无
 === 比赛 ===
+无
 === 题目 ===
+无
 ==== pmxm ====
@@ 行 22: / 行 27: @@
 === 专题 ===
+无，哦
 === 比赛 ===
+  * 2020/7/24 [[https://clist.by/standings/srm-788-20577952/|SRM 788]] ''problems: 1/2/3'' ''rank: 102/190''
+  * 2020/7/25 [[https://atcoder.jp/contests/m-solutions2020/|ABC: M-SOLUTIONS Programming Contest 2020]] ''problems: 5/6/6'' ''rank: 58/6527''
 === 题目 ===
+无哦
 ==== jsh ====
+=== 比赛 ===
+  * 2020/7/24 [[https://clist.by/standings/srm-788-20577952/|SRM 788]] ''problems: 1/2/3'' ''rank: 112/190''
+  * 2020/7/24 [[http://codeforces.com/contest/1383|Codeforces Round #659 (Div. 1)]] ''problems: 2/2/6'' ''rank: 220/1169''
+  * 2020/7/25 [[https://atcoder.jp/contests/m-solutions2020/|ABC: M-SOLUTIONS Programming Contest 2020]] ''problems: 5/6/6'' ''rank: 281/6527''
+  * 2020/7/29 [[http://codeforces.com/contest/1389|Educational Codeforces Round 92 (Rated for Div. 2)]] ''problems: 6/6/7'' ''rank: 55/13826''
+  * 2020/7/30 [[http://codeforces.com/contest/1388|Codeforces Round #660 (Div. 2)]] ''problems: 5/5/5'' ''rank: 24/13083''
 === 专题 ===
+无
-=== 比赛 ===
 === 题目 ===
+无
 ===== 本周推荐 =====
 ==== zzh ====
-[[url|Link]]
+[[xvi-open-cup-ukraine#j_joining_powers|XVI Open Cup named after E.V. Pankratiev. GP of Ukraine J. Joining Powers]]
-**Tags**：
+**Tags**：number theory, binary search
-**题意**：
+**题意**：见链接
-**题解**：
+**题解**：见链接
-**Comment**：
+**Comment**：有点意思的数论，如果你看着指数最多 $60$，想着去暴搜，你就输了。
 ==== pmxm ====
-[[url|Link]]
-**Tags**：
+Atcoder M-SOLUTIONS Programming Contest 2020 problem E
-**题意**：
+https://img.atcoder.jp/m-solutions2020/editorial.pdf
-**题解**：
+**Tags**：search
-**Comment**：
+**题意**：平面上若干个点 已在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 等复杂度和如何优化查询
 ==== jsh ====
-[[https://yukicoder.me/problems/no/1143|yukicoder - No.1143 面積Nの三角形]]
+=== Codeforces Round #660 (Div. 2) - E. Uncle Bogdan and Projections ===
-**Tags**：海伦公式，Ravi 变换
+[[https://codeforces.com/contest/1388/problem/E|题目链接]]
-**题意**：求面积恰好为 $n$、各边均为正整数的三角形有多少个（全等的记为同一个）。
+**Tags**：几何，Convex Hull Trick
+**题意**：有 $1 \le n \le 2\,000$ 条在 $x$ 轴上方、平行于 $x$ 轴的线段。现在你可以让这些线段以相同的一个方向平移到 $x$ 轴上，就像一个平行光源打到了这些线段上，然后在 $x$ 轴上投影。**但是要求投影之间不能相交。**记投影的范围为最大坐标和最小坐标的差，求投影之间不相交情况下，最小的投影范围是多大。
 **题解**：
-首先，若三边为 $a, b, c$ 的三角形面积为 $n$ 有海伦公式：
+首先，如果线段都在同一个水平线上，那投影的范围是不会变的。所以以下我们考虑存在有至少一对线段，所在高度是不同的。
-$$n^2 = s (s - a) (s - b) (s - c)$$
-其中 $2 s = a + b + c$。
+记投影方向与 $y$ 的负半轴的角度为 $\theta \in (-\pi, \pi)$，容易得出点 $(x, y)$ 的投影的横坐标为 $f_{x, y}(\theta) = x + y \tan{\theta}$。
+让 $u = \tan{\theta} \in \mathbb{R}$，改写一下函数 $g_{x, y}(u) = x + y u$，题目需要的就是在投影之间不相交情况下，最小化所有线段上的点的函数值的最大值和最小值的差，相当于线段端点的函数值的最大最小差。
+一个显然的想法是取线段投影没有相交、但是存在几个投影恰好相切时候的角度来对答案进行更新。
+因为在投影之间完全不相交也不相切的情况下，角度逐渐偏左或偏右会让投影之间变化到恰好相切，根据 $g_{x, y}(u)$ 容易知道在取恰好相切的时候是能够取到答案的局部极值点的（极大或极小都有可能，但总有一个极值点比所有没有相切的情况要优）。
+好，接下来我们需要能够知道，在什么情况下，才不会有投影相交。
-这时可能就没什么好头绪了，因为枚举 $a, b$ 后，即不容易解出 $c$，也还需要额外判一次合法性。同时复杂度也没有保障。
+容易发现一对高度不同的线段，会在某个特定的角度区间出现投影相交的情况，而求出来区间的左右端点刚好是这两个线段投影相切时候的角度。那我们 $\mathcal{O}(n^2)$ 处理出来所有的区间（可以用分数类），让端点为关键点，排个序 $\mathcal{O}(n^2 \log n)$，然后在扫描线过程中不计算存在有投影相交情况下的关键点即可。
-这时我们记 $x = s - a$, $y = s - b$, $z = s - c$，公式就变成了：
+你会想说单关键点计算时间复杂度 $\mathcal{O}(n)$ 不就爆了吗。
-$$n^2 = x y z (x + y + z)$$
-考虑枚举 $x, y$，发现 $z$ 只需要解一下二次方程即可，同时枚举的复杂度上界也是 $n$ 的因子数量的平方，并不大。
-再考虑是否会出现不合法的解，首先容易知道一组 $x, y, z$ 的解可以确定出唯一的 $a, b, c$；同时，实际上 $2 x = b + c - a$, $2 y = a + c - b$, $2 z = a + b - c$，即只要保障 $x, y, z > 0$，就可以确定一个合法的三角形了。
+会发现 $g_{x, y}(u)$ 都是些直线。应用一下 [[https://codeforces.com/blog/entry/63823|Convex Hull Trick]]，我们就能在 $\mathcal{O}(\log n)$ 的时间内计算 $\mathcal{O}(n)$ 个线性函数在某个自变量下的最大值啦。开两个表，一个 $g$，一个 $-g$，在关键点各自取最大值求和即可。
-上述 $a, b, c$ 与 $x, y, z$ 的变换被称作 Ravi 变换。
+时间复杂度 $\mathcal{O}(n^2 \log n)$。
-**Comment**：没见过的科技，但是也确实应当可以自己来构造一下，有点菜。
+**Comment**：为数不多能现场 AK 的比赛，写一个 E 题的题解纪念一下。

CVBB ACM Team

用户工具

站点工具

差别

页面工具