首页 > 其他 > 详细

(zst的博弈) 【推理+找规律】

时间:2017-07-19 15:50:49      阅读:268      评论:0      收藏:0      [点我收藏+]
题目:

甲乙两人玩一个游戏: 一张卡片上有个数字,甲乙两人轮流操作, 若当前卡片上的数字为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;
}
View Code

 

(zst的博弈) 【推理+找规律】

原文:http://www.cnblogs.com/linda-fcj/p/7206129.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!