果然 Div2 Only 的题很多都比 Div1+Div2 的题简单一点吗/fad

A

分类讨论。设 $0$ 的个数为 $c_0$，$1$ 的个数为 $c_1$。

• $c_0 \geq \frac{n}{2}$：直接输出 $\frac{n}{2}$ 个 $0$ 即可。
• $\frac{n}{2} \bmod 2 = 0$：直接输出 $\frac{n}{2}$ 个 $1$ 即可。
• $\frac{n}{2} \bmod 2 = 1$：发现 $c_1 > \frac{n}{2} \Rightarrow c_1 \geq \frac{n}{2}+1$，并且 $\frac{n}{2}+1 \bmod 2 = 0$，输出 $\frac{n}{2}+1$ 个 $1$ 即可。

B

每次贪心选取能让 $c_i$ 最大的值就可以了，因为这个是 $\gcd$ 的前缀和，所以 $c$ 一定是单调不增的，而如果当前有两个数 $a,b$ 满足 $\gcd(a,c_i) = \gcd(b,c_i) = g$，那么也一定有 $g|a,g|b,g|\gcd(a,b),\gcd(a,b,c_i) = g$，所以贪心不用关心相等贡献的数之间的顺序是正确的。

C

设 $(x,y)$ 表示询问 $p_x \bmod p_y$ 的值，那么我们设 $a=(x,y),b=(y,x)$ 讨论一下：

• $p_x < p_y$：那么 $(x,y) = p_x,(y,x) = p_y \bmod p_x < p_x$
• $p_x > p_y$：那么 $(x,y)=p_x \bmod p_y < p_y,(y,x) = p_y$

所以只需要询问 $(x,y),(y,x)$ 判断下最大值在那一边就行了。这样就能两次操作确定一个数（实际上可以做到 $2n-2$ 次操作，最后一个数不需要询问就能确定）

D

对于一个位置 $i$ 我们考虑它能从哪里来，到哪里去：

设 $p_1$ 表示 $i$ 前面第一个 $\leq a_i$ 的位置，$p_2$ 表示 $i$ 前面第一个 $\geq a_i$ 的位置，$t_1$ 表示 $i$ 后面第一个 $\leq a_i$ 的位置，$t_2$ 表示 $i$ 后面第一个 $\geq a_i$ 的位置，发现 $i$ 只能从 $p_1,p_2$ 来，到 $t_1,t_2$ 去（如果继续往前/往后发现无论如何都被这个数阻挡了），简单 dp 转移即可。

E

这个题只要想到大胆设 $t_{i,0},t_{i,1}$ 表示 $i$ 点颜色为 $0/1$ 的答案就好了，然后设 $v_i$ 表示 $i$ 点的最优解（其实就是 $\max\{t_{i,0},t_{i,1}\}$。

然后我们发现 $t_{i,0}$ 肯定是从白边的 $v_i$ 转移过来，$t_{i,1}$ 从黑边的 $v_i$ 转移，考虑我们是让最短路最大，于是我们建反图从 $n$ 到 $1$ 跑边权为 $1$ 的最短路（bfs），过程中直接类似 bfs 那样更新就好（也就是只用第一个访问这个点的 $v_i$ 去更新答案），因为你无论选哪条边这个人一定是走最短路的，所以我们就要从两种不同方案的最短路中选出最长的。