jiangly的博客

博客

The 3rd Universal Cup. Stage 0: Trial Contest 题解

2024-06-02 14:46:11 By jiangly

A. Arrested Development

动态规划,f(i,j) 表示考虑前 i 个任务,第一个人总时间为 j 时,第二个人总时间的最小值。

时间复杂度 O(n2max

B. Champernowne Substring

讨论以下情况:

  • 对于位置不超过 100\,000 的情况暴力判断,以下都假设串中出现的都至少是五位数。

  • 特判串中出现 10^k10^k-1 的情况,以下都假设串中所有数的长度相等。

  • 串中只包含一个数。问号一定贪心填 0(首位是 1),如果首位是 0 还需要在前面补 1

  • 串中包含超过一个数。枚举这个数的开始位置和长度,以及进位的位数(因为串长不超过 25 且都至少是五位数,因此至多有一次进位)。那么进位的部分全部填 09,前一位枚举 09,再之前的位每个数都一样,问号同样贪心填 01。对于每种可能性都检查一遍。

C. Comparator

首先注意到,表达式只有两个输入,我们可以直接枚举这两个输入后求表达式的值。从而,每条语句的效果都可以拆分为不超过 4 条:如果 x 的第 a 位为 uy 的第 b 位为 v,则返回 r。当两条语句的 (a,u,b,v) 四元组相同时,靠后的语句实际上没有任何效果,因为它所能作用的输入已经全部返回了。因此,我们实际上只需要考虑不超过 4k^2 条语句,每条语句的效果可以在 O(2^{2k}) 的时间内暴力处理。

当我们得到了所有 f(x,y) 的值后,就可以统计答案。前两个答案都可以暴力统计,最后的答案枚举 x,y 后使用 bitset 优化即可。

时间复杂度 O\left(\sum|expr|+k^22^{2k}+2^{3k}/w\right)

D. Dihedral Group

二面体群的操作对应到字符串其实就是翻转和循环移位,只需要判断未翻转/翻转的 d+d 是否包含 t 作为子串。

时间复杂度 O(n)

E. House Deconstruction

1. n=m 的情况

首先考虑 n=m 的情况,即人的数量和房子的数量一样多时,如何求最小代价。对于一个方案,设 c_i 表示经过了 ii+1 这条边的人数(这里模 x 相等的下标表示同一个位置,例如 x+1 代表 1)。如果是从 i+1ic_i 是经过人数的相反数,显然最优解中不会有一条边两个方向都有人经过。则方案对应的代价是 \sum_{i=1}^x|c_i|,需要满足的限制如下:

  • 如果 i 位置是人,则 c_i=c_{i-1}+1
  • 如果 i 位置是房子,则 c_i=c_{i-1}-1
  • 如果 i 位置是空,则 c_i=c_{i-1}

容易发现,c_i 序列几乎是确定的,除了可以整体加上一个任意整数。设一个合法的序列是 c_i',则最小代价为对于任意 k\sum_{i=1}^x|c_i+k| 的最小值。这个函数关于 k 是下凸的,因此可以用三分求出答案。(事实上,k 一定是 c_i 的中位数的相反数。)

2. n< m 的情况:最优解

延续 n=m 的思路,我们可以稍微修改 c_i 的定义,即如果 i 位置是房子,c_i 可以等于 c_{i-1}-1c_{i-1}(表示该房子未被选择)。我们可以猜测以下的引理:

引理 1g(k)c_x=k 时的最优解,则 g(k) 是下凸函数。

有了引理 1 之后,对于 n< m 的情况我们同样可以三分 k,之后只需解决固定 c_x 之后的问题,即可求出最优解。

引理 1 的证明 只需证明 2g(k)\le g(k-1)+g(k+1)。设 k-1k+1 对应的序列分别为 c_i^{(k-1)}c_{i}^{(k+1)}。则令 c_i^{(k)}=\frac{c_i^{(k-1)}+c_i^{(k+1)}}{2}。该序列几乎满足我们的需求,包括 c_x^{(k)}=k 以及相邻 c_i 之间的关系,并且因为三角形不等式 |a+b|\le |a|+|b|,该序列的代价不超过 \frac{g(k-1)+g(k+1)}{2}。唯一有问题的地方是当某一处房子只在 k-1k+1 中的一个方案中被选择时,我们会算出 c_i=c_{i-1}-1/2。然而,对于每一个极长的小数部分为 1/2 的连续段,整体加上或减去 1/2 就是合法的序列,且其中的一种不会使得代价变大(只需比较正数和负数的数量)。从而我们证明了 2g(k)\le g(k-1)+g(k+1)\blacksquare

对于证明中存在小数部分的调整,事实上,即使我们把 i 位置是房子时的限制改为 c_i\in[c_{i-1}-1,c_i],最优解仍然会在所有数都是整数时取到。(提示:仍然可以考虑调整,也可以直接把原问题写成费用流,这样也能得到原问题的凸性。)

接下来只需要考虑固定 k 时如何求最优解。我们可以使用 DP。

f(i,j) 表示考虑了前 i 个位置,c_i=j 的最小代价。初始值为 f(0,k)=0。转移如下:

  • 如果 i 位置是人,则 f(i,j)= f(i-1,j-1)+|j|
  • 如果 i 位置是房子,则 f(i,j)= \min \{f(i-1,j+1),f(i-1,j)\}+|j|。这里代表房子可选可不选。
  • 如果 i 位置是空,则 f(i,j)=f(i-1,j)+|j|

最终的答案即为 f(x,k)

注意到 f(i,j) 对于固定的 i,关于 j 是下凸的,很容易维护。实现中,为了方便,可以把状态改为 f(i,j) 表示前 i 个位置选了 j 个房子的最小代价,这时最小值的位置一定是单调不降的,可以用差分维护最小值之后的斜率,对于房子只需插入一个 0 的斜率。

把空的位置一起处理,就能做到 O(m) 的时间复杂度。

因此,我们可以在 O(m\log n) 的时间内求出最优解。

3. n< m 的情况:方案数

为了计算方案数,我们还需要以下的引理:

引理 2 一个全局最优解 S 只会在唯一的 k 处取到最优解。

证明 注意到对于一个全局最优解的匹配方案,每个未选择的房子 i 都应该满足 c_i=0,即没有匹配经过该房子,否则用该房子替换这个匹配中的房子,代价严格变小。如果一个全局最优解 S 在两个不同的 k 处取到最优解,那么一定有一个 k 使得某个未选择的房子 i 满足 c_i\ne 0,矛盾。因此, 一个全局最优解 S 只会在唯一的 k 处取到最优解。\blacksquare

根据引理 2,我们只需对每个 g(k) 取到最小值的 k 分别计算方案数并求和即可。

我们还需要以下引理:

引理 3 至多有两个 k 满足 g(k) 是最小值。

证明 采用反证法,假设 g(k-1),g(k),g(k+1) 都是最小值。根据引理 1 的证明过程,g(k)=\frac{g(k-1)+g(k+1)}{2} 的必要条件是 c_i^{(k-1)}\cdot c_i^{(k+1)}\ge 0(否则三角形不等式严格不等),以及对于每个极长的小数部分为 1/2 的连续段,正数的个数等于负数的个数(从而无论加还是减 1/2,都不会改变代价)。因此不妨设 k-1\ge 0k+1\le 0 是对称的),找到最小的 j 满足 c_j^{(k-1)}\ne c_j^{(k+1)}-2,则 j 位置是房子。这样的 j 一定存在,否则两个方案对应相同的 S,根据引理 2,一定不是全局最优解。此时 c_j^{(k-1)}=c_j^{(k+1)}-3c_j^{(k-1)}=c_j^{(k+1)}-1,且 c_j^{(k-1)}\ge 0。无论如何,我们都可以令 c_{j}^{(k)}=c_{j-1}^{(k)}>0,同时调整极长的连续段。但是因为 j 是未选择的房子,所以这一定不是全局最优解。因此至多有两个 k 满足 g(k) 是最小值。\blacksquare

根据引理 3,我们只需要对至多两个 k 分别计算方案数并求和。因此这不会增加我们的复杂度。

至于计算方案数,可以在 DP 的过程中同时进行。我们维护 DP 取到最小值的位置,并且最小值至多有两个。最小值之后的部分的方案数只需进行一个平移。因为最小值的位置单调不降,方案数也很容易维护,时间复杂度仍然为 O(m)

综上,我们可以在 O(m\log n) 的时间复杂度内解决该问题。

F. Magic Bean

我们只需要构造出能够交换两个环内的豆子的操作,之后每次找到 a 环内的 b 豆子,和 b 环内非 b 的豆子交换,即可在不超过 30 次交换内完成复原。

构造的操作如下:把 a 环内要交换的豆子移至 1b 环内要交换的豆子移至 4a 环转到 b 环,b 环逆时针转一格,b 环转到 a 环。

G. Manhattan Walk

由于每个格子的状态是均匀独立随机的,并且到一个格子之前无法得知该格子的状态,因此可以看做到每个格子时再均匀随机状态。

f(i,j) 表示从 (i,j) 开始,到达终点的期望最小时间。如果 i=rj=c,则可以直接转移,否则设两个方向的 f 值分别为 aba\le b)。

讨论两种情况:

  • b\ge a+p,那么无论如何都会选择 b,期望为 a+p/4
  • b < a+p,那么只有当离能走 a 还有超过 b-a 的时间才会选择走 b,期望为 (p-b+a)/2p\cdot b+a/2+(b-a)/2p\cdot (a+b)/2。(三项分别代表选择走 b、可以走 a 时走 a、等待后走 a 的期望。)

时间复杂度 O(rc)

H. MountainCraft

注意到斜线的长度等于横向覆盖的长度乘以 \sqrt 2。而横向覆盖的长度就是所有 [x-y,x+y] 的并。使用线段树维护即可(维护区间最小值和最小值个数;或者因为减法只是加法的撤销,维护每个结点的覆盖次数)。

时间复杂度 O(q\log q)

I. Not Another Constructive!

我们可以在字符 A 的位置计算贡献,也就是前缀中 N 的数量和后缀中 C 的数量的乘积。因此设 f(i,N,C,k) 表示考虑了长度为 i 的前缀,前缀中 N 的数量为 N,后缀中 C 的数量为 C,是否能恰好有 k 个 NAC 子序列。可以用 bitset 优化。

时间复杂度 O(n^3k/w)

J. Passport Stamps

i 趟旅行可能无法进行的条件是 p\le \sum_{j=1}^{i-1}c_j+i\cdot (c_i-1),也就是在前面每个章之间留恰好 (c_i-1) 的间隔。

时间复杂度 O(n)

注意,直接计算可能会超过 long long 的范围,需要使用 __int128 或改用除法。

K. Shadow Line

注意到要判断是否只有一片影子,只需要知道每个端点在墙上的位置的相对关系。而这些相对关系只会有 O(n^2) 次变化,也就是在两两的连线与 x 轴交点的位置。算出这些变化的位置之后就可以进行模拟。

只有一片影子的充要条件是对于每个真前缀,下端点的数量大于上端点的数量。因为每次都是交换位置相邻的端点,因此这个条件可以在 O(1) 时间内维护。

要注意的细节包括在有三点共线时的交换顺序,以及 x 轴上的下端点应该始终排在上端点之前。

时间复杂度 O(n^2\log n)

L. Square of Triangles

M. Training, Round 2

f(i,j,k) 表示考虑前 i 个题,是否能恰好加 j 次实现水平和 k 次思维水平。注意这里当某个 (j,k) 能达到时,之后都能达到。因此我们对每个 j 维护两个集合:已经能达到的 k 的集合以及已经更新过的 k 的集合。对于每个问题,我们只需找到矩形中能达到但还未被更新过的 (j,k),将 (j+1,k)(j,k+1) 都加入能达到的集合。因为每个 (j,k) 只会被更新一次,所以时间复杂度是 O(n^2\log n)

评论

L 题简要题解:https://qoj.ac/blog/zsh-zsh/blog/897
  • 2024-06-13 19:41:25
  • Reply
L 题简要题解:https://qoj.ac/blog/hhoppitree/blog/904
  • 2024-06-29 12:12:01
  • Reply

发表评论

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