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
给定一个包含
个整数的数组 ,其中 为奇数。 在一次操作中,您将从数组
中删除两个相邻元素,然后连接数组的剩余部分。例如,给定数组 ,我们可以分别通过操作 和 获得数组 和 。但是,我们无法获得数组 ,因为它需要删除不相邻的元素 。 您将重复执行此操作,直到
中只剩下一个元素。 找出
中剩余元素的最大可能值。
B
给定一个包含
个整数的数组 。 如果包含
个整数的数组 为 & (其中 为 & 表示 按位与运算符,则该数组为好数组。 构造一个好数组,否则报告不存在好数组。
C
您将获得一个包含
个整数的数组 。 在一次操作中,您将执行以下两步移动:
- 选择一个整数
( )。 - 将每个
替换为 ,其中 表示 的 绝对值。 例如,通过选择
,数组 将更改为 。 构造一个操作序列,使
的所有元素在最多 次操作中等于 ,或者确定这是不可能的。您无需最小化操作次数。
D
给定一个无向图,其中有
个顶点,编号从 到 。当且仅当 为 素数 时,顶点 和 之间有一条边,其中 表示 按位 XOR 运算符。 使用最少的颜色数为图中的所有顶点着色,使得没有两个通过边直接连接的顶点具有相同的颜色。
这道题本质上和昆明邀请赛的一个题相似,都用了异或 和 4 相关的性质。那道题赛时队友打表找规律过了。
你发现首先有这样一个事情,考虑二进制下的最后一位,偶数 xor 偶数 和 奇数 xor 奇数 结果都是偶数。那么偶数集内部不会有边,奇数集也是。
只有奇数 xor 偶数才是奇数,才有可能是质数,那你奇数全用一个颜色,偶数用另外一个颜色即可。
但是注意有个特殊的质数是 2,所以考虑 xor 出来是 2 的情况,也就是最后两位 xor 出来是 10。这样的数是 4 个一循环的,所以你用 4 个颜色即可。
E
这是一个交互式问题。
考虑一个由
个顶点和 个边组成的无向连通图。每个顶点可以用以下三种颜色之一着色: 、 或 。最初,所有顶点都是未着色的。 Alice 和 Bob 正在玩一个由
轮组成的游戏。在每一轮中,都会发生以下两步过程:
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)