Codeforces Round 941 (Div. 1) VP记录

Codeforces Round 941 (Div. 1) VP 记录

我了个掉分场啊。没场切 C 导致看起来会 - 50。

A

排序后差分。它毕竟还是个公平组合游戏，所以如果 Alice 在一次操作中能够控制能把后手扔给自己还是对面就赢了。

然后我们发现如果一个差分值 \(x \ge 2\) 就是必胜的吧。先手可以自己取完也可以剩一个给后手，输出当前先手即可。

然后如果当前是 \(0\)，先后手不变，如果是 \(1\)，先后手交换。如果结束了都没有一个 \(x > 2\)，那么判下是谁最后面临着不能动的局面就行。

B

不会构造题，写了一小时二十分钟自信掉分。

把 \([1, n] - \{k\}\) 分成 \([1, k), (k, n]\)。

先考虑怎么能做到能且仅能表示 \([1, k)\) 的所有数。

考虑如果用一堆 \(2\) 的幂能够做到表示 \([1, 2 ^ x)\) 的所有数。

那么我们找到一个最大的 \(x\) 满足 \(k - 1 \ge 2 ^ x - 1\)，并把 \(2^0, 2 ^ 1, \dots , 2 ^ {x - 1}\) 扔进答案里就能表示 \([1, 2 ^x)\)。

再扔个 \((k - 1) - (2 ^ x - 1)\) 进去就能恰好表示 \([1, k)\) 了。

然后我们把 \(x\) 后面的 \(2\) 进制幂也都扔回去就能得到大部分数了。

最后考虑填空，考虑哪些位置是没有的。因为我们损失了 \(2 ^ x\)，但是 \(2k \ge 2 ^ x\)。

所以扔个 \(k + 1\) 进答案表示 \([1, k) \cup (k, 2k]\) 的数，然后就能用当前数得到一个 \(2 ^ x\)，对后面没什么影响。

但是还有最后类个空要填。此时我们无法解决 \((x > k) + k\) 这样的数，因为我们在这一个 \(2^x\) 段中没有 \(k\)。然后其实直接扔个 \(2^x + k\) 就是对的，手玩一下，它与其他的数能够拼成所有数了。

C

考场上想 B 想不到然后在 C 随便写了发马拉车发现过不了就重新回去想 B 浪费了 20min，而实际上如果这 20min 认真利用起来我是真可以切掉这题的。

注意到 \(1\) 和 \(0\) 都是可以缩的，折成像 Z 字形的东西。

然后其实，如果 \(a_{i } = a_{i - 1}\) 就以 \(i - 0.5\) 为折痕折一下就行，这一定是合法的且最优的，证明合法性很简单，最优性看着就很对是吧。

D

不会构造题。

考虑如果没有吃掉一个数怎么构造。

有两种构造方法：

Method 1:

考虑每个出现次数为奇数的数。它们代表的区间一定跨过回文中心，并且本身也对称。也就是区间 \([i, n - i + 1]\)。

那把每一个出现次数为奇数的数从小到大排个序，显然这些区间长度越长其和越大，简单的做个差分就能还原序列了。

Method 2:

考虑区间 \([1, n]\) 最大值和次大值，要求最大值和次大值不同。

那么最大值一定是 \([1, n]\)，次大值一定是 \([1, n - 1]\)，减一下就能得到 \(a_n\) 也就是 \(a_1\)。

然后删掉 \([1, n]\) 找第三大值得到 \([1, n - 2]\) 后做差就行了……吗？

注意到 \([2, n - 1]\) 区间长度和 \([1, n - 2]\) 相等，有可能 \([2, n - 1]\) 的值大于 \([1, n - 2]\)，所以还得删掉 \([2, n - 1]\) 这一区间。然后就能用同样的方法得到 \(a_{n - 1}\) 即 \(a_2\)。

形式化的，每次求出 \(a_i\) 后，把以 \(i + 1\) 为左端点的和以 \(n - i\) 为右端点的区间都删了然后求当前最大值和次大值，差分下去就能还原序列。

考虑对于删除一个而言，这两种方法是否适用。

Method 2 只要最大值存在就能用，而 Method 1 只有删除最大值才能适用，两种方法互补。

讨论最大值出现了 \(1\) 次还是 \(2\) 次。\(1\) 次说明最大值还在，用 Method 2，否则用 Method 1 即可。

E

不会构造题。

但是我觉得这题代码比 D 题好写。

题解 CF1965E【Connected Cubes】 - 洛谷专栏 (luogu.com.cn) 尺子姐的题解讲的非常清楚，我觉得我讲一遍也就只是复述一遍题解而已，而且我懒得放图。

F

不会 Hall 定理是否应该爬？