【POJ】1067.取石子游戏

题解

这道题让我对SG函数有了更深刻的理解，这是道打表找规律题

我们打出来SG函数似乎是

1 2必败

3 5必败

4 7必败

6 10必败

8 13必败

哇我找到规律了……

然而，我显然不会通项

后来百度题解这个东西是威佐夫博弈，前面东西的通项是

\(\lfloor \frac{\sqrt{5} + 1}{2} \rfloor * (b - a)\)

orzzzz好吧

代码

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

//#define ivorysi

#define MAXN 200005

#define eps 1e-8

using namespace std;

typedef long long int64;

typedef double db;

db u = (sqrt(5.0) + 1) / 2;

int a,b;

int main() {

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

    while(scanf("%d%d",&a,&b) != EOF) {

	if(a > b) swap(a,b);

	if(floor((b - a) * u) == a) puts("0");

	else puts("1");

    }

}

巴特西

【POJ】1067.取石子游戏

题解

代码

最新文章

热门文章