Tanky WooRSS

HDU/HDOJ 2516 取石子游戏

18 Jan 2011
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

传送门:http://acm.hdu.edu.cn/showproblem.php?pid=2516

找规律。。。

网上有分析:

题意:这题就是博弈,而且是简单的博弈,但是分析时候要一点时间, 解题分析: 当n为1的时候是输出first,n为2的时候输出second, 3的时候也是输出second,当n为4的时候,第一个人想获胜就必须先取 一个,这是剩余的石子数为3,此时无论第二个人如何取,第一个人都 能够赢,当n为5的时候,first不可能获胜,因为他取2时,second直接 取掉剩余的3个,取1时,second也是取1,这样就演变为n为3的时候了, 所以n为5时候,输出的是second ,当n为6的时候,first只要取掉1个, 就可以让局势变为n为5的时候,输出的是first,n为7的时候,first取掉 2个,又可以变为5的时候,所以也是输出first,n为8的时候,当first 取1个时候,局势变为7的时候,第二个人可以赢,取2时候,变为n为6的时 候,也是第二个人赢,取三个时候,second直接取掉剩余的5个,所以,n为 8的时候,是输出second。从上面可以看出,n为2,3,5,8时,这些都是输 出second,也就是说这些就是必败点,仔细的人会发现这些满足斐波那契数 的规律,可以推断13也是一个必败点,也就是说,只要是斐波那契数,都是 必败点,输出的就是second,所以,我们可以利用斐波那契数数的公式: fib[i]=fib[i-1]+fib[i-2],只要n是斐波那契数,那就输出second,所以有 if(n==fib[i]) printf("Second win\n"); else printf("First win\n");

#include
#include
#include
using namespace std;

int Fib[44];

int main()
{
     int n;
     Fib[0]=2;Fib[1]=3;
     for(int i=2;i<44;i++)
         Fib[i]=Fib[i-1]+Fib[i-2];
     while(cin>>n&&n;){
         if(std::binary_search(Fib,Fib+44,n))
              cout<<"Second win"<<endl;
         else
              cout<<"First win"<<endl;
     }
     return 0;
}