jiangly的博客

博客

The 3rd Universal Cup. Stage 7: Warsaw 题解

2024-08-25 21:10:44 By jiangly

A. Bus Analysis

不妨将价格除以 2,变为 13,最后将答案乘 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(n753)。实际上,状态数的常数非常小,有用的三元组 (a,b,c) 都满足 0aa+20bb+20c75

B. Missing Boundaries

首先,对于已经确定两个端点的区间,它们一定不能相交。

对于已经确定一个端点的区间,确定的端点一定不能包含在已经确定的区间里面,且互不相同。

剩下的区间可以任意填,我们可以计算出最小和最大的可能区间数量,判断输入的区间数量是否在范围内即可。

最大的区间数量就是(L 两端点确定的区间的长度和 一个端点确定的区间个数)。

最小的区间数量就是相邻且差大于 1 的右端点和左端点的对数(包括开头和结尾)。

时间复杂度 O(NlogN)

C. Price Combo

考虑最终方案中每个物品是在商店 A 购买还是商店 B 购买。注意到如果 ai>ajbi<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 个数奇偶性是 pb 个数奇偶性是 q 的最小代价。那么假设 (ai,bi)(aj,bj) 转移来(ai<aj,bi<bj),则需要加上的贡献是 ai<ak<ajbk>bj)和 bi<bk<bjak>ai),以及 ai 的贡献。

考虑按照 ai 从大到小扫描线,用线段树维护转移。线段树以 b 作为下标,维护 DP 值加上 ak 的贡献的最小值。对于 ak 的贡献,只需在扫描线时在线段树上做前缀加(bj<bk)。注意这里的加法标记实际上是(0 位置加上的值,1 位置加上的值,加的数的个数)三元组。对于 bk 的贡献,考虑直接在线段树上维护,即每个结点维护 dp(j) 加上小于 bjb 的贡献后的最小值,以及 b 的贡献。这里 b 的贡献本质上和 ak 的加法标记一样。合并时,DP 值应当是左区间的 DP 值以及(右区间的 DP 值加上左区间 b 的贡献)的较小值。这样,要求 dp(i),只需要在线段树上查询后缀 (bi,+)

时间复杂度 O(NlogN)

D. Data Determination

不妨设 a1a2an

k 是奇数时,需要存在 i,满足 ai=m,i1k12,nik12

k 是偶数时,需要存在 i<j,满足 ai+aj=2m,i1k21,njk21。注意对于相同的 (ai,aj)ij 离得越近越好,这样的 (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

不妨设 a1a2an

枚举 j,则 aj<ai+aj2aj,满足这样条件的斐波那契数只有至多两个,假设我们能求出这两个斐波那契数,就只需要求某个数的出现次数。

由于 ai 非常大,对应的斐波那契数也非常大,所以我们计算斐波那契数对大素数取模的值(避免碰撞),同时需要估算对应的数的下标。

因为 Fn=15((1+52)n(152)n)15(1+52)n ,所以可以用 nlog1+525ai 来估算。

时间复杂度 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 c0\le c< i),因此可能的罚时可以写成 O(N) 个段,每个段以 K 为周期。对于跨段的区间我们可以 O(\log N) 计算。而对于段内我们可以抽象成 O(K) 个以下询问:

  • 有多少对 (\mathrm{bronze},\mathrm{gold}) 满足 \mathrm{bronze}\bmod K=il\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 则无解。

假设确定了根,则根的值为 01(度数小于 2 则为 0,等于 2 则为 1),深度不超过 3231,每个孩子的值是 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)。例如 B500 可以通过此题。

M. Mathematics Championships

答案等于前 2^i0\le i\le k)大数和的最大值。排序后即可计算。

时间复杂度 O(n2^n)

评论

[+3]
鸽鸽豪强~
  • 2024-08-25 21:19:59
  • Reply

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。