本文主要是介绍B - Stone Game，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这题看懂之后还是相当简单的：
三个状态求sg：(s,s)必败态
s一定时求能到（s,s）的必胜态（s,c）；
根据题意可知当c+c*c>=s时都为必胜态，现在考虑临界情况t+t*t==s,此时t刚好为必胜态，若t再减小一则变为必败态因为（s,t）只能到必胜态；当t在增大时状态无法直接确定；
故分以下三种状态：
1.c>t：必胜sg呈链状
sg[s-c]=mex(sg[y]|0<=y<s-c)
可得 sg[s-c]=s-c;
2.c==t:必败态
sg[s-c]=0;
3.c<t
转化为求到必败态的胜负即求(t,c);
B - Stone Game
Crawling in process... Crawling failed Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
Submit Status
Description
This game is a two-player game and is played as follows:
1. There are n boxes; each box has its size. The box can hold up to s stones if the size is s.
2. At the beginning of the game, there are some stones in these boxes.
3. The players take turns choosing a box and put a number of stones into the box. The number mustn’t be great than the square of the number of stones before the player adds the stones. For example, the player can add 1 to 9 stones if there are 3 stones in the box. Of course, the total number of stones mustn’t be great than the size of the box.
4.Who can’t add stones any more will loss the game.
Give an Initial state of the game. You are supposed to find whether the first player will win the game if both of the players make the best strategy.
Input
The input file contains several test cases.
Each test case begins with an integer N, 0 < N ≤ 50, the number of the boxes.
In the next N line there are two integer si, ci (0 ≤ ci ≤ si ≤ 1,000,000) on each line, as the size of the box is si and there are ci stones in the box.
N = 0 indicates the end of input and should not be processed.
Output
For each test case, output the number of the case on the first line, then output “Yes” (without quotes) on the next line if the first player can win the game, otherwise output “No”.
Sample Input
3 2 0 3 3 6 2 2 6 3 6 3 0
Sample Output
Case 1: Yes Case 2: No
#include<stdio.h>
#include<math.h>
get_sg(int s,int c)
{int t=(int)sqrt(s*1.0);while(t+t*t>=s)//找到必败态 t--;if(c>t)return s-c;else if(c==t)return 0;elsereturn get_sg(t,c);//求到必败态是必败还是必胜；
}
int main()
{int n;int m=0;while(scanf("%d",&n)!=EOF&&n!=0){m++;int sum=0;for(int i=1;i<=n;i++){int a,b;scanf("%d%d",&a,&b);sum=sum^get_sg(a,b);} if(sum==0){printf("Case %d:\nNo\n",m);}elseprintf("Case %d:\nYes\n",m);} }
这篇关于B - Stone Game的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
