题解：P10335 [UESTCPC 2024] 取数游戏
pocafup
·
·
题解
P0:写在前面
出题人题解。
难题比赛没人写，还是出点清新签到题适合。
### P1：题解
首先判断序列中有没有一个权值大于等于 $\lceil \dfrac{\sum_{i=1}^{n} a_i}{2} \rceil$，如果有必然 A 获胜。
否则如果 $n$ 是偶数则 A 获胜，否则 B 必胜。
证明：发现其实合并过程并不重要，因为一旦出现一个权值大于等于 $\lceil \dfrac{\sum_{i=1}^{n} a_i}{2} \rceil$，取他必然最优。所以一方胜利当且仅当对方操作时不存在两个权值可以合并得到小于 $\lceil \dfrac{\sum_{i=1}^{n} a_i}{2} \rceil$ 的权值。考虑什么时候会出现这种状况。
发现一个必要要求是所有权值都大于等于 $\lceil \dfrac{\sum_{i=1}^{n} a_i}{4} \rceil$。这直接证明了序列长度不超过 4。而如果序列长度为 4，则唯一可能合并出一个小于等于 $\lceil \dfrac{\sum_{i=1}^{n} a_i}{2} \rceil$ 的权值的情况为四个权值均相等。由于 $\sum_{i=1}^{n} a_i$ 是奇数，不存在这种情况。
因此，双方均可以使用最优策略保证在序列长度大于等于 3 的情况下均不会出现所有权值大于等于 $\lceil \dfrac{\sum_{i=1}^{n} a_i}{4} \rceil$ 的情况，因此在序列长度为 3 时操作的选手必败。由于操作顺序固定，故只需要考虑初始序列长度的奇偶性即可。
```cpp
signed main(){
t = read();
while(t--){
n = read();
ans = 0;
For(i,1,n) pos[i] = read(),ans += pos[i];
For(i,1,n) if (pos[i]>ans/2.0) {puts("YES");goto abc;}
puts(n%2 ? "NO" : "YES");
abc:;
}
}
```
时间复杂度 $O(n)
P2:其他做法
这题其实有一个普遍的猜想：每次合并最小两个数字，最后谁先无法合并即判负。这个猜想的正确性基于正解，容易想到但不好写。复杂度为 O(n\log n) 由于是签到题最后没有卡这种做法。