jiangly的博客

博客

The 3rd Universal Cup. Stage 5: Moscow 题解

2024-07-28 13:15:20 By jiangly

A. Counting Permutations

对于所有满足条件的排列,二元组序列 (apimodm1,apimodm2) 一定是相同的,也就是按 aimodm1 为第一关键字,aimodm2 为第二关键字升序排序。

如果这个序列不合法则无解,否则方案数为每个 (aimodm1,aimodm2) 二元组出现次数的阶乘乘积。

时间复杂度 O(nlogn)

B. Bookshelf Tracking

如果只有 E 操作,则维护每本书的位置,就可以 O(1) 进行交换。

如果有 R 操作,注意到 R 操作的本质是将位于前一半的书按编号降序排序,后一半的书按编号升序排序。因此,在最后一次 R 操作之前,只需维护每本书是在前一半还是后一半。排序后再处理最后的一段 E 操作即可。

时间复杂度 O(n+q)

C. Painting Fences

最优解一定是从一个极大全黑矩形开始扩展。这样的矩形共有 O(nm) 个,可以通过枚举底端然后笛卡尔树求出。

考虑求从一个矩形扩展到全部的步数。显然两维是独立的,因此只需要考虑 [l,r] 扩展到 [0,n] 的最少步数。

如果 l=0 或者 r=n,显然最优解是长度每次翻倍。

对于一般情况,枚举 l=0r=n 哪个先满足。不妨设 l=0 先满足。设初始时 d=lrl,则至少需要 log2(d+1) 步。但是一直向左对称可能会导致一些浪费。事实上,最优解是:第 i 轮,如果 d 的二进制从低到高第 i 位是 1,则向左对称,否则向右对称。

因此从一个矩形开始扩展的最小步数可以在 O(lognm) 甚至 O(1) 的时间内求出。

总时间复杂度 O(nmlognm)O(nm)

D. Function with Many Maximums

首先要注意到,假设 ai 是降序排序,则 f(ai)=ij=1aj+iai。如果不考虑 ai 必须是整数的条件,令 ai=1i(i+1) 可以使所有 f(ai) 相同。

考虑找一个大数 M(大约为 Cn4 级别),然后令 ai=Mi(i+1),然后对其进行调整。我们希望使得 f(an),f(an2),f(an4),,f(an2(b1)) 是最大值,因此对于 i<n2(b1),只需令 ai=ai+1+1。注意这时 a1 也就是 ai 的最大值不超过 O(Cn2),符合题目要求。

对于后面部分的调整,首先需要将 f(ai) 调整成递增,这只需将函数值下降位置的 ai 增加 O(n) 的值。这是因为原来相邻函数值的差是 O(n) 的,所以调整后累计的差是 O(n2),而将 ai 增加 1 会使得 f(ai) 增加 i+1

调整后,相邻函数值的差仍然是 O(n) 的,而相邻 ai 的差是 Θ(Cn),因此将 a2i+1 的值减少 f(a2i+2)f(a2i) 就能使得 f(a2i+2)=f(a2i)

E. Building a Fence

分类讨论。不妨设 wh

  • 如果 swh,那么从一个角开始贪心铺放,不可能出现一个 s 被分成三段的情况,因此答案可以取到下界 2(w+h)s
  • 如果 wh<s,那么答案可能是 2,34
    • 要答案为 2,只可能是两个 s 都被分成了两段,即 w+h=s
    • 要答案为 3,肯定有 ks 恰好拼了 k+1 条边。
      • k=1,即 2w=s2h=s
      • k=2,即 2w+h=2s2h+w=s
      • k=3,即 2(w+h)=3s
    • 否则答案为 4
  • 如果 w<sh
    • 如果 2w+h2s,那么可以先拿两个 s 分出两个 w,剩下部分拼到同一个长边,然后从这条边开始贪心,能取到下界 2(w+h)s
    • 否则答案为 34,分析同上,但因为大小关系的限制只可能 k=3,即 2(w+h)=3s

F. Teleports

注意到经过任意的操作后,我们都知道可能的宝藏位置是一个区间。设 f(l,r) 是已知宝藏在第 l 个到第 r 个箱子时,找到宝藏的最小代价。

转移如下。

  • 枚举选择的传送器 x,则新的可能的宝藏范围是 [2xr,2xl]
    • 如果 12xr2xln,则 f(l,r)f(2xr,2xl)
    • 如果 2xr<1,则 [2x,r] 中的宝藏无法传送,f(l,r)max{f(1,2xl),f(2x,r)}
    • 如果 2xl>n,则 [l,2xn1] 中的宝藏无法传送,f(l,r)max{f(2xr,n),f(l,2xn1)}

注意到转移图是一个关于区间长度 rl 的分层图,每一层中只有第一类转移。因此可以从小到大枚举 rl,执行所有的第二、三类转移,然后使用 Dijkstra 进行第一类转移。这里是稠密图所以可以使用 O(n2) 的 Dijkstra(当然堆优化的 Dijkstra 也很快)。

时间复杂度 O(n3)

G. Exponent Calculator

因为只有加法、减法和乘法,因此不考虑牛顿迭代。考虑用 ex=n=0xnn! 来逼近。但是这样在 |x| 较大时收敛较慢。因此考虑先将 x 除以 2B,然后展开到 xT 项,最后将结果平方 B 次。实验可以发现 T=7,B=10 时较优,可以在 x=20 时达到 1012 以下的相对精度。

H. Ancient Country

考虑所有城市的顶点,不可能出现 i<j<k<l 满足 PiPk 在同一个城市,并且 PjPl 在同一个城市(否则 PiPkPjPl 就会相交或是在国家范围之外)。因此这些城市的顶点形成一个树形结构。即设包含最小顶点的城市的顶点为 Pi1,Pi2,,Pik,那么剩余的城市顶点一定分布在 [i1+1,i21],[i2+1,i31],,[ik+1,n] 这些区间中。

因此我们可以设计区间 DP,即 f(l,r) 表示只是用下标在 lr 的顶点,所构造城市的最大保护级别。转移如下。

  • 假设 Pl 不属于某个城市,则 f(l,r)f(l+1,r)

  • 否则我们要选一个包含 Pl 的凸包,然后用凸包的权值加上凸包顶点间的区间的 f 值之和来更新 f(l,r)。这一步也可以用 DP 进行。

    • 首先枚举 i 连的第一条边 PiPs,然后令 g(j,k) 表示凸包最后一条边是 PjPk 的最大权值。转移是枚举下一条边 PkPe,然后转移到 g(k,e)。最后检查一下连回 l 是否合法并更新答案。需要枚举第一条边是因为要检查 PkPiPs 这个角是否合法。注意这里判断凸包只需要相邻三个点的夹角,因为下标递增,必然是不会自交的。

具体实现时,可以从大到小枚举 l,然后进行 DP。枚举 l,s 后,DP 的复杂度是 O(n3)。注意到转移可以用极角序优化,即枚举 k,e,可以转移到 g(k,e)i 是极角序上的一段。事实上,我们不需要记录极角序,因为下标递增,每个点所连出的边按下标排序就是极角序,因此枚举 k,e 后,可以转移的 i 是一个前缀,用双指针维护即可。

总时间复杂度 O(n4)

I. Marks Sum

如果长度小于 2000,可以直接返回 d=info=0

如果长度大于等于 2000,我们一定能找到一个前缀,使得剩余字符数小于 2000,且总和是 2000 的倍数或其加 1。我们令 info=2x+y0y1)表示前缀的总和等于 2000x+y。因为字符串长度不超过 106,因此 x<1000,是足够的。

第二次时只需根据 info 计算出前缀的总和,在加上输入串的总和即可。

J. Prefix Divisible by Suffix

枚举选择最短的后缀。如果后缀有前导 0,则去掉之后仍然满足条件。因此满足条件的最短后缀长度不超过 7(如果大于 7 则前缀小于后缀)。

因为我们钦定枚举的后缀是最短的一个,需要枚举更短的一些进行容斥。若干后缀都满足的数形如 km+a,可以用扩展欧几里得算法求出。

时间复杂度 O(10727logn)。但是注意到在后缀较长时,对于很多的集合,满足条件的数的大小都超过了 n。我们在枚举的时候对这种情况直接剪枝,总枚举次数实际上远小于这个上界。

K. Train Depot

首先可以把所有列车转化为 siti 的路径(tisi 的祖先),价值为 ci,然后选择若干条点不相交的路径使得总价值最大。

f(x) 为在 x 的子树里面选择路径的最大价值。如果 x 不是某条路径的顶端则 f(x)ych(x)f(y)

如果选择了 xy 的路径,那么 yx(不包括 x)的路径上的每一个点的兄弟以及 y 的所有孩子 z 会贡献 f(z)。反过来考虑,每个点 x 会对底端是 x 的父亲或 x 的兄弟子树中的点的路径有贡献,在 DFS 序上即 [inparentx,inx)[outx,outparentx) 这两个区间。使用线段树或树状数组维护这个贡献即可。

时间复杂度 O((n+ki)logn)

L. Array Spread

二分答案 x,如果有一种序列满足每个区间的总和在 [1,x] 中,说明答案不大于 x

si 是前 i 个数的和,则限制为 sisi11srisli1x,显然是差分约束的形式。离散化之后点数和边数都是 O(m),因此判断负环的时间复杂度是 O(m2)。这里也可以看出答案是分子和分母不超过 O(m)(分母不超过简单环长度也就是图中点数,分子不超过图中除 x 外的边权和)的分数。因此二分次数是 O(logm),二分之后可以根据实数值还原答案。也可以直接对这 O(m2) 个分数二分。

总时间复杂度 O(m2logm)

事实上,我们可以去掉二分。将边权为 x 的边称为特殊边,剩下的是普通边。令 f(i,v) 表示从任意点开始,经过恰好 i 条特殊边,到达 v 的路径的普通边边权和的最小值。则答案等于 maxvn1mini=0f(i,v)f(n,v)ni

其中 n 是顶点数。

证明见此论文

M. Uniting Amoebas

每次将最大值和相邻的合并就可以做到 ni=1aimaxni=1{ai}

显然这是最优解,因为每次花费 v 的代价至多使得最大值增加 v

评论

暂无评论

发表评论

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