威佐夫博弈:有两堆各若干个物品,两个人轮流从任意一堆中取出至少一个或者同时从两堆中取出同样多的物品,规定每次至少取一个,至多不限,最后取光者胜利。我们局势为
我们定义一个奇异局势为可以让先手A必输的局势。例如在上面这个题中,可以找到类似于(1,2),(3,5),(4,7)(1,2),(3,5),(4,7)等奇异局势。
所谓适当的方法,分为以下几种情况:(假设当前的情况为(a,b)(a,b))
当的时候,显然可以通过把两堆石子各取走a个,这样就转为了(0,0),必定为奇异局势。
当的时候,取走b-b[k]个石子。
当的时候,取走
个石子
当的时候,取走
个石子
当的时候,当
的时候,从第二堆中取走
堆,而当
的时候,从第二堆中取走
个即可。
我们可以找到公式,我们只要判断是否等于即可。
MY CODE:
#include <bits/stdc++.h>
using namespace std;
int main()
{
int x;
int y;
while(cin>>x>>y)
{
if(x>y)
swap(x,y);//交换x和y
if(x==floor((y-x)*(1+sqrt(5*1.0))/2))//套公式
puts("0");
else
puts("1");
}
return 0;
} 
京公网安备 11010502036488号