Pinely Round 4 (Div.1+Div.2) 个人记录

· · 个人记录

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 了