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}$
yrq
