*1900 ~ *2100 做题记录

2148G - Farmer John’s Last Wish *1900

转化题意，设一个前缀的 gcd 为 $g$，要选尽可能多的数使得这些数的 gcd 不为 $g$。

遍历前缀，当从 $i$ 到 $i+1$ 时，分三种情况讨论：

• $a_{i+1}$ 在选取的数中，此时这些数的 gcd 一定为 $a_{i+1}$ 的约数，开一个桶，枚举取 max 即可。
• $a_{i+1}$ 不在选取的数中，继承 $i$ 的答案。
• $a_{i+1}$ 不在选取的数中，且 $a_1\sim a_i$ 全被选，判断一下 gcd 的关系即可，若合法答案即为 $i$。

时间复杂度 $\mathcal{O}(n\sqrt{n})$。

1510D - Digits *2100

这有 *2100？直接 dp 存不下最大乘积，但是你取个 log 就能过了（python 可能也能过）。

正解好像是先判掉 $d=0$ 和 $d=5$ 的情况，然后末位为 $0$ 或 $5$ 的数字就不能选了。

有个结论是剩下的数中最多只有三个数不会被选，分 $d$ 的奇偶性讨论一下就行。从而对这 $\le 3$ 个数 dp 即可，时间复杂度 $\mathcal{O}(n)$。

1665D - GCD Guess *2000

询问 $(a,b)$ 相当于得知 $\gcd (x+a,b-a)$，据此固定 $a$ 而改变 $b$ 即可得知 $x+a$ 与某个常数的 $\gcd$。根据询问次数不超过 $30$ 的提示，我们考虑逐位确定 $x+1$ 的值（因为 $a\ge 1$，求 $x+1$ 会更加方便）。

首先我们可以发现询问 $\gcd (x+1,2)$ 可得知 $x+1$ 的奇偶性，假设我们已经知道了 $x+1$ 的后 $k$ 位对应的值为 $c$，那么判断第 $k+1$ 位是否为 1 只需判断 $x+1+(2^k-1-c)+1$ 是否是 $2^{k+1}$ 的倍数，如此即可逐位求出 $x+1$ 的值，且询问次数 $30$ 次。

549D - Haar Features *1900

每次找最右下角的系数不为 $1$ 的格子，将其系数变为 $1$ 即可，复杂度 $\mathcal{O}(n^2{m}^2)$。

倒序遍历可以省去找格子的时间，再使用二维树状数组可以将时间复杂度优化至 $\mathcal{O}(nm\log n\log m)$。

考虑这样为什么是对的，取最优方案，你会发现这个过程刚好能够覆盖到最优方案的所有操作点，于是正确性显然。

940E - Cashback *2000

这有 *2000？首先选出来的区间长度肯定为 $c$ 的倍数（不然最小值会更小），其次选一个长度为 $2c$ 的不如选两个长度为 $c$ 的，于是直接 dp 就行，转移只可能从 $f_{i-c}$ 或 $f_{i-1}$ 转移来，用单调队列或者 st 表优化区间最值即可，复杂度 $\mathcal{O}(n)$。

484B - Maximum Value *2100

貌似写了个非常规做法，但是 $\mathcal{O}(n\sqrt{V})$ 咋还得卡常啊。

熟知 $a_i\mathrm{mod}{a}_j=a_i-a_j\lfloor \frac{a_i}{a_j}\rfloor$，对 $a_i$ 数论分块，每次只需要查询值域在 $[l,r]$ 内的最小值即可最大化答案，加了点剪枝（$l$ 的初始值设为 $\text{ans}$）就能过。

有点唐了，把数论分块换成去重后枚举 $a_j$ 和 $\lfloor \frac{a_i}{a_j}\rfloor$ 就是均摊 $\mathcal{O}(V\log V)$ 的，调和级数都忘了。

557D - Vitaly and Cycle *2000

先二分图染色，不能染的已经含有奇环，然后把加三条边和两条边的特殊情况判掉。

考虑一个连通的二分图，想要让其含有奇环即把其变为非二分图，于是连接两个黑点或两个白点即可，总时间复杂度 $\mathcal{O}(n)$。

2044F - Easy Demon Problem *1900

即求是否存在 $r,c$ 满足 $\left(\sum _{i\ne r}{a}_i\right)\cdot \left(\sum _{i\ne c}{b}_i\right)=x$，由于 $q\le 5\times 10^4,x\le 2\times 10^5$，直接枚举 $x$ 的约数，开个桶判断即可，时间复杂度 $\mathcal{O}(q\sqrt{x})$。