A-CF755D
考虑每次加边产生的贡献。
发现每次加边的贡献是这条边与别的边的交点数量加 \(1\)。所以可以用线段树或树状数组等数据结构维护，注意要令 \(k=\min(k,n-k)\)。
B-CF746F
考虑双指针维护听的歌的区间，同时用 \(2\) 个 multiset \(s1,s2\) 分别维护只听一半的歌的原长度和全听的歌的原长度。
对于一首新加进来的歌：
若只听一半的歌的数量不足 \(w\) 个且剩余时间足够就加入 \(s1\) 中。
否则若当前歌的长度大于 \(s1\) 中最短的歌的长度且剩余时间足够就加入 \(s1\) 中并把 \(s1\) 中最短的歌加入 \(s2\) 中。
否则若剩余时间足够就加入 \(s2\) 中。
否则就要考虑将左端点弹出，分类讨论左端点在哪个集合中即可。
C-CF1304F2
状态很好想，\(f_{i,j}\) 表示前 \(i\) 行，第 \(i\) 行选 \([j,j+k-1]\) 时前 \(i\) 行拍到动物的最大值。容易发现，\(j\) 一定不超过 \(m-k+1\)，再靠右就不可能优了。若不考虑重复选的有转移：
\[f_{i,j}=\max\limits_{p=1}^{m-k+1}\{f_{i-1,p}+\sum\limits_{q=p}^{p+k-1} a_{i,q}\}+\sum\limits_{p=j}^{j+k-1} a_{i,p} \]，若要减去重复贡献，就把 \([j,j+k-1]\) 这段 \(a\) 的贡献赋为 \(0\)，左端点右移时加回左端点贡献，减去此时对应右端点贡献，线段树维护区间加，区间 max 即可。
D-CF1174E
容易发现前缀 gcd 一定是不增的，且后面的一定是前面的约数。将第一个数表示为 \(\prod\limits p_i^{c_i}\)，此时排列价值的最大值为 \(\sum c_i\)，即每次 gcd 除以一个约数。想要使排列价值最大，只需使第一个数的 \(\sum c_i\) 最大。若要使范围内的一个数的 \(\sum c_i\) 最大，则这个数必然是 \(2\) 的若干次幂乘上 \(3\) 的若干次幂，因为一个 \(5\) 就不如两个 \(2\) 划算了。而且 \(3\) 最多有一次幂，因为 \(3^2>2^3\)。于是设 dp 状态 \(f_{i,j,k}\) 为前 \(i\) 位，此时 gcd 为 \(2^j\times 3^k\)，转移的时候 gcd 可以是上一位的 gcd 除以 \(2\) 也可以是除以 \(3\)。
E-CF1679F
对于本质相同的一些数，选一个字典序最小的作为代表，原题相当于求代表数一共有多少个。从前往后填，容易证明第 \(i\) 位能填 \(a_i\) 当且仅当满足每个元素都能和要填的 \(a_i\) 交换的极长后缀 \(a_p,a_{p+1},\dots,a_{i-1}\) 中所有数均小于 \(a_i\)。于是设 \(f_{i,s}\) 为前 \(i\) 位，第 \(i\) 位不能填的数集为 \(S\) 的方案数，答案即为 \(\sum f_{n,S}\)。预处理后面填上 \(i\) 后 \(S\) 会变成的数集 \(to_{i,S}\) 就能转移了。
F-CF809C
打表可以发现这个矩阵是个分形，然后考虑填数的过程。当行列编号和数都减一后，一次看二进制下的每一位，会发现当 \(i,j\) 这一位不同时就会放到左上和右下，相同时就会放到左下和右上，而这个过程和异或很想，所以可以得出一个结论：\(a_{i,j}=(i-1)\oplus(j-1)+1\)。
知道这个结论后考虑在 \(i,j,a_{i,j}\) 都减一的前提下进行数位 DP：\(dp_{0/1,0/1,0/1,k}\) 表示考虑前 \(k\) 位，\(i\) 是否到行的上界，\(j\) 是否到列的上界 \(i\oplus j\) 是否到上界 \(p\) 时有多少种方案（当 \(i,j\) 确定时 \(a_{i,j}\) 也能确定）。
G-CF1698F
首先可证 \(a\) 能转化成 \(b\) 的充要条件是 \(a_1=b_1 \and a_n=b_n\) 且 \(a\) 和 \(b\) 相邻元素组成的无序数对集合相同。
必要性：由于只有两端点相等的区间能翻转，所以 \(a_1\) 和 \(a_n\) 的值不会有变化，且每次翻转区间内部的相邻元素无序数对不会变化，由于两端点相等，所以两端点与其相邻元素数对也不会发生变化。
充分性：可依照一下方案构造。
建一个图 \(G\)，将原序列的值作为点，将相邻元素之间建无向边，那么 \(a\) 和 \(b\) 都给出了一条 \(G\) 的欧拉路径 \(A\) 和 \(B\)。容易发现操作是可逆的，所以问题转化成每一次可以操作 \(a\) 和 \(b\)，使最后 \(a\) 和 \(b\) 相同。若 \(A\) 和 \(B\) 在 \(x\) 的出边不同，\(A\) 走 \((x,y)\)，\(B\) 走 \((x,z)\)，容易发现走这步之前与 \(x\) 相连的边还有 \(2k+1(k\in \N)\) 条没走过，也就是 \(k\) 条入边，\(k+1\) 条出边。
- 若在 \(A\) 中 \((x,z)\) 是入边，那么 \(A\) 翻转 \(x \rightarrow y \rightarrow \cdots \rightarrow z \rightarrow x\) 后 \(A\) 和 \(B\) 在这步就会走相同的边。\(B\) 中 \((x,y)\) 是入边同理。
- 若 \(A\) 和 \(B\) 中 \((x,z),(x,y)\) 都是出边，若 \(A\) 和 \(B\) 中 \((c,x)\) 都是入边，那么 \(A\) 翻转 \(x \rightarrow y \rightarrow \cdots \rightarrow c \rightarrow x\)，\(B\) 翻转 \(x \rightarrow z \rightarrow \cdots \rightarrow c \rightarrow x\) 就能保证在这一步走相同的边。发现 \(A\) 和 \(B\) 都要在剩下的 \(2k-1\) 条边中选 \(k\) 条入，\(k-1\) 条出，根据抽屉原理，必有 \(1\) 条入边相同，于是一定能找到 \(c\)。
按照上面的证明构造一种方案即可。
H-CF1418F
构造 \(a,b\)，两个数使 \(x_2=\dfrac{x_1}{a}b,y_2=\dfrac{y_1}{b}a\) 且 \(a\mid x_1,b\mid y_1\)，不难证明当 \(a=\dfrac{x_1}{\gcd(x_1,x_2)}\) 时 \(a,b\) 存在。所以当 \(a,b,x_1\) 确定时 \(x_1,x_2,y_1,y_2\) 可以确定，所以我们的目标就变成了找出一对 \((x_1,a)\)，由于 \(a\mid x_1\)，所以有效的 \((x_1,a)\) 只有 \(n\log n\) 对。
当枚举出一对 \((x_1,a)\) 后，就要快速查询是否存在一对 \((y_1,b)\) 满足以下条件：
\[\begin{aligned}y_1\leq m\\\lceil\dfrac{l}{x_1}\rceil\leq y_1\leq\lfloor\dfrac{r}{x_1}\rfloor\\\dfrac{x_1}{a}b\leq n\\a< b\end{aligned} \]随着 \(x_1\) 的增大，\(y_1\) 的范围会越来越小，所以可以用双指针加 set 维护 \(y_1\) 的取值，同时选取最小的 \(b\)。复杂度 \(O(n\log^2 n)\)，需要轻微卡常才能通过原题。
标签：gcd,dfrac,sum,20230207,端点,题解,s1,模拟,rightarrow From： https://www.cnblogs.com/lxy-2022/p/17129929.html