A. Bus Analysis
不妨将价格除以 2,变为 1 和 3,最后将答案乘 2 即可。
先考虑对于给定的 t1,t2,…,tn,如何计算最小代价。
设 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⋅753)。实际上,状态数的常数非常小,有用的三元组 (a,b,c) 都满足 0≤a≤a+20≤b≤b+20≤c≤75。
B. Missing Boundaries
首先,对于已经确定两个端点的区间,它们一定不能相交。
对于已经确定一个端点的区间,确定的端点一定不能包含在已经确定的区间里面,且互不相同。
剩下的区间可以任意填,我们可以计算出最小和最大的可能区间数量,判断输入的区间数量是否在范围内即可。
最大的区间数量就是(L− 两端点确定的区间的长度和 − 一个端点确定的区间个数)。
最小的区间数量就是相邻且差大于 1 的右端点和左端点的对数(包括开头和结尾)。
时间复杂度 O(NlogN)。
C. Price Combo
考虑最终方案中每个物品是在商店 A 购买还是商店 B 购买。注意到如果 ai>aj 且 bi<bj,那么在商店 A 购买物品 i 、商店 B 购买物品 j 一定是不优的(交换之后一定不劣)。因此,假设我们把一个物品看做点 (ai,bi),那么一定存在一条右上到左下的折线,折线上以及左上方的物品在商店 A 购买,折线右下方的物品在商店 B 购买。我们对这条折线进行 DP。
不妨设 ai,bi 互不相同。我们考虑从右上到左下确定折线,当折线向左的时候,加入折线上方的 ai 产生的贡献;折线向下的时候,加入折线右方的 bi 产生的贡献。注意因为是买一送一,因此只有第 1,3,5,… 个会产生贡献。
显然我们只需要将 (ai,bi) 作为折线的关键点。为了方便起见,我们可以加入 (+∞,+∞),(−∞,−∞)。
设 dp(i,p,q) 是折线走到了 (ai,bi),选择的 a 个数奇偶性是 p,b 个数奇偶性是 q 的最小代价。那么假设 (ai,bi) 从 (aj,bj) 转移来(ai<aj,bi<bj),则需要加上的贡献是 ai<ak<aj(bk>bj)和 bi<bk<bj(ak>ai),以及 ai 的贡献。
考虑按照 ai 从大到小扫描线,用线段树维护转移。线段树以 b 作为下标,维护 DP 值加上 ak 的贡献的最小值。对于 ak 的贡献,只需在扫描线时在线段树上做前缀加(bj<bk)。注意这里的加法标记实际上是(0 位置加上的值,1 位置加上的值,加的数的个数)三元组。对于 bk 的贡献,考虑直接在线段树上维护,即每个结点维护 dp(j) 加上小于 bj 的 b 的贡献后的最小值,以及 b 的贡献。这里 b 的贡献本质上和 ak 的加法标记一样。合并时,DP 值应当是左区间的 DP 值以及(右区间的 DP 值加上左区间 b 的贡献)的较小值。这样,要求 dp(i),只需要在线段树上查询后缀 (bi,+∞)。
时间复杂度 O(NlogN)。
D. Data Determination
不妨设 a1≤a2≤⋯≤an。
当 k 是奇数时,需要存在 i,满足 ai=m,i−1≥k−12,n−i≥k−12。
当 k 是偶数时,需要存在 i<j,满足 ai+aj=2m,i−1≥k2−1,n−j≥k2−1。注意对于相同的 (ai,aj),i 和 j 离得越近越好,这样的 (i,j) 只有 O(n) 对。
时间复杂度 O(nlogn)。
E. Express Eviction
解法 1
最小割。注意到存在路径当且仅当不存在左下区域到右上区域、每个格子都有居民、且相邻格子行列差都不超过 2 的路径。我们认为左下边界和左下区域是相邻的,右上边界和右上区域是相邻的。
因此我们可以对每个有居民的格子建两个点 (au,bu),如果它是左下边界则连边 (S,au,+∞),右上边界则连边 (bu,T,+∞),同时连边 (au,bu,1) 代表可以花费 1 的代价删除这个格子。对于行列差都不超过 2 的每对格子 u,v,连边 (bu,av,+∞)。这个图的最小割即为答案。
时间复杂度 O(Maxflow(HW,HW))。
解法 2
最短路。考虑普通的最短路在什么时候会得不到最优解。
.#....
....#.
...#..
###...
###..#
###...
如这个例子,只需删除第三行的第四个格子。我们注意到这样的路径实际上是经过了一个格子相对的两个角,但我们的状态中并没有记录经过的格子,所以导致重复计算代价。
考虑所有经过两次的格子,如果一个有居民的格子 u 的两次经过在另一个格子 v 的两次经过之间,我们不如额外花费 1 的代价直接穿过格子 v。因此可以假设没有这样的两个格子 (u,v)。在这个前提下,我们可以发现路径上的每一个点至多在两个格子的两次经过之间(路径的两侧各一个),通过在状态中记录这两个格子,我们可以做到 O(H3W3) 的时间复杂度。
进一步地,假设我们依次经过了格子 u,v,那么下一步一定是从 v 走到格子 u 的对角。并且如果在下一次经过 u 之前我们花费了额外的代价,也是不如直接穿过 u 的。因此我们只需要记录一个之前经过的格子,并加一种额外的转移,即当前位置是 x,经过了 v,对于 v 的每个对角相邻的点 w,如果 x 可以不花费额外代价到达 w,则可以直接转移到位置 w,经过了 x。转移可以通过从每个点 BFS 预处理。
时间复杂度 O(H2W2)。
F. Fibonacci Fusion
不妨设 a1≤a2≤⋯≤an。
枚举 j,则 aj<ai+aj≤2aj,满足这样条件的斐波那契数只有至多两个,假设我们能求出这两个斐波那契数,就只需要求某个数的出现次数。
由于 ai 非常大,对应的斐波那契数也非常大,所以我们计算斐波那契数对大素数取模的值(避免碰撞),同时需要估算对应的数的下标。
因为 Fn=1√5((1+√52)n−(1−√52)n)≈1√5(1+√52)n ,所以可以用 n≈log1+√52√5ai 来估算。
时间复杂度 O(nlogn+∑logai)。
G. Game of Geniuses
答案等于 maximinjaij。
设答案为 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)。