跳至主要內容

ICPC 2024 横滨区域赛(Yokohama Regional)部分题解

Wallbreaker5th大约 4 分钟OI×ICPCOI×ICPCOI×ICPC - 题解OI×ICPC - 贪心OI×ICPC - DPOI×ICPC - 最短路OI×ICPC - DFSOI×ICPC - 计算几何OI×ICPC - 交互题OI×ICPC - 二分答案OI×ICPC - 二维数点

注意

题解写得可能非常抽象。

「如果一个题解你看不懂,那是题解垃圾而不是你垃圾。」

比赛链接:Codeforces Gymopen in new window

A. Ribbon on the Christmas Present

题意

一个数组,初始为 00。一次操作可以选一个区间,选定 xx,如果区间内的数都不大于 xx,则把区间内的数都变成 xx。问最少多少次操作得到给定序列。n100n\leq 100,值域 100100

题解

对于每个存在的值 yy,找到所有 y\geq y 的位置,它们构成多个段,每个包含 yy 的段都要操作一次。

B. The Sparsest Number in Between

题意

[l,r][l,r] 内二进制下 11 最少的数。l,r1018l,r\leq 10^{18}

题解

2log2r2^{\lfloor \log_2 r\rfloor} 为界,递归即可。

C. Omnes Viae Yokohamam Ducunt?

题意

给定一无向图,边有边权、点有点权。求一棵生成树,满足每条边【边权乘以(以 1 为根时)子树内点权】之和最小。求最小值。n105n\leq 10^5

题解

答案等于每个点的点权乘以它到 11 的距离。注意到取最短路树时,每个点的距离都能取到最优。答案即为每个点的点权乘以 11 出发的最短路。

D. Tree Generators

题意

给定一个字符串,满足文法 E ::= 1 | (E E)。其对应一种生成一棵树的方式:

  • 1 对应一个点
  • (E E) 代表:将右侧的树的所有点的编号加上左侧树的最大编号,然后在左右侧树各自取一个点连边。

给定两个字符串 S,TS, T,判断有多少能同时由这两个字符串生成的树。S7×105|S|\leq 7\times 10^5

题解

一次合并代表有一条编号 [l,m][l,m] 中的点到编号 (m,r](m,r] 中的点的边,即一条跨过 mm 这条缝的边。现在考虑 SS 中的合并对应一条边对应 TT 中的合并,从而我们要找到一个 SSTT 中的合并的匹配。我们从低到顶考虑 SS 的合并;对于 SS 中最小的 1+11+1 的合并,它只能跨过唯一一个缝,因此它对应的 TT 中的合并的是唯一的(由这个缝的位置决定);在进一步合并时,我们可以归纳证明匹配的唯一性。现在我们有若干 [l1,m](m,r1][l_1,m] (m,r_1][l2,m](m,r2][l_2,m] (m,r_2] 的匹配,每个匹配对应 (mmax(l1,l2)+1)(min(r1,r2)m)(m-\max(l_1,l_2)+1) (\min(r_1,r_2)-m) 条边。相乘即可。

E. E-Circuit Is Now on Sale!

题意

给定一个网格,一个格子可能是数、四联通的导线 #、运算符、输出、空。电路构成一棵树,每个运算符都有两个输入和一个输出。求输出。保证中间结果 1018\leq 10^{18}n,m50n,m\leq 50

题解

一个比较简单的实现是从输出 DFS。

F. The Farthest Point

题意

给定一个长方体的三边长度。求离一个顶点最远的点(沿长方体表面算)的距离。

题解

考虑展开长方体。先枚举答案所在的底面,接下来任意取一个不在这个面上的点,根据展开方式不同,这个点可以对应到 66 个坐标(有的坐标会能与长方形内部所有点求距离,有的则会被一条线段隔开)。拿出它们两两的垂直平分线、拿出底面的四条边、拿出顶点到隔开线段的端点,得到 2121 条直线;两两求交点,得到大量候选点,每个候选点求它到 66 个坐标的距离最小值,对所有候选点取最大值即可。

G. Beyond the Former Explorer

题意

交互题。有一个 (2n+1)×(2n+1)(2n+1)\times (2n+1) 的网格,你初始位于正中。有一个未知的藏宝点。某些格子有箭头,箭头串成了一条从起点到藏宝点的路径。你一步可以向上下左右移动一个,交互库返回到达的格子上的箭头方向。你要在 3000030000 步内到达藏宝点。n2000n\leq 2000

题解

二分。维持藏宝点可能的区域为一个矩形,每次轮流横着、竖着将其分为两半,查询分界线左右的两排格子,由此可以得到两个小矩形的边界处有多少向内的箭头、向外的箭头,从而确定藏宝点在哪个小矩形内。

I. Greatest of the Greatest Common Divisors

题意

给定一序列。多次查询一个区间内任取两个不同的数的最大的最大公约数。n105n\leq 10^5n,q,ai105n,q,a_i\leq 10^5

题解

枚举约数,每个约数对应若干个位置,从而对应若干个 lpi,rpi+1l\leq p_i,r\geq p_{i+1} 的可能的区间。查询对应二维数点。