Edu 160
A Rating Increase
枚举分割，能中止就中止。
B Swap and Delete
枚举删除数量，能否使得 $0$ 和 $1$ 数量相等。
C Game with Multiset
使用 map 统计每个数字个数，查询时从大到小能减则减。
D Array Collapse
发现对于序列的任意区间一定无法删除最小值。考虑在笛卡尔树上 DP。答案可以由两棵子树相乘，若在区间左边或右边存在祖先，则区间最小值可以被从左 / 右边删除。
E Matrix Problem
费用流建图，左侧点表示行，右侧点表示列，边表示网格中某个点，边权为 $1$ 或 $-1$ 分别对应点初始值为 $0$ 和 $1$。
Edu 159
A Binary Imbalance
注意到若能插入一次，便可以沿着插入无穷次。
B Getting Points
二分工作日数量，每天上节课并处理出最多可以完成的任务数量。
C Insert and Equalize
若从结果反过来考虑，可以发现过程中一定可以存在某个时刻序列除 $a_{n+1}$ 都等于原序列最大值，于是 $x$ 为原序列所有数与最大值的差的 $\gcd$。
D Divisibility Test
使用 map<pair<int, int>, set<int> > 维护访问每个坐标的对应时间。询问时分三类分讨。
E Collapsing Strings
哈希，处理出每个反串与所有原串的总匹配长度之和。
F Trees and XOR Queries Again
不难想到可以树上倍增合并线性基的 $3\log$ 做法，可以使用树上 ST 表优化掉一个 $\log$。
Edu 158
A Line Trip
对每个间隔取 $\max$，最后一部分要翻倍。
B Chip and Ribbon
每个位置增量之和即为答案。
C Add, Divide and Floor
注意到操作不会损失大小关系，只保留极值并每次操作对奇偶分讨即可。
D Yet Another Monster Fight
考虑若从某个位置开始，对前面和后面的影响。对其前缀后缀 $\max$ 后二分答案。
E Compressed Tree
树上 DP，DP 记录的值用于转移，并对每个位置分别统计答案，分离以上两个环节，可以非常整洁。
Edu 150
A Game with Board
先手最优策略是合并 $n-2$ 个。
B Keep it Beautiful
按照题意直接维护两个队列即可。
C Ranom Numbers
可以 DP，也可以考虑找出少量特殊位置暴力枚举。
D Pairs of Segments
既然对与对之间不交，就是典型的前缀 $\max$ 优化 DP。
E Rearrange Brackets
从下往上扫，一段区间被切割是不可逆操作了，用 set 维护区间及其出现时间，求出对应长度的数量。
Edu 61
A Regular Bracket Sequence
最优拼法形如 (( () )( ))
B Discounts
排序后贪心选总和减第 $k$ 大。
C Painting the Fence
考虑先枚举一个不出现的，前缀和支持查询区间覆盖数，覆盖恰好为 $1$ 的数。
D Stressful Training
最优构造是优先满足剩余时间短的。二分答案后优先队列即可卡过，可以对剩余时间桶排去掉一个 $\log$。
E Knapsack
看到这个首先意识到和 $\lcm$ 有关。若总和不超过 $W$ 是简单的，否则枚举剩余部分的大小，检查能否构造，注意不能先提前操作。
F Clear the String
相对暴力的做法是维护答案 $f_{l,r}$ 和区间设置成某一颜色 $g_{l,r,c}$ 的最小操作数。注意到对于区间 $[l,r]$ 若 $s_l=s_r$ 则一定可以一起删除，否则一定不可，可以只保留 $f$。
G Greedy Subsequences
好题，既然每个点的后继转移是固定的，考虑连边，发现可以形成森林。启发我们从后往前扫，弹出某个值即为将某个根拆除出几棵子树。相当于对某棵树的距离统一减 $1$。启发我们考虑 $dfs$ 序。良好性质是序列中点 $1,2,\cdots,n$ $dfs$ 序恰好为 $n,n-1,\cdots,1$，于是可以使用区间修改区间 $\max$ 的线段树解决。
Edu 36
A. Garden
挨个检查，限制是 $a_i \mid k$。
B. Browser
显然是到达 $l-1$ 或 $r+1$ 后删掉一侧再去另一侧。
C. Permute Digits
从高到低位填数，状压 DP，额外记录一维是否恰好在和 $b$ 相同。
D. Almost Acyclic Graph
考虑拓扑排序的过程，删掉一条边的意义为将一个点的入度减小 $1$。枚举这个点即可。
E. Physical Education Lessons
颜色段覆盖问题，直接使用珂朵莉树。
F. Imbalance Value of a Tree
可以拆成路径最大值和减路径最小值和。考虑其中的最大值，并对最小值同样处理。可以对边排序，遍历到每条边就将答案加入边两侧连通块大小之积的贡献，实现时可以倒着处理。
G. Coprime Arrays
显然有 DP $f_i$ 表示长度为 $n$，值域为 $i$ 的互质序列个数。转移是容斥，枚举序列的 $\gcd$，并减去对应的 $f_j$。考虑 $f_j$ 对 $f_i$ 的贡献，随着 $i$ 单调增系数也单调增，可以枚举系数并差分处理，复杂度调和级数， $O(n\log n)$。
Edu 35
A. Nearest Minimums
找到最小值后再扫一遍。
B. Two Cakes
枚举左右各分配多少个盘子。
C. Three Garlands
合法的情况当且仅当存在 $1$ 或两个 $2$ 或 $(2,4,4)$ 或 $(3,3,3)$。
D. Inversion Counting
注意到一次翻转只有造成的奇偶变化只和 $r-l$ 相关。
E. Stack Sorting
限制等价于序列一个顺序对 $(x,y)$ 后不能出现比 $x$ 小的数。记 $f_x$ 为已经加入的，不超过 $x$ 的数的数量，则加入一个数 $x$ 需要满足 $f_x = f_{f_x}$。
F. Tree Destruction
显然和直径相关，考虑先删除非直径的点，最远的叶子一定是直径的一个端点，然后再删除直径的链。
G. Mass Change Queries
存在一种线段树做法为维护每个节点的变色信息，记 $m$ 为值域，复杂度为 $O((n+q)m\log n)$。
有一种具有启发性的分块做法，对每个块维护并查集，困难在于 $x\to y,z\to x$ 的变化难以描述，可以使用 trick 用每个颜色的最先出现位置来代表这个颜色。
Edu 34
A Hungry Student Problem
枚举 $a$ 判断。
B The Modcrab
不难发现嗑药要在攻击前面，注意除法上取整。
C Boxes Packing
贪心用 priority_queue 维护单调子序列的末尾。
D Almost Difference
从头到尾扫，减去相差为 $1$ 的即可。注意溢出。
E Swapping Characters
hash 被卡了。考虑枚举第一个字符串交换的位置，与接下来的字符串比对，可以预处理每个字符串和原来的第一个串的差异，再对交换的位置单独处理即可做到。
F Clear The Matrix
不是很好写的状压，压缩最后 $4\times 4$ 的矩阵，限制操作只允许从第一列开始。
G Yet Another Maxflow Problem
这类问题一般都要考虑转最小割处理，图的形状由左右两条链和一些连接左右的边构成。考虑左右分别割断的位置，记为 $u,v$，通过恰当的处理 $a,b$ 和边权 $c$，那么贡献有 $a_u+b_v+\sum_{(x,y),x\le u,y\ge v}$，线段树扫描线即可。
Edu 33
A Chess For Three
维护每局下棋的双方。
B Beautiful Divisors
枚举 $k$ 一一检查。
C Rumor
购买一个即可解决一个连通块，并查集处理 $\min$。
D Credit Card
有趣的题，考虑只有晚上需要检查，才可能在早上去银行，若这一次的漏洞可以通过上一次去银行多补充而解决掉，这次就不操作，否则这次就先补上当前的漏洞，并记录，维护余额最大值以用来检查可不可以续加。
E Counting Arrays
考虑每个素因子的分配情况即可。
F Subtree Minimum Query
两个限制，分别通过 DFS 序和深度上限解决。主席树。
Edu 32
A Local Extrema
直接统计即可。
B Buggy Robot
发现上和下，左和右的操作数应当分别对应相等。
C K-Dominant Character
二分答案，前缀和求出任意区间包括的字符，状压后取交，检查是否空。
D Almost Identity Permutations
枚举 $p_i\neq i$ 的个数 $x$ 后，答案为 $\binom{n}{i}f_i$ 之和，其中 $f_i$ 为错位排列数。
E Maximum Subsequence
带取模不好处理，只能暴力尝试，考虑双向搜。同时若 $x+y\ge m$ 则其一定不如只选 $x$ 或 $y$ 中较大者。
F Connecting Vertices
线段不交意味着区间 DP。对于枚举区间考虑是否存在边 $(l,r)$，若存在则可以枚举两个连通块，否则即为多个类似上面的东西的连接。两种情况分别用 $f,g$ 互转即可不重。
G Xor-MST
考虑常规的 MST 求法 Kruskal 和 Prim 都无法应对完全图的情况，此时可以 Boruvka，其本质思想是在不超过 $\log$ 次过程中，每个连通块找到向外的最小边，并合并。对于本题，可以使用 trie 找到异或最小的结果，常数略大。另外有一种做法为直接在 tire 上，考虑某个子树的 MST 一定最多只有一条跨越子树的边。
Edu 20
A. Maximal Binary Matrix
按照顺序检查每个位置可不可以插入 $1$，如果可以就一定插入。
B. Distances to Zero
使用 set 记录每个 $0$ 的位置，对每个下标找前驱后继。
C. Maximal GCD
考虑将序列除以 $\gcd$，得到的应该是 $1,2,3,\cdots,k-1,x$，枚举 $\gcd$ 判断能否构造。
D. Magazine Ad
注意到被分隔符分开的部分相当于多个单词。二分答案，从前往后扫，贪心的加入即可。
E. Roma and Poker
$f_{i,j}$ 表示到第 $i$ 局赢了 $j$ 是否可能。最后顺着 $f$ 逆推回去。
F. Coprime Subsequences
考虑容斥，$f_i$ 表示 $\gcd$ 为 $i$ 的子序列数量。先得到 $g_i$ 表示 $i\mid \gcd$ 的子序列数量，再狄利克雷差分回去得到 $f$。
G. Periodic RMQ Problem
区间复制持久化平衡树非常好写，但是会 MLE。考虑离线离散化，对每个小区间求一遍在 $a$ 中的最小值后，问题就是普通的动态 $rmq$。
Edu 19
A. k-Factorization
分解质因数，若有多余就乘起来。
B. Odd sum
记 $f_{i,0/1}$ 表示考虑到第 $i$ 个数的奇/偶子序列的和的最大值。
C. Minimal string
相当于单栈排序，只有栈头的数不大于接下来加入到栈的任何数，才会弹出。
D. Broken BST
同样的对于每一个节点有一个区间，表示若输入值属于这个区间，则可以到达这个点。
E. Array Queries
根号分治，$k\le \sqrt{n}$ 则预处理，否则暴力跳。
F. Mice and Holes
注意到每个洞容纳的老鼠是一段连续的区间，对这个区间 DP 即可。
Edu 16
A. King Moves
分三种情况讨论。
B. Optimal Point on a Line
排序后一定在序列中间偏左。
C. Magic Odd Square
奇数的形状是一个斜着的正方形。
D. Two Arithmetic Progressions
exgcd 找到第一个数，下一个数就是这个数加上 $\lcm$。
E. Generate a String
考虑什么时候可能由 $x+1$ 转移来，只有当 $x$ 为奇数时，可能存在 $\frac{x+1}{2}\to x+1\to x$。
F. String Set Queries
AC 自动机经典题。二进制分组建出 $\log$ 组自动机，插入最小的，容量达到上限就和上一个合并。
