2020-2021:teams:i_dont_know_png:qxforever:practice2021.1
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:i_dont_know_png:qxforever:practice2021.1 [2021/01/31 17:20] 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 ===== | ===== 1477 C - Nezzar and Nice Beatmap ===== | ||
| [[https://codeforces.com/contest/1477/problem/C|link]] | [[https://codeforces.com/contest/1477/problem/C|link]] | ||
| 行 31: | 行 31: | ||
| Subtask 1 : $A \le 100$ ；Subtask 2 : $A \le n$ | Subtask 1 : $A \le 100$ ；Subtask 2 : $A \le n$ | ||
| - | **题解**：设整个序列的众数为 f，那么 f 也一定是 subarray 中的众数之一。 | + | **题解**：设整个序列的众数为 $f$，那么 $f$ 也一定是所求 subarray 中的众数之一。 |
| - | Subtask 1 $O(n)$ 枚举另一个众数； | + | |
| - | Subtask 2 需要分块。出现次数多的数 $O(n)$ 暴力求，出现次数少的可以 $O(T^2)$ 求，T 是出现次数。 | + | 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.1612084817.txt.gz · 最后更改: 2021/01/31 17:20 由 qxforever
