Codeforces Round #693 (Div. 3)
比赛链接Codeforces Round #693 (Div. 3)
D.Even-Odd Game
Alice 和 Bob 玩游戏
给定含 \(n\) 个数字的数列 \(\{a\}\)
两人轮流进行游戏，Alice 先手
每一轮一人从数列中选取一个数字并将这个数字从数列中删掉
如果 Alice 选择的数字是偶数，那么 Alice 得分加上这个数字，否则 Alice 不加分
如果 Bob 选择的数字是奇数，那么 Bob 得分加上这个数字，否则 Bob 不加分
假设二人都采取最优策略，最后得分高的获胜，请输出胜者（Alice 或者 Bob），或者指明这是平局（Tie）
输入
多组测试数据
先输入 \(T\) 表示有 \(T\) 组测试数据（\(1\le T \le 10^4\)）
接下来 \(T\) 组数据，每组数据先输入 \(n\)（\(1\le n \le2\cdot10^5\)），接下来 \(n\) 个数字描述数列 \(\{a\}\)
保证每个测试点 \(T\) 组数据的 \(n\) 之和不超过 \(2\cdot10 ^5\)
输出
每组数据一行
[*]如果 Alice 赢了，输出 Alice
[*]如果 Bob 赢了，输出 Bob
[*]如果二人得分相同，输出 Tie
解题思路
博弈论
博弈策略：两人都选择最大的数
假设两人某时刻分数为 \(x,y\)，最终结果为两者的差值 \(x-y\)，现在轮到先手决策，假设现在最大值为 \(z\)，如果先手选择该数，若该数为偶数，则最终差值为 \(x+z-y\)，此时选最大值对先手最优，反之如果该数为奇数，\(z\) 本来是作为 \(y\) 的一部分，但被先手选择了，即最终差值为 \(x-(y-z)=x+z-y\)，相当于给先手加分了，故每次选择最大值为最优策略
[*]时间复杂度：\(O(nlogn)\)
代码
// Problem: D. Even-Odd Game
// Contest: Codeforces - Codeforces Round #693 (Div. 3)
// URL: https://codeforces.com/contest/1472/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
// %%%Skyqwq
#include <bits/stdc++.h>
//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
template <typename T> void inline read(T &x) {
int f = 1; x = 0; char s = getchar();
while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
x *= f;
}
const int N=2e5+5;
int t,n,a;
int main()
{
for(cin>>t;t;t--)
{
cin>>n;
for(int i=1;i<=n;i++)cin>>a;
sort(a+1,a+1+n,greater<int>());
LL res=0;
for(int i=1;i<=n;i++)
{
if(i&1)
{
if(a%2==0)res+=a;
}
else if(a&1)
res-=a;
}
if(res==0)puts("Tie");
else if(res>0)puts("Alice");
else
puts("Bob");
}
return 0;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]