A. Bus Analysis
不妨将价格除以 $2$，变为 $1$ 和 $3$，最后将答案乘 $2$ 即可。
先考虑对于给定的 $t_1,t_2,\ldots,t_n$，如何计算最小代价。
设 $\mathrm{dp}(i,j)$ 表示用 $j$ 的代价覆盖了前 $i$ 个点，最多还能覆盖多长的距离。设覆盖前 $i$ 个点的最小代价为 $x$，则只有 $f(i,x),f(i,x+1),f(i,x+2)$ 的值有用。这是因为在如果前 $i$ 个点花费了至少 $x+3$ 的代价，一定不比“花费 $x$ 的代价覆盖前 $i$ 个点，然后再买一张 $3$ 元的票”优。
于是，在 DP 的过程中我们只需要记录 $x,f(i,x),f(i,x+1),f(i,x+2)$ 这些值。现在变为计数问题，只需要将这些值记在状态里面。并且注意到，我们只需要求代价的和，所以不需要将 $x$ 计入状态，只需在代价变大时统计进答案。
时间复杂度 $O(n\cdot 75^3)$。实际上，状态数的常数非常小，有用的三元组 $(a,b,c)$ 都满足 $0\le a\le a+20\le b\le b+20\le c\le 75$。
B. Missing Boundaries
首先，对于已经确定两个端点的区间，它们一定不能相交。
对于已经确定一个端点的区间，确定的端点一定不能包含在已经确定的区间里面，且互不相同。
剩下的区间可以任意填，我们可以计算出最小和最大的可能区间数量，判断输入的区间数量是否在范围内即可。
最大的区间数量就是（$L-$ 两端点确定的区间的长度和 $-$ 一个端点确定的区间个数）。
最小的区间数量就是相邻且差大于 $1$ 的右端点和左端点的对数（包括开头和结尾）。
时间复杂度 $O(N\log N)$。
C. Price Combo
考虑最终方案中每个物品是在商店 A 购买还是商店 B 购买。注意到如果 $a_i>a_j$ 且 $b_i< b_j$，那么在商店 A 购买物品 $i$ 、商店 B 购买物品 $j$ 一定是不优的（交换之后一定不劣）。因此，假设我们把一个物品看做点 $(a_i,b_i)$，那么一定存在一条右上到左下的折线，折线上以及左上方的物品在商店 A 购买，折线右下方的物品在商店 B 购买。我们对这条折线进行 DP。
不妨设 $a_i,b_i$ 互不相同。我们考虑从右上到左下确定折线，当折线向左的时候，加入折线上方的 $a_i$ 产生的贡献；折线向下的时候，加入折线右方的 $b_i$ 产生的贡献。注意因为是买一送一，因此只有第 $1,3,5,\ldots$ 个会产生贡献。
显然我们只需要将 $(a_i,b_i)$ 作为折线的关键点。为了方便起见，我们可以加入 $(+\infty,+\infty),(-\infty,-\infty)$。
设 $\mathrm{dp}(i,p,q)$ 是折线走到了 $(a_i,b_i)$，选择的 $a$ 个数奇偶性是 $p$，$b$ 个数奇偶性是 $q$ 的最小代价。那么假设 $(a_i,b_i)$ 从 $(a_j,b_j)$ 转移来（$a_i< a_j,b_i< b_j$），则需要加上的贡献是 $a_i< a_k< a_j$（$b_k>b_j$）和 $b_i< b_k< b_j$（$a_k>a_i$），以及 $a_i$ 的贡献。
考虑按照 $a_i$ 从大到小扫描线，用线段树维护转移。线段树以 $b$ 作为下标，维护 DP 值加上 $a_k$ 的贡献的最小值。对于 $a_k$ 的贡献，只需在扫描线时在线段树上做前缀加（$b_j< b_k$）。注意这里的加法标记实际上是（$0$ 位置加上的值，$1$ 位置加上的值，加的数的个数）三元组。对于 $b_k$ 的贡献，考虑直接在线段树上维护，即每个结点维护 $\mathrm{dp}(j)$ 加上小于 $b_j$ 的 $b$ 的贡献后的最小值，以及 $b$ 的贡献。这里 $b$ 的贡献本质上和 $a_k$ 的加法标记一样。合并时，DP 值应当是左区间的 DP 值以及（右区间的 DP 值加上左区间 $b$ 的贡献）的较小值。这样，要求 $\mathrm{dp}(i)$，只需要在线段树上查询后缀 $(b_i,+\infty)$。
时间复杂度 $O(N\log N)$。
D. Data Determination
不妨设 $a_1\le a_2\le \cdots\le a_n$。
当 $k$ 是奇数时，需要存在 $i$，满足 $a_i=m,i-1\ge\frac{k-1}{2},n-i\ge\frac{k-1}{2}$。
当 $k$ 是偶数时，需要存在 $i< j$，满足 $a_i+a_j=2m,i-1\ge \frac{k}{2} -1,n-j\ge\frac{k}{2}-1$。注意对于相同的 $(a_i,a_j)$，$i$ 和 $j$ 离得越近越好，这样的 $(i,j)$ 只有 $O(n)$ 对。
时间复杂度 $O(n\log n)$。
E. Express Eviction
解法 1
最小割。注意到存在路径当且仅当不存在左下区域到右上区域、每个格子都有居民、且相邻格子行列差都不超过 $2$ 的路径。我们认为左下边界和左下区域是相邻的，右上边界和右上区域是相邻的。
因此我们可以对每个有居民的格子建两个点 $(a_u,b_u)$，如果它是左下边界则连边 $(S,a_u,+\infty)$，右上边界则连边 $(b_u,T,+\infty)$，同时连边 $(a_u,b_u,1)$ 代表可以花费 $1$ 的代价删除这个格子。对于行列差都不超过 $2$ 的每对格子 $u,v$，连边 $(b_u,a_v,+\infty)$。这个图的最小割即为答案。
时间复杂度 $O(\mathrm{Maxflow}(HW,HW))$。
解法 2
最短路。考虑普通的最短路在什么时候会得不到最优解。
.#....
....#.
...#..
###...
###..#
###...如这个例子，只需删除第三行的第四个格子。我们注意到这样的路径实际上是经过了一个格子相对的两个角，但我们的状态中并没有记录经过的格子，所以导致重复计算代价。
考虑所有经过两次的格子，如果一个有居民的格子 $u$ 的两次经过在另一个格子 $v$ 的两次经过之间，我们不如额外花费 $1$ 的代价直接穿过格子 $v$。因此可以假设没有这样的两个格子 $(u,v)$。在这个前提下，我们可以发现路径上的每一个点至多在两个格子的两次经过之间（路径的两侧各一个），通过在状态中记录这两个格子，我们可以做到 $O(H^3W^3)$ 的时间复杂度。
进一步地，假设我们依次经过了格子 $u,v$，那么下一步一定是从 $v$ 走到格子 $u$ 的对角。并且如果在下一次经过 $u$ 之前我们花费了额外的代价，也是不如直接穿过 $u$ 的。因此我们只需要记录一个之前经过的格子，并加一种额外的转移，即当前位置是 $x$，经过了 $v$，对于 $v$ 的每个对角相邻的点 $w$，如果 $x$ 可以不花费额外代价到达 $w$，则可以直接转移到位置 $w$，经过了 $x$。转移可以通过从每个点 BFS 预处理。
时间复杂度 $O(H^2W^2)$。
F. Fibonacci Fusion
不妨设 $a_1\le a_2\le \cdots\le a_n$。
枚举 $j$，则 $a_j< a_i+a_j\le 2a_j$，满足这样条件的斐波那契数只有至多两个，假设我们能求出这两个斐波那契数，就只需要求某个数的出现次数。
由于 $a_i$ 非常大，对应的斐波那契数也非常大，所以我们计算斐波那契数对大素数取模的值（避免碰撞），同时需要估算对应的数的下标。
因为 $F_n=\frac{1}{\sqrt5}\left(\left(\frac{1+\sqrt5}{2}\right)^n-\left(\frac{1-\sqrt5}{2}\right)^n\right)\approx \frac{1}{\sqrt 5}\left(\frac{1+\sqrt5}{2}\right)^n$ ，所以可以用 $n\approx \log_{\frac{1+\sqrt 5}{2}}{\sqrt 5a_i}$ 来估算。
时间复杂度 $O(n\log n+\sum\log a_i)$。
G. Game of Geniuses
答案等于 $\max_i\min_j a_{ij}$。
设答案为 $x$，答案大于等于 $x$ 是平凡的，先手可以删除除最小值等于 $x$ 的行以外的其余行。
要证明答案小于等于 $x$，我们只需要证明每轮后，后手都能保证每行都有小于等于 $x$ 的数。不妨设先手删除了第一行，则后手找到剩余 $n-1$ 行中各一个小于等于 $x$ 的数，标记其所在列，然后删除未被标记的列即可。
时间复杂度 $O(n^2)$。
H. Henry the Plumber
因为每个水管都必须立即转弯，所以答案至少是 $2$。
而答案不超过 $4$，因为可以分别连平行于 $z$ 轴的水管，到同一个 $z$ 之后垂直于 $z$ 轴连接起来（如果两点连线平行于 $z$ 轴则直接连）。
分类讨论：
- 如果 $(x_1,y_1,z_1)-(x_2,y_2,z_2)$ 垂直于 $(p_1,q_1,0)$ 和 $(p_2,q_2,0)$，则答案为 $2$。
- 否则答案至少为 $3$。答案为 $3$ 当且仅当存在一个中间点 $P$，和 $(x_i,y_i,z_i)$ 的连线垂直于 $(p_i,q_i,0)$。即 $P$ 在经过 $(x_i,y_i,z_i)$ 且垂直于 $(p_i,q_i,0)$ 的平面上。
- 如果这两个平面平行，则答案为 $4$。
- 否则找到这两个平面的交，设为 $(x_0,y_0,z)$（一条平行于 $z$ 轴的直线）。现在要确定 $z$ 的值，使得 $P$ 的夹角为直角，即 $(x_0-x_1,y_0-y_1,z-z_1)$ 和 $(x_0-x_2,y_0-y_2,z-z_2)$ 的点积为 $0$。
- 如果 $(x_0,y_0)$ 和某个 $(x_i,y_i)$ 重合，则满足条件的 $P$ 就是 $(x_i,y_i,z_{j})$，如果 $z_1\ne z_2$ 则答案为 $3$，否则答案为 $4$（因为水管长度不能为 $0$）。
- 否则，条件是一个关于 $z$ 的二次方程，只需判断判别式是否大于等于 $0$。大于等于 $0$ 则答案为 $3$，否则答案为 $4$。
时间复杂度 $O(1)$。
I. ICPC Inference
枚举获得金银铜牌的队伍。铜牌一定是通过了一个题目，且罚时尽量大。金牌一定是通过了尽量多的题目，且罚时尽可能小。
我们可以将分数设为 $M\cdot \mathrm{num}-\mathrm{penalty}$，其中 $M$ 是一个非常大的数。则分数越大的人排名越高。
考虑银牌可能的分数，因为铜牌只通过一个题，银牌分数应当在不小于铜牌的前提下尽可能小，因此有用的分数只有通过一个题的情况以及通过两个题且罚时最大。设这些可能的分数是 $s_1< s_2< \ldots< s_k$，则满足 $s_i<\mathrm{bronze}\le\mathrm{gold}< s_{i+1}$ 的金铜牌是不合法的（当然还有小于 $s_1$ 和大于 $s_k$ 的情况）。
我们可以在 $O(\log N)$ 的时间里面对每一个区间计算答案，但是区间的数量可以是 $O(N^2)$ 的。注意到罚时 $K=20$ 比较小，而可能的罚时都形如 $t_i+K\cdot c$（$0\le c< i$），因此可能的罚时可以写成 $O(N)$ 个段，每个段以 $K$ 为周期。对于跨段的区间我们可以 $O(\log N)$ 计算。而对于段内我们可以抽象成 $O(K)$ 个以下询问：
- 有多少对 $(\mathrm{bronze},\mathrm{gold})$ 满足 $\mathrm{bronze}\bmod K=i$，$l\le \mathrm{bronze}\le r$ 且 $\mathrm{gold}-\mathrm{bronze}\le j$。
这样的 $(\mathrm{bronze},\mathrm{gold})$ 也只有 $O(NK)$ 对，预处理之后可以 $O(\log N)$ 回答询问。
注意金银铜牌必须互不相同，因此需要做一些容斥。
时间复杂度 $O(NK\log N)$。
J. Juliet Unifies Ones
数据范围很小，所以做法很多。
一个线性的做法是分成三段，分别是 $0,1,0$，设 $\mathrm{dp}(i,j)$ 表示考虑 $i$ 个字符，目前在第 $j$ 段，至少要删几个字符。
K. Routing K-Codes
如果 $K(b)=\left\lfloor\frac{K(a)}{2}\right\rfloor$ 则我们将边定向为 $a\to b$。因为所有 $K(x)$ 互不相同，因此每个点的出度都不超过 $1$，入度不超过 $2$，且图中不存在环，因此只可能是内向二叉树。因此如果 $m\ne n-1$ 则无解。
假设确定了根，则根的值为 $0$ 或 $1$（度数小于 $2$ 则为 $0$，等于 $2$ 则为 $1$），深度不超过 $32$ 或 $31$，每个孩子的值是 $2K(x)$ 或 $2K(x)+1$。最小的代价和可以通过 DP 求出。使用换根 DP 即可求出每个点作为根的答案。
时间复杂度 $O(n+m)$。
L. Random Numbers
注意到长度为 $k$ 的区间的和的期望是 $k\cdot \frac{n+1}{2}$，因此当 $k$ 距离 $\frac{n}{2}$ 较近时才有较大的概率存在合法区间。当 $k$ 较小的时候，因为总的组合数量不多，因此也有一定的概率存在合法区间。
因此只需设置常数 $B$，枚举所有长度在 $[1,B]$ 或 $\left[\frac{n}{2}-B,\frac{n}{2}+B\right]$ 中的区间检查即可。
时间复杂度 $O(nB)$。例如 $B$ 取 $500$ 可以通过此题。
M. Mathematics Championships
答案等于前 $2^i$（$0\le i\le k$）大数和的最大值。排序后即可计算。
时间复杂度 $O(n2^n)$。