hdu 1729 Stone Game 博弈论

时间:2023-03-10 03:07:22
hdu 1729 Stone Game 博弈论

那么对于这题对于每一堆,放石子放满就想当于满的时候取s-c个,反向只是让我理解题意更深。

首先我们知道(S,S)这个局面是必败局面。对于每一堆能加的数量有限,而当c的值(大于或者等于)

D=sqrt(s) 或者 D=sqri(s)+1的时候就可以一次完成,就是说可以从当前局面到达(S,S)的局面,

所以当前局面是必胜局面。而这种情况下,你能造成的局面有集合A={0,1,2,...,s-c-1};因为你可以去

s-c,s-c-1,s-c-2,.....,1;那么对应mex(x)函数(即A中未出现的最小的一个数字),那么自然该局面的SG值就是s-c了;

另外当c的值小于D的时候,是不可能一下子加满的,因为c*c+c绝对是小于s的;那么小于D的局面一定能够是必输的吗?很显然不是的。

对于(S,D-1)这个局面,一定是必输,因为他能到的局面都是必胜!现在c小于D,那么如果(S,C)这个局面能到(S,D);

就代表这个局面是必胜的。所以现在SG值要在新集合(D,C)中求,而求法与上面的相同求新的D,所以可以用递归函数:当C>D时,返回(S-C)

差不多就是这样。其实D = sqrt(s);这里算是个加速,要不然就要:while(d*d+d < S) d++;这样会很慢的。

代码如下:

 #include<iostream>
#include<stdio.h>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<vector>
#define ll __int64
#define pi acos(-1.0)
#define MAX 50000
using namespace std;
int mex(int s,int c)
{
int t=(int)sqrt(1.0*s);
while(t*t+t>=s) t--;
if(t<c) return s-c;
else return mex(t,c);
}
int main(){
int t=,m,s,c,ans;
while(scanf("%d",&m)&&m){
ans=;
for(int i=;i<m;i++){
scanf("%d%d",&s,&c);
if(s==||c==||s==c) continue;
ans^=mex(s,c);
}
printf("Case %d:\n",++t);
puts(ans==?"No":"Yes");
}
return ;
}