AcWing 4875. 整数游戏
原题链接
困难
作者:
炽热的
,
2023-03-18 20:15:15
,
所有人可见
,
阅读 952
最小值是最快变成 $0$ 的,如果第一个元素是最小值则先手必败,否则后手必败
若第一个元素
是最小值
且不是 $0$ (是 $0$ 直接输了,没必要讨论):
- 则先手 $Alice$ 减 $1$ 后,不管与谁交换值,交换后都比之前大, 由于第一个元素不是 $0$ , 所以交换后轮到 $Bob$ 也必然不是 $0$。而 $Bob$ 只需要做一件事,不断将最小值扔回给 $Alice$ , 则 $Alice$ 必然最先达到 $0$, 必败。
若第一个元素不是最小值
- 则 $Alice$ 在减 $1$ 后, 直接选择最小值扔给 $Bob$,转变为 $Bob$ 先手拿到最小值,则转变上面那种情况,必败。
#include <cstring>
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n;
int a[N];
void solve() {
scanf("%d", &n);
int minv = 2e9;
for (int i = 1; i <= n; i ++ ) {
scanf("%d", &a[i]);
if (a[i] < minv) minv = a[i];
}
puts(a[1] == minv ? "Bob" : "Alice");
}
int main() {
int _; scanf("%d", &_);
while (_ -- ) solve();
return 0;
}
啊,头好痛,好像要长脑子了
好强 瞬间理解了 orz 直击重点爱了爱了
我当时写的时候一点没思考,看样例猜出来的,运气好过了。
能猜出来也是实力
强的,我一开始以为是博弈就用异或乱搞……
好神奇的变量名(关注点错)
哈哈哈哈
为什么令N=1e5 + 10?
因为习惯
orz
第一次觉得自己没有智商
可能是看到以为是博弈被吓跑了
我其实觉得这个东西和智商没啥关系……感觉是如果以前接触过类似的问题才会往这个方向去想,否则确实是打死也想不出来……
加了一些没用的特判666
666