原来的太长了，更新和使用都不方便，就分裂一下。又水一篇blog
标 * 的为有价值的题，标 ^ 的为欺诈题，标 - 的为知识点待填坑，标 ? 的表示看别人是这样做的但是没懂为什么
组队训练的题，如果是队友过的板刷题，题面又很长，就会标个“队友说是沙雕题”
2019 Official
2019ccpc网络赛
1001 1007：略
1002：建一棵值域线段树，维护区间最大值
1003：建 SA，用主席树找第 $k$ 小
1004：用堆找第 $k$ 小，更新堆时，对于一条路径，要么加入末端点连出去最短的边，要么把最后一条边变大
1005：$a$ 和 $b$ 互质的话就变成 $\sum_{i=1}^n \sum_{j=1}^i (i-j)[\gcd(i,j)=1]$ 了，再化成 $\sum i\phi(i)$ 然后杜教筛
1006：倒着做
1008：按 $t_i$ 从大到小排序，前面每煮一条鱼会剩下 $t_i \mod k$ 的时间，存到堆里，到后面没鱼可煮了要钓一条煮一条的时候，就拿这个堆来优化
1009：分层递推（设 $f_{i,x,y,now}$ 表示当前到了第 $i$ 层，黑点放了 $x$ 个，白点放了 $y$ 个，当前层共有 $now$ 个点，的答案，$i$ 这一维可以优化掉）
2019 ICPC 银川 网络赛
当年他 tourist 用 4 小时 AK WF，我 *** 今天用 5 分钟 AK 网络赛，不是问题
ABC：队友说是沙雕题
D：第一问是 $\frac 12$，第二问递推一下
*E：数据结构课练习题
F：动态 Floyd
G：暴力 dp 是 $O(nk)$ 的
H：按 $\frac{局数}{ATK}$ 从小到大打
K：
*L：像析合树的预处理部分那样，扫描右端点，线段树维护左端点是否可行
方法一：维护 $区间最大值-区间最小值-不同的数的个数$
方法二：维护 $区间长度-[有多少个 x满足x和x+1都在区间内]-最大值的个数$
方法二的代码长度是方法一的两倍
2019 ICPC 南京 网络赛
A：剥洋葱那样从外到里一圈一圈地确定给定坐标的权值，然后线段树维护一下
*B：暴力递归，欧拉降幂，指数很快就 $0$ 的了
**C：解法一：打表，每 $\sqrt n$ 打一次表，每组询问 $O(n \sqrt n)$
解法二：$2^{ij}=\sqrt 2^{i^2+j^2-(i-j)^2}$，推式子 NTT
D：求的是 $\frac{E(d^2)+E(d)}{2}$，$E(d)$ 和 $E(d^2)$ 都是简单的拓扑递推
E：莫比乌斯反演一套打下去，前面 $\sum_{i=2}^k x^i$ 是等比数列求和，后面 $\mu \ast id^2$ 用杜教筛
F：对于每个 $i$ 在 $[pos_i-k,pos_i+k]$ 找最大的转移过来
H：暴力 Floyd
*I：按照 $t_i$ 从大到小排序，假设前 $k$ 个人机洗，那么随着 $x$ 递减，$k$ 是递增的，维护一个凸壳
2019 ICPC 徐州 网络赛
CJM：略
BEI：随便维护
*A：斐波那契博弈
D：SAM
*F：通过容斥转化为求某个点子树内距离它不超过 $x$ 的点的点权和，这是个二维数点
G：回文树
H：要求的是 $\sum_{i=1}^n f(i)$ 和 $\sum_{i=1}^n f(i)i$，考虑每个质数的贡献，前 $O(\sqrt n)$ 个质数暴力做，后面的质数用 min25
K：$O(n^2)$ 枚举对称中心，$O(n)$ 计算答案
L：状压 dp，求两点距离打个表观察一下有惊喜（
2019 ICPC 南昌 网络赛
BG：略
*A：方法一：每 100 个数取一次样，看下在不在给定的数组里，在的话就暴力判一下
方法二：
C：矩阵乘法优化递推
*D：要求 $[k]x:\prod_{i=1}^n(1+a^{s_i}x)$，分治模任意模数 FFT，敢写敢过
E：约瑟夫，递推
F：考虑 $S$ 每个本质不同的子串的贡献，因此用 SAM 维护
H：求个通项，然后大步小步预处理
*I：设 $b_i=[a_i\not= a_{i-1}]a_i$，那么每次就是问一个矩形中（$[l,r]$，$[x,y]$）有多少个点，树套树或者 cdq
2019 ICPC 沈阳 网络赛
FH：略
BCD：队友说是沙雕题
*E：$n \leq p$ 预处理，$n>p$ 利用 Touchard 同余记忆化搜索
G：大力推式子，发现是递推
J：$f_i=\sum_{j=1}^{\min(X,i)} \binom{i-1}{j-1}\cdot (j-1)! \cdot f_{i-j}$，移项就是 $O(n)$ 递推，然后该递推的前 $X$ 项都是 $1$（卡常）
K：高斯消元解出 $p$ 然后矩阵乘法递推
2019 ICPC 上海 网络赛
BJL：略
*A：方法一：线段树维护树的直径，修改时只用修改子树 dfs 序区间的两个端点，然后维护一下每个点到根的距离以便询问两点距离，共 $O(n \log^2 n)$
方法二：动态点分
C：每个 $C$ 的贡献是有多少对 $A,B$ 满足 $A+B \geq C \geq |A-B|$，用 $A$ 和 $B$ FFT 一下就好
D：大于 $1$ 的数不会很多，暴力搜索就好
E：
G：
*H：每个元素维护从队尾乘到它是多少，路径压缩，bitset 加速矩阵乘法
F：贪心逐位确定，用 dp 算方案数
K：分别画半径为 $a$ 和 $b$ 的圆，然后分别求圆上整点，然后 two pointers 找答案
2019ccpc 秦皇岛
A：作为直角点时极角排序扫一遍，作为非直角点时离线枚举直角点，然后把其余点极角排序扫一遍
D：判断 $n$ 是否只含 $2$ 和 $5$
E：每个机器人的路线不会重叠，因此每个格子拆成横点和竖点，跑最大流
F：tarjan 求边双
G：狠狠地压状态
I：简单 bfs
J：倒过来 kmp
^K：如果有叶子的父亲多于一个儿子，则必胜；否则看叶子到父亲的链长，全是偶数必败，否则可以归约到第一种情况
*L：二分，然后中间每个人按照到达左出口的距离从大到小排序，贪心往右出口塞
BCHL：
2019ccpc 哈尔滨
F：略
*A：解法一：二分，然后差分约束，判负环
B：$O(2^mm^2)$ dp（设 $f_{i,j,k}$ 表示第 $i$ 个数，与 $r$ 的 lca 深度为 $j$，与 $r+1$ 的 lca 深度为 $k$，的贡献）
E：根只有一个，直接算每个叶子要给根贡献多少次
**H：首先只有开始和结束两个时刻是有用的。图可以看作是一棵树加 50 条边。全局按照 $dis_x+cost_x$ 进行 Dijkstra，每个点只会被松弛一次。每个点分中心维护距离队列，每个点在他点分树祖先以及 50 个关键点的队列里进行松弛。
I：递推，$h_i>h_{i-1}$ 就乘 $2$，$h_i=h_{i-1}$ 就相当于插空
J：$n$ 为奇数则 $3+(n-3)$，为偶数则 $2+(n-2)$，$5$ 以内无解
K：$w_i+k\cdot\frac{w_i}{sum}$
L：$O(n^2)$ 预处理所有可能的状态，然后 $O(nq)$ 回答询问。
2019 ICPC Regional 南京
A：取后一半
*B：最后一定是在四个角落结束，且是沿着矩形的边界从一个角落走到另一个角落这样的，因此就是推个组合数式子
D：DAG 计数
H：最坏情况是 $b+c$ 个假人一起演真人，因此真人至少要 $b+c+1$ 个，特判 $1~0~0$
*I：暴力 dp，整数拆分压状态
J：算出每个 $b$ 匹配每个 $c$ 的收益，跑 KM
K：若给定点在三角形顶点上，则连到对边中点；否则按比例算一下连到对边去
2019 ICPC Regional 沈阳
AH：略
D：把 $e^{\min\{a_i\}}$ 提取出来
-E：圆的反演
G：区间 dp，设 $f_{i,j}$ 表示 $i$ 到 $j$ 这段点加上 $(i,j)$ 这条边形成的多边形的划分数，$i$ 和 $j$ 必然同时连向 $[i+1,j-1]$ 中的一个 $k$
*J：每条边算出一个存活时间。按时间分治，每条边有 $\log$ 个小区间是完全存活的，用并查集维护当前连通情况，边在完全存活时加入并查集，退出时撤销，分治到底就询问
-K：答案为 $n-1$ 的整数拆分，五边形数
L：贪心
2019 ICPC Regional 南昌
L：略
A：解法一：可持久化并查集
解法二：按时间树 dfs，维护一个可撤销并查集，删点或者更换集合的时候不用真删，开一个数组用于记录每个点的实际指向即可
*B：状压 dp，左边前 $i$ 个点和右边后 $n-i$ 个点合起来形成一个状态
看大题解
C：枚举 $i$ 最高位的 $1$ 在哪，对于 $n$ 的 $1$ 的位，有 $3$ 种选择，对于 $n$ 的 $0$ 的位，有 $2$ 种选择
*D：每个 $d$ 单独做，设 $f_{i,0/1}$ 表示以全 $0$ 或者全 $1$ 进入这棵子树所得到的答案，这可以 $O(n)$ 递推
E：队友说是沙雕题
^G：那个模数不是质数，最大的质因子为 $2803$，因此等价于 $n<2803$
*J：burnside+矩阵快速幂
2019 ICPC Regional 银川
GILN：略
A：dp，设 $f_{i,j,k}$ 表示前 $i$ 张卡，选了 $j$ 张，加成为 $k$，的最大获利。
B：设 $a_{x,y}=-1$，找另一行另一列的一个点 $(x’,y’)$，则 $a_{x,y}=a_{x’,y}+a_{x,y’}-a_{x’,y’}$
*C：dp，枚举 $i$，每个点到 $i$ 的极差可以用单调栈和树状数组维护出来，极差从左往右是下降的。考虑每次询问二分，然后发现有类似于决策单调的性质，就不用二分了。注意卡常！
D：简单莫比乌斯反演（可能直接叫容斥比较好），注意欧拉降幂
*E：按位考虑，考虑第 $i$ 位和第 $j$ 位，那么所有的 $a$ 分为 4 类（00、01、10、11），其中 00 和 11、01 和 10 配对能产生 $2^{i+j}$ 的贡献，这个 $O(n)$ 遍历一遍即可。
F：队友说是沙雕题
H：按有向边的拓扑序，对每个无向连通块跑最短路
*J：老套路，如果最后在 $1$ 结束则是环边计一次树边计两次，如果不在 $1$ 结束则把树边边权取负跑最短路，类似于退流
K：注意到左右矩阵的元素是一一对应的，就可以精细地写出 $O(n^2)$ 的枚举
2019 EC Final
A：队友说是沙雕题
C：方法一：dp，设 $dp_{i,j}$ 表示把 $i$ 分配成 $j$ 个元素的贡献。幸好厦门的 F 比你早出
方法二（未验证）：$f=g^{k^{-1}}$
E：$最大流=\frac{总容量}{路径长}$，每条路径都可以有若干个阶梯状的 $(x,y)$ 表示增加一个单位的流量需要花费 $x$，最多 $y$ 次。然后用堆取 $(x,y)$ 取到最大流为止。
G：$10!$ 枚举
H：把所有的 $\frac{a_{i+2}}{a_i}$ 和 $\frac{a_{i+1}}{a_i}$ 统计出来，取出现最多的 12 个。若有长度 $\geq \frac n2$ 的等比子序列，则公比必在其中
M：把每一类 $a,a^2,\cdots,a^k$ 抽出来暴力
2019 Sichuan Province Programming Contest
A：暴力
B：一定有一条直线使矩形在两侧，讨论两个矩形的放法
C：队友说是沙雕题
*D：树形 dp，每个点要么把它的儿子全部断掉，要么它本身作为某种颜色的根，然后保留这个颜色的虚树，其他断掉
E：meet in the middle
*G：若 Alice 先手，必胜当且仅当存在两个大于 $k$ 的质数 $p_1,p_2$，使得 $|(x-p_1)-(y-p_2)|=1$，for 一遍判断即可；若 Bob 先手，枚举 Bob 第一步转化为 Alice 先手
H：略
^I：根据 $\sqrt{x_i}$ 为比例来分配
J：每种选择的次数都是 $O(\sqrt{k})$ 的，枚举两种选择的次数，unordered_map 判断另一种选择的次数
K：建一个有向图，地图上一个点能走到相邻点，当且仅当有一种问号安排方式使它走过去，那么如果从起点开始能走到环，或是走到一个点使其可以无路可走，那么就无解，否则就是最长路
F：
2020 Official
2020 CCPC 网络赛
CGJ：略
-**A：横边贡献是线段并长度，竖边的贡献是 $\sum |a_i-a_{i+1}|$，用 segment tree beats 维护
B：min25 卡常
*D：对于一个询问，二分一个 $mid$（实际不用二分），权值大于 $mid$ 的点叫黑点，否则叫白点。从黑点开始反向 bfs，黑点能到达的先手点也都是黑点，只能到达黑点的后手点也是黑点。然后去掉二分，改为点权从大到小加入
E：解法一：打表看 $SG$
解法二：如果没有因子 $2$ 那么就是“质因子个数”的 nim 游戏；质因子 2 的话只要点了就会变成 $SG=0$，所以假设质因子 2 是最后点的，那么就相当于所有的质因子 2 都合并成一个，所以 $SG(n)=n 的奇质因子个数+[n是偶数]$
*H：每一层已探索的门一定是连续的一段区间，因此可以 dp 设 $f_{i,l,r,0/1}$ 表示当前在第 $i$ 层，已探索了 $[l,r]$ 的门，当前在 $l$ 还是 $r$，的期望
^K：$K$ 矩阵相当于重新分配 $A$ 矩阵的元素权值，若 $K_{1,1} \not =1$，则无穷步之后 $A$ 的值都会泄漏到矩阵外面去
*L：容斥转化成 $x-y>K$ 或 $y-x>K$，然后大力数位 dp
M：转化成若干个单项式相乘
FI：
2020 ccpc 威海
DH：队友说是沙雕题
A：$\min(\max(2nt,2t+x),\max((2n+1)t,t+x))+2nt$
B：每个障碍周围 8 个点都是关键点，关键点之间做 Floyd，算答案的时候枚举起点到哪个关键点，终点到哪个关键点，又注意到每个障碍物对于起点、终点各只有一个关键点是有用的，因此 $O(qk^2)$
C：考虑每条边的贡献，当且仅当这条边一侧有 1 人、另一侧有 2 人时有贡献
*F：opentrain6277D 逐层分解，每次找到度数最小的点（一定是最外层的），然后用双源 bfs 剥离最外层
G：线段树维护 hash，要双 hash
*J：黑堆的 $SG$ 值只与黑堆最小值及其重复次数、是否等于最大值有关，枚举最小的黑堆及其重复次数，后面就是个线性基
*K：$p_1,\cdots,p_{l-1}$ 分出了若干个大区间，每个大区间独立操作，每个大区间里又会被 $p_l,\cdots,p_r$ 分成 $O(r-l)$ 个小区间，在这里做区间 dp
L：$x_i$ 只考虑质数，多重背包
EI：
2020 ZJCPC
AK：略
BE：队友说是沙雕题
C：建 trie 或者直接字符串哈希，卡常
F：把 AI 实验课写的 PLA 贴上来
G：只能是从起点开始沿 $v_i$ 递增的路线走到某个风洞，然后从这个风洞直接走到终点，因此 $O(n^2)$ 枚举
H：共 $O(nm)$ 个关键点，相邻关键点之间的线段逐一判断
I：这是一幅若干简单环组成的图，最大环即为答案
*L：快排法求第 $k$ 小
DJ：
2020 ICPC 小米邀请赛
中国大陆全明星赛
**B：分治，跨过当前分治中线的区间的答案只有三种：左边后缀的最大子段、右边前缀的最大子段、左边后缀的最大后缀+右边前缀的最大前缀，预处理出左边每个后缀的最大子段、最大后缀，枚举右边前缀，讨论三种情况都是二维数点算方案数
*E：要么除以 2 然后调整，要么会拆成 $a,b$ 两个数，其中 $a$ 比 $b$ 多一位，dp 求最优
G：$O(3^n)$ 状压 dp，$SG$ 从小到大做的话每次找一个极大独立集，从大到小做的话每次找一个集合连向已选的所有点
I：只要发现爆阈值是一定不会发生的话（因为爆之前回答问题一定会更优），就是个简单 dp 了
J：状压，从上往下放，已有的书的重心要么在新书的左边界，要么在右边界
K：暴搜，bfs 的队列最大只会到 1300 多
ACDFHLM：
2020 ccpc 秦皇岛
AE：略
F：每个连通块的 $\max(0,边数-点数)$ 加起来
G：枚举开根后的数
H：记 $f_{i,j}$ 表示前 $i$ 个数最大值为 $j$ 的方案数（这是正着 dp），同理搞个倒着的 dp 记 $g_{i,j}$ 表示 $i$ 开始的后缀“第一次出现的数”最小是 $j$ 的方案数，算答案时就是前缀后缀合并
J：枚举 $d$ 然后枚举余数段，余数段每次往右移一段时对方案数的影响是 $O(1)$ 计算的
K：树形 dp，假设每棵子树 1 个兵开局，则这个兵最后会在最深的叶子上，那么就把儿子按最深叶子深度排序，依次枚举，如果把兵从它最深的叶子提上来的代价超过从根再派一个过来，就从根再派一个过来
BDIL：
2020 ccpc 长春
2020 ICPC Regional 南京
^D：度数本身就 $\le \frac n2$ 的点直接 Kruskal 合并，剩下的边 random_shuffle 1000 次左右
EF：队友说是沙雕题
H：若 $n=1$ 或 $m=1$ 无解；若 $n>7$ 或 $m>7$ 则任意方案都合法；否则爆搜
*I：二分答案，按 $y$ 关键点从小到大维护可行的 $x$ 坐标段
*J：询问操作等价于找有多少个 $a_i$ 满足它的二进制第 $b$ 位为 $1$（其中 $b$ 是这次游戏 $SG$ 值的最高位），因此 segment tree beats 维护区间异或和、区间每个二进制位为 $1$ 的数量
K：前 $k$ 位 shift 一下
L：找区间最长的 $a$ 连续段
M：经典的“看上去是 $O(n^3)$ 实际上是 $O(n^2)$ 的树型 dp”
ABCG：
2020 ICPC Regional 济南
A：每一列单独考虑，对 $A$ 矩阵推一下式子是一个线性基
C：尽量避免两个 $2$ 合并
D：队友说是沙雕题
*F：
G：根据 $y$ 的最高位在 $x$ 那里是不是 $1$ 讨论一下
*H：min-max 容斥，转化为求各种链并大小的方案数。设 $dp_{i,j,k}$ 表示 $i$ 这棵子树，链并为 $j$，目前有条链往上最长延伸了 $k$，的方案数。转移都是前后缀转移，因此是 $O(n^3)$ 的
*J：2 位作为奇偶层标记位（奇 $01$ 偶 $10$，这样使得同为奇层或同为偶层的不会相互连边），然后选择奇层和偶层较小的一方作为标记层（最多 50 个点），标记层的结点获得 $1$ 至 $50$ 的编号，在 $50$ 位中把它编号的那一位填 $0$ 其他位填 $1$；非标记层的结点默认 $50$ 位全 $0$，相邻的标记结点编号填 $1$。
L：直接枚举 $x$ 的最后 8 位、8 位后的连续 1 的数量、总共的 1 的个数
M：$\max(2,\lceil\frac{2n}{k}\rceil)$
BEFIK：
2020 ICPC Regional 昆明
好耶，大学生和中学生互相给对方出原题
A：可撤销贪心。问题转化成有若干个元素，每个元素有代价 $v_i$，相邻元素不能同时选，问 $m$ 代价以内最多选多少个。每选一个元素，就把左右的元素合并起来，代价为 $v_{i-1}+v_{i+1}-v_i$，用堆维护。
*B：上下界最小费用可行流，先假设全放白棋，那么第 $i$ 行连向第 $j$ 列两条边，一条费用 $-sw_{ij}$ 表示不放棋，一条费用 $sb_{ij}$ 表示放黑棋，注意负环消圈
*C：区间 dp，设 $dp_{l,r}$ 表示区间 $[l,r]$ 合并成同色的最小步数，观察到最后该区间的颜色一定是端点的颜色，因此可以只对该区间内端点颜色的点做背包，复杂度 $O(n^2+n\cdot 15^2)$
*D：$n | k^n$
-F：出题人说是抄 17 集训队论文的回文树
G：按生日排序，设 $dp_{i,j,k}$ 表示考虑了前 $i$ 个人，空了 $j$ 个人没做蛋糕（如果 $j>m$ 就视为 $j=m$），总共花了 $k$ 天做蛋糕，的最大收益
H：$2020+x$
I：队友说是沙雕题
J：观察到，任意的环可以一步变成若干个二元环，因此答案最多为 2
K：依次枚举：摸到哪张牌、打掉哪张牌、雀头、刻子
L：$ans_i=(a_1,\cdots,a_i 的最长下降子序列长度)$
*M：每次询问，置 $mex$ 初始为 $1$，看 $(last_mex,mex]$ 之间是否有数，有就把 $last_mex \gets mex$，把 $mex += (last_mex,mex] 中的数求和$，否则结束。可以证明这是 $O(\log a)$ 的
E：
第十一届山东省大学生程序设计竞赛
B：$n \le 1000$ 时直接 Kruskal，$n$ 大时直接是 $n-1$，注意 $L=R$
C：倍增。一棵子树如果加一个兄弟和父亲，那么方案 $\times 2+1$；如果只加一个父亲，那么方案 $+1$
D：队友说是沙雕题
F：两个字符串拼起来，一定是一个串形如 $a$ 另一个串形如 $bab$，因此枚举每个串的 boarder 然后 hash 寻找有没有 $a$
G：高精度除法
H：队友说是沙雕题
I：用线段树维护每个位置的权重，以及区间和，乘法标记可不下传，注意模数是 3 和 7 的倍数因此要记下这两个因子的次数
*J：解法一：设 $dp_{i,j}$ 表示考虑了能力值前 $i$ 的人，当前剩余 $j$ 个老师，的最大收益。$j$ 只开 500 然后卡常
*M：$A$ 矩阵奇数行全 1 且第 1 列全 1，$B$ 矩阵偶数行全 1 且最后一列全 1
AEKL：
2021 Official
2021 CCPC 网络赛 1
A：略
B：一个周期不超过 27720，直接求出来然后随便搞搞
*E：解法一：写成矩阵乘法：$ans=v_{init}\sum_{i=1}^n\sum_{j=1}^n\binom{i+j}{i}A^iB^j$，然后 NTT
解法二：写成通项公式：$ans=\sum_{i=1}^n\sum_{j=1}^n\binom{i+j}{i}(\alpha_i \lambda_1^j+\beta_i \lambda_2^j)$，然后 NTT
解法三：令 $f(i)=\sum_{j=1}^n\binom{i+j}{i}A^iB^j$，求出 $f(i)$ 与 $f(i+1)$ 的递推关系
F：$(8^2-7^2)-(6^2-5^2)=4$，即连续 4 个数可以得到一个 4。利用这个来构造
G：枚举 $g(x)$，最值只在端点和对称轴取，因此在符合条件的 $x$ 里找 lowerbound 和 upperbound
I：前缀和 hash
*J：最多走 6 步就全是 $b_i$ 了，因此用高斯消元算出全 $b_i$ 的情况，前 6 步 dp
K：简单 dp
L：每个 $i$ 实际上是转移到前面的某个 $p$ 的倍数，而由于答案是单调的，所以这个 $p$ 应是 $i$ 的质因子里最大的
*M：讨论三种情况的凸包求切
BCH：
2021 CCPC 网络赛 2
1002：提神醒脑讨论题
^1004：解法一：质数间隔很小，直接上 Miller_Rabin，暴力枚举 $f(x)$ 和 $f(f(x))$
解法二：如果 $f(x)>2$，那么 $g(x)$ 一定是整数，且在两个相邻的素数之间，所以一定是合数
1005：求出周期 $p$，假设 $p>0$，记 $s_i$ 为 $a_i$ 的前缀和，那么就是求 $\min_{i|s_i\equiv x\pmod p} \frac{x-s_i}{p}+i$，将 $-\frac{s_i-(s_i \bmod p)}{p}+i$ 按 $s_i \bmod p$ 分类放好，那么求答案就是个前缀最小值
1006：找到所有的 nunhehheh，统计后面的 a 的个数
1007：假做法：格子要么是链（两头可能封闭）要么是环，先把有开口的链全部归先手，剩下的两头封闭链和环从小到大排序分奇偶给先手后手
1009：队友说是沙雕题
*1010：最终形态就是 $2n$ 个点形成一个大环，所以贪心，左边每个点依次去找右边的不跟它同一连通块的最小点
1011：按点权从小到大激活每个点，激活一个点意味着它相邻的连通块全部跳到它，因此每个点跳跃路径形成一棵树
1001 1003 1008 1012：
2021 Jiangxi Provincial Collegiate Programming Contest
A：$O(n^3)$ dp，注意空间
BCD：队友说是沙雕题
*E：最多只能跑一个兵，所以判断：1、是否有兵能直接逃；2、是否有两个兵的横差大于纵差，这样这两个兵不能同时被吃；3、特判一个兵在另一个兵的直接左上角，这时两个都可以吃
F：dp
*G：按 $\sqrt{1e6}$ 分为小质数和大质数，小质数暴力，大质数相当于求区间众数，莫队
*H：如果不能开局打死后手，那么后手必胜
*I：每个人要么是 $a_i$，要么是某个 $a_j+dis(j,i)$，旋根 dp
J：解法一：二分+链表 check
解法二：预处理每个数至少要多大的 cache 才能使其命中
K：平方和公式
L：线段树求区间并
2021 ICPC Regional 澳门
A：任找一条哈密顿路，如果正着走不合法那么反着走一定合法
C：队友说是沙雕题
*E：根号平衡，大小在 $\sqrt n$ 以内的环暴力枚举每种置换，大小超过 $\sqrt n$ 的环做卷积
F：模 $n$ 意义下各数的差不变，因此枚举 $a_1$ 的增量，$n$ 次枚举即可
G：设 $dp_{i,0/1}$ 表示要读 $i$ 这个数而它在左端点/右端点的最小代价，用线段树预处理 $i$ 在左端点/右端点时下一个读不到的数
*H：考场解法：考虑 $i$ 下一个是 $j$ 的贡献，要么 $i$ 是 $j$ 的直接父亲，$O(n)$ dp；要么 $i$ 和 $j$ 没有祖先关系，拓扑序会形成一个小环，$O(n^2)$ dp。总共 $O(n^4)$ 但是除以很多个 $2$
I：所有串拼起来做 SA，只有 SA 上相邻的两个串可以连边做 MST。评测机过慢导致 SA 会被卡常，需要改成 SAM
K：MST
BDJ：
The 17th Heilongjiang Provincial Collegiate Programming Contest (2022 黑龙江省赛)
A：题目的隐藏条件是横放的书的右端点不能超出竖放的书。二分或者推式子 $O(1)$
C：2-SAT 用主席树优化连边 从底往上 dp，设 $f_i$ 表示 $i$ 划到 $A$ 集合里时，子树里的 $B$ 集合的点最小是多少；设 $g_i$ 表示 $i$ 划到 $B$ 集合里时，子树里的 $A$ 集合的点最大是多少
*D：第一个圆心切向第二个圆（半径为 $2$）并作切线的垂线得到第二个圆的运动区域，由此判断第三个圆是否落在区域内。
*E：先清洗掉 $b_i$ 含有的平方因子，然后式子变成 $\sum_i \sum_j \frac{b_i \cdot b_j}{\gcd(b_i,b_j)^2}$，正常反演
FGH：队友说是沙雕题
I：$O(k^2)$
L：扩展 kmp
BJK：
2022 Hubei Provincial Collegiate Programming Contest (2022 湖北省赛)
A：核酸点之间 MST，非核酸点一定是走到最近的核酸点
BJ：队友说是沙雕题
*C：（队友做了不想看了）
*E：从高位到低位考虑，每一位一定是选最后一个 or 1 或者最后一个 and 1 作为它 1 的来源（初始也可以看作是一个 or 1），然后后面的 and 0 全部反转，这等价于一个后缀的 and 全部反转，所以从高位到低位依次处理即可
*F：$2, 3, \cdots, n-1, n-1, n-2, \cdots, 2$
G：枚举答案的奇偶性，这样就知道每个位置所需的奇偶性，从左往右每个奇数跟其下标奇偶性相反的奇数配对，横着填过去，中间再加一层横着的消掉对中间的影响，其他竖着填
H：一步操作之后的状态数很少，数位 dp 一下
K：略
L：直接线段树懒标记即可，$s_i$ 转换是单点修改，一定会把相关标记全部推下去的
DI：
2022 Official
2022 ICPC Regional 西安
*A：鬼脚图，每条 bridge 本质上是交换排列中的两项。时间分治
*B：对于每个 $k$，染非 0 色就相当于选尽可能多的点使得每一行选不超过 $k$ 个、每一列选不超过 $k$ 个，因此枚举 $k$，增量网络流
C：最优一定是先大家一起克隆，然后大家一起出题
*D：每个人有个 $m$ 维数组表示他在各比赛中的名次，各比赛也可以对这个五维数组做后缀和，因此每走一步相当于五个后缀和取 $\min$。对每个人预处理倍增即可
E：$f(x)$ 相当于三进制下的数位和加位数，先给 $r$ 加 $1$，然后枚举第一个比 $r$ 小的数位，后面全填 $2$
F：每个队单独考虑
G：队友说是沙雕题
H：超级无敌大分类讨论
J：最多选两个数，所以求最大和次大就行
*L：可以证明如果有反链，一定是全体叶子，所以一层一层地剥掉叶子即可
2022 ICPC Regional 南京
AGI：队友说是沙雕题
*B：考虑修改点是否被选，如果选，那就是前后缀合并（前后缀分别都是单调队列优化 dp）；如果不选，枚举一下修改点上一个被选的位置，也是前后缀合并和单调队列
D：二分，然后每个没满足要求的点可以给起始点贡献一个区间
*E：考场解法：长链剖分，记 $dp_{x,i}$ 表示 $x$ 子树往下 $i$ 层的最小代价，把数组从 $x$ 转移给 $x$ 的父亲时可能有更新，但更新的形式是 $\min$ 上 $a$ 数组的区间最小值，可以懒标记
题解解法：每一层建虚树
看大题解
*J：二分图左边的点表示 $i-a_i$，右边的点表示 $i+a_i$，每个 $i$ 是一条边。对于每个连通块，大小为奇数无解，大小为偶数任建生成树从底往上贪心
K：NaN 点相当于把堆分为两个独立部分，大力推式子
M：求出下凸壳的数量，注意一吨细节
CFHL：
2023 Official
The 2023 ICPC Asia EC Regionals Online Contest (I)
AL：略
*B：$T$ 在 $S_1$ 的 SAM 中对应一个 fail 子树，在 $S_2$ 的 SAM 中也对应一个 fail 子树，问题就是两个子树共有的 $j$ 有多少个，二维数点
D：每个连通块补成团
F：找规律加归纳可得 当三个数不同的时候必胜，所以仅需考虑形如 $0,0,x$ 的情况，$x$ 所含的质因子 $2$ 的数量如果是奇数则必胜，偶数则必败。总数减掉不合法的，建个 trie
G：只需每次判断 $a_i$ 所在连通块连向 $b_i$ 所在连通块是否合法即可，合法那么答案一定是乘上 $\frac{1}{size_{a_i} \cdot size_{b_i}}$，判断合法就启发式一下，按度数或者 size 启发式都可以
I：直接 dp，滚动数组或者把最后三个 0/1 的维度容斥掉
JK：积分推式子，基本都是跟圆心有关
CEH：
2023 ICPC Regional 杭州
A：恶心大模拟
*B：只需判断每个区间 $[2^i,2^{i+1})$ 是否有解，有解输出 $2^i$ 即可。判断有解用 FFT
*D：$x, a, 1-a, \cdots, a, 1-a, 1$
F：每个询问二分，相当于问 $[1,mid]$ 是否有点到询问点的距离超过 $k$。预处理每个前缀的直径，只需考虑直径端点
G：最短路，特殊处理初始被蛇身占领的格子
H：环套树，树边都可以递推（注意递推是求一个长度，不是概率也不是期望），环上的点如果 $a$ 全相同那么谁都不会加 $w$，如果 $a$ 不全相同则必有 $x$ 连向 $y$ 且 $a_x < a_y$，那么 $x$ 必然加 $w$，从这里破环为链
J：队友说是沙雕题
K：带区间修改的主席树
M：略
CEIL：
2023 ICPC Regional 南京
A：bfs 求出所有 $(x_1,y_1,x_2,y_2)$ 表示 $(x_1,y_1)$ 的袋鼠能否把 $(x_2,y_2)$ 的袋鼠干掉
^C：相当于求有多少个 $k$ 使得 $(kp+1) \oplus (p-1) \le m$，可以像数位 dp 一样扫一遍，也可以略加分析然后只判断 $O(1)$ 个 $k$
*D：记 $dp_{i,j}$ 表示以 $i$ 为根的子树每条路径有 $j$ 个黑点的最小代价，$dp$ 关于 $j$ 是凸的，维护其差分
F：实际上是问 DAG 有没有不是 $1 \to 2 \to \cdots \to n$ 的拓扑序
G：将物品按照价值从小到大排序，必有一个后缀是全选的，且全选的后缀中，代价最大的 $k$ 个被免费选走，所以枚举这个后缀，前面普通背包
*K：从左到右的最短路等价于从上到下的最小割等价于从上到下的最大流，相当于每条边衍生出一条容量无穷、费用为 1 的边，求最小费用增加 $k$ 的流量
L：首先把重量为 1 的物品合并，于是重量就没有用了，所以从大到小贪心即可
M：线段树维护区间的水平面之和、柱高最大值，每次修改一根柱子，会修改左右一片的水平面
I：队友说是沙雕题
BEHJ：
2023 ICPC Regional 济南
AD：队友说是沙雕题
*B：当 $k \le \sqrt n$ 时，$dp_{i,j}$ 表示以 $i$ 为根的子树，根所在块大小为 $j$，的方案数，子树卷积 dp；当 $k > \sqrt n$ 时，$j$ 的含义变成该子树切了多少个大小为 $k$ 的块出去
E：先求一个最大匹配，然后新增的边一定是从源点能到的左边点到能到汇点的右边点（这样才能流残余网络），也可以用交错路来讨论
G：第 $j$ 列和第 $c-j+1$ 列总共最多两个 1（中间的列最多一个 1），这两个 1 所在的行可以视为连了一条边，给每个连通块 01 染色，成功就答案乘 2，失败就输出 0
*H：大讨论修改字符对每个后缀的影响
I：每次从左到右找第一个 $a_i > i$ 的，然后以它为左端点，找到尽可能远的右端点进行一次操作
K：考虑固定左端点，右端点怎么算答案，这样就会推导出滑窗维护 $\sum_{j=1}^i 1-(a_j-a_{j-1})$ 的中位数的做法
M：凸包凹一点，想办法枚举凹的那个点即可
CFHJL：
其他 ICPC/CCPC
The 13th Chinese Northeast Collegiate Programming Contest (2019CNCPC)
BCJ：略
^*D：数据结构诈胡大师：关键点只有 $O(m)$ 个，建棵虚树跑暴力，时间 $O(m^2)$
E：非叶子节点把它相关的所有边连向其中最小的那个
*F：拆点，从出度为 0 的开始倒着拓扑求 $SG$，注意演员不能当作对面的人
G：横纵坐标独立，聪明一点就取中位数，不聪明就三分
H：noip2018 铺设道路
2010 ICPC Regional Dhaka
ABC：略
D：状态数很少，暴力
E：$O(n^3)$ 的 dp 能过（设 $f_{i,j}$ 表示区间 $[i,j]$ 的答案）
F：可以先让某对对称位置不一样，然后把别的换完，最后换这对位置。要讨论一下
G：合法的场数是连续的一段数，调和级数求和
*H：方法一：短边所对应的顶点一定是距离最远的，直接三分套三分
方法二：分别假定每个点是最远的，然后跑局部搜索（阉割的模拟退火），得到三个答案，可证取最小即为最后答案
*J：最大点权独立集（网络流）+字典序最小方案（贪心让每个点归属于 $S$ 集或 $T$ 集）
2013 Southwestern Europe Regional Contest (SWERC 13)
CEI：略
A：给了 20s，直接 $O(n^4)$ dp
B：费用流 或 最小流 或 最大权匹配
*D：套路题。暴力生成前几个串 $A_i$，直到 $|A_i| \geq |S|$。然后先判断 $A_i$ 是否包含 $S$，再判断 $A_i L A_i^{-1}$ 之类的是否包含 $S$
F：数位 dp
G：暴力搜索
H：dp $f_i$ 表示 $T$ 串从 $i$ 开始往后的不同的方案数
2018 ICPC Regional Seoul
BDF：略
A：扫描线，扫描 y 轴枚举第一条线，用线段树查找覆盖最多的位置作为第二条线
*C：先放 $a_{\frac n2}$，然后 $a_{\frac n2-1}$，然后 $a_{\frac n2+1}$，然后 $a_{\frac n2-2}$，然后 $a_{\frac n2+2}$……
E：
*I：计蒜之道2016复赛 青云的网络设计方案。基本思想就是，分层确定，最后讨论第二第三层怎么搞
看大题解
K：2-SAT
L：算出每天需要新开多少个人，然后每天贪心地选人，优先选工作狂
2015 ICPC Regional 沈阳
*B：$i$ 和 $j$ 以 two pointers 的形式往前枚举（若 $s_j$ 是 $s_i$ 的子串则 $j$ 往前走，否则 $i$ 往前走）
D：队友说是沙雕题
F：把 $a_i$ 变成 $\gcd(a_i,m)$，最多只有 $m$ 的约数个不同的 $a_i$。在由 $m$ 的约数构成的整除关系图上模拟容斥
G：讨论三种情况：A 直接在 2-3 这条边上蹲 B；A 直接在 3-4 这条边上蹲 B；A 先摸了 2 然后去 3-4 这条边上蹲 B。注意 corner case 和精度
^H：大家一起走，每一条指令最多会产生 2000 次合并，记录偏移量，暴力并查集
I：三维偏序，有两维在 1000 以内这个可以写得暴力一点
K：首先发现它是个卷积，然后写个模任意质数 NTT
M：每个集合新建一个方点，跑最短路
2015 ICPC Regional 上海
F：略
A：队友说是沙雕题
B：用 $2$ 的幂来构造，$n$ 为偶数时先构造 $n-1$ 再给 $2^{k-1}$ 加 $1$
*D：把挡板建出笛卡尔树，然后分治
E：记忆化搜索 $f_{a,b,c,k}$ 表示枚举三位，第一位数字为 $a$，第二位数字为 $b$（乘号视为 $10$），第三位数字为 $c$，进行了 $k$ 次交换，的贡献和
K：预处理前后缀的答案，枚举换哪一位
L：模拟往回走，路径是一条链来的
2014 ICPC Regional 西安
A：队友说是沙雕题
B：大模拟
*C：二分，然后二元关系网络流
E：平移可以看作是一个平行四边形加上端点的两个扇形；旋转就是一个大扇形
F：推式子，是个容斥
G：两个串拼起来建个回文树
H：总共 $O(n^2)$ 个游戏状态形成一幅 DAG，递推一下就好了
I：建个 trie 乱搞
K：相当于更相减损术中所有元素都会出现一次
2011 ICPC Regional 成都
A：无脑递推（设 $f_{i,j}$ 表示有 $i$ 堆 $1$、其他和为 $j$，是必胜还是必败）
B：手掰是点数减一，刀切是 $\log$
D：状压 dp（设 $f_{i,s}$ 表示到了第 $i$ 个点，状态为 $s$ 的最小代价，状态是三进制的）
E：每一局 Alice 只有两种选择，是个 2-sat
*H：考虑每条边的贡献，就是两棵子树的 size 的 $\min$ 的两倍
I：大模拟
*J：根据二阶差分可以算出腿数 $\leq k-1$ 的动物，剩下的大讨论
2019 ICPC Regional Southern and Volga Russian (NERC)
AH：略
BCFLN：队友说是沙雕题
E：对于两个点，若他们必须相同或相反，则连一条边，那么一个连通块只有两种染色方案
G：枚举最后一次 Reset 在哪，前面的只要贪心让自己不爆牌就行了，后面的就找到最远的位置使自己恰好不爆牌，看对面爆不爆牌。后面的部分可以 two pointers
J：二分
*M：对于边长为 $n$ 的矩阵，取掉左下的最大矩形、右上的最大矩形，还剩下的左上矩形和右下矩形是可以并行操作的，因此操作数大约是 $f(n)=f(\frac n2)+4$
2019 ICPC Regional Jakarta
ACGH：队友说是沙雕题
B：dp，设 $f_{i,j}$ 表示 $i$ 这棵子树，$i$ 状态为 $j$ 的方案数，一个点有 3 种状态：作为终止端点、作为非终止端点、不是端点
E：贪心然后调整
F：枚举根，然后 hash
J：dp，设 $f_{i,j}$ 表示到了第 $i$ 块石头，选了 $j$ 个 $G_3$，所能达到的最少的奇数段数量是多少
K：线段树维护矩阵
L：网络流
2014 ICPC Regional 鞍山
EI：队友说是沙雕题
B：$n$ 只有 $5000$，暴力
*C：不合法的三元组是，有两对互质一对不互质，或者有一对互质两对不互质。对于每个数算出 $(跟它互质的数\times跟它不互质的数)$，那么不合法的三元组每个被算了两次
D：距离平方和最小是取平均数，用 $n-k$ 的滑窗算一遍
G：每个 byte 只有两种取值（阈值以上和以下分别取 $w$ 最大的），然后二元关系
H：打表，暴力写得优美可以 10s 出解
K：暴力旋转（枚举一条边，再枚举另一条边套上去）套 Burnside
L：题意转化成：点集的子树并全体 +1、点集的祖先链并求和，线段树维护
2014 ICPC Regional 北京
A：队友说是沙雕题
B：搜索剪枝冲过去了
C：x 轴 y 轴独立，解同余方程
D：区间 dp（设 $f_{i,j}$ 表示 $[i+1,j-1]$ 全部删掉的最小代价）
E：总的减去不合法的，不合法的就枚举交点算一算
*F：$X^3$ 转化成，枚举 $i,j,k$，问有多少种方案使得这三盏灯全亮。状压 dp
**G：解法一：暴力找出前 1e8 个解，剪枝冲过去了？？？
-解法二：DAG 轻重链剖分，在重链上二分跳出去的位置，每个询问两个 $\log$
H：折半搜索，FWT
I：圆环交板子
*J：dp，设 $f_{i,j,0/1}$ 表示考虑 $i$ 的子树，$i$ 这个点在它的子树里排第 $j$，它是否被选，的答案。
K：如果一个数后面有比它小的，它就一定要操作一次
2019 ICPC Regional North-Western Russia
A：队友说是沙雕题
B：第 $i$ 个数为 $11+710i$
*C：每个叉的左右两条竖线都加上，跑欧拉回路
*E：以一个关键点为根，在其他关键点的深度为 $\frac{deep_i}{2}$ 的祖先处打标记，标记可以下传到他其他儿子上。最后 dfs 一遍看谁的标记数量是关键点减 1
H：每种 $t$ 只算一次，暴力复杂度是 $O(\sum a \ln \sum a \log n)$ 跑不满
I：先求出一个矩形边框作为金字塔底边的必要条件，再取矩形的较长的边长作为金字塔底边长
J：倒着逐位确定
K：使 A 极大，然后每个字母默认是一行，某一行空了就沿用它上一行或下一行
*L：SAM 上枚举每个结点作为 border，那么最小的 period 就是这个结点的出现位置集合的最小差分
M：$O(n^2)$ 写优美一点
2019 ICPC Regional Taipei-Hsinchu
CDHJK：略
A：暴力
*B：树形 dp 疯狂讨论
*E：考场解法：$-inf,-inf,0,0,\cdots,0,-1,a$，则 std 是 $1997(a-1)$，他是 $a$，理想情况下 $1996(a-1)=k+1$。若 $1996$ 不整除 $k+1$，则把 $k+1$ 变大，并且修改第一位。
别人解法：$-1,a_2,a_3,\cdots,a_{1999}$，其中 $\sum_{i=2}^{1999} a_i=k+1999$，则 std 是 $1999(k+1998)$，他是 $1998(k+1999)$。妙啊
I：暴力
L：四边形的四个点一定都在凸包上，旋转卡壳
*M：魔改的组合数取模，主要目标是修正组合数中 $D$ 各质因子的数量，使其成为正常的组合数取模。
2019 ICPC Subregional Brazil
ABDGHJM：队友说是沙雕题
*E：找到♀最少（有多个时♂最多）的缸，称为♂缸，如果♂缸里有♂则需要再找一个♂最少的缸作为♀缸。剩下的每个缸有一个扔♂的代价和扔♀的代价，一个空缸可以减少一点扔♂的代价，于是 dp 确定最小值。注意一堆特殊情况！！
F：
I：
*K：大力推式子（枚举开头所在列和结尾所在列），最后是个斐波那契数列求和
L：出烂掉的广州一模题，$ans=2^{n的二进制的1的位数}$
2019 ICPC Regional North American Southeast (Div 1)
H：略
A：暴力
B：预处理每个询问是哪个数组的哪个版本，然后每个数组单独处理
D：二分图最大独立集
E：预处理 $f_{i,j,k}$ 表示长度为 $i$ 的序列、前 $j$ 个位置不算 fixed point、共放了 $k$ 个 fixed point 的方案数（全错排+组合数），然后贪心放
F：
G：树上 LIS，正常地用线段树做 LIS，每个点临走时把自己造成的影响还原回去
I：字符串处理题，每个封闭的区域都需要破一道墙
J：把每个数字的最后出现位置集合记为 $s$，那么就是在 $[1,s.begin()-1]$ 里选最小的，这样一直贪心下去
2019 ICPC Regional Northwestern European (NWERC 2019)
FI：略
AEG：队友说是沙雕题
*B：贪心 check 每一个点，判断依据是会不会跟已选结点冲突、必需结点数量是否超过 $k$
看大题解
C：贪心，先放交点
H：二分，转化成求最长的区间使得 $h_r-mid \cdot r \ge h_l-mid \cdot l$，区间必有一端点在整点上，枚举整点，预处理前后缀最值
*J：从大到小枚举最大改变量，相当于每次有一个元素从自由符号变成固定符号，只需判断每相邻两个固定符号是否会贡献一个删除操作
K：dp
D：
2019 ICPC Regional Southwestern European (SWERC 2019-20)
ABCFGI：队友说是沙雕题
D：模拟
H：打表找循环节（大概几亿），然后分段打表
J：设当前处理 $[l,r]$，把这个区间的最小值全部提取出来，贡献是个卡特兰数，剩下分成的区间递归处理
K：边拆点无脑 dominator tree
*L：观察发现每条河流的每段陆地连通块大小不超过 20，因此可以每段状压暴力算 SG
E：
2019 ICPC Regional Latin American
KLM：略
EFGI：队友说是沙雕题
A：$10^5$ 个点的 DAG 求最长反链，Dinic 跑最小链覆盖
*H：dp，设 $f_{i,j,k}$ 表示先手 $i$ 分，后手 $j$ 分，先手手上握着 $k$ 点，的获胜概率。发现存在循环转移：
解决方法一：无视循环迭代 100 次
解决方法二：对 $f_{i,j,0}$ 进行二分，就会破掉这个环
*J：从一个点出发肯定先到左右最大值较小的那个，然后再往对面跳一步，随便维护一下
BCD：
2018 ICPC Regional Southwestern European (SWERC 2018)
ADE：队友说是沙雕题
B：二分，判断长度为 $mid$ 的连续段是否合法
C：暴力
F：枚举一个点，极角排序 two pointers
*G：每个串如果是 APP 则可以直接得到 ascii 码的和，如果是 SUB 则递归求 ascii 码和，转化成前缀询问，每次只走一个方向
H：三次最短路以后三维数点
I：先把边框和噪音去掉，然后对每一个连通块做模式识别
*J：先对前两个数、后两个数分别生成足够的后 $\frac n3$ 位相同的数对，然后暴力枚举两边的数对
K：区间 dp
2018-2019 ICPC, NEERC, Northern Eurasia Finals
EG：略
A：枚举比分情况，判断是否合法
B：把每个 cavalier 拆成两个点，并连一条边，跑一般图最大匹配
*C：每步暴力 $O(n^2)$ 找重心，询问重心，然后删去不合法的点
F：若 $n$ 为质数的幂则二进制分组；否则找两个互质的因子就可以解了
H：把 2-sat 做成 DAG 之后满足三个条件即可：$\forall$ 不能互相到达、$\exists$ 不能到达它后面的 $\forall$、$\exists$ 不能到达自己的反
**I：析合树计数 dp
看大题解
K：$ans=\max_{i:t_i \leq T}\{t_i+d_i+\sum_{j:t_i<t_j \leq T} t_j\}$，线段树随便维护一下
L：贪心
M：队友说是沙雕题
DJ：
2019 ICPC NERC Northern Eurasia Finals
BEK：队友说是沙雕题
A：带很多细节的贪心
*F：考场解法：先把第二个序列补全到总长为 $n+m-1$，然后 prufer 还原，途中若第一个序列不够长则把第二个序列的补全位让给第一个序列
正常解法：把第一个序列任意补全到长度为 $n-1$，把第二个序列任意补全到长度为 $m-1$，一定有解
J：暴力枚举 $s$，复杂度是 $O(n)$ 的
*L：先贪心前 $k$ 个一位一位地放
CDGHI：
2017 ICPC Regional Latin American
BCEH：略
A：（队友做了不想看了）
*D：用 set 维护连续段。势能分析，每次操作最多增加 2 个连续段，所以连续段的总量是 $O(n)$ 的
F：二维数点
G：dp，设 $f_{i,s,t}$ 表示以 $i$ 为根的子树，原本应该是 $s$ 但现在却是 $t$ 的方案数
I：MST 上找最大边
J：$n$ 的约数都 $O(n)$ 判断一下
*K：黑白染色，网络流，源点连向黑格子，黑格子连向白格子，白格子连向汇点，o 的位置流量为 $1$，其余位置流量为 $2$，这样一种流的方案就对应原图一种画法。
*L：假设从左下走到右上，竖直距离大于水平距离，那么就是找一列宽度为 $1$ 的来游走补回多出的竖直距离，其他情况同理，稍微推推式子
M：把一个栈看成一个字符串，每次贪心找字典序最小的那个
ICPC Egyptian Collegiate Programming Contest (ECPC 2018)
BFLM：队友说是沙雕题
A：折半搜索
*C：dp，设 $f_{i,j}$ 表示 $A$ 数组前 $i$ 个位置匹配了 $j$ 个，的最小代价。转移条件是转移点到 $i$ 之间不能有正在匹配的数字。单调队列转移
D：简单莫比乌斯反演
E：dp，设 $f_{i,j,k}$ 表示用了 $i$ 个数、最后一段长度为 $j$、最后一个数相对大小为 $k$ 的方案数。转移就考虑是新开一段还是接在最后一段末尾
H：等价于 $u$ 往外走 $L-k$ 步能走到的最小边
I：枚举直角点，极角排序+two pointers
*J：GDKOI2015 青蛙跳环 $x$ 和 $x+\frac n2$ 的连边情况是一样的，把它们缩为一个点，去除重边，就成了欧拉回路
K：分为 $P$ 在左边、$P$ 在右边、$P$ 在中间被劈开分别计数
G：
2020 ICPC Asia Taipei-Hsinchu Site Programming Contest
ABM：队友说是沙雕题
C：$O(n^2)$ 暴力冲过去了 std 甚至连空间都是 $O(n^2)$ 的
*D：先把度数 $>28$ 的点去掉，剩下的搜索
*E：区间 dp，设 $dp_{l,r}$ 表示 $[l,r]$ 消掉是否可行，再设 $f_{l,r}$ 表示 $[l,r]$ 这段消掉某些区间之后最多剩下多少个颜色 $s_l$
F：环套树最小点覆盖，对于一条环边枚举某一端点作根然后断掉这条边形成树做 dp
G：树哈希+最小表示
H：MST
I：点双模板题
K：数位 dp 但是不用 dp，从高位到低位依次枚举前 $i$ 位压线，用排列算方案数
JL：
EC-Final 2017
A：$2^n-\sum_{i=0}^{k-1}\binom{n}{i}$
B：均值是固定的，每个 $a_i$ 关于 $m_i$ 的代价的一阶导也是递增的，所以直接贪心
*C：只要等了红灯接下来必定全程绿灯，而他一定可以选择在某个灯下等红灯，因此是 $\sum s+\max b_i$
H：LIKE就是全部选元音或全部选辅音，存在DISLIKE可以用 dp 或者贪心
J：实际上是每次选的长度 $\ge 3$ 都可以，差分之后贪心
KM：略
*L：只要摆出 S _ _ S 这样的局面，且其余的空位数量是偶数，那么先手必胜了，因此：
$n \le 6$ 暴力（全部是平局）；$7 \le n \le 15$ 若 $n$ 奇数则先手胜否则平局；$n>15$ 若 $n$ 奇数则先手胜否则后手胜
DEFGI：
2018-2019 ICPC Northwestern European Regional Programming Contest (NWERC 2018)
*A：两维独立，每一维任务是找出 $x_1 \le x_2 \le \cdots \le x_n$ 使得 $\sum(x_i-a_i)^2$ 最小。枚举 $i$，若当前 $x_{i-1} \le a_i$ 则令 $x_i=a_i$；否则 $x_i$ 要跟 $x_{i-1}$ 相等（可能还要跟更前的相等），并整体左移
B：按拓扑序的倒序依次贪心确定
C：取 $\alpha=\frac{180\degree}{n}$，然后各点按 dfs 序依次确定角度，间隔 $\alpha$
*D：二分答案 $mid$，找出 $[a,b]$ 时间段内能游走的子图，按 $dis(1,x) \le a+mid-dis(x,n)$ 标出子图的起点，如果子图有环则一定合法，否则在 DAG 上 dp 出最长逗留时间
看大题解
E：shuffle 和 sort 都相当于是在一个集合上标注这是 shuffle 还是 sort
*F：解法一：朱刘硬艹
解法二：$s$ 边形成环套外向树，默认每个点都是通过树边通关的，每棵树默认都是用 $n$ 来破开环的，所以问题转化成从 $0$ 通关 $n$ 的最短时间，$O(n^2)$ dp
G：从起点往外分成若干圈，每一步都要走到更外面的一圈即可
H：贪心即可，注意相邻的 0 之间的贡献只能是偶数
IJK：队友说是沙雕题
2020-2021 ACM-ICPC Latin American Regional Programming Contest
A：归纳可证所有数都形如 $1/n$，因为 $1/n$ 与 $1/m$ 运算得到 $1/(n+m)$，因此暴力+打表
B：枚举段长，预处理每个数的左右上升下降
CDE：队友说是沙雕题
F：$O(n^2)$ dp
*H：相当于问有向图从 1 出发，有些边能经过无数次，有些边只能经过一次，问最多经过 1 号点多少次。将 1 号点拆点，网络流
*J：合法的机器数和包含关系不多，建出图，按度数根号平衡
K：$O(kn)$ dp
L：暴力枚举初始时刻，$O(n)$ 判断
*M：后缀平衡树
N：看小数点后的数的和模 $100$
GI：
hdu 多校
2019 Multi-University Training Contest 1
*A：最小表示 dp（设 $f_{i,j,k,l}$ 表示到了第 $i$ 位，最小表示后第一个 $2$ 在第 $j$ 位，第一个 $3$ 在第 $k$ 位，第一个 $4$ 在第 $l$ 位的方案数）
*B：每个点更新维护一个线性基，使得基元都是最新的
看大题解
D：逃生模型（$f_i=\max(f_{i+1},\frac{dis_{i}}{v_i})$）
E：最短路图最小割
I：贪心
*K：枚举三次根，然后正常 $gcd$ 反演套路
**L：三种前缀和分别对应三次组合数卷积
看大题解
*M：判断 $1$ 的凸包和 $-1$ 的凸包是否有交
2019 Multi-University Training Contest 2
hdu多校怎么出成介个亚子啊
B：合唱队形，字典序方案符合贪心性质
E：考虑每一对的贡献，因此是 $\frac{\sum_{i=1}^n \binom{i}{2} \times \frac12 \times [\sum_{j=0}^{\infty} (\frac14)^j]}{n}=\frac{\sum_{i=1}^n i(i-1)}{3n}$
*F：每两点都会产生贡献，因此用 FWT 算 $cnt_i$ 表示有多少个点的 $x \oplus y \oplus z=i$
-G：超现实数不平等博弈，详见 WC2018 杜老师课件
H：二元关系
I：回文树瞎搞
J：每个二进制位都问一下，所以是 $n!$
K：每个区间找最大的 50 个左右暴力判断
L：枚举右端点，线段树维护左端点是否可行，那么是区间 $\pm1$ 的操作
2019 Multi-University Training Contest 3
B：dominator tree，写 DAG 版就好了
D：二分，然后 dp 判断
*E：式子最后化出来，前面是质数幂和（洲阁筛或 min25），后面是 $i^2\phi(i)$（杜教筛或 min25）
看大题解
F：素数分布很密集的，$n$ 往前暴力找，Miller_Rabin 判一下，求阶乘用 Willson 定理
G：线段树二分
H：前缀异或和，询问区间有多少对数是不同的，带修莫队
I：暴力连边费用流卡常加乱水
K：dp，换根
2019 Multi-University Training Contest 4
A：$n=2^k-1$ 时答案为 $1$，否则答案为 $0$
C：分奇偶大讨论
F：吃树和休息的贡献是独立的，贪心吃树的贡献，dp（斜率优化）休息的贡献
*G：用逆序对来判断华容道是否有解，有解必有 120 步以内的解
H：二分+主席树
**I：$ans$ 初值为 $\sum a_i$，每次默认加上 $\sum b_i$，预处理 $-p_i$ 标记。用一个巧妙的分块优化
看大题解
J：先把 100 以内的质数判掉，那么剩下的质数指数都 $<10$，最小指数 $cnt$ 满足 $(\lfloor \sqrt[cnt] n \rfloor)^{cnt}=n$
2019 Multi-University Training Contest 5
*A：化成 $\frac px \leq \frac bk \leq \frac p{x-1}$，套法雷序列
B：两个数组放一起建棵 trie，然后 $n$ 次贪心
*C：分别设 $S$ 和 $T$ 划分线段比例为 $x$ 和 $y$，根据面积相等列出两个等式，大讨论解方程
D：$n$ 个关键点把函数划分成 $n+1$ 段，每段分别求解
E：打个表观察一下就知道如何 next_permutation 了
F：扩展 kmp
G：$[x,y]$ 外面的走法是唯一的，因此问题化成 $1$ 走到 $y-x+1$，递推一下
H：枚举对称轴暴力判，会有恶心的情况
2019 Multi-University Training Contest 6
*A：最大获利，贪心模拟网络流，合并用长链剖分
看大题解
B：随机下 LIS 长度只有 $O(\sqrt n)$，按这个分层来跑 LIS 的 dp
D：队友说是沙雕题
E：枚举上下边界，线段树维护区间最大值
F：划分成 $n^2$ 个小区域，每个区域分别算答案
H：$\gcd(f(n,m)-n,n)=1$，因此 $f(n,m)-n$ 非常小，大概前 160 个质数那么大
-I：杨氏图表
*J：枚举根，dfs 序 dp，有用的 $m$ 只有 $O(\sqrt m)$ 个
*K：解法一：有用的问号不会太多，大概最后几十个，所以逐位确定就好了
解法二：倍增式的逐位确定，详见题解
L：贪心取叶子中的最大值，可证最优
2019 Multi-University Training Contest 7
A：队友说是沙雕题
*B：选 1 作根，对于每个点 $i$，它的儿子根据子树的形态（用 hash 来判）分为若干个类，那么这个点的贡献 $ans_i=\frac{(儿子数量)!}{\prod (每个类的个数)!}$，这棵树的答案为 $\prod ans_i$，然后换根
*F：让复习最少的 $n-k+1$ 题时间和大于 $m$，即前 $n-k+1$ 题不能全被卡，那么至少能做 $k$ 题
G：本质上是每次带权二分，用 dp 实现，设 $f_i$ 表示区间长度为 $i$ 时的答案，由于 $f_i$ 单调递增，因此决策点也是单调的，可以 $O(n)$
*H：四个象限都可以归约为第一象限，然后 $a=\min(a,2b)$、$b=\min(a,b)$，那么所有情况都可以归约为先 右左右左…… 地蛇形扭，再直走
J：按 $a_i-b_i$ 排序（这是先手的收益），先手和后手分别从两端开始取，注意判断 $a_i=0$ 或 $b_i=0$ 的情况
^k：设 $f_i$ 表示从 $i$ 走到 $i+1$ 的期望花费
2019 Multi-University Training Contest 9
*A：一顿乱推得到 $g_m(n)$ 是两个调和级数相加（再加一些杂项），那么每 $\sqrt n$ 打一次表，要用的时候再 $O(\sqrt n)$ 去递推
B：$ans=1+$交点数
C：先折半搜索得到两个集合，然后对于每一位单独统计，枚举这一位是 $x+y+($是否进位$)=4$（或 $14$），然后提取出这一位是 $x$ 和 $y$ 的数，双指针扫一遍统计符合进位规定的数对
E：开头一段 y 是不动的，然后看这段 y 后面是不是跟一个 z，如果是就会翻成 b，否则不动
F：枚举 10、20、50 分别用多少
*G：一条边分成两棵树，总共得到 $n-1$ 个直径对，双指针扫一遍统计贡献
H：$n$ 次贪心，每次取异或和最大的一对
*K：设 $g_i$ 表示 $i$ 个叶子的线段树的 叶子深度乘叶子 id 的和，$G_i$ 表示 $g_i$ 的前缀和，当然还要有一些辅助函数。记忆化搜索，每次只会到 $\lfloor \frac n2 \rfloor$、$\lfloor \frac n2 \rfloor \pm1$ 两个数，再往下走会交的，因此总量是 $O(\log^2 n)$ 的
看大题解
2019 Multi-University Training Contest 10
C：从大到小排序，答案一定是一个前缀
E：按 $x$ 从小到大排序，枚举最后一个选 $x$ 的，那么它后面的全选 $y$，前面的用 set 维护与当前 $x$ 最接近的 $x$，其余选 $y$
H：$a_i \geq b_i$ 的可拆成独立的两个物品，这些散装的肯定是从大到小排序取前缀；$a_i<b_i$ 的最多只有一个人是只选 $a$ 的，因此枚举 $a_i<b_i$ 的这些里面选了多少个 $a_i+b_i$ 就行了，这个有单调性
I：模拟
*K：解法一：枚举长度 $len$，会激活 $a_i \leq len$ 的点，然后对于每个被激活的区间算它的贡献（即假设这个区间就是这么长了，然后计算每个点作为左端点时的贡献）。然后再处理那些以它为左端点长度为 $len$ 时会遇到重复值的点
解法二：分治，每次考虑跨过中线的区间，枚举左边的端点快速计算右边有多少个端点，枚举右边的端点快速计算左边有多少个端点
2020 Multi-University Training Contest 1
D：特判 $n \le 3$，当 $n>3$ 时字符串一定是 $abcabcabc\cdots$ 的形式
E：直接用斐波那契的通项公式来推，二项式展开+等比数列
*F：lxl 时间 以度数是否大于 $\sqrt n$ 分为大点和小点
I：按初始距离从大到小进栈（保证栈底到栈顶依次称王），每新来一个人，如果它能在栈顶称王之前就取代它，那么栈顶退栈
L：凸多边形往内缩 $r$ 的距离得到新凸包（用半平面交实现），然后做半径为 $r$ 的圆角凸包，这就是能被圆覆盖到的面积
ABCGHJK：
2020 Multi-University Training Contest 2
A：每次肯定选整个连通块一直减，直到连通块分裂。倒序做，每次合并的时候计算贡献
E：最小权匹配，每个工人只用连二次函数最值点附近 60 条边即可。用单路增广费用流
G：二分一个 $mid$，然后树形 dp 判定，设 $f_{i,j}$ 表示以 $i$ 为根的子树，改了 $j$ 条边，保证自身直径不超过 $mid$ 的情况下，到 $i$ 的路径的最大长度最小是多少
H：李超树
I：暴力枚举框出来的每个格子，时间复杂度是对的。具体实现用射线法判断每个格子是否在多边形中
J：爆搜+剪枝
L：dp，设 $f_{i,j,k}$ 表示 $A$ 到了第 $i$ 位，$B$ 到了第 $j$ 位，lcs 为 $k$，的最大左端点是谁。查询时从大到小枚举 $ans$，若发现 $f_{r,*,ans} \ge l$，则 $ans$ 合法
BCDFK：
2020 Multi-University Training Contest 3
DE：队友说是沙雕题
C：每一位单独考虑，动态开点线段树维护子树的 $0,1$ 数量以及每个点的祖先链的 $0,1$ 数量
*F：像数位 dp 那样依次枚举前 $i$ 位压线，后面是个组合排列问题，用整数拆分压状态
I：贪心
ABGHJK：
2020 Multi-University Training Contest 4
BD：队友说是沙雕题
^*C：dp，设 $f_{i,j}$ 表示考虑了 $i$ 个数，两个班重量差为 $j$，的最大 beauty 值。将数组随机打乱，限制 $j \in [-10^5,10^5]$
E：求出每个相邻对是否能换位，然后随便 dp 一下
G：左边一排点表示 $x+t$ 的值，右边一排点表示 $x-t$ 的值，一个人代表一条连边，$n-最大匹配$ 即为答案。dinic 冲过去
*I：考虑每条边的贡献，把 $\min$ 拆掉是个组合数式子，预处理一些递推就能算了
看大题解
^K：引力太小可以忽略，物体几乎不动，直接输出初始距离
AFHJL：
2020 Multi-University Training Contest 5
A：$abc=h \cdot S_{\triangle ABC}$，最后推出 $\frac{1}{h^2} = \frac{1}{a^2}+\frac{1}{b^2}+\frac{1}{c^2}$
C：大模拟
*E：把 $i$ 连向 $a_i$ 可得环套树森林，$k=0$ 答案为 $0$，$k=1$ 答案为 $E(n-环套树数量)$，$k=2$ 答案为 $E(n-环套树数量+叶子数量)$。$E(环套树数量)$ 用 EGF 推一推，$E(叶子数量)=\frac{n(n-1)^n}{n^n}$
G：树形 dp
*H：dp，每有一个数要当作某次删除的最小数时，可以视作新增一个大小为 $k$ 的篮子，最终要把篮子填满。设 $f_{i,j}$ 表示当前到了第 $i$ 个数，篮子总共还有 $j$ 个空位，的方案数。转移就枚举当前数是当作最小数，还是填篮子，还是不选。
I：最终折痕形成的每个小格子都被划了十字，因此纸片数 $=(2^{横折次数}+1)(2^{竖折次数}+1)$
K：二分 + 2sat 判断 + 线段树优化连边
L：前 $\lfloor\frac n2 \rfloor$ 个答案为 $0$，对于第 $i$ 个数存活的方案数，考虑后面 $n-i$ 个人连向前面的谁，因此方案数为 $\frac{(i-1)!}{(i-1-n+i)!}(i-1-n+i-1)!!$
BJM：
2020 Multi-University Training Contest 6
ABK：队友说是沙雕题
C：先归一化到均值为 0，设 $f_x$ 表示正数的和为 $x$ 时的期望步数，分“两正一负”和“一正两负”讨论递推
E：方法一：设 $dp_{sum,x,y}$ 表示选出了一个区间得到值为 $sum$，区间左端点 $\bmod 10=x$，区间右端点 $\bmod 10=y$，的最小代价。打表
方法二：打表发现答案 13 以内，于是可以做得更暴力
F：保留 MST 的边即可
G：莫比乌斯反演一套打下去
*H：$k <\sqrt n$ 的时候仿照 min25 进行 dp（设 $f_{i,j}$ 表示考虑了前 $i$ 个质数、除去这些质数的贡献后这个数最大只能是 $j$，的方案数，这个是 $O(\frac{n^{\frac 34}}{\log n})$ 的）；$k>\sqrt n$ 的时候即要去掉含 $>\sqrt n$ 质因子的数，分块+min25 求素数个数
I：$ans=[(b-1) \bmod x=0]$
J：每一位单独考虑，是个矩阵树定理
D：
2020 Multi-University Training Contest 7
D：
G：对于当前点集，找出所有可能成为最远点对的点，把它们叫第一层，删掉，递归下去。先手必胜当且仅当起点不在最后一层或最后一层大小 $>1$
**H：解法一：子集卷积，按最高位从小到大做子集卷积，以避免重复
解法二：子集卷积 $exp$
I：划分成 $x$ 个组，每个组至多 $y$ 个元素，且递减排列。那么显然贪心地塞满后面的组，前面的组尽量放单个元素
*J：若走到主对角线或坐标轴则能走到无限远，此时答案为 $0$；否则可行区域是有限的（上下左右会被素数夹住），答案为 $\frac{起点度数}{连通块内所有点的度数和}$，其中度数包括连向自己的那条边
ABCEFK：
2020 Multi-University Training Contest 8
C：略
B：dp，设 $f_i$ 表示前 $i$ 个数划分的答案。$i$ 每向右移动一位，只有 $O(1)$ 种前缀和的转移发生了变化。前缀和的每个位置维护一个单调队列，基于这个再用线段树或堆实现前缀后缀最大值。
D：tow pointers + LCT 求出每个左端点最右能到哪里使得这个区间内没有环
F：老 flappy bird 了 从左到右+从右到左即可求出合法区间
*G：假题害人 设 $g_i$ 表示游戏在 $i$ 轮之内结束的概率，这等价于选 $i$ 个数使得它们互质的概率，莫比乌斯容斥算出来。算出 $g_i$ 之后类似差分一下，就算出恰好 $i$ 轮结束的概率，取偶数下标的和就是答案
*H：从外往里一圈一圈绕进去，参考题解的图
*I：枚举 $k$，$O(k)$ 的时间算出 $s_1$ 的所有循环同构的哈希，然后看后面每个子串的哈希是否合法
*K：$x \oplus y \in B \iff x \oplus B = y \oplus B$，因此两个数组每个元素都异或掉线性基，然后哈希或者 kmp
*L：每个点产生代价当且仅当它跟父亲最后权值不相同。dp，设 $f_{i,[l,r]}$ 表示 $i$ 这个点取值在 $[l,r]$ 这个区间的时候的最小代价，本质不同的区间只有 $O(n)$ 个。
AEJ：
2020 Multi-University Training Contest 9
A：新加的边终点肯定是根节点最优
*C：先推博弈得到形如 $(a_i,b_i)$ 的必败态对的规律，然后 betty 定理算出 $a_i,b_i$ 关于 $i$ 的式子 为啥全世界都会啊
E：
G：平衡树
BDFHIJ：
2020 Multi-University Training Contest 10
CDG：队友说是沙雕题
*E：dp，设 $f_{i,j}$ 表示 $i$ 这棵子树，根到叶子距离不超过 $j$，的最小代价。长链剖分优化
I：PCA，维护一些必要的信息以快速计算
^J：去掉的两个格子必然属于两行两列，剩下的一行一列每个格子拿空即输，也就是剩 $1$ 就赢，也就是 $a_{ij}-1$ 的 nim 堆；与去掉的两个格子同行同列的其他格子则是普通 nim 堆，因此这些格子异或起来判断是否为 0
K：按 $t$ 降序排列，注意 $k=0$ 时不用排序
ABFH：
2021“MINIEYE杯”中国大学生算法设计超级联赛（1）
中超好耶
AE：队友说是沙雕题
*B：题解解法：kd tree
考场解法：大力猜时间复杂度是 $O(n^2/20)$，因此把平面分成 $80\times80$ 个小格，每画一个圆，格子就分为完全在圆内、完全在圆外、与圆有交 这三种情况，只用对于最后一种情况枚举小格内的所有点，这个面积占 $4*80/80*80\approx1/20$
*C：解法一：每条边设一个变元，高斯消元
未尝试的解法：插头 DP，轮廓线上每个顶点用 0/1 表示它是不是线的端点，那么一条轮廓线上一定是相邻的两个 1 配对。
F：求出异或前缀和 $s$，枚举右端点，左端点的 $s$ 建 trie，维护子树的最大左端点，在 trie 上每次只用往一个方向走
*G：设 $f_t$ 表示 $t$ 时刻传回自己的方案，那么 $f_t=(n-1)^{t-1}-f_{t-1}$，通项是等比数列求和，最后解离散对数
H：枚举上边界，可以知道每列往下延伸到哪里，然后左起右起单调栈
I：MST
*J：解法一：莫队+值域分块，$O(m \sqrt n)$
解法二：cdq
K：burnside 引理，每个不动点写出来的式子可以直接暴力，复杂度 $O(k \ln k)$
D：
2021“MINIEYE杯”中国大学生算法设计超级联赛（2）
签了一小时到，抬头一看 pku 差一题 AK
AE：队友说是沙雕题
B：对于链来说，在 $x$ 位置开始加一个二次函数，对 $y$ 的影响是 $(y-x)^2$，拆开来，每个位置维护修改的 0、1、2 次方和。
D：每个询问拆成 trie 树上的 $\log c$ 次询问，转化成二维数点
*G：解法一：每个位置维护六元向量 $(a,b,a^2,b^2,ab,1)$，线段树维护矩阵乘法
H：先每科预处理 $g_i$ 表示这科考 $i$ 分要多少天，然后再 dp 合并
*J：排列逆序对奇偶性 $sign$ 的式子列出来得到 $a^{\frac{p-1}{2}}$
看大题解
*K：高维前缀和
L：贪心
CFI：
2021“MINIEYE杯”中国大学生算法设计超级联赛（3）
1003：每种符号做一次 FFT
1004：每次使得互相平行的直线数量最少即可，按斜率分类，倒着做，每次删掉 size 多大的一类的一条线段
1007 1011：队友说是沙雕题
*1010：考场解法：大胆猜测具有 $k$ 条折扣边的 MST 是具有 $k-1$ 条折扣边的 MST 替换一条边而得来的，这也导致有用的边只有原始 MST 和折扣 MST 这 $2(n-1)$ 条，因此每次暴力找最优替换并重构 MST 即可
题解解法：有用边只有原始 MST 和折扣 MST 这 $2(n-1)$ 条，设 $f(k)$ 是具有 $k$ 条折扣边的最优答案，则 $f(k)$ 是凸的，类似于 wqs 二分
1001 1002 1005 1006 1008 1009 1012：
2021“MINIEYE杯”中国大学生算法设计超级联赛（4）
1001：非 0 即发散
1002：略
1004：二分答案，然后使用任意一种后缀数据结构 check 即可
*1005：HNOI2016 序列 每个区间先找出最大值，然后左右两边 $O(1)$ 求，最小值同理
看大题解
*1007：cdq，分治区间里的数从小到大排序，左半和右半各维护一个单调栈
看大题解
1008：障碍点使得有障碍的行被分为总共 $O(k)$ 段空白段，依据空白段来维护可达段
1009：字母和数字一定只有 1 个连通块，因此从右往左，去掉 6 个连通块以后就是汉字了
1003 1006 1010 1011：
2021“MINIEYE杯”中国大学生算法设计超级联赛（6）
A：长度只能为 $1,2,p,2p$，讨论一下
D：2021 bytecamp day2 对于 $1\sim n-1$ 节点用旋转法构造 $\frac{n-2}{2}$ 条不相交的长度为 $n-1$ 的哈密顿路径，用 $n$ 号点把它们连起来
E：队友说是沙雕题
*G：观察数字对应的颜色，每次交换会使两个数字的颜色反色（相邻无关），因此如果有奇环就只与各颜色的奇偶性有关，否则是二分图，需要每个数字每侧的颜色数量完全相等
BCFHIJK：
CCPC Wannafly Camp 2020
Day1 - Rikka Contest
BF：队友说是沙雕题
A：按 $\frac{l_i+r_i}{2}$ 从小到大放
C：每种颜色平均分是最优的，答案等于总边数减去每种颜色的团。式子写出来可以分块
**D：带 $x$ 的基尔霍夫矩阵，求导
看大题解
*E：dp旋根。若根把一条链分成 $a$ 和 $b$ 两部分，那么往 $a$ 处移动产生的贡献是 $(a-1)(b+1)-ab=a-b-1$，因此记录每个子树的一直到根的链数及链长和即可
*G：去掉被包含的圆，两两求公切线，得到所有切点，做凸包，对于凸包上的每条线段，若它被一个圆完全覆盖，则它的贡献是一段圆弧，否则是它本身
H：$k$ 乘上 $\lfloor \frac nk \rfloor$ 以内的质数，高精度
*I：分块，每个块维护一个值域前缀和（用树状数组），查询时二分。
J：大模拟，卡常
Day2 - Legilimens Contest
A：略
B：每个 $m_i$ 拆成 $\log$ 个小区间（这个区间表示 $x_i$ 的后若干位是任选的），分组背包，$k$ 只决定有无解，有解的话每一位的解的数量由覆盖该位的 $x$ 的数量决定。
C：每个前缀假设异或和为 $s$，其最高位是第 $w$ 位，那么第 $w$ 位为 $1$ 的 $a_i$ 有唯一操作方法。
*D：mex 实际上是最大 LCP 加 1，而最大 LCP 随着字符的插入是递增的，因此建 SAM 时每次分裂出来的结点的 $maxlen$ 就可以更新答案。注意特判 mex=0
E：启发式合并
*F：维护子树的 $x$ 的和，询问时每个点枚举往父亲的边和往链剖重儿子的边，轻儿子的答案在修改时维护
H：实质上是个欧拉回路
I：黑白染色，则实际上是求最小顶标和，等于最大权匹配
J：如图
*K：dp，设 $f_i$ 表示前 $i$ 个字符的答案，找合法后缀可以 AC 自动机（fail 链最长为 $\sqrt n$），也可以把模板串按大于或小于 $\sqrt n$ 分类然后 hash。
Day 6
CLM：略
*A：2019 南京网络赛 C
*D：分成了 $O(n)$ 个段，dp，设 $f_{i,j}$ 表示前 $i$ 个段放了 $j$ 个数的方案数
F：正难则反，总数减去异色三角形
G：贪心，第 $i$ 轮记当前最左边的空位为 $w$，先倒序把 $f$ 为 $i$ 的位置全部放数字，然后如果 $w$ 还空着就放它
H：先转化成前缀询问。考虑 $[0,2^{30})$ 有多少数字异或 $x$ 之后落在 $[0,r]$ 内，会发现实际上是有 $\log$ 个区间
I：dp，设 $f_{i,j}$ 表示前 $i$ 个数用了 $j$ 次操作的最大和。转移就是枚举一个后缀，然后这个后缀全部变成最大值。
J：整数拆分枚举环长，判断是否合法，合法就算方案数
K：大数放中间，小数放两边
^N：两两乘起来
Day 7
H：略
A：正难则反，算不得分的数对
G：该矩阵一定存在哈密顿回路，因此 $k \geq nm$ 时一定可以遍历完整个地图，$k<12$ 时暴力
J：相邻两项之间会对 $j$ 产生一个上界和下界的限制。于是枚举开头，二分最远的结尾
Tsinghua University Bootcamp
Tsinghua University Bootcamp Qualification Round 2023
A：队友说是沙雕题
B：维护一下每个元素被包含的次数即可
C：枚举三点定圆，排序优化一下
D：每个子树维护一个堆，表示 $T$ 时间内能获得的收益，堆外加维护一个总和和 offset。启发式合并每个子树的堆
E：如果有两个栈顶相同，则可以两步搞掉两个栈顶，然后想办法处理掉这两个大小为 $1$ 的栈。最后剩下的栈一定是每个栈顶指着另一个栈底，形成若干个环，每个环的代价是环长 $+1$
F：总的减去不合法的，不合法的随便哈希一下
H：拆位，线段树维护每个区间的 $a_i$ 当位为 $0/1$、$i$ 当位为 $0/1$ 共四种情况的数量
I：状压树形 dp，维护三种结构：从 $i$ 出发去子树又回到 $i$、从 $i$ 出发去到子树不回来、从子树出发又回到子树
J：枚举 $a_i$ 再枚举 $b_j$，这样就知道 $baseline$ 了，$a_i$ 的上一个是 $a_{i-1}$，$b_j$ 的上一个是 $a_{i-1}+baseline$，用个桶快速找到 $b_j$ 的上一个，并判断这两个 $b$ 之间有没有大于 $baseline$ 的
GKL：