ARC152

HUNGRY123 · 2025-01-18 19:22:43 · 个人记录

ARC152

A

• 题意：

• 题解：

  最小化剩余座位中，相邻两个座位都是空着的个数

  每次都和前面的隔着坐就行

B

• 题意：

  有一条路，还有一堆休息点，两人只能同时存在于休息点处。

  将初始的两人都放在休息点，问最短需要多长时间，两人都能游览完整条路线，并且回到休息点

• 题解：

  最有情况下两人一定是从同一个出发点相向出发

  二分出来第一次相遇点就行

C

• 题意：

  有一个数组，每次可以从数组中间人选一个 s=a_j，使数组里面的 a_i 变成 2\times s-a_i，不能出现负数，问最大值最小是多少

• 题解：

  差分数组不变，因此只需要考虑最小化最小值

  考虑原有的最小值 a_1，经过任意两次操作后仍然为最小值，为 a_1-2\times(a_i-a_j)

  发现这是对差分的不定方程

  令 g 为差分数组的 \rm gcd，a_1 的最小值就是 a_1 \bmod g，推出 a_n 的即可

  也可以先进行一次操作，之后相同的方法最小化 a_n，反推出 a_1

  两种答案取 \rm min

D

• 题意：

• 题解：

  若 n 是偶数，连成树需要连接奇数条边，一定不成立

  若 n 是奇数，对于 i = 0\cdots\gcd(n, k) 的每个数字，求出 (i+tk) \bmod n 的环，将这个环上的数字按顺序写道第 i 行上面

  这样得到的数字表有几个性质：

  • 行，列元素个数均为奇数
  • 每行相邻元素在 \bmod n 意义下差 k
  • 每列相邻元素在 \bmod n 意义下差 1

  剩下的连边很简单，第一行连成一条链，除了最后一列的每一列连成一条链，剩余的点两两成对加入连通块即可

E

• 题意：

  有一个 1\sim 2^n-1 的数字排列在数轴上面，每个数字都向异或和较大的那一端移动，两个数字相遇后变成这俩数字的异或和。现在在数轴的正无穷和负无穷位置都添加一个权值 z，问有多少权值可以使得这堆数字最后合并成一个数字

• 题解：

  最简单的一集

  从高到低考虑，每一位都有偶数个数字使这一位为 1

  如果第 i 位为 1 的球的个数不为 0，则 z 的第 i 位一定为 0，否则此位为 1 的最左端和最右端两个数字会分别向数轴的负半轴和正半轴相向运动

  但是只要 z 的第 i 位不为 1，那么相邻两个此位为 1 的数字一定会相遇，直接更新异或和为此段区间的异或和即可