本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-30 00:20:01

A

显然只有奇数位置可以保留，取最大值就可以。

B

对于 $1 \le \forall i \le n$，$a_i$ 都包含 $b_{i-1} | b_{i}$ 的所有 $1$。另外，容易证明，再增加其他位作为 $1$ 没有任何好处，所以，$a_i = b_{i-1} | b_{i}$。

C

容易发现，每次选定一个 $x$，每个数都会变为其与 $x$ 的距离。
另外，如果 $x$ 是偶数，那么操作之后所有的数的奇偶均不变，反之所有数的奇偶均变化。
也就是说如果一开始所有数奇偶不是完全一致，那么无解。
反之，根据 $40$ 的操作次数限制，容易想到每次将某个东西折半。
再考虑到操作的本质，容易发现每次操作都可以通过选择 $x=\frac{\min(a)+\max(a)}{2}$ 将 $a$ 的极差除以 $2$，最后显然能在 $40$ 步内出结果。

D

观察样例，发现 $n=6$ 时答案是 $4$，后面就不给了。
作出一个猜想：对于 $n \gt 6$，答案一定都是 $4$。
考虑构造一组可行方案，此时，考虑到偶数只有 $2$ 是质数，那么是否能让所有相同的位置异或和是偶数呢？
再考虑到有 $4$ 种颜色，或许是 $1,2,3,4$ 交替？
现在只需要证明假设位置从 $0$ 编号，模 $4$ 同余的所有位置的编号异或和不是 $2$，而这个简单观察下其二进制构成就 ok 了。

E

容易想到对于 Alice 来说，始终选择 $(1,2)$ 是最优解（并不会证明），也就是说整张图只有两种颜色。
所以说，判断 Bob 是否获胜只需要判断图是否为二分图。
如果不是二分图，那么 Alice 获胜。
此时交互选择 Alice，然后反复输出 1 2 就可以。
否则 Bob 获胜，记录填 $1$ 的点集合，填 $2$ 的点集合。
然后，开始交互，选择 Bob。
对于每次 Alice 给出的选择 $(a,b)$，有以下情况：

1. 可以选择 $1$，并且选 $1$ 的点集还有剩余用来配对。此时颜色选 $1$ 就行。
2. 可以选择 $2$，并且选 $2$ 的点集还有剩余用来配对。此时颜色选 $2$ 就行。
3. 此时，$(a,b)$ 肯定至少有一个是 $3$，并且另一个数所属的集合已经填满，此时应当以选择 $3$ 并将其加入没填满的集合。

显然总是能构造出解的。

值得一提的是，2sat 需要注意加边是否加完。
这道题值得注意的点在于想到如果正确的分配 Alice 的方案，突破口在于直接相关的信息。

F

设 $b = sort(a[l \cdots r])$。
此时，对于任意 $1 \le i \lt j \lt k \le |b|$，合法当且仅当 $b_i + b_j \gt b_k$。
这时候就发现一个问题，长度为 $K$ 的区间不合法，随着 $K$ 增加，$b_K$ 的增长速度一定不慢于斐波那契额数列，而后者增长速度是 $O(2^n)$。
这就意味着大约在 $|b| \ge 50$ 的时候一定有解。
那么现在考虑如何处理 $|b| \lt 50$ 的情况。
容易证明以下两个结论：

1. 只有两种情况：不存在两条分别来自两个三角形的小棒的编号相邻；两个三角形的编号是 $6$ 个连续整数；
2. 当不存在两条分别来自两个三角形的小棒的编号相邻时，组成两个三角形的小棒的编号分别是 $3$ 个连续整数（最优情况）。

然后枚举就 ok 了