2022“杭电杯”中国大学生算法设计超级联赛(1)
2022/7/20 9:19:40
本文主要是介绍2022“杭电杯”中国大学生算法设计超级联赛(1),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
比赛链接
2022“杭电杯”中国大学生算法设计超级联赛(1)
7149. Alice and Bob
有 \(a_i\) 个 \(i\)(\(0\leq i\leq n\)),\(Alice\) 每次可以将这些数划分为两个集合,\(Bob\) 每次可以删除一个集合,同时另外一个集合所有数减一。如果任何时候存在 \(0\) 则 \(Alice\) 胜,否则 \(Bob\) 胜
解题思路
博弈论
需要对 \(Alice\) 构造一种必胜策略,考虑将 \(a_i\) 个 \(i\) 平分,即每次平分进两个集合,无论 \(Bob\) 如何选择,而由于每次平分后另外一个集合所有数减一,相当于将 \(i\) 减一,逆序处理所有的 \(a_i\),累计所有贡献,只要判断最后轮次的时候是否还存在数即可,因为划分集合后选择权在 \(Bob\) 手上,如果 \(Alice\) 不采取平分的策略,\(Bob\) 一定会删除对自己最有利的集合,而如果采取平分策略,即主动权掌握在 \(Alice\) 手上,无论 \(Bob\) 如何操作,其结果都是一定的。另一种理解:平分策略的任一子集是非平分策略的两个子集的中和,如果采取非平分策略,\(Bob\) 可以删除使对 \(Alice\) 平分策略更差的子集,这样可能平分策略能获胜但有一步采取非平分策略结果却败了,故平分策略是最优策略
- 时间复杂度:\(O(n)\)
代码
// %%%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=1e6+5; int a[N],n,t; int main() { help; for(read(t);t;t--) { cin>>n; for(int i=0;i<=n;i++)cin>>a[i]; for(int i=n;i>=1;i--)a[i-1]+=a[i]/2; puts(a[0]?"Alice":"Bob"); } return 0; }
这篇关于2022“杭电杯”中国大学生算法设计超级联赛(1)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-01后台管理开发学习:新手入门指南
- 2024-11-01后台管理系统开发学习:新手入门教程
- 2024-11-01后台开发学习:从入门到实践的简单教程
- 2024-11-01后台综合解决方案学习:从入门到初级实战教程
- 2024-11-01接口模块封装学习入门教程
- 2024-11-01请求动作封装学习:新手入门教程
- 2024-11-01登录鉴权入门:新手必读指南
- 2024-11-01动态面包屑入门:轻松掌握导航设计技巧
- 2024-11-01动态权限入门:新手必读指南
- 2024-11-01动态主题处理入门:新手必读指南