ICPC 2024 沈阳区域赛(Shenyang Regional)部分题解:<br>B. Magical Palette<br>D. Dot Product Game<br>G. Guess the Polygon<br>H. Guide Map<br>I. Growing Tree
注意
题解写得可能非常抽象。
「如果一个题解你看不懂,那是题解垃圾而不是你垃圾。」
B. Magical Palette
题意
给定 和 ,构造 和 使得 互不相同。。
题解
互质时,构造 , 即可。大胆猜想不互质时无解。证明就看官方题解吧。
D. Dot Product Game
题意
给两个 到 的排列 和 ,Alice 和 Bob 轮流操作,Alice 先操作,Alice 只能操作排列 ,Bob 只能操作排列 ,每次操作可以选两个元素交换,使得点积严格变大,不能操作的输,问最优策略下谁赢。
另有 次修改操作,每次选取其中一个排列的区间 做 次区间左移。。
题解
点积严格变大即交换一个逆序对;一次交换后逆序对的奇偶性一定变化,因此答案只取决于逆序对的奇偶性。一次修改只需要观察 的奇偶性即可得知答案奇偶性的变化。
G. Guess the Polygon
题意
乱序给出一个简单多边形的 个顶点,每次可以询问竖直线 与简单多边形的相交部分总长,交互器以分数形式 返回结果,要在 次询问内求出简单多边形的面积,以分数形式 输出。,坐标是 内的整数。
题解
我们对“竖线在多边形内的长度”做积分。这是一个分段线性函数。
- 如果某两点的横坐标相同,这个函数可能在此有一个间断点。我们查询其 处的值
- 否则,我们查询这个点的值
- 最左、最右的点,如果是单独的,这个值一定是 ;否则,我们查询其一侧 处的值 这样,我们可以得到每一段的积分结果。
注意到交互库返回的分母可能很大,但由于答案一定是 的整数倍,使用浮点运算或者取模都可以在最后得到准确的结果。
H. Guide Map
题意
给定一张 个点的完全图,给定 条特殊边,这些特殊边构成两棵树。计算完全图中选取边的子集的方案数,使得从 出发按照点编号顺序 DFS 遍历边导出子图时可以经过所有特殊边,同时只经过不多于一条不同的非特殊边。答案对 取模。。
题解
先考虑我们如果有 条特殊边组成一棵有根树,我们要额外选哪些边。对于边 ,我们 可以选择 里面所有编号大于 的点连过去;即统计除了根以外,每个点的子树内比它大的点的个数的和。设这个和为 ,那么方案数为 。
现在考虑两棵树,假设我们选入了一条特殊边 放进树里,其中 。我们考虑有多少边可以放进来:
- 内部的边:考虑方式如上。这一部分为常数
- 内部的边:统计的内容跟上面的类似,但是要对所有根求。这一部分只与 有关
- 和 之间的边:对于 和其所有非 祖先 , 都可以往 中大于 的点连边。这一部分只与 有关
借助几个树状数组,可以把这三部分都统计出来。答案即为 。
I. Growing Tree
题意
给出一棵有 层边的满二叉树的所有边的边权,初始这棵树只有根,接下来 天,每天上午会新生长出一层,每天下午可以选择至多一条边将其边权修改为任意正整数,要修改最少的边使得 天后根到每个叶子的简单路径的边权和两两不同,或判定无解。
题解
自底向上合并,记录每个子树里、到根路径上没有边被修改的边权集合。当两个子树合并,如果没有冲突则不管他,如果有冲突,则需要在两个子树里面选一个修改,另一个向上传。每向上一层会多一次修改的机会,如果修改的次数不够用了,那么无解。
注意到上面的做法需要决策每次到底取哪个子树向上传, 枚举即可。