Codeforces Round #726 (Div. 2) D题解
2021/6/21 6:26:09
本文主要是介绍Codeforces Round #726 (Div. 2) D题解,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
传送门
题意
\(Alice\)和\(Bob\)在玩游戏。
他们从一个正整数\(n\)开始轮流对它进行运算。每个回合,玩家可以从\(n\)中减去一个非\(1\)或\(n\)的因数。在他/她的回合中不能移动的玩家输。\(Alice\)总是先动。
注意,他们在每个回合中都要减去当前数字的除数。
你被要求找出如果两名玩家都选择最佳策略,谁将赢得游戏。
思路
证明:
我们先考虑\(n\)为奇数的情况:
- 当\(n\)为质数时,先手无法选择任何数。即先手必输
- 当\(n\)为合数时,这个奇数的因子必然是奇数,那么这个\(n\)可以被分解为\(p_1*p_2(p_1,p_2均为奇数)\)。那么先手选择\(p_1\),则变为\((p_1-1)*p_2\),后手若选择\(p_2\),那么可以变为\((p_1-2)*p_2\),此时又转移为了两个奇数相乘,即先手必然面对奇数乘奇数的情况,辗转最后可转移成先手面对质数\(*1\)。即先手必输,面对奇数乘偶合数的人必赢。
综上所述若\(n\)为奇数,则先手必输。
在考虑偶数的情况:
- 若\(n\)不被\(2\)的幂次整除,即\(n=2^t*k(k为奇数)\)。此时若先手选择\(k\),则后手将面对\((2^t-1)*k\),即面对奇数的情况,由上述所知后手必输。即先手必赢。
- 若\(n\)被\(2\)的幂次整除,则分为:
- \(n=2*t(t为奇数)\),先手只能选择\(2\)的倍数,则后手将面对\(x=(2^k-1)*2^{t-k}\):若\(k\)不为\(1\),\(x=奇数*偶合数\),由上述所知必赢,所以先手必赢;若\(k\)为\(1\),\(x=2^{k-1}\),此时同样可以选择\(2^{k-2}\),将\(2^{k-2}\)局面抛给先手,即先手必然面对\(2的奇次幂\),辗转下来必然面对\(2\),先手必输。则综上所述先手必输。
- \(n=2*t(t为偶数)\),先手可以选择\(2^{t-1}\),将\(2的奇次幂\)局面抛给后手,则后手必输。即先手必赢。
综上所述若\(n\)不被\(2\)的幂次整除先手必赢,若\(n\)为\(2\)的奇次幂先手必输,若\(n\)为\(2\)的偶次幂先手必赢。
证毕。
代码
int main() { int T; cin >> T; while (T -- ) { int n; cin >> n; if (n % 2 != 0) puts("Bob"); else { int cnt = 0; while (n % 2 == 0) { cnt ++ ; n /= 2; } if (n > 1) puts("Alice"); else if (cnt % 2 == 0) puts("Alice"); else puts("Bob"); } } return 0; }
这篇关于Codeforces Round #726 (Div. 2) D题解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-29易优CMS安装常见问题汇总-icode9专业技术文章分享
- 2024-06-28易优新手必读安装教程-icode9专业技术文章分享
- 2024-06-28忘记eyoucms后台密码怎么办?-icode9专业技术文章分享
- 2024-06-26终极指南:Scrum中如何设置需求优先级
- 2024-06-26AI大模型企业应用实战(25)-为Langchain Agent添加记忆功能
- 2024-06-26小白家庭 nas 搭建方案-icode9专业技术文章分享
- 2024-06-23AI大模型企业应用实战(14)-langchain的Embedding
- 2024-06-23AI大模型企业应用实战(15)-langchain核心组件
- 2024-06-23AI大模型企业应用实战(16)-langchain核心组件
- 2024-06-23AI 大模型企业应用实战(06)-初识LangChain