400 The last hour of the contest
题意 已知 ICPC 封榜前的榜单以及封榜后发放的气球总数，求你所在队伍可能的最高排名和最低排名。
分析 贪心+模拟。
399 Berodoskar Development
题意 给 15×15 的网格图，每个格子有 2 种类型：’X’ 表示蓄水池，’.’ 表示空地。有公共边的 ‘X’ 相互连通成一个大蓄水池。现需要从地图边缘搭建管道引流到至少 2 个蓄水池上，管道可复用。求最少需要的管道长度。
分析 贪心。
398 Friends of Friends
题意 给 50 个人的好友列表。若 c 不是 a 的好友，且存在 b 是 a 和 c 的好友，则 a 和 c 互为 friend of friend。求给定 x 的 friend of friend 列表。
分析 模拟。
397 Text Editor
题意 （光标模拟）。
分析 模拟。
396 Dance it up!
题意 背景类似劲舞团游戏。给长为 $1\le N\le 10^3$ 的按键序列，序列由 $L, R, U, D$ 和 $N$ 构成。每个节拍需要按一个键，$N$ 表示空操作（但即使按了任意键也没有惩罚）。
游戏开始时，角色左手在 LEFT 键上右手在 RIGHT 键上，每个节拍角色有以下行动模式：
- 空操作，不花费任何能量。
- 不移动手的位置，但手按下其所在位置的键，花费 1 单位能量。
- 将一只手移动到一个空按钮上（即另一只手不在该键上），然后按下该按钮。若这只手前一节拍没有按键行为，花费 3 单元能量，否则花费 9 单元能量。
- 将两只手移动到任意位置并按下该位置下的键，花费 10 单元能量。
不允许出现左手在 RIGHT，右手在 LEFT 的情况，该情况视为游戏失败。
求完成游戏序列的最小能量花费，并给出任一方案。
分析 DP。状态转移只与前一节拍的左右手状态相关，按游戏序列动态规划即可。
395 “Binary Cat” Club
题意 给 $1\le N\le 200$ 条按时间序但可能部分缺失的日志，日志有 3 种类型：
- “+ name”：表示名字为 name 的人进入 club；
- “- name”：表示名字为 name 的人离开 club；
- “= visitors”：表示当前 club 有 visitors 个人。
由于日志可能存在缺失导致连续出现 “+ A”, “+ A”，此时中间需要补充 “-A”。求最少需要补充的日志条数。
分析 对于需要补充 “+ name” 和 “- name” 都有一个区间，当有 “= visitors” 查询操作时，贪心利用即可。
394 Berhatton
题意 给二维平面上 $2\le N\le 10^5$ 个点 $(x_i, y_i), 0\le x_i, y_i\le10^9$，每个点覆盖曼哈顿距离不超过 $1\le w_i\le 10^9$ 的点。求哪些点被覆盖至少 $1\le K\lt N$ 次。
分析 扫描线+线段树。将点坐标进行变换 $(x_i+y_i, x_i-y_i)$，则曼哈顿距离变成切比雪夫距离，每个点的覆盖范围是一个正方形。套用扫描线+线段树的做法覆盖点，线段树维护区间最大值，当最大值大于等于 $K$ 时，将该点删除（置为无穷小，保证后续操作不会重复删除即可）。因为每个点最多只会被删除一次，因此整体时间复杂度仍然是 $O(N\log N)$。
393 Bergamot Problem
题意 前 $1\le N\le 13$ 个小写字母构成大小为 $0\le M\le 50$ 的字典，每个单词仅由 2 个字母构成。设计一个按键布局，放置每个字母到不同的按键上，使得 2 个按键对应唯一的一个单词。求最少的按键数量 $K$。
分析 状压 DP。
392 Cyclic Troubles
题意 给 $R\times C(1\le R, C\le 30)$ 的网格图，每个格子上都有一小写字母以及一个方向，指向相邻的格子。有 $1\le Q\le 50$ 个询问，每个询问给定压缩长度为 $2000$ 的字符串，判断是否能从某个格子出发拼出该询问字符串。数据保证不存在嵌套压缩，且询问字符串的原始长度不超过 $10^9$。若存在多个可行的起点，输出最小的 pair 对 $(r, c)$。
分析 因为每个格子的出度为 1，每个格子最多落入到一个环中。主要难点在于压缩字符串和环上字符串的匹配问题。用 $dp(i, j)$ 表示匹配到压缩字符串位置 $i$ 和环上字符串位置 $j$ 的循环长度。
391 Mr. X
题意 在 $n\times m(1\le n, m\le 10^5)$ 网格图上有 $0\le k\le 10^5$ 个标记点 $(x_i, y_i), 1\le x_i\le n, 1\le y_i\le m$。每次操作允许沿连续两行或两列的中线进行对折，判断是否能通过若干次对折使得所有的标记点叠在一起，并且非标记点不与标记点重合。
分析 x，y 两坐标轴相互独立。
390 Tickets
题意 给定阈值 $1\le k\le 1000$，当若干连续值的数位和不小于 $k$ 时，计数器加一。求区间 $l, r$ 的计数器的值。
分析 数位 DP 。$dp(i, ds)$ 表示到第 $i$ 位时，数位和为 $ds$ 的计数值和数位和，即
389 Strange Planet
题意 给定 $1\le n\le 10^5$ 维的超立方体上的三个点 $A, B, C$。点 $A$ 坐标为 $(x_{A, 0}, x_{A, 1}, \dots, x_{A, n-1}), x_{A, i}\in\{0, 1\}$，点 $B, C$ 坐标格式相同。求超立方体上到点 $A, B, C$ 曼哈顿距离相同的点的数量，结果对 $10^9+7$ 取模。
分析 组合数学。
每一维 $i$ 对距离的贡献都是独立的，因此只需要考虑 $2^3=8$ 种情况。若 $x_{A, i}=x_{B, i}=x_{C, i}$，则其他点到 $A, B, C$ 的曼哈顿距离不会发生变化，此时只需要考虑 $2^3-2=6$ 种情况 $(x_{A, i}, x_{B, i}, x_{C, i})$。但是根据 $dis(P, A) = dis(P, B)=dis(P, C)$ 两个方程显然不足以解决问题。
进一步地，其实我们只需要知道第 $i$ 维 $x_{A, i}$ 是否等于 $x_{B, i}$，$x_{A, i}$ 是否等于 $x_{C, i}$，$x_{B, i}$ 是否等于 $x_{C, i}$ 即可计算 $P$ 到三个点的距离。将三者全等的情况排除掉后，若 $x_{A, i}=x_{B, i}$，则蕴含了 $x_{A, i}\neq x_{C, i}, x_{B, i}\neq x_{C, i}$。设 $x_{A, i}=x_{B, i}\neq x_{C, i}$ 的情况数为 $G_{A, B}$，当 $x_{P, i}$ 分别为 0 和 1 时会有 2 种情况：$dis(P, A)+=1, dis(P, B)+=1$ 或者 $dis(P, C) += 1$。不失一般性，假设 $G_{A, B}$ 中有 $u_{A, B}$ 种情况使得点 $P$ 到点 $A, B$ 的距离都加 1，则有 $dis(P, C) += G_{A, B}-u_{A, B}$。
3 种情况下可以计算出 $dis(P, A), dis(P, B), dis(P, C)$，列出 2 个方程后剩一个自由元，枚举计算即可。
388 Soap Opera
题意 有 $2\le n\le 100$ 个演员，Juan 和 Rosa 给这些演员进行配对，每对演员都是一男一女。给定 Juan 认为可行的 $m_1$ 个可行方案，保证这 $m_1$ 对不相同。同理给出 Rosa 认为可行的 $m_2$ 个可行方案。（题目应该蕴含了 Juan 和 Rosa 的配对方案没有交集）。求最大演员数量 $k$，使得 Juan 和 Rosa 都能让这 $k$ 个演员两两配对。
分析
387 Lazy Judges
题意 给 $1\le N\le 50$ 条线段，使用线段上的点构造正方形，求面积的期望值。
分析
386 Happy Birthday, Jedi Knight!
题意
分析
385 Highlander
题意 $2\le n\le 100$ 个人玩游戏，一开始每个人拿到印有 $[1, n]$ 数字的卡片。当 A 手上有 B 的卡片时，A 可以淘汰 B 并获取 B 手上的所有卡片。当没有人能被淘汰时，游戏结束且手上有最多卡片的人获胜（若卡片相同时，则两人同时视为冠军）。求游戏结束冠军人数的期望值。
分析 组合数学+动态规划。能互相淘汰的人一开始就在同一个环上，本质上是对人分群求方案数。$dp(i, j, k)$ 表示前 $i$ 个人组成 $k$ 个最大环为 $j$ 的方案数。
384 Country
题意 给 $3\le n\le 10^5$ 个点和 $m$ 条边的无向图，保证任意两个点之间有且仅有一个公共点。进行 $0\le q\le 2\times 10^5$ 次操作，操作分 2 种类型：将第 $i$ 条边删除；询问 $x, y$ 之间的距离。
分析 根据任意两个点之间有且仅有一个公共点这个性质，可以发现原图是多个三角形共享同一个顶点，将这些顶点找出来即可。
383 Caravans
题意 二维平面上有 $3\le n\le 10^5$ 个点 $(x_i, y_i), 0\le x_i, y_i\le 10^4$。进行 $1\le q\le 10^5$ 次询问，最小化从 $s$ 到 $t$ 所需要的两点间最大距离。
分析 整体二分。单次询问，二分从 $s$ 到 $t$ 所需要的最大两点间距离 $D$，然后将两点距离不超过 $D$ 的边构造生成树，判断 $s, t$ 是否在同一联通块中即可。因为不同询问在相同 $D$ 下的处理是一样的，因此可以通过整体二分将复杂度降至 $O(N\log N)$。
剩下的问题在于如何构造二维平面点的最小生成树。Delaunay triangulation（三角剖分）可以将平面点分割出 $O(N)$ 级别的三角形，利用三角形边构造最小生成树即可。
参考
382 Cantor Function
题意 给定康托函数 $f(x)$ 以及整数 $0\le n\le 50$，求 $\int_{0}^{1} f(x)^ndx$ 的最简分数形式。
分析 将积分分段积分，即 $\int_0^1{f(x)^n}dx=\int_{0}^{\frac 1 3} f(x)^ndx+\int_{\frac 1 3}^{\frac 2 3}{f(x)^n}dx + \int_{\frac 2 3}^1{f(x)^n}dx$。对于区间 [0,1/3] 根据分段函数形式并换底：
换底后与原问题相同。
而对于区间 [2/3, 1]，因为有常数项 $1/2$ 的存在，需要用二项式展开，然后会发现需要对 $f(x)^{n-1}, f(x)^{n-2},\dots, f(x)$ 都进行积分得到相应值。
假设二项式展开除 $f(x)^n$ 外的和为 $S$，则有：
381 Bidirected Graph
题意 给 $1\le N\le 10^5$ 个点的和 $0\le M\le 5\times 10^5$ 条边的有向图，每条边 $e=(u, v)$ 均定义了边权 $\omega(e, u), \omega(e, v)\in \{-1, 1\}$。允许对任意点 $v$ 进行变换：对于所有边 $e=(u, v)$，使得 $\omega(e, v) *=-1$。当所有边 $e$ 都满足 $\omega(e, u)\times \omega(e, v)=-1$ 时，此时有向图可视为无向图。
判断通过点变化是否将有向图转换成无向图，若能输出至少需要几次点变换并输出任一方案。
分析 模拟。一个联通块中的点确定是否变换后，随后该联通块的其他点变换状态也固定了。因此，选取联通块任意点并枚举状态后，取点变换数量少的方案即可。
380 Synchronised Alpinism
题意 两个人从山的左右两个山脚开始爬山，要求两个人每时每刻都必须在同一高度，判断两个人最后是否能够相遇。山简化成多边形，其顶点为 $(1, y_1), (2, y_2),\dots, (n, y_n)$，其中 $y_1=0, y_n=0, |y_i|\le 10^9$。
分析
代码 380.cpp
379 Elevator
题意 $1\le N\le 100$ 层楼高的建筑中仅有一部电梯，每次能承载 $1\le C\le 10^9$ 个人。已知第 $i$ 层楼有 $0\le A_i\le 10^9$ 个人在等电梯到 -1 层，电梯上升或下降一层楼需花费 $1\le P\le 10^9$ 秒。电梯初始位置在 -1 层，求 $1\le T\le 10^9$ 秒内最多能带多少人到 -1 层。
分析 二分。二分人数。
378 Save the Fisher
题意
分析 (没看懂样例，skip)
377 The Lesson of Physical Culture
题意 给 $N\times M(2\le N, M\le 1000)$ 的网格图，要求任意 $2\times 2$ 的正方形中有且仅有 2 个 1，求方案数。
分析 构造。考虑第一行状态，若存在相邻的 2 个 1 或 0，那么下一行的状态便固定了。当第一行不存在相邻的相同数字时（即 101010.. 或者 01010…），下一行与第一行相同或者互补。
376 Berland All-Round Competitions
题意 $1\le N\le 10^3$ 个选手参与竞赛：先游泳，然后进行 $1\le K\le 10^3$ 段赛马。每匹马有不同的速度，先到达某一阶段的选手优先选下一阶段的马（若存在同时到达的选手，力量值 $P_i$ 的选手优先）。按照选手到达顺序，求选手的排名。
分析 模拟。
375 Amplifiers
题意 Shurik 想利用电压放大器得到标准电压的 $1\le N\le 2\times 10^9$ 倍电压。电压放大器有两种：从 X 放大至 2X-1；从 X 放大至 2X+1。求最少需要几个电压放大器，或判断无解。
分析 二进制。显然 $N$ 必须是奇数。根据题意有 $X=\frac {N+1} 2$ 或者 $X=\frac {N-1}{2}$ 且 $N$ 二进制位末位是 1，因此 ±1 会影响倒数第二位。当二进制位倒数第二位是 1 时，此时只能 - 1 否则 +1 会导致新的 $X’$ 不为奇数。当二进位倒数第二位是 0 时，此时必须 +1 否则同样导致新 $X’$ 不为奇数。
因此 $N$ 向下转化时路径是固定的。
374 Save Vasya
题意 求多项式 $(ax+b)^k$ 的系数和，其中 $1\le a, b\le 100, 1\le k\le 20$。
分析 模拟。令 $x=1$，则问题转化成 $(a+b)^k$。
373 Carlsson vs. Winnie-the-Pooh
题意 一块圆形披萨被切了 4 刀，Carlsson 和 Winnie 轮流取一小块披萨吃，花费的时间与披萨面积成正比。每个人都希望最大化自己最终吃到的披萨，求最后两人吃到的披萨面积。
分析 计算几何+DP。圆形切 4 刀最多划分出 11 个区域，$dp(3^{11})$ 表示每个披萨未被吃/被 Carlsson 吃了/被 Winnie 吃了三种状态，依据状态可以计算出下一个取披萨的人。
剩下的问题就是如何求各块小披萨的面积了。
372 Tea Party
题意 一场聚会上有 $1\le K\le 1000$ 个客人，Alice 会在客人离开时送茶包。茶包有红茶和绿茶两种品类，但有 $1\le N\le 1000$ 不同类型。Alice 会给不同客人不同类型的茶包，但不允许连续 3 个茶包都是红茶或绿茶。已知 $N$ 个茶包的价格 $c_i$ 以及品类 $s_i$，求 Alice 至少需要花费多少费用。
分析 贪心。从结果角度入手，假设送出 $a$ 包红茶以及 $b$ 包绿茶且 $a <= b$。因为不能连续送出 3 个茶包，因此 $b <= 2 * (a + 1)$。先按价格 $c_i$ 排序，若不满足该限制条件，则根据条件补充相应品类的茶包。
371 Subway
题意 构造地铁路线方案：地铁由若干 circle lines 和 radial lines 构成，但需要满足：
- 每个 circle line 至少 3 个站点，但不超过 10 个站点；
- Circle lines 通过换乘站串联起来形成一条链；
- Radial lines 站点之一在 circle line 上，而另一个站点不在任何 circle lines 上；
- Radial lines 之间不能有相同站点；
- 任意站点最多在 2 条 lines 上，即换乘站不能作为 radial line 的站点之一。
给定站点数 $N$ 和站点对数 $M$，求任一方案或判断无解。
分析 构造。站点本质上可以分为 4 类：换乘点、circle line 经过点、radial line 终点、radial line 起点，其数量分别记为 $x, y, z, u$。
根据题意有 $x+y+z+u=N, 4x+2y+z+3u=M,u=z$ 共 3 个等式，可以枚举 $y$ 来求解其他 3 个值。注意条件一会限制 $x, y$ 之间的关系。之后根据求解值构造即可。
370 Rifleman
题意 在大小为 $N\times M(1\le N,M\le 10^6)$ 网格图中，从位置 $(1,1)$ 需要设置几条射线以覆盖所有格点。
分析 容斥原理。网格图的一条射线可以使用 $(dx, dy)$ 表示，其中 $dx,dy$ 互质，问题可以转化为：给定 $dx$，求 $[1, M-1]$ 中与 $dx$ 互质的数的数量。
因为 $2\times 3\times 5\times 7\times 11\times 13\times 17 \times 19\gt 10^6$，因此 $dx$ 的质因子数量不超过 7 个。根据容斥原理可以在 $O(2^7)$ 求出互质数的数量。
369 Game
题意 二维平面上给 $0\le K\le 2\times 10^5$ 个点。若三个点构成了矩形的三个点，则会填充矩形的第四个点。求最终平面上有多少个点。
分析 模拟。假设直线 $y=Y$ 有个若干个点 $(x_1, Y), (x_2, Y),\dots, (x_n, Y)$，对于直线 $x = x_1$ 上的给定点，会在其他直线 $x=x_2,\dots, x_n$ 上填充新点，最后形成一个网格图，其坐标值域是由给定点所决定的。也就是说，我们只关心哪些 $X$ 或者哪些 $Y$ 出现过。
当其他点落在网格图直线上时，可以沿新点垂直于该点所在直线上覆盖其他给定点。
368 Tests
题意
分析 ？模拟？
367 Contest
题意 有 $1\le N\le 1000$ 道题目，解决第 $i$ 道题目需要花费 $1\le t_i\le 3500$ 单位时间。题目之间有 $0\le M\le 10000$ 种依赖关系：解决问题 $b_i$ 之间必须先解决问题 $a_i$，保证 $t_{a_i}\le t_{b_i}$。求在时限 $1\le T\le 10^9$ 内最多能解决多少道题目。
分析 图+贪心。因为有 $t_{a_i}\le t_{b_i}$，所以必然会优先解决 $a_i$。
366 Computer Game
题意 游戏中有 $1\le N\le 6\times 10^4$ 道题，主角答对第 $i$ 道题会获得 $0\le a_i\le 50$ 的愉悦度和 $0\le b_i\le 50$ 的得分。主角只会答对其中的 $1\le K\le \min(N,20)$ 道题，因此程序需要选择其中的 $K$ 道题使得 $|A-B|$ 尽可能小其次最大化 $A+B$，其中 $A=\sum a_i, B=\sum b_i$。
分析 动态规划。因 $a_i, b_i$ 的值域较小，$a_i-b_i$ 的值域为 [-50, 50] 共 101 种可能。相同差值 $a_i-b_i$ 中根据最大化 $A+B$ 固定了选取顺序，因此仅需要枚举 $100\times K$ 道题，替换原先 $N$ 的枚举。
365 Ships of the Desert
题意 当一个 $1\le S\le 20$ 个数位的数字，其数位先单调递增后单调递减，则定义该数字为幸运数字。允许有前导 0 的前提下，统计幸运数字的数量。
分析 动态规划。$dp(i, j)$ 表示有 $i$ 个数位且最后一位为 $j$ 的方案数。
364 Lemmings
题意 有 $1\le N\le 100$ 只旅鼠每隔 $1\le s\le 10$ 秒从点 $A(x, h)$ 出发，以 1cm/s 的速度朝右前继直至从平台掉落，掉落速度也为 1cm/s。旅鼠会从一个平台掉落至另一个平台或者永远在下落状态。
我们可以停止行进中的旅鼠使其保持在原地，当其他旅鼠碰到停在原地的旅鼠会改变行进方向。
旅鼠的最终目的在终点 $(a, b)$，求最多能让几只旅鼠到达终点，此外让最小化最后一只旅鼠到达时间。
分析 最短路。关键点只有旅鼠在其他平台的落点，依据这个构造图，使用 $dis(i, j)$ 表示到点 $i$ 方向为 $j$ 的最少停止旅鼠数量以及最短耗时。
363 Baggage Room
题意 有 $1\le N\le 100$ 个人和 $1\le M\le 100$ 个柜台，已知每个人的到达时间 $k_i$ 和处理时间 $t_i$。当一个人到柜台前时会优先选择排队人少的柜台办理业务，有多种选择时优先考虑编号小的柜台。求每个人选择的柜台编号以及离开时间。
分析 模拟。
362 Robot-Annihilator
题意 一个机器人欲遍历 $N\times M(1\le N, M\le 10)$ 的网格图，按照下左上右顺序挑选下一步格子，每个格子仅能被遍历一次。求机器人的执行序列。
分析 模拟。
361 National Flag
题意 用红色和蓝色给 $N\times M(3\le N, M\le 200)$ 网格图染色，要求所有 $2\times 3$ 和 $3\times 2$ 的子矩阵都必须刚好有 2 个蓝色，并且整张图的蓝色数量最少。求任一种染色方案。
分析 构造。对于任意 $3\times 3$ 的正方形，填充 3 个不同行、不同列的蓝色方格即可满足题意。
360 B++ Interpreter
题意 给 $N\times M(1\le N, M\le 50)$ 的网格图以及朝向顶部的机器人，图上有若干个目标点，用 $*$ 表示。机器人根据给定指令序列行动：指令序列由主函数 m() 开始，调用其他函数或者执行基本操作符 $L, R, C$。
分析 模拟。
359 Pointers
题意 给 4 个 integer 类型的指针，有 3 种操作：给指针所在地址赋值常数/其他指针所在地址的值；修改指针指向地址。对于 writeln 操作输出相应指针所在地址的值。
分析 模拟。
358 Median of Medians
题意 给 3 组数，每组 3 个数。先求每组数中的中位数，然后再求这些数的中位数。
分析 模拟。
357 Remote Control
题意 电视有 0 到 99 的频道，遥控器可以通过 ↑↓ 键切换至相邻频道或者通过 — 和数字键直接切换到指定频道。遥控器部分按键损坏了，问从频道 $X$ 切换至频道 $Y$ 最少需要按键几次。
分析 构图跑最短路。
356 Extrasensory Perception
题意 有 $1\le N\le 100$ 对夫妇但不知谁和谁配对，求刚好猜中 $0\le K\le N$ 对的概率。
分析 组合数学。$C(N, K)$ 枚举猜中的夫妻对，剩下进行错位排列 $D(n)=(n-1)(D_{n-1}+D_{n-2})$。
355 Numbers Painting
题意 给 $[1, N]$ 的数字染色，要求若 $A$ 整除 $B$，则两者颜色不同。求最少需要的颜色数，并给出其中一种染色方案。
分析 本质上是求数 $x$ 的约数个数。
354 Just Matrix
题意 有一 $N\times N(1\le N\le 600)$ 的矩阵 $A_{i,j}$，且 $\cup A_{i,j}=\{1,2,\dots, N^2\}$。已知 $top_{i,j}$ 表示第 $j$ 列中满足 $A_{k,j}>A_{i,j}(k
分析 从单行的前 2 个元素入手，根据 $left_{i, 2}$ 可比较这 2 个元素的大小。（再走一步），考虑第 3 个元素，根据 $left_{i, 3}=0,1,2$ 也可以推断出前 3 个元素的大小关系。以此类推，我们可以知道单行/单列的所有元素的大小关系，进而可以构造一张 DAG。
根据 DAG 的拓扑序填充 $1, 2, \dots, N^2$ 即可。
353 Billing
题意 （模拟）
分析
352 Beerland Attacks
题意 $2\le N\le 4000$ 个点 $N-1\le M\le 10^5$ 条边的无向图，给定以 1 为根的一棵最短路径树。对于除 1 外的点 $i$，当 $i$ 的最短路径树上的父边不可用时，1 到 i 的最短距离。
分析 最短路算法。
351 A Mission for a Scout
题意 给定二维平面一个圆 $C$ ，圆外两点 $A, B$，以及一常数 $D$ 表示能在圆 $C$ 行走的最大距离。求从点 $A$ 到点 $B$ 的最短距离，输出其中一种方案。
分析 （计算几何）