HDU/HDOJ 2516 取石子游戏

传送门: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”);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include<fstream>
#include<algorithm>
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;
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《HDU/HDOJ 2516 取石子游戏》有10个想法

    1. 雖然kita英語不好,但是kita覺得學英語的話,盡量就是通過想像成像來理解,這樣對於腦內的記憶比較深刻些。就像當看到一隻貓的時候,我們就能立刻將貓這個字與貓這個動物聯繫起來。那kita想如果能看到貓這只動物的時候,就能將貓和cat聯繫起來的話,而不是先想到中文再由中文聯想到英文對應的單詞的話,雖然英文熟練了以後,這種腦內轉換可以快速到讓人忽略。。。

发表评论

电子邮件地址不会被公开。 必填项已用*标注