闲话
卡了好几道题了，怎么回事呢。
A. CF1796C
不难想到最优解应该是某个数 \(x\) 不断乘上 \(t\)，即这个集合（大致）可以表示为：
容易想到令 \(x=2\) 先求出最大 \(k\)，然后直接二分底数 \(t\) 的最大值。
过不了样例怎么回事呢？发现可以将其中一个 \(2\) 改成 \(3\)，特判一下于是过了。
只改一个是因为 \(\frac{3^2}{2^2} \gt 2\)，这样就可以再塞一个 \(2\)；只能改成 \(3\) 同理。
B. CF1798C
什么魔怔题啊。
考虑两个限制，一个是区间 \(\gcd \{ a_i \times b_i \}\)，另一个是 \(lcm \{ b_i \}\)。
只要 \(\gcd\) 是 \(lcm\) 的倍数即可。
这两个限制分别满足了 \(a \times b\) 的上界和 \(b\) 的下界，因此是对的。
C. CF1799C
感觉这题十分困难。
先手搓了三种决策取最优输出，然后愉快地 WA 了。
显然和出现次数奇偶性相关，最优决策应当是：
- 从小到大考虑字符 \(i\)。
- 对于 \(\geq 2\) 的直接左右各塞一个，直到 \(\leq 1\)。
- 如果还剩 \(1\) 个，考虑让它和一个更大的字符 \(j\) 配对。
- 如果现在只剩下 \(i,j\)，则先把 \(j\) 中 \(\geq 2\) 的左右塞满，然后中间放 \(j,i\)。
- 否则观察样例，做如下构造：将 \(j\) 和比 \(j\) 大的按顺序塞进去，然后放 \(i\)。
D. CF1800F
恰好出现 25 种，考虑枚举哪一种没有出现。
然后枚举对应的字符串，异或一下用桶记即可。
复杂度 \(O(26 n)\)。
E. CF1796D
直接 DP，设 \(f_{i,j}\) 表示前 \(i\) 个使用了 \(j\) 次加法最大值。
注意无解情况以及统计答案边界问题。
好像还有诡异单调队列做法，大致思想是枚举删左右多少，保留中间。
F. CF1516D
相当于分割成若干两两 \(\gcd=1\) 的区间。
不妨求出每个点往后延申最长长度使得两两 \(\gcd=1\)，于是不难想到倍增，然后做完了。
G. CF1896E
诡异题。
考虑移动过程中相对位置是不变的。
断环为链，从起点向终点连边得到若干有向线段，则对于两个包含关系的线段，小的一定比大的更早到。
因此一个区间 \([l,r]\) 所需的步数是它原本需要的步数减去区间内包含的区间数量。
二维数点问题，直接树状数组。
H. ARC111D
获得了 11 发罚时的好成绩。
如果一条边两个点的权值不同，则一定大向小连边。
否则由于两个点能到达的点数相同，它们一定在同一个强连通分量里。
然而同一个强连通分量里面的边由已经定向的边确定，所以直接从每个点开始 dfs 覆盖边即可。
I. CF1795F
不难注意到有单调性，于是二分。
考虑随便选一个点为根，然后从下往上贪心，能往下放就往下放（因为往上走的要留给子树外）。
然后写了一个不知道是什么的东西就过了。
J. CF2164E
第一眼就是重构树，但是并不是很敢写，因为权值是二元的（编号、边权）。
但是这并不影响。我们按照编号建重构树，则一个点能获得的最小点权应当是它和它祖先中边权的最小值，这个是好做的。
考虑代价最少是边权和，现在至少需要额外花费多少代价让它能“一笔画”回到原点。
一笔画提示我们联想到欧拉回路，要求每个点 \(deg\) 为偶数。记 \(deg\) 为奇数的点为特殊点。
问题变成重构树上有 \(k\) 个特殊点叶子，求出配成 \(\frac{k}{2}\) 对的最小代价。
根据贪心，祖先最小点权是单调不升的。
所以从下往上拓扑，如果子树内有偶数个特殊点则直接配对，奇数个就留给祖先。