CF刷题计划？（upd:11.15）

CF刷题计划？

CF1285F

太nb了这个题

暴力一点的做法是二分后直接莫反，但是不够快

考虑枚举一个\(\gcd\)，令其为\(d\)

然后从大到小枚举数，然后把\(\gcd(\frac{x}{d},\frac{y}{d})=1\)的点对找出来

因为要求最大化，所以如果当前有一组点\(x<z<y\)，且\(\gcd(\frac{x}{d},\frac{y}{d})=1\)

那么\(z\)一定可以删去，\(y\)同理

也就是说，这是一个从小到大退栈的过程，而每个数的入栈退栈次数都恰好为\(1\)

为了保证复杂度，需要莫反算出有多少个与当前数互质的数

当然我们可以做得更快

即两个数\(x,y\)一定存在\(a|x,b|y,lcm(a,b)=lcm(x,y),\gcd(a,b)=1\)

于是可以\(O(A\log A)\)

CF1548E

连通块的信息量太大，考虑将一个连通块中\(a_i+b_j\)最小的位置标记

相同则按\((i,j)\)关键字排序

记\(pre_i\)表示最大的\(k\)满足\(a_k<a_i\)，记\(suf_i\)表示最小的\(k\)满足\(a_i\le a_k\)，列同理

首先如果\((i,j)\)被标记，则其不能走到\(pre_i,suf_i\)

但还不够

我们希望\((i,j)\)能走到\(pre_i\)等价于其能走到\((pre_i,j)\)

可以发现，如果从\((i,j)\)出发到达了\((pre_i,k)\)，不妨假设\(k<j\)

那么由于\(a_{pre_i,pre_i+1\cdots i-1}\ge a_i\)，同时这些位置加上对应的\(b\)小于等于\(x\)

则\(a_{pre_i}+b_{k,k+1\cdots j}\le x\)，结论得证

然后可以数据结构维护一下

CF1637H

将数看成平面上的点\((i,p_i)\)

然后有一个结论：

对于\(\forall i<j,p_i>p_j\)，若\(i\)被选，\(j\)被选一定不会更劣

证明：

对于原序列中\(j-i\)最小的\(p_i\)被选\(p_j\)未被选的一对点

我们可以考察第一象限中被其划分出的9个区域的贡献

跳过有限步会发现

只有\(i<k<j\)，\(p_k>p_i\)且\(k\)被选 或 \(p_k<p_j\)且\(k\)未被选 的点可能会使调整后逆序对数增多

但是我们钦定的是\(j-i\)最小的一对点，所以上述情况不存在，结论得证

于是贪心选一选就做完了