AtCoder Beginner Contest 128 题解

AC Codes

A – Apple Pie

B – Guidebook

C – Switches

求解异或方程组的裸题，直接高斯消元后求自由元的个数即可。不过由于数据范围小，暴搜其实就可以做了。

D – equeue

给定一个双端队列，里面有 $N$ 个整数，你可以进行如下 $4$ 种操作：

1. 从队首拿一个元素到手里。
2. 从队尾拿一个元素到手里。
3. 把手中任意一个数放到队首
4. 把手中任意一个数放到队尾。

给定最大操作次数 $K$ （你只能操作不超过 $K$ 次），询问手中数字之和的最大值？

$N\leq 50, K\leq 100$ 。

可以发现数据范围非常小，所以用相对暴力的做法解决本题。

不妨枚举从队首拿了 $L$ 个元素，从队尾拿了 $R$ 个元素，然后将这些元素丢到优先队列中，将最小的负数元素依次丢回队列。

时间复杂度 $O(N^3\log N)$ 。

E – Roadwork

$N$ 个障碍物和 $Q$ 次询问，第 $i$ 个障碍物会在 $[S_i-0.5,T_i-0.5]$ 这一时间段内存在，坐标位于 $X_i$ 。每次询问会给出一个出发时间 $D_i$ ，从原点向正方向每秒前进一个单位距离，询问最多能走多远距离（遇到障碍物就会停下）？

$N,Q\leq 2\times 10^5$ 。

不要考虑某个人什么时候会被障碍物拦下，反向考虑：对于每个障碍物而言，它能拦截哪个时间段出发的人。然后对所有障碍物的时间段进行区间最小值覆盖，对于所有询问查询区间最小值即为答案。

这个思路可以用线段树实现区间覆盖+区间最值查询，总体复杂度 $O((N+Q)\log (N+Q)$ 。

F – Frog Jump

水池里有 $N$ 片荷叶排成一列，编号分别为 $0,1,\ldots,N-1$ ，荷叶 $i$ 有一个权值 $s_i$ 。你需要选择两个正整数 $A,B$ ，然后从荷叶 $0$ 开始重复以下跳跃过程：向前跳 $A$ 步，向后跳 $B$ 步；向前跳 $A$ 步，向后跳 $B$ 步；……直到跳到 $N-1$ 后结束。

在跳跃过程中，不能重复跳到同一片荷叶，不能跳出边界。你会得到遍历过的荷叶上的权值，询问这个权值的最大值是多少？

$3\leq N\leq 10^5$ 。

容易发现跳跃序列可以表示为：$0,A,A-B,2A-B,2A-2B,\ldots,N-1$ ，令 $C=A-B$ 则变为：$0,A,C,A+C,2C,A+2C,3C,\ldots,N-1$ 。

假设我们跳跃了 $K+1$ 轮到达终点，则有 $A+KC=N-1$ ，注意到 $KC\leq N-1$ 因此我们可以枚举 $K,C$ ，如果能 $O(1)$ 求出所有遍历节点的点权和就能 $O(N\log N)$ 解决本题了。不妨固定 $C$ ，枚举 $K$ 然后跳跃序列就是：

不难看出，随着 $K$ 的增长，新增的点是 $KC$ 和 $N-1-KC$ ，我们只需要保证枚举的过程中所有荷叶不重复经过并且 $A>B$ 即可。