CF1965A 题解
2026-01-09 22:43:48
发布于：广东
23阅读
0回复
0点赞
笑点解析：
然后 Duel 的所有题都是超绝博弈论（（（
题意解析：Alice 和 Bob 在一个长度为 的数组 里进行操作。他们轮流对 进行如下操作：
- 选定一个正整数 使得 且对于所有 ，。
- 将所有 的值减去 。如果 ，则删除 。剩下的数重新按顺序排列。
如果在某个人的回合中数组为空，则对方获胜。
Who will 获胜 if both players play optimally?
不难发现，在某个人的回合中，如果 ：
- 如果取 后他可以获胜，则他就选 。
- 如果取 后他不能获胜，则他可以选 ，然后让后面一个人被迫选 ，依然可以获胜。
所以此时这个人必胜。
所以我们可以将 排序去重，找到第一个 的 ，就能确定哪个人获胜了。
namespace cjdst{
void solve(){
int n;
std::cin >> n;
std::vector <int> a(n + 5);
for(int i = 1; i <= n; i++){
std::cin >> a[i];
}
std::sort(a.begin() + 1, a.begin() + n + 1);
n = std::unique(a.begin() + 1, a.begin() + n + 1) - a.begin() - 1;
int cur = 0;
for(int i = 1; i <= n; i++){
if(a[i] - a[i - 1] > 1){
if(!cur) std::cout << "Alice\n";
else std::cout << "Bob\n";
return;
}
cur ^= 1;
}
if(cur) std::cout << "Alice\n";
else std::cout << "Bob\n";
}
}
时间复杂度：。
有帮助，赞一个