CF1900D

*2000
*dp,rongchi
首先就排个序，答案为 \(\sum_{i=1}^n \sum_{j=i+1}^n gcd(a_i,a_j) \times (n-j)\)。
考虑枚举 \(j\)，那么现在的想法就是对于一个 \(j\) 求合前面数的 \(gcd\) 的和。这个东西就是一个经典容斥，令 \(f_x\) 表示当前 \(x\) 的倍数的 \(a\) 的个数，\(g_x\) 表示 \(gcd(a_i,a_j)=x\) 的 \(a_j\) 数量。那么首先令每个 \(g_x=f_x\) 然后容斥，启动！对于每个 \(g\) 就减一下他倍数的 \(g\)，但是值域太大了，不过没关系，就对于每个有值的 \(g\) 对他的因数减一下就行，但是这样的话更新顺序需要 reverse 一波，就在预处理因数的时候 reverse 一下即可。
该套路： P1447 [NOI2010] 能量采集 CF839D Winter is here

CF840B

*2100
*dfs,spanning tree
感觉，可能，也是比较套路的一个题？
首先，如果每个 \(d\) 都确定了，那么显然这个时候就首先可以判一下总度数，如果是奇直接叉掉。
然后的话考虑如果有=-1 的 \(d\) ，那么就以这个点来 \(dfs\) 来一波生成树，为啥捏？等会解释。在 \(dfs\) 到叶子结点的时候显然必须要他的父节点来搞，如果他的 \(d=1\) 那么只能在父节点操作一波，就把连接两点的边来操作，就这样从底下网上做，对每个点记录一下收否需要在父节点帮忙选一条边 \(flip\)，然后因为我最顶上的点（根结点）的 \(d\) 是 \(-1\)，所以最后一定可以都调整好。
然后是全都确定的，可以证明这个时候随便选个结点做都可以，当然似乎我只会感性证明。。。。。

CF900D

*2000
*dp,rongchi
首先因为 \(gcd=x\)，那么显然所有数都是 \(x\) 的倍数那么就有和应该也是 \(x\) 的倍数，那么如果 \(y\) 不是 \(x\) 的倍数就寄了。这个判完以后可以把所有数都除掉 \(x\)，那么问题转化为：拿一些数满足 \(gcd=1\) 且和为 \(\frac{y}{x}\)，求方案数。我们令 \(f_x\) 表示和为 \(x\) 且 \(gcd=1\) 的方案数，接下来考虑咋算。正难则反，首先不限制 \(gcd\)，此时插板一下可以算出来方案数是 \(2^{x-1}\)，然后考虑去掉 \(gcd>1\) 的情况，那么此时可以所有数除掉 \(gcd\)，此时的和就是 \(\frac{y}{gcd}\)，那么 \(gcd>1\) 的方案数就是 \(\sum f_{\frac{x}{gcd}}\) 其中满足 \(gcd>1\) 且 \(gcd|x\)，直接做一下就行了。

CF1875D

*1600
*dp
令 \(f_i\) 表示 \(mex=i\) 时的 \(m_{min}\)。然后转移也比较简单：
\(f_i=min(f_j+(c[i]-1) \times j+i)\)
c[i] 表示 \(a_x=i\) 的数量。

CF730J

*1900
*dp,greedy
首先第一问比较简单，就对 \(b\) 从大到小排个序，然后贪心的选一下即可。
然后看第二问，操作次数=\(\sum a-选中a\)，然后就 \(dp\) 一下就差不多了，记个 \(选中a\) 的 \(max\) 即可。

CF980D

*2100
*dsu,math
感觉，可能，有一点点点点想法的题。
注：以下 \(ok\) 表示是完全平方数。
首先第一问肯定是贪心的选，能一起就一起。
然后证明一下平方的传递性（？）：若 \(ab\) ok，\(bc\) ok，则 \(ac\) ok.这个感觉还是比较好证的吧，质因数单独考虑，令三个数指数mod 2 分别为 \(x,y,z\)，那么有 \((x+y) mod 2 = 0,(y + z) mod 2 = 0\) 减一下就得到 \((x-z) mod 2=0\) 等价 \((x+z) mod 2=0\)，然后就做完了。
然后就并查集合并一下，一个子段的答案等价于连通块个数，当然需要特判断一波0吧。

CF213C

*2000
*dp
感觉，可能，比较没有想法的题。
就令 \(f_{i,j,k}\) 表示 \(i\) 步，第一条走到第 \(j\) 行，第二条走到第 \(k\) 行，然后算一下，如果相遇就算一次，否则算两次就差不多了。
答案是 \(f_{2n-1,n,n}\)

CF1151E

*2100
*math
知周所众，链上的连通块数量=点数-边数，然后就对每个点和每条边考虑一波算贡献，每个点的话就要满足 \(l \leq a_i\) 且. \(a_i \leq r\)，所以这个点的贡献就是 \(a_i(n-a_i+1)\)，然后求个和就是点的总贡献，然后考虑 \((i,i+1)\) 这个边，然后就是 \(l \leq a_i\) 且 \(l \leq a_{i+1}\) 且 \(a_i \leq r\) 且 \(a_{i+1} \leq r\)，然后算一下也是差不多了。

CF128C

*2000
*combinatorics
行，列独立，然后每个东西都组合数算一下就行了，感觉没有好写的？
\(comb(n-1,2k)*comb(m-1,2k)\)