ICPC 2024 横滨区域赛(Yokohama Regional)部分题解
注意
题解写得可能非常抽象。
「如果一个题解你看不懂,那是题解垃圾而不是你垃圾。」
比赛链接:Codeforces Gym
A. Ribbon on the Christmas Present
题意
一个数组,初始为 。一次操作可以选一个区间,选定 ,如果区间内的数都不大于 ,则把区间内的数都变成 。问最少多少次操作得到给定序列。,值域 。
题解
对于每个存在的值 ,找到所有 的位置,它们构成多个段,每个包含 的段都要操作一次。
B. The Sparsest Number in Between
题意
求 内二进制下 最少的数。。
题解
以 为界,递归即可。
C. Omnes Viae Yokohamam Ducunt?
题意
给定一无向图,边有边权、点有点权。求一棵生成树,满足每条边【边权乘以(以 1 为根时)子树内点权】之和最小。求最小值。。
题解
答案等于每个点的点权乘以它到 的距离。注意到取最短路树时,每个点的距离都能取到最优。答案即为每个点的点权乘以 出发的最短路。
D. Tree Generators
题意
给定一个字符串,满足文法 E ::= 1 | (E E)
。其对应一种生成一棵树的方式:
1
对应一个点(E E)
代表:将右侧的树的所有点的编号加上左侧树的最大编号,然后在左右侧树各自取一个点连边。
给定两个字符串 ,判断有多少能同时由这两个字符串生成的树。。
题解
一次合并代表有一条编号 中的点到编号 中的点的边,即一条跨过 这条缝的边。现在考虑 中的合并对应一条边对应 中的合并,从而我们要找到一个 和 中的合并的匹配。我们从低到顶考虑 的合并;对于 中最小的 的合并,它只能跨过唯一一个缝,因此它对应的 中的合并的是唯一的(由这个缝的位置决定);在进一步合并时,我们可以归纳证明匹配的唯一性。现在我们有若干 和 的匹配,每个匹配对应 条边。相乘即可。
E. E-Circuit Is Now on Sale!
题意
给定一个网格,一个格子可能是数、四联通的导线 #
、运算符、输出、空。电路构成一棵树,每个运算符都有两个输入和一个输出。求输出。保证中间结果 。。
题解
一个比较简单的实现是从输出 DFS。
F. The Farthest Point
题意
给定一个长方体的三边长度。求离一个顶点最远的点(沿长方体表面算)的距离。
题解
考虑展开长方体。先枚举答案所在的底面,接下来任意取一个不在这个面上的点,根据展开方式不同,这个点可以对应到 个坐标(有的坐标会能与长方形内部所有点求距离,有的则会被一条线段隔开)。拿出它们两两的垂直平分线、拿出底面的四条边、拿出顶点到隔开线段的端点,得到 条直线;两两求交点,得到大量候选点,每个候选点求它到 个坐标的距离最小值,对所有候选点取最大值即可。
G. Beyond the Former Explorer
题意
交互题。有一个 的网格,你初始位于正中。有一个未知的藏宝点。某些格子有箭头,箭头串成了一条从起点到藏宝点的路径。你一步可以向上下左右移动一个,交互库返回到达的格子上的箭头方向。你要在 步内到达藏宝点。。
题解
二分。维持藏宝点可能的区域为一个矩形,每次轮流横着、竖着将其分为两半,查询分界线左右的两排格子,由此可以得到两个小矩形的边界处有多少向内的箭头、向外的箭头,从而确定藏宝点在哪个小矩形内。
I. Greatest of the Greatest Common Divisors
题意
给定一序列。多次查询一个区间内任取两个不同的数的最大的最大公约数。。。
题解
枚举约数,每个约数对应若干个位置,从而对应若干个 的可能的区间。查询对应二维数点。