官方题解。来源：清华大学学生算法协会仓库

操作顺序无关。一堆积木操作后会变成一段或两段连续的 $1$。两个这样的东西合并还是会变成一段 $1$ 被挖掉一个空的形状。

注意到操作前后坐标和不变，所以可以直接算出最后的位置。

由于 $x_i$ 已经排好序了，可以使用栈进行合并。

询问的时候也是从左到右扫一遍，时间复杂度 $O(n)$。

官方题解。来源：清华大学学生算法协会仓库

$H$ 的数据范围暗示，需要高效的算法来确定分界值 $u^*$。由于分界值 $u^*$ 和划分出的席位数（即 $u_i/2^j \ge u^*$ 的 $(i,j)$ 对数）之间具有良好的单调关系，可以用二分 $u^*$ 的办法求解。

每次二分 $u^*$，对每个 $u_i$ 判断可以分得多少席位。整理不等式可得

$$j \le \log\frac{u_i}{u^*}$$

故可以分得 $\left\lfloor\log(u_i/u^*)\right\rfloor$ 个席位。对每个 $u_i$ 可以 $O(1)$ 求解（假设忽略运算复杂度），则总复杂度为 $O(T\log H)$，可以通过本题。

直接对 $u^*$ 二分，可能会出现很大的精度问题：每个 $u_i$ 最少分得 $H/T$ 个席位，故

$$u^* \approx \frac{u_i}{2^{H/T}} \rightarrow 0$$

一种解决办法是，对 $v^*=\log u^*$ 进行二分，则可以转化为 $j = \left\lfloor\log u_i − v^*\right\rfloor$，相对而言精度问题不大。

更进一步地，可以对 $v^*$ 的整数部分和小数部分分开求解。整数部分需要根据是否大于 $\left\lfloor\max\log u_i\right\rfloor$ 简单讨论，小数部分直接排序即可。这样可以完全避免精度问题。

官方题解。来源：清华大学学生算法协会仓库

$n\leq 2$ 的情况可以特判。

可以发现，任意时刻，如果 The BOT 在位置 $x$，那么可以移动到相邻位置之一，无论 The NIT 怎么操作，The BOT 至少可以得到相邻位置的次小值并结束。

另外，当 $n\geq 3$ 时，可以先走到一个 $1<x<n$ 的位置，此时一定可以有三个选项。所以至少可以获得全局的第三小值。

于是一个答案的下界就是 $\max($相邻位置次小值，全局第三小值$)$，容易发现这也是一个上界，如果答案更大，那么将小于答案的看成 $0$，大于等于的看成 $1$，那么全局有 $\geq 3$ 个 $0$，且初始与位置相邻的位置至多有一个 $1$，The NIT 始终可以把一个 $0$ 交换过来，使得 The BOT 周围的三个数都是 $0$。

官方题解。来源：清华大学学生算法协会仓库

枚举平移的距离，考虑把第二张图中所有的点分成四类：

• 当前和第一张图不相等，在平移之后也不相等。
• 当前和第一张图不相等，在平移之后相等。
• 当前和第一张图相等，在平移之后也不相等。
• 当前和第一张图相等，在平移之后也相等。

最终的答案一定是由第二类点和第四类点组成的极大子矩阵。这个可以 使用全 1 子矩阵的算法计算。

第一类点必须是平移之后被随机填充的部分，如果他的坐标是 $(x,y)$，那 么 $(x,y-d)$ 必须被平移。我们可以找到一个能覆盖所有 $(x,y−d)$ 的最小 矩形，答案矩形必须包含这个矩形。

再考虑第二类点，它要么是被随机填充的部分，要么是被平移的部分。 对于一个矩阵，我们只需要求出这两块里第二类点的数量，就知道其是 否合法了。

做全 1 子矩阵，把求出的每个极大子矩阵 check 一遍即可。

官方题解。来源：清华大学学生算法协会仓库

简要题意

• 小 Rei 在 $n$ 天内每天骑共享单车，第 $i$ 天 $s_i$ 分钟，每分钟费用 $c$ 元
• 可任意购买 $m$ 种骑行卡，其中第 $i$ 种骑行卡：
• 售价为 $w_i$ 元，在有效期 $d_i$ 天内每天前 $t_i$ 分钟免费
• 同一天多张卡有效时，取免费时间的最大 $t_i$
• 求最小总开销
• 数据范围：$n,t \le 150$

区间 DP？

• 每张骑行卡会在一个区间的时间内产生影响，自然可以想到区间 DP
• 考虑最优方案中 $t_i$ 最小的骑行卡 $i$，设这张卡在第 $x$ 天购买。接着可以把 $n$ 天分成三段：$[1,x-1],\,[x,x+w_i-1],\,[x+w_i,n]$，这三段分别成为相对“独立”的子问题
• 但是独立性不一定成立：可能存在其他的骑行卡的有效时间与上述的至少两段时间都有交，这样就不是独立的子问题了

构造独立性

• 我们假设存在一个 $t_j > t_i$ 的骑行卡 $j$，其有效时间为 $[y,y+w_j-1]$，满足 $y\le x \le y+w_j-1$。此时可以舍弃卡 $i$ 与 $[y,y+w_j-1]$ 有交的部分时间而不影响答案
• 也就是只要将卡 $i$ 的有效期限定为 $\le w_i$ 的任意整数值，同时不允许后续的有效期区间跨过卡 $i$ 有效期边界，就能分成三个独立的子问题

区间 DP

• 接着就可以做区间 DP，设 $f[i][j][k]$ 表示只考虑时间 $i,i+1,\cdots,j$ 与路程中超过 $k$ 分钟的部分，最小的代价是多少。转移只需要枚举区间内的最小 $t$ 以及左右端点，就能做到 $O(n^4 t^2)$
• 为了时间复杂度与 $m$ 无关，可以预处理 $\mathrm{cost}_{i,j}$ 表示有效期为 $i$ 免费时间为 $j$ 的最少骑行卡价格

DP 优化

• 转移中需要枚举区间中的最小 $t_i$，实际上是在求后缀最大值，在加入辅助数组优化后做到 $O(n^4t)$
• 注意到转移时需要同时枚举中间区间的左右端点。我们考虑再设计一个中间状态，将转移中的枚举左右端点分成两步，就能做到 $O(n^3t)$
• 区间 DP 自带 $1/3!=1/6$ 的常数，$150^3/6\approx 8\times 10^7$ 可以在时限内通过

喜提最劣解（常数最大解）。第一遍甚至读错题一个小时，喜提视力最好奖。

不难发现题目要求除了给定的黑点外其他点不能染成黑色（就是读错在这里了）。

因此不难发现，若一个灰点周围有至少一个黑点，则这个点要满足两个条件之一。

一：这个点初始染成白色

二：这个点与一个初始染成白色的点相连。

然后就是很基础的东西了，因为相连在树上有儿子和父亲的关系，所以要分讨几种情况。

假如说将 $1,5,6$ 染成黑色，答案为 $1$，将 $3$ 染成白色即可，可以手玩一下，就知道怎么设置状态了。

设 $dp_{x,0/1/2/3}$ 分别表示 $x$ 不染成白色/染成白色/不染成白色，但保证父亲染成白色/不染成白色，但保证有至少一个儿子染成白色。

若 $x$ 是 $y$ 的父亲：需要保证 $dp_{y,2}$ 只能通过 $dp_{x,1}$ 转移。

对于至少一个儿子染成白色，先不强制限制，最后加上 $\min(dp_{y,1}-\min(dp_{y,0},dp_{y,1},dp_{y,3}))$ 做一个类似反悔的操作即可。

若 $x$ 初始染成黑色，则所有转移结束后令 $dp_{x,1}\gets \infty$，若 $x$ 周围至少有一个黑点，则所有转移结束后令 $dp_{x,0}\gets \infty$，防止传上去不合法的状态。

最后的答案是 $\min(dp_{1,0},dp_{1,1},dp_{1,3})$。时间复杂度为 $O(n)$。