总结——6.29终章-2

· · 个人记录

T1 [AGC058A] Make it Zigzag

一道比较傻逼的贪心题。

核心就是只考虑偶数位是否需要交换，强烈谴责OJspj炸了。

T2 [AGC058B] Adjacent Chmax

还没改，好像是一道区间dp，考试的时候用记忆化搜索骗了点分。

T3 [AGC057B] 2A+x

神题。

看着是要构造，实则根本不需要关心具体的值。

我们可以计算出这个值在经过变化之后的取值范围，这样我们就得到了 n \log n 个区间。 对于区间，我们要极差尽可能的小只需要对左端点取最大，右端点取最小就好。

好像 10^{18} 内是有解的，但是我 3\times 10^{17} 过了，是真的离谱。

T4 CF1034A Enlarge GCD

和第一题一样傻逼。

给一个序列，要求删最少的数，使得 gcd 变大。

我们的思路是对全部 a_i 除一个 gcd 这样我们只需要求出现最多的素数的出现次数。

数据范围乍一看还挺吓人的 n\le 10^5,a_i\le 1.5\times 10^7。

但是仔细想想就会发现，我们分解质因数的复杂度在不用科技的情况下最快可以做到 \frac{\sqrt{n}}{\log n}。

带入数据再加计算，最后我们的复杂度达到了 10^8。这是可以接受的了，实际上这是最坏估计，OJ上只跑了 400MS。