感觉本地编辑器有点卡了就先放到博客园上
1. ccpc 2023 深圳 M 3 Sum
先取模，就是第 \(x\) 位加给 \(x\bmod K\) 位，\(\mathcal{O}(len)\) 复杂度。然后就只有相加为 \(0,M,2M\) 这三种情况，找几个模数进行 check 就行。
2. ccpc 2023 深圳 E Two in One
考虑俩颜色咋做。先想想答案上界，假设出现了 \(x,y\) 次，那么答案至多是 x|y|(highbit(x&y)-1)，首先 highbit 以上的位变了肯定寄了，其次发现下面的部分能全变成 1，所以这个就是答案。出现次数至多只有 sqrt 个不同的数所以直接枚举就行。Code。
3. ccpc 2023 深圳 D Bot Brothers
可以下模仿棋，所以后手一定不会输，考虑后手怎样才能赢。如果后手必胜，对于先手在 \(x\) 节点，能够唯一确定后手所在节点，从下往上推就行了。
4. CF1835F Good Graph
匈牙利找最大匹配，当一个点找不到最大匹配的时候，尝试增广所走到的所有点就是 NO 需要求的集合（若不满足条件说明会增广成功）。
YES 的情况下，求出完美匹配后考虑一条非匹配点 \(x\to y\)，令 \(pos_y\) 表示 \(y\) 的匹配点，这时发现 \(x\) 在 tight 集合中说明 \(pos_y\) 一定也在 tight 集合中，如果不在的话考虑包含 \(x\) 的 tight 集合，它存在一个完美匹配，而这个完美匹配完全可以取全局完美匹配的子集，从而 \(pos_y\) 必须在 tight 集合中。
从而包含 \(x\) 的最小 tight 集合一定是这样不断 push \(pos_y\) 直到不需要松弛为止得到的集合。另一方面对于所有的 tight 集合想让它们唯一地被一些小的 tight 集合确立，发现若干个包含某个左部点的最小 tight 集合不交并起来就能生成所有的 tight 集合。反证对于一个 tight 集合挑选出它包含的最大的《包含某个点的最小 tight 集合》左部点 \(X\) 及其对应右部点 \(P(X)\)，剩下若干左部点 \(Y\) 及其对应右部点 \(P(Y)\)，如果 \(X\leftrightarrow P(Y)\) 有边，与其为最大的《》定义矛盾，如果 \(Y\leftrightarrow P(X)\) 有边，与其为 tight 集合矛盾。
综上，仅需满足 \(x\to pos_y\) 这样连出来的传递闭包相同，即说明原二分图等价。根据传递闭包构造边数最少的有向图即可，scc 内部连成环，scc 之间不断尝试让它连向拓扑序最小且仍不能到达的 scc。bitset 优化时间复杂度 \(\mathcal{O}(n^3/w)\)
5. CF1835D Doctor's Brown Hypothesis
对每个 scc 考虑，\(k\) 充分大大概说明每个环都能任意走好几圈，所以和所有环的 gcd 有关。具体而言：首先强连通可以找到经过所有点的路径，假设所有简单环是 \(len_1\leq len_2\leq ...\leq len_m\)，每个 \(len\) 可以走任意多次，假设 \(g=\gcd\{len\}\) 由同余最短路和裴蜀定理可以得出 \(\geq (len_1-1)len_m\) 且是 \(g\) 倍数的所有长度都能凑出。注意这里并未考虑起点直接走到终点（不走环的那些路径）对路径长度的增量。
先假定结论成立，也就是 \(x\to y\) 合法当且仅当存在一条路径长为 \(d\) 且满足 \(d\equiv k\pmod g\)。先尝试求出 \(g\)。
边带权有向图所有环长 gcd。这里出现一个染色的技巧，对于某个 scc，\(d\mid g\) 当且仅当能够将每个点染成 \(col_i\in [0,d)\) 的颜色，使得对于任意 \((x,y,w)\) 满足 \(col_y-col_x=w\pmod d\)。
充分性就考虑一个环上所有边 \(col_y-col_x=w\pmod d\) 加起来，左侧是 \(0\)，右侧就是环的总权值，也就是 \(d\) 整除这个环的总权值。
必要性就构造。因为强连通所以可以找到外向生成树并令 \(dep_x=dep_{fa}+w\)，树边已经满足。（这里长度是原图中路径边权和，而权值是 \(col_v-col_u\) 的值，权值始终在模 \(d\) 意义下讨论）对于非树边 \((u,v,w)\)，\(rt\to v\to rt\) 权值为 \(0\)，而走树边 \(rt\to v\) 权值为 \(dis_v\)，那么所有 \(v\to rt\) 路径权值为 \(-dis_v\)，同时 \(rt\to u\) 树边路径权值为 \(dis_u\)，\(rt\to u\to v\to rt\) 路径权值为 \(0\)，即可得证 \(u\to v\) 路径权值为 \(w\)。
首先找到 dfs 树并令 \(dep_x=dep_{fa}+w\)，现在对非树边满足条件，并且其 \(col_i=dep_i\bmod g\) 一定是想要的合法的 \(col\)，但是不知道 \(g\) 是多少。还要对所有非树边满足条件，于是对于所有非树边 \((x,y)\) 不断令 \(g\gets \gcd(g,|dep_y-dep_x-w|)\) 即可得到 \(g\)。
这里回过来看结论为什么成立，首先 \(x\) 到 \(y\) 之间的某条路径模 \(g\) 一定是 \(col_y-col_x\)，其中最短的大小 \(<(n-1)^2\)，而 \((n-1)^2+(len_1-1)len_m\leq (n-1)(2n-1)\leq n^3\) 所以结论成立。
得到 \(g\) 和 \(col\) 后，回过头看结论，考虑上起点走到终点不走环的路径，发现 \(x\to y\) 满足条件就是需要 \(col_y-col_x=k\pmod g\)，也有 \(col_x-col_y=k\pmod g\)，当 \(g\mid k\) 时就是 \(col_x=col_y\)，否则就必须要 \(2\mid g\) 且 \(k\bmod g=\frac{g}{2}\)，对 \(col\) 开桶即可完成统计。
6. LOJ3033【口胡】
因为是求最大值所以绝对值可以拆。扫描线，对于 \(i\) 让它在 \(i+A_i\) 加入，\(i+B_i+1\) 删除，枚举 \(j\) 的时候在 \([j-B_j,j-A_j]\) 中更新答案，那么现在线段树要维护区间以下信息：最大的 \(h_j\)（这个是完整覆盖区间 也就是会下放的一个标记），最大的 \(-h_i\)，最大的已经更新为答案的 \(h_j-h_i\)（后面两个是信息需要子树合并，前者需要支持单点修改，后者是区间打标记的时候进行更新答案）。
直接套模型的做法好像就是，如果一个 \(i\) 被插入了标记为 \(-h_i\)，没被插入是 \(-inf\)，然后一个 \(j\) 要更新答案的时候，区间 \(+h_j\)，再区间 \(-h_j\)，维护区间历史最大值。（其实应该和我编的本质相同）
7. CCPC Final 2023 M Bot Friends
考虑第一个行动完了会对整个游戏有啥影响，比方说第一个向右，那么唯一的影响就是右侧紧挨着的那个向左会带来 1 的答案，同理接下来左侧的向右也能行。然后直到不找了为止，剩下的和这段就没有关系了可以直接切下来。
所以相当于每次用 1 的代价删掉连续的 >>><<<，其中 > 和 < 的个数相差不能超过 1。这样就很好 dp 了，大概是 \(f[i][j]\) 考虑完了前 \(i\) 位还有 \(j\) 个 <，为了表示一个正在删的段再设一个 \(g[i][j]\)，如果来了一个 < 可以先匹配上 0/1/2 个 > 从 \(f[i][j]\) 进入 \(g\) 表示还需要 \(j\) 或 \(j-1\) 或 \(j+1\) 个 <，\(g\) 遇到 < 可以到 \(g\) 继续删，也可以回到 \(f\) 表示这一段删完了。时间复杂度 \(\mathcal{O}(n^2)\)。
8. CCPC Final 2023 A Add One 2
相当于不断让 \(a\) 某个数增加使得它能删完，然后求最小的 \(\sum a\)。先考虑判定答案是不是初始的 \(\sum a\)，考虑 \(4\ 2\) 这样子就要求 \(4\) 那个位置至少 \(2\) 个前缀减，\(2\ 5\) 这样子就要求 \(5\) 这个位置至少 \(3\) 个后缀减。那么从前往后考虑维护一个基准线，遇到一个上升相当于后面整体往下降来和基准线对齐，遇到一个下降就需要基准线往下平移。所以合法当且仅当 \(a_1\) 减去所有下降的高度和要 \(\geq 0\)。
此时考虑怎样才能让左侧的值增加，首先对于一个凹下去段也就是 3 1 1 1 4 这样子，可以每次花 3 的代价让左侧 +1；对于 \(a_1\) 来说，它增加的同时还要让下降数不变，所以只能是最开头是类似 1 1 1 1 4 这样子的结构，就能每次用 4 的代价让左侧 +1。
此时发现让左侧 +1 操作类型是相同的，为了避免边界处的讨论情况在头尾补上 inf，那么操作相当于每次将一个凹的段整体 +1，至少要操作 \(d\) 次，求最终序列的总和最少是多少。对于用链表维护所有连续段，将所有可以整体 +1 的连续段放到一个堆里即可。时间复杂度 \(\mathcal{O}(n\log n)\)；考虑最终一定是和最高的合并，两侧就可以递归下去，所以可以建出笛卡尔树的结构直接得到所有段的合并过程，就能从短到长贪心，这样的复杂度是 \(\mathcal{O}(n)\)。
9. UOJ 37【清华集训2014】主旋律
一个有向图缩点之后分为若干弱连通块，每个弱连通块是个 DAG，DAG 中每个节点是原图一个 SCC。
- \(f_S\) 为将 \(S\) 集合缩点后仅为一个 SCC 的方案数；
- \(g_S\) 为 \(S\) 集合缩点成若干两两之间无边的 SCC（可以仅为一个）权值为 \((-1)^{c+1}\)，\(c\) 是 SCC 个数；
- \(h_S\) 为 \(S\) 集合缩点后是若干弱连通 DAG。
首先有 \(h_S=2^{cnt[S]}\)，\(cnt[S]\) 为 \(S\) 内部边数。
同时考虑 DAG 计数那个容斥，有：
\[h_S=\sum\limits_{T\subseteq S,T\neq \varnothing}g(T)2^{T\to \{S-T\}}h(S-T) \]\(2\) 的次幂上的指标是 \(T\) 连向 \(S-T\) 的边数。
\[g_S=\sum\limits_{T\subseteq S,lowbit(S)\in T}-f(T)g(S-T) \]逆过来稍微解一下 \(f_S\) 是啥就行了。
10. CCPC Final 2023 E Min or Max 2
如果最后留下的是 \((a_i,b_j),i\leq j\)，假设走到 \(i\) 时二元组为 \((a_i,y)\)，那么后面的操作是 \(\min\) 还是 \(\max\) 就已经根据 \(a_i\) 和 \(x\) 的大小关系而确定了，从而后面每个操作都是对 \(y\) chkmax 或者 chkmin，如果最小的 chkmax \(r\) 比最大的 chkmin \(l\) 还要小，说明最后取值唯一，否则只可能是最小的 chkmax \(r\) 或者最大的 chkmin \(l\)。
这说明了答案个数是 \(\mathcal{O}(n)\) 的。可以按照 \(a_i\) 从小到大扫描，用线段树维护得到 \(l,r\)，如果 \(r<l\) 不动脑子做法是维护 \(x\gets \max(q,\min(p,x))\) 这个玩意的复合，它的函数值一定是平着一段然后再 \(y=x\) 再平着一段，外面套个 \(\min\) 相当于将函数值 \(>p\) 的全都推平为 \(p\)（此套路出现在 slyzoj 305）。
动脑子的做法：将 chkmin 看成从顶向下的竖线，chkmax 看成从底向上的竖线，那么最终的值实际上是最后一个露头的竖线，也就是上侧的后缀 \(\min\) 和下侧的后缀 \(\max\) 第一次产生交错时被超越的那个，于是可以在线段树上二分。
\(l<r\) 时，那么相当于看前面的操作 \([x<a_i]\) 为 \(0\) 或 \(1\) 时是否能 \(>r\)，是否能 \(<l\)，也就是求 \([x<a_i]=p\) 时 \(y\) 的最大值和最小值。
将 \(<a_i\) 的看成 \(-1\)，\(>a_i\) 的看成 \(1\)，那么只有对 \(-1\) 的 chkmin 和对 \(1\) 的 chkmax 是有用的操作，假如确定了最后一个有用的操作位置在 \(p\)，那么 \((p,i)\) 中的操作一定是 \(1\) 为 chkmin \(-1\) 为 chkmax，而为了让 \(y\) 更大/更小，\(p\) 前方的操作一定全是 chkmax 或者全是 chkmin。那么可以把序列看成三部分：\([1,p)\) 全是 chkmax 全是 chkmin，\(p\) 位置是 chkmax 或者 chkmin，\((p,i)\) 根据 \(1,-1\) 确定为 chkmax 还是 chkmin。使用线段树维护分治信息即可，还是要搞 \(x\gets \max(q,\min(p,x))\) 这个信息的复合。
11. CCPC Final 2023 B Periodic Sequence【口胡】
考虑啥样的字符串可能出现，假如出现了 \(1,2,...,k\)，那么此后一定是 \(1,2,...,a_1,1,2,...,a_2,1,2,...a_3,...\) 并且满足 \(a_1=k,a_i\leq k,i\geq 2\)，并且发现所有这样的序列能全出现在答案中。（注：仅需字符集 \(\{a,b\}\) 使 \(1,2,...,k\) 为 \(abbb...\) 即可）
构造直接归纳，初始 \(n=1\) 时仅有 \(\{a\}\)，然后每次对于每个字符串在它后面添加长度为 \((n+1)\) 的字符串（也就是它不断循环截取前 \(n+1\) 项），如果有个字符串被加入多次只选一个位置加入，然后在所有字符串的最前面加入长度为 \(n\) 的 \(abb...\)。由于 \(n\) 时刻所有合法字符串均出现，归纳得到 \((n+1)\) 时刻所有合法字符串均出现。
所以相当于于求这个的前 \(n\) 项系数：
\[\begin{aligned} &\frac{1}{1-x}\sum_{k\geq 1}\frac{x^k}{1-\frac{x-x^{k+1}} {1-x}}\\ =&\sum_{k\geq 1}\frac{x^k}{1-2x+x^{k+1}} \end{aligned} \]\(k\leq \sqrt n\) 直接 \(\mathcal{O}(n)\) 递推出每个 \(\frac{x^k}{1-2x+x^{k+1}}\)，\(k>\sqrt n\) 直接将分母展开然后大力推式子得到：
\[\sum_{j\geq 0}\frac{(-x)^j}{(1-2x)^{j+1}}\frac{x^{(\sqrt n+1)(j+1)}}{1-x^{j+1}} \]此时 \(j\leq \sqrt n\)，对于每个 \(j\) 以 \(\mathcal{O}(n)\) 复杂度求出式子的值即可。现在能做到 \(\mathcal{O}(n\sqrt n)\) 了。
如果是 NTT 模数的话，对于 \(k\leq \sqrt n\) 那部分 \(\sqrt n\) 个分子分母大小均为 \(\sqrt n\) 的多项式，分治 ntt 通分复杂度就是 \(\mathcal{O}(n\log^2 n)\)。
对于 \(k>\sqrt n\) 的部分，此时大概相当于下面这个东西偶数位置处前缀积的和，\(2\sqrt n\) 个分子分母度数均为 \(\sqrt n\)，同样分治 ntt 即可，总复杂度 \(\mathcal{O}(n\log^2 n)\)。
\[\frac{(-x)x^{\sqrt n+1}}{1-2x}\times \frac{1-x^j}{1-x^{j+1}} \]12. CCPC Final 2023 L Exchanging Kubic【口胡】
\(n\) 次操作把正负性问出来，对于正数已经问出了具体值。相同奇偶性的可以直接合并（连续的 \(\leq 0\) 就看成一个负数和一堆 \(0\)），考虑对于 +-+ 进行询问，如果两个 + 是 \(a,b\)，如果问出来 \(>\max(a,b)\) 那么可以直接得到 -，否则只能知道 \(abs(-)>\min(a,b)\)。
假设是 \(axbyc\)，其中 \(a,b,c\) 已知正数，\(x,y\) 未知负数，并且 \(b\) 是所有正数的最小值，先问 \(axb\)，如果能确定 \(x\) 直接确定；再问 \(byc\)，如果能确定直接确定。
如果都不能确定，说明 \(|x|\) 和 \(|y|\) 均 \(>b\)，那么 \(xby\) 就能看作一个新的未定负数 \(z\)。则可以两次操作去掉一个负号，一共有 \(n/2\) 个负号，所以总的询问次数至多是 \(2n\)。
13. P7520 [省选联考 2021 A 卷] 支配
可以每次删点 dfs，暴力求支配树，加入 \(s\to t\) 后发现 \(x\) 不再支配 \(y\) 当且仅当 \(1\to s\) 不被 \(x\) 支配，\(t\to y\) 不被 \(x\) 支配。没观察到的：\(x\) 受支配集改变当且仅当 \(fa_x\) 支配集改变或者 \(fa_x\) 不再支配自己。
所以只需要在支配树上对每个节点快速判断是否《删除 \(fa_x\) 之后 \(1\) 能到达 \(s\) 且删除 \(fa_x\) 之后 \(x\) 能到达 \(t\)》，那就预处理删除 \(fa_x\) 之后 \(1\) 在正图上能走到的点，以及 \(x\) 在反图上能走到的点。总时间复杂度 \(\mathcal{O}(nm+qn)\)。
14. P7519 [省选联考 2021 A/B 卷] 滚榜
对全排列那个贪心状压 dp。
那么 \(f[S][i][p]\) 表示滚完了集合 \(S\)，已经用完了\(i\) 道题，最后一个滚到的是 \(p\)，转移枚举下一个滚到的 \(q\)，它至少需要新用 \(j=\max(0,a_p-a_q)\) 个题（\(p<q\) 可能还要 +1），那么转移到 \(f[S+\{q\}][i-j(n-|S|)][q]\)。
状态 \(\mathcal{O}(2^nnm)\)，转移 \(\mathcal{O}(n)\)，总的复杂度就是 \(\mathcal{O}(2^nn^2m)\)。
15. P7516 [省选联考 2021 A/B 卷] 图函数
先看 \(h(G)\) 怎么算，求出删去编号 \(1\sim k\) 的点后缩点之后的图 \(A_k\)，那么每次相当于从 \(A_0\) 跳到 \(A_c\)（\(c\) 是所在 scc 中最小编号）再往后跳的过程。那么删掉一个点 \(k\) 对答案带来的贡献就是 \(A_{k-1}\) 中 \(k\) 所在 scc 的大小。倒过来变成加点，对于一对点 \((a,b),a<b\) 来说，加入 \(a\) 之后 \(a,b\) 在一个连通块中即对答案 +1，这时仅需考虑 \(a\to b\) 仅走 \(\geq a\) 的点 \(b\to a\) 仅走 \(\geq a\) 的点，经过的边编号最小值最大是 \(k\)，那么其对 \(ans_1,ans_2,...,ans_{k-1}\) 都有 +1 的贡献。
对于 \(a\to b\) 方向，枚举 \(a\)，从小到大加边（仅考虑 \(\geq a\) 的点），维护每个点是否被 \(a\) 可达，加入一条 \(u\to v\) 的时候如果 \(a\) 可达 \(u\) 则从 \(v\) 开始 dfs/bfs 找新的可达点（一个点不会入队多次），这里复杂度是 \(\mathcal{O}(nm)\)。
对于 \(b\to a\) 方向，枚举 \(a\)，同样从小到大加边维护每个点是否可达 \(a\)，加入 \(u\to v\) 的时候如果 \(v\) 可达 \(a\) 则在反图上从 \(u\) 开始 dfs/bfs 找新的可达点，复杂度也是 \(\mathcal{O}(nm)\)。
uoj 太慢了被卡常了/cy 上面这个东西也是可以 Floyd 做的，这样能循环展开，就能过了...
16. P7515 [省选联考 2021 A 卷] 矩阵游戏
确定第一行第一列即可唯一确定整个矩阵，先不管 \([0,10^6]\) 的限制构造任意一个解，考虑在它基础上调整。发现能够做的操作是对某一行或者某一列进行 +k -k +k -k ...，并且它等价于直接改变最初始时第一列某个位置或者第一行某个位置。然后这个操作也能构造出直接改变最初始时 \((1,1)\) 的取值。所以这个操作确实能生成所有符合 \(b\) 的解，而且不需要操作第一行（仅用第一列以及 \(2\sim n\) 行即可构造出修改 \((1,1)\)）。
正负交替还是有些麻烦，将网格图黑白染色，将 \(2\nmid (i+j)\) 的格子 \((i,j)\) 取反，此时操作变成整体加，只不过这些格子的取值范围变成了 \([-10^6,0]\)。此时再考虑第 \(i\) 行整体加 \(A_i\)，第 \(j\) 列整体减 \(B_j\)，那么限制相当于 \(L(i,j)\leq A_i-B_j\leq R(i,j)\)，差分约束求解出符合条件的 \(A,B\) 即可。这里可以直接以 \(A_1\) 作为源点（前面分析过它为 0 照样可以生成所有解）。
直接跑 bellman-ford 就是 \(\mathcal{O}(n^3)\)。
17. P6622 [省选联考 2020 A/B 卷] 信号传递
先预处理出 \(A[i][j]\) 表示有几次 \(i\) 后面是 \(j\)，然后依次决策位置 \(i\) 处的塔的标号。那么 dp \(f_{S}\) 表示已经将 \(S\) 中的标号填入了 \(1\sim |S|\) 的塔，将下一个标号 \(p\) 分配到第 \((|S|+1)\) 个塔时，令 \(c=|S|+1\)，新增的代价是：
\[c\sum_{i\in S}A[i][p]-c\sum_{i\notin S}A[p][i]+\\ kc\sum_{i\in S}A[p][i]+kc\sum_{i\notin S}A[i][p] \]对代价的预处理，枚举 \(i\) 枚举 \(S\)，移除 lowbit 来转移可以做到 \(\mathcal{O}(m2^m)\)，对 \(f\) 的 dp 直接做就是 \(\mathcal{O}(m2^m)\)，这里问题是预处理的数组 \(g(i,S)\) 是开不下的。
将二进制位分开，\(g_1,g_2\) 分别预处理前 \(m/2\) 个和后 \(m/2\) 个就行，这样空间直接开根，也非常好写（可以直接 \(2^{m/2}m^2\) 暴力算出每个 \(g\)）。
18. P6628 [省选联考 2020 B 卷] 丁香之路
不是很能想到欧拉回路。如果要 \(s\to t\)，相当于加上 \((s,t)\) 边之后，加上尽可能权值和较小的边，使得整张图存在欧拉回路，注意这里是要求度数均为偶数并且所有度数的点是连通的（可以有孤立点）。
先考虑固定 \(s,t\)，再加上 \((s,t)\) 之后咋做。首先需要将奇度点之间进行一个匹配，为了尽可能满足连通，匹配的两个奇度点中间一定是 \(x\leftrightarrow (x+1)\leftrightarrow (x+2)\leftrightarrow ...\leftrightarrow y\) 这样连边，连完之后可能会存在若干连通块，因为这张图两点之间无论怎么走，最短路唯一，所以走一遍将它们连通的路径一定是最小生成树的两倍，根据 kruskal，只需要将相邻的有度数的点之间连的边拉出来跑最小生成树即可。
问题在于怎么确定奇度点之间的连边，这里结论是直接相邻的两个连起来即可。为什么不能跨过去连从而保证连通性的性质？感性理解一下，如果本来奇度点是 \(a<b<c<d\)，会连上 \(a\leftrightarrow b\) 和 \(c\leftrightarrow d\)，这样我们可以选择是否连 \(b\leftrightarrow c\) 这个路径使得 \([a,d]\) 中所有点连通，而如果直接连 \(a\leftrightarrow d,b\leftrightarrow c\)，花费了更多的代价将 \([a,d]\) 连通。
然后这里我们仅需要知道连通性和度数的信息，所以记录加 \((s,t)\) 前的并查集的形态以及每个点度数，枚举 \(t\) 之后 \(\mathcal{O}(n\log n)\) 求答案即可，总时间复杂度是 \(\mathcal{O}(n^2\log n)\)。
19. [ARC145D] Non Arithmetic Progression Set
结论：三进制下全是 \(0,1\) 互不相同的数，一定不存在三个数形成等差数列。
那么可以先找出前 \(n\) 个满足条件的数，然后它们整体加减一个数依然满足条件，这样可以在保证条件满足的情况下使得数的总和和 \(m\) 相差 \(t\in [0,n)\)。此时还需要往里面添 \(t\)，只需要让最初 \(n\) 个数满足三进制最低位为 \(0\)，这样最后可以在最后直接让其中 \(t\) 个数 \(+1\)。
20. P10311 「Cfz Round 2」Weighted Mean
先对 \(a\) 排序，令 \(t\) 为加权平均数。从简单入手，对于 \(n=2\) 的情况，\(a_1+1=a_2\) 时因为 \(t\in (a_1,a_2)\) 所以无解。否则 \(\frac{a_1b_1+a_2b_2}{b_1+b_2}=t\)，那么 \(b_1(a_1-t)+b_2(a_2-t)=0\)，令 \(b_1=(a_2-t),b_2=(t-a_1)\) 即可。
\(n\) 更大时，同理相当于要满足 \(\sum b_i(a_i-t)=0\)，令 \(c_i=a_i-t\) 那就是 \(\sum b_ic_i=0\)。
\(n\) 是奇数，直接令 \(t\) 为 \(a\) 的中位数，两边就可以直接对称 \(a_i,a_{n-i+1}\) 进行匹配，也就是 \(b_i=|c_{n-i+1}|\)，两侧递增所以一个 \(b\) 最多出现两次，而 \(m\) 一定不会出现所以令中位数的 \(b=m\) 即可。
\(n\) 是偶数且 \(a_{n/2}+1\neq a_{n/2+1}\) 也可以直接构造。
否则，令 \(p=n/2\)，先考虑 \(a_p=t\) 的情况，此时让 \(c_{p+1}=1\) 和 \(c_n\) 合起来变成 \(c_{n}+1\) 考虑，此时和 \(c_n+1\) 匹配的那个 \(c_q\)（注意正数和负数之间可以任意匹配），会使得 \(b_{p+1}=b_n=|c_q|\)，那么就要求存在一个 \(c_q<0\) 满足 \(|c_q|\) 只出现一次。
如果不满足条件，再校验 \(a_{p+1}=t\) 的情况即可，由于不满足条件说明两侧一定对应一一相等，容易验证此时 \(a_{p+1}=t\) 一定符合条件。
21. IMO2022 T6
考虑怎么统计答案，按照权值从小到大点亮格子。如果一个格子被点亮时四周没有亮，那么其权值为 1（它是山谷），否则它的权值就是四周亮格子的权值和（权值的意思是以它为终点的路径个数）。观察答案下界，首先每个格子都会作为终止路径，这个下界是 \(n^2\)；更紧一点就考虑每相邻两个格子的边一定会给答案贡献至少 1，然后至少存在一个山谷，它会给答案贡献 1，那么答案下界是 \(2n^2-2n+1\)。
这个答案的构造需要标为 1 的格子形成了一棵连通的树，并且不被标为 1 的格子两两不相邻。这样就很好手玩出规律了。
22. P7921 [Kubic] Division
考虑倒过来做，最大化初始的数的个数，要合并出 \(n\)，（应该）每次合并最小和次小是最优的。现在考虑怎么样一个状态是合法的，如果出现了 4 次 \(x\)，那么要不然先合并前两个要不然先合并中间两个，这样会使得 \(x,2x\) 同时出现导致条件不满足；同理如果出现了 3 次 \(x\)，那么 \(<x\) 的数的个数一定是奇数个。进而发现这个条件是充要的。因为 \(2\min > \max\)，所以合并最小和次小一定是新产生一个更大的最大值，从而条件依然满足。
那么现在就能贪心构造答案了，首先最小值越小更优，照抄一下 by_chance 的题解：
记 \(f(w, c), g(w, c)\) 分别表示最小值为 \(w\) 的 \(c\) 个数的 sum 的最小值和最大值。那么只能取 \(w\sim 2w-1\) 这些数，\(c\) 为奇数时 \(\min\) 为 \(2...210...0\)（每个数出现多少次），\(\max\) 为 \(10...02...2\)；\(c\) 为偶数是 \(\min\) 为 \(2...20...0\)，\(\max\) 为 \(10...02...23\)。之后分类讨论就需要一些计算：
首先算得最大情况 \(g(w,2w)=3w^2-1\)，那么找到最小的 \(w\) 满足 \(3w^2-1\)。从小到大贪心取，每个数最多取两次，直到不能取为止，那么当前的数的个数就是最大的 \(c\)。可以每次将最大的数往后挪，那么 \([f(w,c),g(w,c)]\) 中每个数都能取到。问题在于 \(n\) 是不是真的在这个区间内？
画一下发现 \(c\leq 2w-2\) 总有 \(g(w,c)\geq f(w,c+1)\)，仅在 \(c=2w-1\) 时 \(3w^2-2w=g(w,2w-1)<f(w,2w)=3w^2-w\)，那么 \(n\in (3w^2-2w,3w^2-w)\) 时一定不合法，此时将 \(w\gets w+1\) 即可。由于 \(3w^2-w<3(w+1)^2-2(w+1)\) 所以 \(w\gets w+1\) 后一定能构造出解。
23. CF1882E2 Two Permutations (Hard Version)
将操作简化，看成环排列，为了区分开头需要在最前面加入一个 \(x\)，那么 \(xABC\) 操作 \(B\) 就变成了 \(xCBA\) 转一下就是 \(BAxC\)，也就是相当于选择一个位置和 \(x\) 交换位置。
再重新断环为链，对于任意合法最终状态 \(4,5,6,...,n,x,1,2,3\) etc. 将排列分解成若干环，\(x\) 存在的环对答案贡献为环长 -1，否则为 环长 +1。若同时考虑两排列，需要满足排列奇偶性相同的情况下两者 \(\max\) 最小，找到这个最小值然后模拟即可。时间复杂度 \(\mathcal{O}(n^2)\)。
24. CMO2023T6
还是抄的 by_chance。
令 \(n=99=4m-1\) 为顶点数，求最小操作次数使得能够从任意圆排列复原到顺时针 \(1,2,\cdots,n\) 排列（这等价于任意到任意）。观察答案的上界，定义“劣弧逆序对” \((i,j)\) 为从 \(i\) 逆时针走不超过 \(\frac{n-1}{2}\) 步能走到 \(j\)，并且放在 \(i,j\) 上的数有 \(a_i<a_j\)。最终状态劣弧逆序对个数为 \(0\)，而交换两个相邻的数劣弧逆序对至多 \(-1\)（若交换了 \(a_x,a_{x-1}\)，分类讨论 \(a_x,a_{x-1},a_{x-\frac{n+1}{2}}\) 三者大小关系即可得证）。从而对于顺时针 \(n,n-1,n-2,\cdots,1\) 共 \(\frac{(n-1)^2}{4}\) 个劣弧逆序对，所以答案的下界是 \(\frac{(n-1)^2}{4}\)，现在证明任意圆排列均可以在不超过 \(\frac{(n-1)^2}{4}\) 步还原为 \(1,2,\cdots,n\)。
考虑将环分为大小为 \(2m-1\) 和 \(2m\) 的两部分，且两部分分别有 \(m\) 个 \(\leq 2m\) 的数（称之为小数，反之为大数），因为对于 \([1,2m-1],[2m,4m-2]\) 如果有其一有 \(m\) 个小数，那么即找到合法的解。否则一定其一 \(<m\) 个小数，另一 \(>m\) 个小数（如果都 \(<m\) 那么小数个数 \((m-1)+(m-1)+1<2m\) 矛盾。此时考虑将一个长度为 \(2m-1\) 的区间在环上转的过程中，小数个数变化只能是 \(\pm 1\) 或 \(0\)，而 \(<m,>m\) 个小数的区间均存在，说明一定存在小数个数为 \(m\) 的长为 \(2m-1\) 的区间。
现在考虑将两段圆弧分别排序，让小数凑在一起，大数凑在一起，再将小数内部排序，大数内部排序。假设圆弧是分为左右两部分，那么有小数凑在上半部分和大数凑在上半部分两种情况，只需其中一种合法即可。
标签：...,2024.4,复杂度,sum,权值,mathcal,col From： https://www.cnblogs.com/do-while-true/p/18157934