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 |
A
给定一个包含 $n$ 个整数的数组 $a$ ,其中 $n$ 为奇数。
在一次操作中,您将从数组 $a$ 中删除两个相邻元素,然后连接数组的剩余部分。例如,给定数组 $[4,7,4,2,9]$ ,我们可以分别通过操作 $[\underline{4,7}, 4,2,9] \to [4,2,9]$ 和 $[4,7,\underline{4,2},9] \to [4,7,9]$ 获得数组 $[4,2,9]$ 和 $[4,7,9]$ 。但是,我们无法获得数组 $[7,2,9]$ ,因为它需要删除不相邻的元素 $[\underline{4},7,\underline{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$ 。
在一次操作中,您将执行以下两步移动:
- 选择一个整数 $x$ ( $0 \le x \le 10^{9}$ )。
- 将每个 $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$ 轮组成的游戏。在每一轮中,都会发生以下两步过程:
Alice 选择两种不同的颜色。
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 涂剩下的。
赛后群友说这是个原题
Pinely Round 4 (Div. 1 + Div. 2)