定义
威佐夫博弈（Wythoff's game）：有两堆各若干个物品，两个人轮流从任一堆取至少一个或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。
思路
看到题目首先拿出看家绝活打表
#include<bits/stdc++.h>
#define fi first
#define se second
#define debug cout<<"I AM HERE"<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn=1e3+5,inf=0x3f3f3f3f,mod=1e9+7;
const int eps=1e-3;
int n;
int dp[maxn][maxn];
signed main(){
scanf("%d",&n);
dp[0][0]=0;
int last=0;
for(int i=0;i<=n;i++){
for(int j=0;j<=n;j++){
for(int k=1;k<=min(i,j);k++){
dp[i][j]|=(!dp[i-k][j-k]);
}
for(int k=1;k<=i;k++){
dp[i][j]|=(!dp[i-k][j]);
}
for(int k=1;k<=j;k++){
dp[i][j]|=(!dp[i][j-k]);
}
if(dp[i][j]==0&&i<=j){
cout<<i<<" "<<j<<endl;
}
}
}
return 0;
}
//(0,0),(1,2),(3,5),(4,7),(6,10)
打出所有必败态
这个时候你会发现差值是0,1,2,3...逐步递增
对于正常人来说还是没什么思路......所以看题解
首先说一些性质
你观察会发现
任何自然数都包含在一个且仅有一个必败态中。
显然地，全体正整数被必败态分割成两个不相交的集合。
这个时候可以想到beatty定理
设a、b是正无理数且 1/a +1/b =1。
记P={ [na] | n为任意的正整数}，Q={ [nb] | n 为任意的正整数}，([x]指的是取x的整数部分)则P与Q是N+的一个划分，即P∩Q=Ø且P∪Q=N+（正整数集）
设第一个数为\(\lfloor a*n\rfloor\) 则第二个数为\(\lfloor a*n+n\rfloor\)
因为差值为n
带入式子
\(\frac{1}{a} + \frac{1}{a + 1} =1\)
\(a^2-a-1=0\)
\(a=\frac{1+\sqrt 5}{2}\)
那么如果这是必败态则第二个数减第一个数乘a=第一个数
模板题
代码
#include<bits/stdc++.h>
#define fi first
#define se second
#define debug cout<<"I AM HERE"<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn=1e3+5,inf=0x3f3f3f3f,mod=1e9+7;
const double rat=(sqrt(5)+1)/2;
int a,b;
signed main(){
scanf("%d%d",&a,&b);
if(a<b) swap(a,b);
if((int)((a-b)*rat)!=b){
printf("1\n");
}else{
printf("0\n");
}
return 0;
}
//(0,0),(1,2),(3,5),(4,7),(6,10)
参考链接: