2020-2021:teams:i_dont_know_png:qxforever:practice2021.1

差别

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

到此差别页面的链接

--- 2020-2021:teams:i_dont_know_png:qxforever:practice2021.1 [2021/01/31 16:53]
qxforever 创建
+++ 2020-2021:teams:i_dont_know_png:qxforever:practice2021.1 [2021/01/31 17:38] (当前版本)
qxforever
@@ 行 1: / 行 1: @@
-一些个人觉得有意思的题的记录
+====== 做题记录 ======
+可能包含一些剧透？
+===== 1477 C - Nezzar and Nice Beatmap =====
+ [[https://codeforces.com/contest/1477/problem/C|link]]
+tag : 构造
+**题目大意**：给 $n$ 个二维平面上的点，求一个排列使得 $P$ 对任意 $i$ 有 $\angle{P_iP_{i + 1}P_{i + 2}}$ 为锐角。$n \le 5000$ 。
+**题解**：
+每次从没有使用过的点中选择离当前点距离最远的点，作为下一个点即可。
+难以想到的简单的初中几何原理。
+===== 1446 F - Line Distance =====
+[[https://codeforces.com/contest/1446/problem/F|link]]
+tag : 几何
+**题目大意**：给 $n$ 个二维平面上的点，求在这些点两两连成的所有直线中，与原点距离第 $k$ 大的。$ n \le 10 ^ 5$
+**题解**：在圆外两点连线与圆相交时，设他们的切线在圆上弧度分别为 $[l_1, r_1], [l_2, r_2]$，那么当这两个区间相交（不包括包含）时，直线与圆相离。
+可以画图感受一下
+===== 1446 D - Frequency Problem =====
+[[https://codeforces.com/contest/1446/problem/D1|link]]
+**题目大意**：给一个长度为 $n$ 的序列 $a$ ，求出最长的 **subarray** ，使得 subarray 中的众数不唯一。$n \le 2 \times 10 ^5, a_i \in [1, A]$。
+Subtask 1 : $A \le 100$ ；Subtask 2 : $A \le n$
+**题解**：设整个序列的众数为 $f$，那么 $f$ 也一定是所求 subarray 中的众数之一。
+Subtask 1： $O(n)$ 枚举另一个众数；对所有前缀，维护 $cnt_f - cnt_i$。
+Subtask 2： 分块。出现次数大于 $k$ 用上面的暴力求。剩下的数只需要在出现位置前后 $T$ 个 $f$ 的位置处维护即可。复杂度 $O(nk + n ^ 2 / k)$。
+===== 1421 E - Swedish Heroes =====
+[[https://codeforces.com/contest/1421/problem/E|link]]
+**题目大意**：给一个长度为 $n$ 的序列 $a$ ，每次可以将相邻的两个数 $a_i, a_{i+1}$ 删除，将 $-(a_i + a_{i + 1})$ 放入原来的位置。求在 $n - 1$ 操作后剩下的数最大值。 $n \le 2 \times 10 ^ 5$。
+**题解**：考虑每一位对最终答案的贡献，$a_i$ 最终可能变为 $+a_i$ 或 $-a_i$。牛逼结论： $(n + 负号个数) \mod 3 == 1$，并且至少存在两个连续的符号相同的 $a_i$。然后就能 dp 了。

2020-2021/teams/i_dont_know_png/qxforever/practice2021.1.1612083202.txt.gz · 最后更改: 2021/01/31 16:53 由 qxforever