2020-2021:teams:i_dont_know_png:jagiellonianu2020

差别

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

到此差别页面的链接

--- 2020-2021:teams:i_dont_know_png:jagiellonianu2020 [2020/07/11 16:14]
qxforever
+++ 2020-2021:teams:i_dont_know_png:jagiellonianu2020 [2020/07/20 22:21] (当前版本)
nikkukun add C
@@ 行 26: / 行 26: @@
 总时间复杂度 $O(\max \{a_i\} \log \max \{a_i\})$。
+===== C - Bookface =====
+Upsolved by nikkukun.
+==== 题目描述 ====
+给 $n \leq 2 \times 10^5$ 个数 $x_1, x_2, \ldots, x_n$（$x_i \in [0, 3 \times 10^{11}]$）和一个参数 $d \in [1, 10^6]$，你可以将这个序列的值任意改动为其余非负整数，使得对任意的 $i \neq j$ 都有 $|x_i - x_j| \geq d$，代价为每个数的改变量绝对值之和。
+求最小代价。
+==== 解题思路 ====
+不妨考虑先将 $x$ 数组排序，并在维持相对位置的情况下，使得排序后数组 $x_{i+1} - x_i \geq d$，这样原题的条件便得到满足。
+先转化条件为非降序列：要求 $x_{i+1} - x_i \geq d$，则令 $x'_i = x_i - (i - 1) \cdot d$，就变成了令 $x'_{i+1} \geq x_i'$ 的条件。
+再保证所有数非负：对所有 $x_i' < 0$ 的数，都将其先改为 $0$，并将变化量统计在答案中。此时显然转化回 $x_i$ 的数组既非负，又满足了条件。同时，在 $x_i'$ 中由于所有数也非负，为了用最小代价将 $x_i'$ 变为非降，不会把某些 $x_i'$ 重新调回负数，这并不优。
+于是，现在问题变成让 $x'$ 数组非降，而这是经典 $L_1$ 问题，参考 [[.:nikkukun:isotonic_regression#l_1_问题 | 保序回归问题]]。
+===== E - Contamination =====
+Solved by Potassium.
+==== 题目描述 ====
+$n$ 个互相无交点的圆是原子弹伤害范围，有 $q$ 次查询，每次查两个位于 $x_1$ 和 $x_2$ 坐标，且 $y$ 坐标可以任意游走于 $[ymin,ymax]$ 的动物能否相遇。
+==== 解题思路 ====
+有显然结论：如果两动物不能相遇，一定有一个圆跨过 $[ymin,ymax]$ 且位于两点之间。于是将圆和动物都放在 $ymin$ ，从小到大枚举，遇到动物就查询中间能够到达的最大 $y$ 值，如果超过 $ymax$ 则无法到达；遇到圆就更新 $c_x$ 处的值为 $c_y+r$。
 ===== F - The Halfwitters =====
@@ 行 47: / 行 89: @@
 问题的答案为 $\min(cost_{inv},E+c)$ 。
+===== G - Invited Speakers =====
+Solved by Potassium.
+==== 题目描述 ====
+签到构造题，跳了
+==== 解题思路 ====
+===== H - Lighthouses =====
+Solved by Potassium.
+==== 题目描述 ====
+给一个凸多边形以及一些顶点间的路，求最长不重复经过点的路径。
+==== 解题思路 ====
+区间 $dp$，考虑某个区间不能选和终点位置，向外转移即可。
 ===== I - Sum of Palindromes =====

2020-2021/teams/i_dont_know_png/jagiellonianu2020.1594455298.txt.gz · 最后更改: 2020/07/11 16:14 由 qxforever