450 Ramen Shop
题意
分析 模拟。
449 Dendrograms
题意（画树状图）
分析 按 Y 值从大到小合并并查集。
448 Controlled Tournament
题意 有 $1\le N\le 16$ 个选手参与锦标赛，已知每对选手之间对阵的比赛结果，求冠军是 $1\le M\le N$ 的方案数。
分析 状压 DP。
447 Optimal Rest
题意 Rest command 使用字符 ‘R’ 和一个停留时长 $t$ 表示，其中停留时长 $t\in\{1,2,4,8,16,32,64\}$，’1’ 表示停 1 拍，’2’ 表示停半拍，’4’ 表示停 1/4 拍，以此类推。字符 ‘.’ 表示当前停留时长是前一个停留时长的一半，比如 R1. 表示先停 1 拍，然后再停半拍。最短停留时长不能少于 1/64 拍。给一长度为 $10^5$ 的 rest command 合法序列将其转化成表达式最短的序列，若有多个解则输出字典序最小的表达式。
分析 从样例可以看出，两个表达式的总停留时长是一致的，而合法的表达式是有限的，因此可以转换成背包问题。
446 Rotation Estimation
题意 使用 $1\le n\le 10^3$ 个二维平面点表示星座图，给出前后拍摄得到的星座图上各点坐标，求星座图最小旋转角度。
分析 将两张星座图的中心点平移至原点，然后挑第一张图的任意一点，在第二章图找到相匹配的点。匹配原理借助极角排序即可。
445 Dig or Climb
题意 Red 按照路线图从 $(x_1, y_1)$ 走到 $(x_n, y_n)$ ，路线图是一条折线，折线上的点分别为 $(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)$，速度为 $v_w$。Red 也可以重新开辟点到点的捷径，其速度为 $v_c$。求从起点到终点的最小花费时间，其中 $1\le n\le 10^3$。
分析 dp。
444 Headstrong Student
题意 给定两个正整数 $1\le x, y\le 10^6$，求 $x/y$ 的循环部分长度。
分析 模拟。
443 Everlasting…?
题意 定义 key number 为一个正整数的最大质因子减去其它质因子的和。给定两个数 $2\le a, b \le 10^6$，判断哪个数的 key number 更大（数据保证两个数的 key number 不同）。
分析
442 X+R(X)=N
题意 给一个大数 $1\le N\le 10^{10000}$，求有多少个 $X$ 满足 $X+R(X)=N$，其中 $R(X)$ 表示 $X$ 的数位翻转，如 $R(123)=321$。
分析：
假设 $X=\overline {a_ma_{m-1}\dots a_0}, N=\overline {B_mB_{m-1}\dots B_0}$，$d_i$ 表示第 $i$ 个位置是否有进位，且 $d_0=0, d_i\in \{0, 1\}$。
显然有，$a_m+a_0+d_m=B_m, a_0+a_m+d_0=B_0$。进位 $d_m$ 受 $a_{m-1}+a_{1}+d_{m-1}$ 的影响，$d_1$ 受 $a_0+a_m+d_0$ 的影响。
由外向内处理时，仅需考虑相邻位的进位即可，自然而然地使用 $dp(l, r, s_0, s_1, t_0, t_1)$ ：$l, r$ 表示区间的两个端点，$s_0$ 表示位置 $l$ 是否产生进位，$s_1$ 表示位置 $l$ 是否借位，$t_0, t_1$ 同理。状态 $dp(l, r, s_0, s_1, t_0, t_1)$ 可转移到 $dp(l, r, s_1, s’, t’, t_0)$。
441 Set Division
题意 将 $1\le N\le 10^9$ 个不同的物品放入 $1\le K\le \min(N, 10)$ 个相同的盒子种，求方案数对 2007 取模。
分析 第二类斯特林数。
440 Moles and Holes
题意 给二维平面上 $3\le N\le 800$ 个点 $(x_i, y_i), |x_i|, |y_i|\le 10^3$，若个点 A, B, C 构成的锐角 A 满足 $[\frac {90} A]$ 等于 $\cos A$ 的第 3 位小数，记为一个合法的三元组。求合法三元组的所有数量。
分析
439 A Secret Book
题意 给长度分别为 $N$ 和 $M$ 两个字符串，先求出第二个字符串的最小表示，然后循环移位第一个字符串，使得转换后的第一个字符串开头与第二个字符串匹配或仅一个字符不同。题目保证存在解，求第一个字符串的最小移动次数，其中 $1\le M\lt N\le 10^6$。
分析 扩展 KMP。
438 The Glorious Karlutka River =)
题意 有 $1\le M\le 50$ 个人要从河的一岸 $y=0$ 跳到河的另一岸 $y=W, 0\lt W\le 10^3$。河中有 $1\le N\le 50$ 个石头，每个石头的坐标为 $(X_i, Y_i), 0\lt X_i \lt 10^3, 0\lt Y \lt W$，每个石头最多同时容纳 $0\le C_i\le 10^3$ 个人。每个人跳远的最远的距离是 $0\le D\le 10^3$，每次跳跃需花费 1 秒钟。求所有人都跳到河对岸的最少花费时间或判断不可能。
分析：
如果有解，答案不超过 $N+M$。因为如果存在通路，第二个及以后的人顺着第一个人的路径走即可。
按时间分层建模网络流，当流量总和达到 $M$ 时便是最小时间花费。
437 Hexodoku
完整题面 https://www.eolymp.com/en/contests/3632/problems/29681
题意 将数字 $1\sim K, 7\le K\le 31$ 填入下图中的 $1\sim 31$ 格子中，要求：1）相邻格子的数字不同；2）每“行”的数字均不相同；3 ）以黑色格子为中心的 7 个格子组成一个 cell，cell 中的数字均不相同。已知某些格子已经填数，求字典序排名第 $1\le N\le 10^5$ 个序列。
分析（？DLX 搜索）
436 The Diputs notation
题意
分析 模拟（maybe）。
435 UFO Circles
题意 给 $1\le N\le 100$ 个圆 $(x_i, y_i, r_i)$，所有数字绝对值不超过 1000。求被覆盖奇数次的面积和覆盖偶数次的面积。
分析：
圆的离散化模板题。按照 $y_i-r_i, y_i+r_i$ 以及圆的交点纵坐标划分圆，相邻纵坐标构成的区间将圆划分成圆弧和梯形，基于这两种形状计算面积。
相邻纵坐标构成的区间中，每个区间包含若干左圆弧和右圆弧，可以视为合法的括号序列。根据这一性质，可以计算当前形状的覆盖次数。
434 Chemists
题意 有 $1\le N\le 21$ 个容器，每个容器当前有 $1\le S_i\le 10^3$ 升液体。每次操作从一个容器中倒出任意多的液体到另一个容器中，使得第 $i$ 个容器最终有 $1\le D_i\le 10^3$ 升液体，求最少的操作次数或判断不可行。
分析：
假设有 $n$ 个容器 $S_i>D_i$ 以及 $m$ 个容器 $S_i<D_i$，如果 $\sum S_i=\sum D_i$，那么至多需要 $m+n-1$ 次操作。对于液体有多余的 $n$ 个容器，每个容器需倾倒 $S_i-D_i$ 到其他的容器中，承接的容器中必然有一个容器仍没有达到目的（如果达到目的，说明可以将这个集合划分成两个新集合以减少操作次数），那就需要额外一次操作。
记 $dp(mask)$ 表示集合状态为 $mask$ 能创建最多的集合数，每次转移需枚举子集满足 $\sum S_i=\sum D_i$，则时间复杂度为 $O(3^N)$。
当从一个 $\sum S_i\neq \sum D_i$ 的状态转移到一个 $\sum S_i =\sum D_i$ 状态时，就可以创建一个新集合，而不需关心具体的集合状态，时间复杂度可以降至 $O(N\times 2^N)$。
433 Japhshan and Ramshut
题意 有 $1\le K\le 5$ 种砖头，第 $i$ 种砖头的形状是 $1\times L_i$ 的长条。现使用这些砖头铺满 $N\times M, 2\le N+M\le 20$ 大小的网格图，求任一方案或判断不可行。
分析 状态压缩+动态规划。每次使用一种砖头覆盖坐标最小且未被覆盖的格子。需要注意的事，横向覆盖和纵向覆盖的二进制表示需要预处理，时间复杂度为 $O((N+M)\times 2^{N+M})$。
432 XYZX 2009
题意（字符串模拟题）
分析 模拟。
431 Wildcards
题意 使用小写字母, $\star$ 和 $?$ 匹配 $1\le n\le 10$ 个字符串，并且不能匹配 给定 $1\le m\le 10$ 个字符串，求任一匹配方案或判断无解，其中 $\star$ 可以匹配任意子串（包括空串），$?$ 匹配任意小写字母。数据保证每个字符串长度不超过 11。
分析
430 Unit-distance graph
题意 给 $1\le n\le 7$ 个点的图，要求在二维平面给每个点设定坐标使得有连边的点在平面图上的距离为 1，没有连边的点的距离不为 1，输出任一方案。
分析
429 Problem Stacks
题意 有 $1\le n\le 5$ 堆石子排成一排，每堆石子有 $1\le a_i\le 10^5$ 个。两个人轮流从第一堆或最后一堆石子取任意数量的石子，取走最后一个石子的玩家获胜。要求判断先手胜还是后手胜。
分析
当 $n=1$ 时，显然先手胜。
当 $n=2$ 时，问题就是普通的取石子游戏，判断异或和即可。具体操作：当两堆石子数量一致时，后手复制先手的操作就能取走最后一个石子。
当 $n=3$ 时，分情况讨论
- 若前两堆石子或后两堆石子数量相同时，先手必胜（将问题转化成 $n=2$ 的情形）。
- 若前两堆和后两堆石子数量不同，若第一堆和最后一堆石子不相同，先手可以操作使得第一堆和最后一堆石子数量相同，之后复制对手除取光石堆以外的操作。当对手取光一堆石子后，先手可以立即让剩余两堆数量一样。
当 $n=4$ 时，
当 $n=5$ 时，
428 Rebus
题意
定义 proper addition rebus 为，使用大写字母表示数字使得形如 ABC+CBA=BDB 的加法等式成立。
要求加数与加数的和位数相同；该形式下有且仅有一组解，即字母与数字之间有且仅有一种映射；字母之间的置换视为相同的解。
输出 1000 个 proper addition rebus，每个等式的长度不超过 100。
分析
因为加数和加数的和位数相同，即没有最高位进位。
RRR+TTR=EDT 符合条件，那么 RRRTTR+TTRRRR=EDTEDT 也符合条件。
427 Hamiltonian polyhedron
题意
分析
426 Double cyclic
题意 给一个 $1\le n\le 5\times 10^4$ 个元素的序列 $\sigma$，其元素为 $0\le a_i\lt m$。通过循环位移得到字典序最小的序列 $a’_i$ 记为最小循环位移。给定常数 $1\le m\le 5\times 10^4$，分别求序列 $\sigma, \sigma + 1 \pmod m, \dots, \sigma+m-1\pmod m$ 的最小循环位移序列的第 $k$ 个元素。
分析
425 Control function
题意 给 $n\times m, 1\le n, m\le 1000$ 大小的矩形，要求找到一个值域在 $[0, 50]$ 的函数 $f$ 满足 $\forall i \in [2, n], \exists j\in [1, m], f(T_{1, j})\neq f(T_{i, j})$，即第一行与其他行不相同。数据保证 $\forall i \in [2, n], \exists j\in [1, m], T_{1, j}\neq T_{i, j}$。
分析：
对于第 2 行至第 $n$ 行，每行与第一行不同的列有很多，如果考虑选择哪一列作为 diff 项显然是很复杂的。
假设每一行任选一列，将数字视为点，diff 列连边，构建一张新的无向图。原问题转化成，使用 $[0, 50]$ 对新图进行染色，要求相邻点的颜色不相同。
对于 $N$ 个点的全连接图，需要 $N$ 种颜色染色，才能保证相邻点的颜色不同。而新的无向图边数是 $n-1\approx 1000\lt C_{51}^2=1275$，即使用不超过 51 种颜色即可对新的无向图进行染色。
424 Beautiful graph
题意 使用不超过 $n\le100$ 个点构造不包含自环的无向图，使得没有任意两个简单环有且仅有一条共同边，要求边数最多。
分析
423 Battle
题意
分析（贪心？）
422 Fast Typing
题意 Vasya 使用键盘输入 $1\le n\le 3000$ 个字符，第 $i$ 个字符输错的概率为 $10^{-5}\le a_i\le 0.5$。Vasya 检查输入正确性需要花费 $1\le t\le 10^6$ 秒。当 Vasya 发现错误时，会按退格键回退到正确的字符前然后重新输入。输入字符和退格键均花费 1 秒。求 Vasya 正确输入 $n$ 个字符的最小期望时间。
分析 $f(i)$ 表示输入前 $i$ 个字符的最小期望时间。
421 k-th Product
题意 给 $1\le n\le 10^4$ 个整数 $-10^6\le a_i\le 10^6$，从中取 $1\le m\le 13$ 个数的乘积第 $1\le k\le 10^4$ 大值。
分析
参考 https://blog.sengxian.com/solutions/bzoj-1425
420 Number Permutations
题意 两个正整数定义为相似时，当且仅当两个正整数的十进制位数相同，并能通过排列数位相互转换，如 123 和 213 是相似的。求区间 $[l, r], 1\le l\le r\le 10^{15}$ 中有且仅有 1 个相似数字的数的个数。
分析 枚举数位的最小排列，那么情况有 $C(14 + 9, 9)=817190$ 种，直接计算即可。
419 Hexagonal Walkaround
题意 在六边形网格上从起点 $(0, 0)$ 方向 $d_1$ 走向终点 $(x, y), -10^{12}\le x, y\le 10^{12}$ 方向为 $d_2$ 最少需要几个回合。每个回合允许向当前方向前进 1 格或者逆时针旋转 60 度方向后前进 1 格。不允许在一个方向上连续前进 $2\le b\le 10$ 格。
分析
418 Deducing Grammar
题意
分析
417 Heavy Disc
题意 给圆心 $(x_0, y_0)$ 半径为 $r$ 的圆，保证原点不在圆内。已知圆内一点 $(x, y)$ 处的密度为 $ln(x^2+y^2)$，求整个圆的质量。
分析
416 Optimal Dartboard
题意 将 $1\sim N(6\le N\le 100)$ 填入双层飞镖靶上，如下图所示。要求相邻格子上的数的方差之和最大，更具体地，$R=\sum_{i=1}^n(a_i-a_{i+2})^2+\sum_{i=1}^{n/2}(a_{2i-1}-a_{2i})^2$。
分析（构造）
415 Necessary Coins
题意 有 $1\le N\le 200$ 枚硬币，第 $i$ 枚硬币价值 $1\le a_i\le 10^4$ 元。现需支付 $1\le x\le 10^4$ 元，判断哪些硬币必然会用于支付。
分析
$dp(i, j)$ 表示使用前 $i$ 枚硬币支付 $j$ 元是否可行。前向和后向分别动态规划，在去除第 $i$ 枚硬币后看前后硬币是否能支付 $x$ 元即可判断该枚硬币是否必须。
使用 bitset 优化：前向 dp 时从 0 开始记录，后向 dp 则从 xxxx 开始记录，则时间复杂度由 $O(NX)$ 降至 $O(\frac {NX}{32})$。
414 Orthogonal Circles
题意 给二维平面上 $1\le N\le 10^5$ 个圆，求一个圆使得该圆和给定的所有圆都正交。两个圆正交，当且仅当两圆有交点且在交点的切线相互垂直。
分析 记所求圆的圆心坐标 $(x, y)$ 以及半径为 $r$。因为圆的切线与切点-圆心垂直，则相交圆的切线过圆心，两个圆心与切点构成直角三角形。联立多个三角形即可求解 3 个变量。
413 Berland Division
题意 给 2 ≤ n ≤ 100 个点，1 ≤ m ≤ 1000 条边的无向图（保证 n 是偶数，且不存在重边和自环），要求划分点集，满足：每个子集大小不少于 2；每个子集中的点对之间有且仅有一条路径，即导出子图是一棵树，输出任一划分方案。
分析 使用 DFS 构树，那么兄弟节点没有边，继而有每个节点及其儿子节点都是一棵树的结论。但该做法在树根上可能出现根没有分组的情况，需分情况讨论：
尝试将根分配给某一儿子节点的分组中。
若无法直接分配，说明每个分组下都有一孙子节点和根有边相连。若该分组的点数大于 2，则重新将孙子节点和根分成一组即可。
剩余情况为：每个儿子节点的分组均只有 2 个点，根据奇偶性的性质，有一儿子节点所在的分组连接了一点数为奇数的子树（不考虑分组），将儿子节点或孙子节点分配给这棵子树得到偶数个节点的“新树”，则得到了原问题的子问题，递归求解即可。
参考：姜碧野 - SGU413 Berland Division 解题报告
412 Expedition
题意 给 $3\le N\le 10^5$ 个点的凸包，凸包内有 $0\le M\le 10^5$ 条线段。坐标原点 (0,0) 处有一盏灯（数据保证原点在凸包内），部分凸包的边会被线段挡住光线，求被遮挡的凸包边的长度总和。
分析 扫描线+极角排序。
411 Petya the Hero
题意 给长度为 2000 的字符串，求最长公共子串。
分析 二分+hash。
410 Galaxy in danger
题意 有 $1\le N\le 10^5$ 堆石子，第 $i$ 堆有 $1\le a_i \le 10^6$ 个。有 2 种操作：从所有石子中都取走 1 个；将第 $i$ 堆石子的数量翻倍，即乘 2。求最少操作次数拿走所有石子。
分析 贪心。假设单堆石子的最大数量为 A，其余堆石子在满足不超过 A 的前提下不断翻倍，数量记为 a，显然 $A-a < a$，否则可以继续翻倍。然后从所有石子中取走 1 个，直至 $a’=A-a$，此时将 $a’$ 翻倍后两堆石子数量便相同了。
409 Berland Flag
题意 给 $N^2\times N^2, 1\le N\le 20$ 的网格进行黑白染色，要求：1）每行恰好有 $K$ 个黑色格子；2）每列恰好有 $K$ 个黑色格子；3）每个 $N\times N$ 子矩阵中恰好有 $K$ 个黑色格子。求出任一染色方案。
分析 构造。 构造任一满足条件的 $N\times N$ 子矩阵，然后填充大矩阵中即可。
408 Game with points
题意 从起点 (0, 0) 开始画 $0\le N\le 1000$ 个点，假设第 $i$ 步要画点 $A_i$，要求该点与 $A_j, j\lt i$ 相连成线段，要求：$A_i$ 不在先前的线段上；$\overline {A_jA_i}$ 距离不超过 1，且不与其他线段相交。每画完一点后，求当前有公共顶点的线段最大数量以及点对之间最大的欧几里得距离，两者相乘作为本次得分。求画完 $N$ 个点后的最大得分总和。
分析 贪心。每次要么有公共顶点的线段最大数量 +1，要么点对的最大距离 +1，两值尽可能相同以使乘积尽可能大，最后形成类似蒲公英的形状。
407 Number of Paths in the Empire
题意 有 $3\le n\le 1000$ 个城镇位于山脚下且形成一个环，每个城镇与相邻两个城镇有道路相连。首都位于山顶且与所有 n 个城镇相连。在可重复经过道路和城镇的前提下，求从首都出发经过 $0\le m\le 5000$ 条道路后回到首都的方案数。
分析 动态规划。容易想到 $dp(i, j)$ 表示经过 $i$ 条道路后位于城镇 $j$ 的方案数。但注意山脚下的所有城镇本质上都是一样的，因此只需要区分首都和城镇，即 $dp(i, 0)$ 表示在首都的方案数，$dp(i, 1)$ 表示在山脚城镇的方案数。
406 Goggle
题意 数据库中有 $1\le n\le 10$ 条序列，第 $i$ 条序列长 $1\le k_i\le 10$，序列元素的值域是 [1, 100]。现有 $1\le m\le 10$ 条查询，每次查询如 a,-b,c 形式，表示查询包含 a, c 且不包含 b 的序列。
分析 bitset。
405 Totalizator
题意 观众竞猜两队比分结果，有 4 条得分规则（详见题面）。给定赛后两队的得分和 $1\le n \le 100$ 个观众的猜测结果，求每位观众的得分。
分析 模拟。
404 Fortune-telling with camomile
题意 给长为 $1\le M\le 100$ 的字符串列表，求第 $1\le N\le 100$ 个位置的字符串。因为列表是循环的，所以存在 $N\gt M$ 的情况。
分析 模拟。
403 Scientific Problem
题意 给定整数 $1\le x\le 10^9$，求数 $N$ 使得 $\sum_{i=1}^{N-1}i=xN$。
分析 $N = 2x+1$
402 Terrorists in Berland
题意 给 $3≤N≤50$ 个点和 $1≤M≤500$ 条边的有权无向图，第 $i$ 条边的权重为 $1≤w_i≤10$。现要求破坏一个点以及若干条边，将原图划分成不连通的两部分，求最小边权和。
分析 枚举删除点，剩下的交给全局最小割算法 Stoer-Wagner。
代码 402
401 Geologist Dubrovsky
题意： 有 $1\le N\le 50$ 条南北走向的河流，第 $i$ 条河宽 $1\le w_i\le 1000$, 流速为 $1\le v_i\le 1000$。主角在静止水流中游泳速度可达 $1\le u\le1000$。判断主角能否在 $t$ 时间内从河流西岸游到东岸，若能则求出距离起点最远距离。
分析 河流是南北走向，不影响主角东西走向的游泳速度。若到达对岸的时间有剩余，则贪心分配给纵向距离最远的河道。