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

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]$ ,我们可以分别通过操作 $[\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$ 。

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

  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 涂剩下的。

赛后群友说这是个原题

Author

TosakaUCW

Posted on

2024-07-29

Updated on

2024-08-02

Licensed under

Comments