【好题乱做】ABC-G
ABC216G 01Sequence
设 \(f_i\) 表示前 \(i\) 个中 \(0\) 的个数，则条件可以转化为差分约束的模型。发现边权非负，跑 Dijkstra 即可。
ABC217G Groups
设 \(f_{i,j}\) 表示前 \(i\) 个数分为 \(j\) 组的方案数，则可以对 \(i\) 放入之前的一组还是新开一组讨论，得到转移方程。
\[f_{i,j}=f_{i-1,j-1}+f_{i-1,j}\times (j-\lfloor \dfrac{i-1}{M}\rfloor) \]ABC222G 222
BSGS 板子。
ABC228G Digits on Grid
直接 dp 可能会算重，但是数据范围非常小，可以考虑将“每次选了哪种数字后下一步能到达的行/列”作为状态，然后 dp 套 dp。
具体地，预处理 \(g_{i,S,0/1}\) 表示当前的行/列集合为 \(S\)，选了数字 \(i\)，下一步能到达的列/行集合。再设 \(f_{i,S}\) 表示当前到第 \(i\) 个字符，并且行/列集合为 \(S\) 时的方案数。转移方程式不难得出。
\[f_{i,g_{j,S,0/1}}\leftarrow f_{i,g_{j,S,0/1}}+f_{i-1,S} \]ABC236G Good Vertices
设 \(f_{i,j}\) 表示从 \(1\) 走到 \(i\) 恰好用 \(j\) 步的最小时间，写出转移式后便可以用矩阵快速幂优化。
ABC242G Range Pairing Query
设 \(cnt_i\) 表示区间内颜色为 \(i\) 的个数，则答案为 \(\sum_{i=1}^N\lfloor \frac{cnt_i}{2}\rfloor\)。这是莫队板子，记录 \(cnt_i\) 即可。
ABC243G Sqrt
设 \(f_n\) 表示以 \(n\) 开头的方案数，得出转移方程式。
\[f_n=\sum_{i=1}^{\lfloor\sqrt{n}\rfloor}f_i=\sum_{i=1}^{\lfloor\sqrt{n}\rfloor}\sum_{j=1}^{\lfloor\sqrt{i}\rfloor}f_j=\sum_{i=1}^{\lfloor\sqrt[4]{n}\rfloor}(\lfloor\sqrt{n}\rfloor-i^2+1)f_i \]预处理 \(6\times 10^4\) 以内的 \(f_n\) 即可。
ABC250G Stonks
考虑反悔贪心，每天的股票有三种贡献，分别是 \(-x,0,+x\)，因此先假设每天都是 \(+x\)，然后用优先队列找到在它之前的一个时间更改当时的状态。
通俗地讲，一开始进行两次 push 操作，并将 \(x\) 计入答案，之后弹出一次，代表从 \(+x\) 变为 \(0\)，再弹出一次，代表从 \(0\) 变为 \(-x\)。
ABC252G Pre-Order
考虑区间 dp，设 \(f_{i,j,0/1}\) 表示编号为 \(P_i\) 到 \(P_j\) 的这些点在树上形成一棵/多棵子树的方案数，对于前者可以直接从 \(f_{i+1,j}\) 转移过来，对于后者可以枚举 \(P_i\) 子树内的最后一个点 \(k\)，从而得到转移方程。
\[f_{i,j,0}=f_{i+1,j,0}+f_{i+1,j,1} \]\[f_{i,j,1}=\sum_{k=i}^{j-1}[P_i<P_{k+1}]f_{i,k,0}\times (f_{k+1,j,0}+f_{k+1,j,1}) \]ABC257G Prefix Concatenation
直接 dp，设 \(f_i\) 表示将 \(T[1,i]\) 分割成若干个 \(S\) 的前缀时的最小个数。则有转移方程式：\(f_i=\min\{f_j\}+1\)，其中要求 \(S[1,i-j]=T[j+1,i]\)。
不难发现 \(f_i\) 单调不降，因此每回需要找到最小的满足条件的 \(j\)。发现这个条件的形式类似于 border，因此对 \(S+T\) 跑一遍 KMP 即可。
ABC258G Triangle
枚举边 \((i,j)\)，用 bitset 统计有多少个点 \(k\)，使得 \((i,k)\) 和 \((j,k)\) 都有边。
ABC263G Erasing Prime Pairs
绝大多数能使得 \(x+y\) 是质数的 \((x,y)\) 必定是一奇一偶，除了 \((1,1)\)，因此这是一个二分图，在满足对数足够多的同时还要最大化剩余 \(1\) 的个数，跑最小费用最大流即可。
ABC266G Yet Another RGB Sequence
将 \(\texttt{rg}\) 看成一个整体 \(\texttt{s}\)，先把 \(K\) 个 \(\texttt{s}\)，\(R-K\) 个 \(\texttt{r}\) 和 \(B\) 个 \(\texttt{b}\) 排好。对于剩下的 \(G-K\) 个 \(\texttt{g}\)，有 \(R+B+1\) 个空可以插入，由于不能插到 \(\texttt{r}\) 后面，因此只有 \(B+K+1\) 个空能插，答案即为 \(\binom{B+R}{B}\binom{R}{K}\binom{B+G}{B+K}\)。
ABC272G Yet Another mod M
本质是判断是否存在 \(M\) 使得模 \(M\) 意义下存在绝对众数，转化为 \(M\mid (A_i-A_j)\)，每次随机出两个下标 \(i,j\)，判断 \(|A_i-A_j|\) 的所有因数是否满足条件即可。
ABC283G Partial Xor Enumeration
线性基第 \(k\) 小板子题。
ABC293G Triple Index
设 \(cnt_i\) 表示区间内颜色为 \(i\) 的个数，则答案为 \(\sum\binom{cnt_i}{3}\)，莫队板子。
ABC294G Distance Queries on a Tree
维护 \(dis_u\)，修改边权等同于子树加，用线段树维护。
ABC297G Constrained Nim 2
打表猜结论，发现 \(\operatorname{SG}(n)=\lfloor\frac{n\bmod (L+R)}{L}\rfloor\)。
ABC299G Minimum Permutation
ABC302G Sort from 1 to 4
最终的序列是确定的，设 \(f_{i,j}\) 表示原来是 \(i\)，最终变成 \(j\) 的位置的数量。考虑 \(i\) 向 \(j\) 连 \(f_{i,j}\) 条有向边，则对于每个环需要交换 \(siz-1\) 次。因此总的交换次数就是 \(n-tot\)，其中 \(tot\) 表示环的数量。
自环的个数是 \(f_{i,i}\)，二元环的个数是 \(\min\{f_{i,j},f_{j,i}\}\)。剩下的三元环和四元环在不存在二元环的条件下一定都包含同一个点，因此剩余环的个数就是 \(\max\{f_{i,j}-\min\{f_{i,j},f_{j,i}\}\}\)。
ABC305G Banned Substrings
在 AC 自动机上做矩阵快速幂优化 dp 即可。
ABC308G Minimum Xor Pair Query
设 \(\{a_n\}\) 从小到大重排后得到 \(\{b_n\}\)，则有结论：
\[\min_{1\le i<j\le n}\{a_i \oplus a_j\}=\min_{1\le i\le n-1}\{b_i \oplus b_{i+1}\} \]开两个 multiset，一个维护每个数当前的排名，另一个维护重排后相邻两项的异或值。每次操作时算出它与前一个数和后一个数分别异或后的值，在记录答案的 multiset 中进行增删操作。
ABC312G Avoid Straight Line
从反面考虑，计算 \((x,y,z)\) 在同一条链上的方案数，在 lca 处统计答案。设 \(f_u\) 表示目前遍历到的子树内（包括 \(u\)）有多少对祖孙关系，直接做即可。
ABC313G Redistribution of Piles
发现操作 2 在所有的操作 1 之后才有意义。对原数列排序后差分，设差分序列为 \(\{b_n\}\)，则操作 1 等价于给 \(\{b_n\}\) 中第一个非零位置 \(-1\)，操作 2 等价于给 \(b_1+1\)。
枚举进行了多少次操作 1，可以得到答案为：
\[b_1+1+\sum_{i=2}^n\sum_{j=1}^{b_i}(\lfloor\frac{\sum_{k=1}^{i-1}b_k(n-k+1)+j(n-i+1)}{n}\rfloor+1) \]内层的求和可以用类欧算法来优化复杂度。
ABC315G Ai + Bj + Ck = X (1 <= i, j, k <= N)
枚举 \(i\) 后就是 exgcd 板子。
ABC321G Electric Circuit
ABC325G offence
考虑区间 dp。设 \(f_{i,j}\) 表示区间 \([i,j]\) 最少剩下几个字符，则有转移方程。
\[f_{i,j}=\min_{i<l\le j}\{f_{i,l-1}+f_{l,j}\} \]当 \(S_i=\texttt{o}\) 且 \(S_l=\texttt{f}\) 并且 \(f_{i+1,l-1}=0\) 时，\([l+1,j]\) 的区间可以再删掉 \(K\) 个，能够得出转移方程。
\[f_{i,j}\leftarrow\min\{f_{i,j},\max\{f_{l+1,j}-K,0\}\} \]ABC328G Cut and Reorder
ABC338G evall
考虑正常从左向右计算的过程，需要记录当前乘积式之前的总和 \(s\)，当前数之前的乘积式的值 \(m\)，当前数的值 \(n\)。将转移写成矩阵形式，对于出现乘号时的非线性转移式，可以将维护的 \(n\) 替换成 \(mn\)。
需要计算每一对 \((i,j)\) 的和，直接在所有出现数字的位置累加矩阵并统计答案即可。
ABC339G Smaller Sum
离散化后对值域建可持久化线段树。
ABC346G Alone
对于每个数字 \(x\)，在相邻两个 \(x\) 之间的区间都满足条件，直接转化为矩形覆盖，最终要求的就是矩形并，扫描线板子。
ABC350G Mediator
并查集维护当前所在树的根，以及每个点的父亲。每次连边类似启发式合并，重构 \(siz\) 较小的树。询问则只有三种情况。
ABC353G Merchant Takahashi
设 \(f_i\) 表示第 \(i\) 次贸易后的最大收益，有转移式：
\[f_i=\max\{f_j+C\times|T_i-T_j|\}+P_i \]拆绝对值后线段树优化即可。
ABC358G AtCoder Tour
发现最优策略一定是走到某个格子后一直不动，那么只需求出从起点走若干步到某个格子时的价值。设 \(f_{l,i,j}\) 表示从起点走 \(l\) 步后到达 \((i,j)\) 的最大价值，每次向四个方向转移即可。
ABC360G Suitable Edit for LIS
设 \(f_i\) 表示以位置 \(i\) 结尾的最长 LIS 长度，\(g_i\) 表示以位置 \(i\) 开头的最长 LIS 长度。枚举修改的位置 \(i\in [2,n-1]\)，答案即为 \(\min\{f_{i-1}+g_j\}\)，其中要求 \(j\ge i\) 且 \(a_j\ge a_{i-1}+2\)。可以用树状数组优化。对于 \(i\in \{1,n\}\)，特殊考虑即可。
ABC362G Count Substring Query
AC 自动机板子。
ABC366G XOR Neighbors
本质上是对于每个二进制位的异或方程组，由于 \(n\le 60\)，因此可以强制要求某个点的某个二进制位为 \(1\) 后高斯消元。
ABC368G Add and Multiply Queries
答案不超过 \(10^{18}\)，并且有 \(A_i\ge 1\)，那么询问的区间中满足 \(B_i\ge 2\) 的至多有 \(\log\) 个。线段树维护 \(\{A_n\}\) 的和，set 维护 \(B_i\ge 2\) 的位置即可。