[CF-1373G] Pawns
将问题转化一下，可以认为是一个数轴上有若干个点，初始的时候某些位置可能会有多个点，每个点可以向右移动，问最优策略下移到最远的点的坐标，支持增加/删去一个点。
首先考虑没有增加删除操作要怎么做，可以想到逐个加入考虑数轴上的点，将其移动到其初始位置往右（包括初始位置）第一个空的位置即可。可以发现点的考虑顺序并不作要求。
考虑有增加删除的情况，把最终位置连续的点看成一团。显然，因为点的考虑顺序不要求，把操作的点看成是最后一个被考虑的，对于增加，可以直接往所在的团最右边加一个；对于删除，直接去除所在的团的最右边一个。这些操作明显可以用线段树搞定。
[CF-1466G] Song of the Sirens
设 \(S\) 表示询问的串，\(m\) 表示询问的 \(k\) ，首先可以用 \(\verb|kmp|\) 或者 \(\verb|hash|\) (容易 \(\verb|hash|\) 冲突，不建议使用）求出 \(S\) 匹配 \(s_0\) 的答案，设其为 \(f_0\) ，那么其对答案的贡献为 \(2^k f_0\) ，接着求出 \(s_i\) 中经过 \(t_i\) 的匹配次数，设其为 \(f_i\) ，显然可以抽出子串 \(s_{i-1,[|s_{i-1}|-|S|+1, |s_{i-1}|]} t_i s_{i-1, [1,|S|-1]}\) 匹配 \(S\) 即可，其对答案的贡献为 \(2^{k-i} f_i\)，但是这样要做 \(O(k)\) 次，会超时。
这时候需要找性质，可以发现对于满足 \(|s_{i-1}| > |S|\) 的，并且中间位置（即 \(t_{i-1}\) 相同）的，其 \(f_i\) 是相同的，证明比较显然。可以用第一个长度大于 \(|S|\) 的 \(s_i\) 作为两侧，然后枚举中间的字符 \(t\) ，这样得到的匹配次数为 \(g_t\) ，贡献显然为：
后面一串显然可以使用前缀和优化。
[CF-1468L] Prime Divisors Selection
设正整数 \(X\) 的质因数分解为 \(\prod_{i=1}^{m(X)} p(X)_i^{c(X)_i}\) 。
首先考虑如何判断一个序列 \(A\) 是否合法。考虑一个出现于 \(A\) 中某一个元素的质因子 \(p\) ，\(A\) 中必须存在至少两个元素是 \(p\) 的幂。比如对于第一个样例 \(\{2,4,6\}\)，没有元素是质因子 \(3\) 的幂，所以不合法。
接下来可以找到待选集合中所有是某质数幂的所有数。设 \(p(x)\) 表示这个质数，形式化的，有：
而我们需要找到待选集合中所有 \(p(x)\ne -1\) 的数。但是由于数的值域过大，我们不能使用一般的质因数分解，而是需要首先用 \(\verb|Miller_Rabin|\) 判断 \(x\) 本身是否是指数，如果本身不是质数，那么可以首先尝试对其开方，如果成功那么 \(p(x)=p(\sqrt x)\) 这时候转化为求 \(p(\sqrt x)\) ，当然了，也可以尝试将其开三次方，如果成功，直接求 \(p(x^{\frac{1}{3}})\) 如果都不成功，那么枚举 \(\leq x^{\frac{1}{5}}\) 的质数即可，这个范围的质数就可以用线性筛筛出。
求出 \(p(x)\) 之后，考虑对于一个质数 \(p\) ，如果不存在至少两个 \(x\) 满足 \(p(x)=p\) ，那么显然包含质因子 \(p\) 的所有数都是不能被选择的，我们首先找出满足至少两个 \(x\) 满足 \(p(x)=p\) 的所有质数 \(p\) ，组成集合 \(P\) ，用 \(P\) 对所有 \(x\) 进行质因数分解，不成功的就不能被选择，设可以被选择的数组成了新的侯选集合 \(S\) 。同时，为了方便构造方案，对于任意一个 \(P\) 中的质数 \(p\) ，挑出两个满足 \(p(x)=p\) 的 \(x\) ，记为 \(s(p)_0, s(p)_1\) ，然后将它们从 \(S\) 中删去。
接着考虑构造方案。进行分类讨论：
- \(2|P|\ge k\)：
- \(2 \mid k\)：这时候随便抽取 \(P\) 中 \(\frac{k}{2}\) 个质数，对于任何一个被选择的质数 \(p\) ，挑取两个 \(p(x)=p\) 的 \(x\) 加入答案即可。
- \(2 \not|~~ k\) ：这时候需要在剩下的侯选集合中挑出一个数，显然，某个数 \(x\) 能被选择当且仅当 \(2C(x) \leq m\) ，选择了这个数时候，将 \(x\) 所有质因子 \(p\) 的 \(s(p)_0, s(p)_1\) 加入答案。如果还剩一些空位，就在 \(P\) 中跳出一些剩下的 \(p\) 的 \(s(p)_0, s(p)_1\) 加入答案。
- \(2|P|< k\) ：首先将所有 \(p\in P\) 的 \(s(p)_0, s(p)_1\) 加入答案，然后剩下的位置加入 \(S\) 中的数。如果发现不够，就表示无解。
[CF-1469F] Power Sockets
贪心的想，一定是将链的中点连到当前最浅的白点上，至于链的选择顺序，可以是按从大到小选择，可以证明这一定是最优的，接下来只需要用一个动态开点的权值线段树，支持区间加/减，找 \(k\) 大即可。
[CF-1486F] Pairs of Paths
设 \(\mathrm{lca}(u,v)\) 表示路径的 \(\rm lca\) 。设 \(\mathrm{blg}(a,l)\) 表示 \(a\) 往上跳 \(\mathrm{dep}(a)-\mathrm{dep}(l)-1\) 步到达的点。
设两条路径 \((a,b),(c,d)\) 的交只有一个点，若 \(\mathrm{lca}(a,b)=\mathrm{lca}(c,d)=l\) ,那么就表示 \(b(a,l),b(b,l),b(c,l),b(d,l)\) 均不相同；若 \(\mathrm{lca}(a,b) \ne \mathrm{lca}(c,d)\) ，设 \(\mathrm{lca}(a,b)\) 的深度较大，那么当且仅当 \(c\) 或 \(d\) 其中一个点在子树 \(T_{\mathrm{lca}(a,b)}\) 中，且不在 \(T_{b(a,\mathrm{lca}(a,b))}\) 或 \(T_{b(b,\mathrm{lca}(a,b))}\) 中。
显然可以两种情况分开算，容斥一下就行了。
[CF-1487G] String Counting
观察性质，可以发现超过限制的字符至多两个，可以使用容斥计算。首先计算出没有限制的情况，显然是：
对于有一个限制的情况，使用 \(\verb|dp|\) ，设 \(f(i,j,0/1, 0/1)\) 表示当前考虑了前 \(i\) 个位置，其中选定的字符 \(c\) 使用了 \(j\) 个，第 \(i-1\) 个位置是否选择了 \(c\) ,第 \(i\) 个位置是否选择了 \(c\) 的方案数，转移显然。可以发现无论选择了什么字符，\(f\) 都是一样的。
对于有两个限制的情况，也是类似的。
最终答案就是 \(\mathrm{ANS}_0\) 减去第一种情况，加上第二种情况。
[CF-1555F] Good Graph
要先找性质。如果考虑在一个好图中加入一条边，如果这条边使得连通性变化，那么显然这条边可以加入。如果不改变连通性，那么就会构成至少一个环，如果存在一个环和之前的环的边重合了，那么必定会让图变成坏图，不能加入。这个东西要画几下草稿。
那么可以将操作离线，构建出一个森林，对于树边，直接输出 \(\verb|YES|\) ，对于非树边，设其为 \((u,v)\) ，那么树上路径 \(P(u,v)\) 的异或和必须和 \(w(u,v)\) 不同，同时 \(P(u,v)\) 上任何一条边不能被之前的环覆盖。上面这些操作显然可以用并查集，树剖\(+\)线段树完成。
[CF-1476F] Lanterns
首先要将可行性转为求最优值，然后用 \(\verb|dp|\) 求解。
设 \(f(i)\) 表示考虑了前 \(i\) 个点，当前能覆盖的最长前缀长度。可以发现这个数组单调不降。考虑两种操作，首先是向左的操作。显然可以得到：
因为 \(f(i)\) 单调不降，所以可以变成：
这个转移可以是用二分 \(+\) \(\verb|ST|\) 表优化。
另一种是向右的，这种可以使用的条件显然是 \(f(i-1) \ge i\) ，
最终的可行条件显然是 \(f(n) \ge n\) 。至于方案的构造，从后往前构造。记住 \(f(i)\) 由哪条转移得到。如果是第一条，显然 \(i\) 选择向左，否则就是向右的。如果选择向左，记住最小的 \(f(j) \ge i - p_i - 1\) 的 \(j\) ，设为 \(t(i)\) ，那么 \(t(i)+1 \cdots i - 1\) 都可以设为向右，然后跳到 \(t(i)\) 继续构造。
[CF-1388E] Uncle Bogdan and Projections
首先有性质：最优解一定有一个左端点和一个右端点共线。因此可以先把所有左端点和右端点连线形成的直线的倾斜角，时间复杂度 \(O(n^2)\) 的，但是有些是不合法的，而且不能逐个判定，考虑将倾斜角从小到大排序，逐个考虑的过程可以看成是将角度从左往右摆的过程。将这些倾斜角分成两类，一类是左端点的纵坐标较右端点大，另一类则反之，第 \(i\) 个倾斜角可以选择当且仅当前 \(i\) 个倾斜角中，两类的个数的绝对值相差 \(\leq 1\) 。
接下来明显可以用三分直接算出答案。