比赛链接
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\),相当于给先手加分了,故每次选择最大值为最优策略
代码
- // 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[N];
- int main()
- {
- for(cin>>t;t;t--)
- {
- cin>>n;
- for(int i=1;i<=n;i++)cin>>a[i];
- sort(a+1,a+1+n,greater<int>());
- LL res=0;
- for(int i=1;i<=n;i++)
- {
- if(i&1)
- {
- if(a[i]%2==0)res+=a[i];
- }
- else if(a[i]&1)
- res-=a[i];
- }
- if(res==0)puts("Tie");
- else if(res>0)puts("Alice");
- else
- puts("Bob");
- }
- return 0;
- }
复制代码 免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作! |