首页 > 代码库 > (zst的博弈) 【推理+找规律】
(zst的博弈) 【推理+找规律】
题目：
甲乙两人玩一个游戏: 一张卡片上有个数字,甲乙两人轮流操作, 若当前卡片上的数字为x, 每次操作可以把它变为x+1或2x, 且不能超过n (例如n=8,x=6,只能变为7而不能变为12), 每次甲首先在卡片上写1,规定写n的人获胜。给定n, 问甲是否有必胜策略?
分析：
看起来像一道博弈论的题，但实际上仅需细心的推理，耐心的找规律即可。
1、因为甲先写的1，所以乙的所有奇数全部要从甲的偶数哪里加1得来，因此如果n为奇数，甲只要保证自己写的数全是 奇数即可，因此奇数的情况下，甲赢。
2、发现因为从 n/2 到 n 两人只能一个一个加上去，因此从 n/2 到 n （n为偶数）中的所有偶数为必胜状态。而从 n/4 到 n/2 中的任何一个数乘以2均可跳到 n/2 到 n 的偶数状态，即为必胜状态，因此谁先写下 n/4 到 n/2 中的数，谁就必 胜。而只要某一个人写下了 n/4 ，对方虽然不会主动乘以2，但当他加了1以后，此人可立即乘以2跳到 n/2 至 n中 的偶数 ，因此谁写下 n/2 谁就必胜。
综上：n/4 是一个必胜周期。
参考代码：
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; int t; long long n; bool dfs(long long n) { if(n==2) return 0; else if(n%2) return 1; else return dfs(n/4); } int main() { cin>>t; while(t--) { cin>>n; bool f=dfs(n); if(f) cout<<"YES"<<endl; else cout<<"NO"<<endl; } return 0; }
(zst的博弈) 【推理+找规律】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。