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)\)
  

代码

1. // Problem: D. Even-Odd Game
2. // Contest: Codeforces - Codeforces Round #693 (Div. 3)
3. // URL: https://codeforces.com/contest/1472/problem/D
4. // Memory Limit: 256 MB
5. // Time Limit: 2000 ms
6. //
7. // Powered by CP Editor (https://cpeditor.org)
9. // %%%Skyqwq
10. #include <bits/stdc++.h>
12. //#define int long long
13. #define help {cin.tie(NULL); cout.tie(NULL);}
14. #define pb push_back
15. #define fi first
16. #define se second
17. #define mkp make_pair
18. using namespace std;
20. typedef long long LL;
21. typedef pair<int, int> PII;
22. typedef pair<LL, LL> PLL;
24. template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
25. template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
27. template <typename T> void inline read(T &x) {
28.     int f = 1; x = 0; char s = getchar();
29.     while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
30.     while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
31.     x *= f;
32. }
34. const int N=2e5+5;
35. int t,n,a[N];
36. int main()
37. {
38.     for(cin>>t;t;t--)
39.     {
40.             cin>>n;
41.             for(int i=1;i<=n;i++)cin>>a[i];
42.             sort(a+1,a+1+n,greater<int>());
43.             LL res=0;
44.             for(int i=1;i<=n;i++)
45.             {
46.                     if(i&1)
47.                     {
48.                             if(a[i]%2==0)res+=a[i];
49.                     }
50.                     else if(a[i]&1)
51.                             res-=a[i];
52.             }
53.             if(res==0)puts("Tie");
54.             else if(res>0)puts("Alice");
55.             else
56.                     puts("Bob");
57.     }
58.     return 0;
59. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！