【hdu1846】Brave Game

这道题就是noi.openjudge.cn上的取石子问题,之前是用搜索写的,但今天发现用博弈论的思路来写会简单非常非常多!

首先,如果m>=n,那么第一个人必胜。

那么如果现在剩下m+1个石子,那么接下来那个人无论取1到m中任意一个数字的石子数,都无法取完石子并会剩下1-m个石子,这样的话下一个人一定获胜。

换句话说,剩下m+1个石子的话接下来要取的人一定输

所以若m+1<n<2(m+1),现在这一个人只要取n-(m+1)个石子,他就一定赢。

而当2(m+1)<n<3(m+1)时,这个人只要取(n-2(m+1))个石子,那么他的对手取后就会出现刚刚的m+1<n<2(m+1)那种情况,他还是必胜。

推广一下,只要存在一个i,使得 i*(m+1)<n<(i+1)*(m+1)成立,则第一个人必胜;反之,若存在一个i使得i*(m+1)==n,则第二个人必胜。

好了,分析完之后代码就很简单了:

#include<cstdio>
int main()
{
    int c,n,m;
    scanf("%d",&c);
    while(c--)
    {
        scanf("%d %d",&n,&m);
        if(m>=n){printf("first
");continue;}
        for(int i=1;;i++)
        {
            if(i*(m+1)<n&&(i+1)*(m+1)>n){printf("first
");break;}
            else if(i*(m+1)==n){printf("second
");break;}
        }
    }
    return 0;
}
View Code
原文地址:https://www.cnblogs.com/JKAI/p/6954053.html