第1到T行：包含“Farmer John”或者是“Bessie”，表示谁赢了这轮游戏。
威佐夫博弈板子（套公式$\frac{\sqrt{5}+1}{2}$）
把横坐标抽象成一堆石头，纵坐标抽象成一堆石头就行了
然后如果不知道威佐夫博弈这玩意的话其实可以用必胜态必败态来推一下
可以画个图什么的，把前几个必败态找出来，然后会发现对于每一列，必败态仅有一点，然后这些点都沿着对角线对称
所以就递推一下必败态就可以了
威佐夫博弈做法
#include <bits/stdc++.h> using namespace std ; int n , m , t ; int main() { int a , b ; scanf( "%d%d%d" , &a , &b , &t ) ; double y = ( sqrt( 5 ) + 1 ) / 2 ; while( t -- ) { scanf( "%d%d" , &n , &m ) ; if( m < n ) swap( m , n ) ; int x = ( m - n ) * y ; if( x == n ) puts( "Farmer John" ) ; else puts( "Bessie" ) ; } }
递推做法
#include <bits/stdc++.h> using namespace std ; const int N = 1e6 + 10 ; int ans[ N ] ; int main() { ans[ 1 ] = 1 ; int tmp = 1 ; for( int i = 1 ; i < N ; i ++ ) { if( ans[ i ] ) continue ; ans[ i ] = ans[ tmp ] + i - tmp + 1 ; tmp = i ; if( ans[ i ] < N - 1 ) ans[ ans[ i ] ] = i ; } int n , m , t ; scanf( "%d%d%d" , &n , &m , &t ) ; while( t -- ) { int a , b ; scanf( "%d%d" , &a , &b ) ; a ++ ; b ++ ; if( ans[ a ] == b || ans[ b ] == a ) puts( "Farmer John" ) ; else puts( "Bessie" ) ; } }
BZOJ3298: [USACO 2011Open]cow checkers 威佐夫博弈
原文：https://www.cnblogs.com/henry-1202/p/BZOJ3298.html