Pinely Round 4 (Div. 1 + Div. 2)

《i didnt know i needed a plush tree until now》

比赛链接

Problems	AC
A. Maximize the Last Element	○
B. AND Reconstruction	○
C. Absolute Zero	○
D. Prime XOR Coloring	○
E. Coloring Game	⊕
F. Triangle Formation
G. Grid Reset
H. Prime Split Game
I. Grid Game

Code Repo

A

给定一个包含 $n$ 个整数的数组 $a$ ，其中 $n$ 为奇数。

在一次操作中，您将从数组 $a$ 中删除两个相邻元素，然后连接数组的剩余部分。例如，给定数组 $[4,7,4,2,9]$ ，我们可以分别通过操作 $[\underset{―}{4,7},4,2,9]\to [4,2,9]$ 和 $[4,7,\underset{―}{4,2},9]\to [4,7,9]$ 获得数组 $[4,2,9]$ 和 $[4,7,9]$ 。但是，我们无法获得数组 $[7,2,9]$ ，因为它需要删除不相邻的元素 $[\underset{―}{4},7,\underset{―}{4},2,9]$ 。

您将重复执行此操作，直到 $a$ 中只剩下一个元素。

找出 $a$ 中剩余元素的最大可能值。

B

给定一个包含 $n-1$ 个整数的数组 $b$ 。

如果包含 $n$ 个整数的数组 $a$ 为 $b_i=a_i$ & $a_{i+1}$ （其中 $1\le i\le n-1$ 为 & 表示 按位与运算符，则该数组为好数组。

构造一个好数组，否则报告不存在好数组。

C

您将获得一个包含 $n$ 个整数的数组 $a$ 。

在一次操作中，您将执行以下两步移动：

1. 选择一个整数 $x$ ( $0\le x\le {10}^9$ )。
2. 将每个 $a_i$ 替换为 $|a_i-x|$ ，其中 $|v|$ 表示 $v$ 的 绝对值。

例如，通过选择 $x=8$ ，数组 $[5,7,10]$ 将更改为 $[|5-8|,|7-8|,|10-8|]=[3,1,2]$ 。

构造一个操作序列，使 $a$ 的所有元素在最多 $40$ 次操作中等于 $0$ ，或者确定这是不可能的。您无需最小化操作次数。

D

给定一个无向图，其中有 $n$ 个顶点，编号从 $1$ 到 $n$ 。当且仅当 $u\oplus v$ 为 素数 时，顶点 $u$ 和 $v$ 之间有一条边，其中 $\oplus$ 表示 按位 XOR 运算符。

使用最少的颜色数为图中的所有顶点着色，使得没有两个通过边直接连接的顶点具有相同的颜色。

$1\le n\le 2\cdot {10}^5$

这道题本质上和昆明邀请赛的一个题相似，都用了异或 和 4 相关的性质。那道题赛时队友打表找规律过了。

你发现首先有这样一个事情，考虑二进制下的最后一位，偶数 xor 偶数 和 奇数 xor 奇数 结果都是偶数。那么偶数集内部不会有边，奇数集也是。

只有奇数 xor 偶数才是奇数，才有可能是质数，那你奇数全用一个颜色，偶数用另外一个颜色即可。

但是注意有个特殊的质数是 2，所以考虑 xor 出来是 2 的情况，也就是最后两位 xor 出来是 10。这样的数是 4 个一循环的，所以你用 4 个颜色即可。

E

这是一个交互式问题。

考虑一个由 $n$ 个顶点和 $m$ 个边组成的无向连通图。每个顶点可以用以下三种颜色之一着色： $1$ 、 $2$ 或 $3$ 。最初，所有顶点都是未着色的。

Alice 和 Bob 正在玩一个由 $n$ 轮组成的游戏。在每一轮中，都会发生以下两步过程：

1. Alice 选择两种不同的颜色。

2. Bob 选择一个未着色的顶点，并用 Alice 选择的两种颜色之一为其着色。

如果存在一条连接相同颜色的两个顶点的边，则 Alice 获胜。否则，Bob 获胜。

您将获得该图。您的任务是决定您希望扮演哪个玩家并赢得游戏。

你首先判断下是不是二分图。

如果不是二分图的话，那 Alice 肯定赢了，他只用 1 和 2 就行了。

如果是二分图，则是 Bob 赢，因为只用 1 和 2 都卡不了 Bob 的话，算上 3 就更没可能了。

现在的问题是，如果 Bob 赢的话，怎么确定方案。因为他可能 1 2 3 的数量和黑点白点数量不一样。

那其实如果数量出现了偏差的话，就是 1 2 变成了 1 3 或者类似的情况。

那我们的策略就是，Alice 给了 1 就涂白点，给了 2 就涂黑点。如果都不满足肯定是某种点涂完了，而且有 3，用 3 涂剩下的。

赛后群友说这是个原题