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。如果不考虑 a_i 必须是整数的条件,令 a_i=\frac{1}{i(i+1)} 可以使所有 f(a_i) 相同。

考虑找一个大数 M(大约为 Cn^4 级别),然后令 a_i=\left\lfloor \frac{M}{i(i+1)}\right\rfloor,然后对其进行调整。我们希望使得 f(a_{n}),f(a_{n-2}),f(a_{n-4}),\ldots,f(a_{n-2(b-1)}) 是最大值,因此对于 i< n-2(b-1),只需令 a_i=a_{i+1}+1。注意这时 a_1 也就是 a_i 的最大值不超过 O(Cn^2),符合题目要求。

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

调整后,相邻函数值的差仍然是 O(n) 的,而相邻 a_i 的差是 \Theta(Cn),因此将 a_{2i+1} 的值减少 f(a_{2i+2})-f(a_{2i}) 就能使得 f(a_{2i+2})=f(a_{2i})

E. Building a Fence

分类讨论。不妨设 w\le h

  • 如果 s\le w\le h,那么从一个角开始贪心铺放,不可能出现一个 s 被分成三段的情况,因此答案可以取到下界 \left\lceil \frac{2(w+h)}{s}\right\rceil
  • 如果 w\le h< 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< s\le h
    • 如果 2w+h\ge 2s,那么可以先拿两个 s 分出两个 w,剩下部分拼到同一个长边,然后从这条边开始贪心,能取到下界 \left\lceil \frac{2(w+h)}{s}\right\rceil
    • 否则答案为 34,分析同上,但因为大小关系的限制只可能 k=3,即 2(w+h)=3s

F. Teleports

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

转移如下。

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

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

时间复杂度 O(n^3)

G. Exponent Calculator

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

H. Ancient Country

考虑所有城市的顶点,不可能出现 i < j < k < l 满足 P_iP_k 在同一个城市,并且 P_jP_l 在同一个城市(否则 P_iP_kP_jP_l 就会相交或是在国家范围之外)。因此这些城市的顶点形成一个树形结构。即设包含最小顶点的城市的顶点为 P_{i_1},P_{i_2},\ldots,P_{i_k},那么剩余的城市顶点一定分布在 [i_1+1,i_2-1],[i_2+1,i_3-1],\ldots,[i_k+1,n] 这些区间中。

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

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

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

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

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

总时间复杂度 O(n^4)

I. Marks Sum

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

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

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

J. Prefix Divisible by Suffix

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

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

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

K. Train Depot

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

f(x) 为在 x 的子树里面选择路径的最大价值。如果 x 不是某条路径的顶端则 f(x)\gets \sum_{y\in ch(x)}f(y)

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

时间复杂度 O((n+\sum k_i)\log n)

L. Array Spread

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

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

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

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

其中 n 是顶点数。

证明见此论文

M. Uniting Amoebas

每次将最大值和相邻的合并就可以做到 \sum_{i=1}^n a_i-\max_{i=1}^n\{a_i\}

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

评论

暂无评论

发表评论

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