A - Chocolate 第一步操作一定是将最大的巧克力放置在左上角，随后会拆成两个长方形，贪心递归进入宽为这块巧克力边长的部分。 B - AtCoder Language 注意到相邻同色至少要有 $N-K$ 个间隙，不妨对每个位置 $1\le i\le N$ 考虑可供选择的颜色数，相乘即可。 C - Election 考虑第 $1$ 个选民导致的变化。记初始状态为 $2,3,\cdots,N,1$，将 $1$ 放到中间某个位置，可能会使其后至少一个字符发生改变。注意到若第一个改变的位置不是 $1$ 的位置的后一个，则这个放置是没有意义的，对所有位置判断在前面放 $1$ 是否发生变化。 E - Last 9 Digits 打表猜结论题，先枚举找到 $n^n \equiv x (\bmod 100)$，考虑每次将模数乘 $10$，则 $n$ 的对应变化是在最前面插入一个数字。
A - No Attacking 先考虑车的放置，任意两个车不能在同一行或同一列，考虑尽可能为兵预留出位置，也就是尽量间隔放置。 B - Chmax 容易想到建图，对部分点建出唯一后继，若 $i\lt P_i$ 则 $i$ 的终点为 $P_i$，那么从 $1$ 到 $N$ 扫描，若 $i\gt P_i$ 则无解，$i\le P_i$ 若 $i$ 为某个点终点则无解，否则有唯一建图方式，$i=P_i$ 则可以任意选择空指向已经开始的起点。 C - Swap on Tree 考虑树上 DP，对于点 $u$ 如何合并儿子的答案。显然每个点对于是否和父亲交换有两种可能 $f_{u,0/1}$，那么先将所有儿子 $v$ 做一遍背包，使得 $g_{x}$ 为有 $x$ 个儿子与 $u$ 交换。考虑 $g_{x}$ 对 $f_{u,0/1}$ 的贡献，相当于抽出了一个以 $u$ 为根的菊花图，每一次可以任意选择一条边进行交换，贡献系数是阶乘。 D - Rolling Hash 考虑前缀哈希值 $P_i$，每一个限制等价于 $P_r \not\equiv P_{l-1}B^{r-l+1}(\bmod
A. Maximise The Score 显然每次操作选择最大值和次大值。 B. Permutation Printing 不妨加强使得不存在 $i,j$ 满足 $p_i\lt p_j,p_{i+1}\lt p_{j+1}$，容易构造出形如 $1,6,2,5,3,4$ 的答案。 C. Lexicographically Largest 考虑从右往左删，如果当前即将加入到集合的数已经存在，则一定存在一种办法，将集合中这个数减一。所以将 $a_i+i$ 降序排序后，若 $a_i\gt a_{i-1}$ 则将 $a_i$ 调整为 $a_{i-1}-1$。 D1. Sum over all Substrings (Easy Version) 考虑如何对一个子串构造答案。注意答案不小于 1 的个数的一半下取整，考虑如何使一个构造串的一个 1 物尽其用。从左到右扫描，若为 1 则进行一次操作，操作为将答案加一并将后两个位置改为 0。 D2. Sum over all Substrings (Hard Version) 不妨考虑一个位置在哪些子串可以贡献答案。可以状压 DP $f_{i,msk}$
A. Sasha and the Beautiful Array 显然答案是最大值和最小值之差。 B. Sasha and the Drawing 抽象结论题，如果只填充第一排和最后一排，在前期可以做到一段连续的 $2$ 的贡献。答案当 $k=4n-2$ 时为 $2n$ 否则为 $\lceil\frac{k+1}{2}\rceil$。 C. Sasha and the Casino 抽象题，注意到若可以在当前基础上增加，则一定可以达到 $a$，否则一定不行。考虑系统的最优决策，对于每一次下注若赢得的价值不超过沉没成本，则一定会赢得但刷新了连续长度且不优。所以记沉没成本为 $s$，每一次的下注都是 $\lfloor\frac{s}{k-1}\rfloor +1$。 D. Sasha and a Walk in the City 小清新树形 DP。考虑处理完 $u$ 为根的子树时计算点集 $lca$ 为 $u$ 的答案，并记 $f_u$ 为若 $fa_u$ 属于点集，满足不构成三点共线的，$u$ 的子树内的点集数量。对于 $u$ 是否在点集中分开计算，若 $u$ 不在点集中，贡献为 $f_
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$ 为原序列所有数与最大
yrq
