省选前学习记录

2021.11.24

CF1612G Max Sum Array

算法 ： 构造，贪心，计数

难度 ： 2500

code

发现一个贪心结论，从两边向中间放数，每次放的数一定是剩余最多的数。证明：

考虑一对数的贡献，对于外部的数，贡献为 $0$ ， 这是显然的。对于内部的数，设一共有 $k$ 个， 位置分别为 $a_i$，则贡献为 $\sum_{i=1}^{k}(r - a_i) + (a_i - l) = \sum_{i=1}^{k}r-l = k(r-l)$. $k$ 越大越优。

然后考虑模拟这个过程。从大到小枚举剩余出现次数。对于出现次数为 $i$ 的数，把它们各取一对从两端（没有数的区间的两端）放入序列中。设剩余出现次数为 $i$ 的数有 $num$ 个， 空区间大小为 $n$ 那么放置方案数为 $(num!)^2$ , 放置的贡献为 $(i - 1)\frac{((n - 1)+(n - 2num + 2 - 1))\cdot num}{2} = (i - 1)(n- num)\cdot num$

然后把答案累积起来就行

CF1610D Not Quite Lee

算法 : 数论，计数，结论

难度 : 2000

code

考虑什么样的子序列满足条件。显然当且仅当 $\gcd(a_1, a_2...a_n)|(\sum_{i=1}^{n}\frac{a_i}{2}[2|a_i])$​ , 显然如果 $\gcd$​ 是奇数则一定满足条件。那么如果不是奇数，就考虑删去原序列里所有的奇数。那么满足条件当且仅当$\gcd(a_1, a_2...a_n)|\sum_{i=1}^{n}\frac{a_i}{4}[4|a_i]$​ ， 即 $\gcd$​ 是 $2$​ 的倍数却不是 $4$​ 的倍数。这样按照 $2, 4, 8, 16, 32 ...$​ 不断重复下去。可以在 $O(nlog10^9)$​​ 内求出答案

---

2021.11.25

[SDOI2011]拦截导弹

算法 : cdq + lis + dp

难度 : 紫

code

模板题，把二维的 $lis$ 通过 $cdq$ 分治转化为三维的 $lis$

[TJOI2010]分金币

算法 : 模拟退火

难度 : 紫

code

模拟退火模板，模拟退火太好用啦，可惜 $noip$​​ 没有写

---

2021.11.26

CF1610E AmShZ and G.O.A.T.

算法 : 贪心 + 二分

难度 : 2300

code

考虑 bad 序列的性质， 一个序列是 bad 序列，当且仅当存在两个相邻数 $a_x$ , $a_{x+1}$ 。满足 $a_{x + 1} - a_x < a_x - a_1$ 。证明挺显然的，但是不知道怎么描述。

然后考虑如何删数，先枚举 $a_1$ , 然后对于第 $i$ 个数。 二分得到右侧第一个满足 $a_{x + 1} - a_x \geq a_x - a_1$ 的数 $a_j$ ， 而 $a_i$ 和 $a_j$ 之间的数和 $a_i$ 是不能共存的， 可以简单的证明最优策略一定是删去 $a_i$ 和 $a_j$ 之间的数。不知道怎么解释证明。感性的想，每次删除较大数显然比删除较小数更优，把这些操作累积起来，就是删除 $a_i$ 和 $a_j$ 之间的数。

然后操作流程为，枚举 $a_1$ , 对于第 $i$ 个数， 二分得到右侧第一个满足 $a_{x + 1} - a_x \geq a_x - a_1$ 的数 $a_j$ 。 另 $i = j$, 不断重复操作，复杂度 $O(nlog10^9logn)$ 关于复杂度的证明如下 ：

考虑二分的到 $j$ 因为满足 $a_{j} - a_i \geq a_i - a_1$ , 所以 $a_j - a_1 \geq 2(a_i - a_1)$ 每次二分之后 $a_j - a_1$ 会变为原来的 2 倍，所以 $log10^9$ 次以内可以二分出答案

CF1614D1 Divan and Kostomuksha (easy version)

算法 ： 数论 + dp

难度 : 2100

code

设 $f_i$​ 表示最后一段的前缀 $gcd$ 都为 $i$ 时， 前缀 $gcd$ 的前缀和。考虑如何进行 $dp$ 。

当前段的前缀 $gcd$ 都为 $i$ 那么上一段的前缀 $gcd$ 一定是 $i$ 的倍数。所以 $f_i$ 可以有 $f_j[i|j]$ 转移过来。方程为 $f_i = \max_{i|j} f_j +(cnt_i - cnt_j)i$ , $cnt_i$ 表示 $a$ 序列中有多少个数是 $i$ 的倍数。那么 $cnt_i - cnt_j$ 表示的就是是 $i$ 的倍数却不是 $j$ 的倍数的数。

考虑为什么这样 $dp$ 是对的。首先 $i$ 的倍数一定不会在前缀 $gcd$ 为 $i$ 的段之后出现，因为如果在之前出现，贡献至少为 $i$ ， 但是如果在之后出现，贡献一定小于 $i$ 。同理 $j$ 的倍数会出现在前缀 $gcd$ 为 $j$ 的倍数的段。即不会出现在前缀 $gcd$ 为 $i$ 的段。所以出现在前缀 $gcd$ 为 $i$ 的段的数为是 $i$ 的倍数却不是 $j$​ 的倍数的数。

所以只需把 $cnt$​​ 求出来，再 $dp$​​ 一遍就行， 复杂度为 $O(n\sqrt{a}+a\log a)$​

---

2021.11.27

CF1614D2 Divan and Kostomuksha (hard version)

算法 : 数论 + dp

难度 : 2300

code

考虑优化之前的做法，瓶颈在于 $dp$​​ 的转移， 发现每次转移其实并不用枚举所有的倍数，只需要从相邻的倍数（即这个数乘上一个质数）转移过来就行了。复杂度就可以变为 $O(a\log \log a)$​