YRQ, OI and sth...
一种可以解决医生和医院的实习生匹配问题的算法。 将问题建模，令医生和医院的数量相等均为 $n$，且分别有一个喜好排列，表示对每个医院或医生的喜好程度。定义一种匹配是稳定的，当且仅当不存在某个不稳定因子：未匹配的医生 $\alpha$ 和医院 $B$ 都更喜好对方，而不是原匹配对象。 一些错误的想法 一开始，我们难以说明一定存在一种稳定匹配。考虑先得到任意一种匹配，尝试每次消除一个不稳定因子。不幸的是，消除一个的代价可能会增加新的一些。事实上，这种渐进的改进方法可能会导致循环。 另一个方向，可以尝试将流程分为多回合。在每一回合中，所有未匹配的医院，向它们最倾向的医生发送 offer，收到 offer 的医生选择一家医院。但是这种情况仍不能保证稳定性。 Gale-Shapley 算法 过程 基于贪心，在每一回合中，任选一个未完成匹配的医院，向最倾向且未曾拒绝过该医院的医生发送 offer。若该医生觉得该医院是更优的选择，则进行替换。 运行时间 共存在 $n^2$ 个医院和医生的匹配，对于每一回合，可以在 $O(1)$ 时间内得到并检查一个匹配，所以复杂度为 $O(n^2)$。 正确性 容易
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_
yrq
