首页 > 代码库 > HDU 1527 取石子游戏 威佐夫博弈
HDU 1527 取石子游戏 威佐夫博弈
题目来源:HDU 1527 取石子游戏
题意:中文
思路:威佐夫博弈 必败态为 (a,b ) ai + i = bi ai = i*(1+sqrt(5.0)+1)/2 这题就求出i然后带人i和i+1推断是否成立
下面转自网上某总结
有公式ak =[k(1+√5)/2],bk= ak + k (k=0。1,2,…,n 方括号表示取整函数)
当中出现了黄金切割数(1+√5)/2 = 1。618…,因此,由ak,bk组成的矩形近似为黄金矩形
因为2/(1+√5)=(√5-1)/2,能够先求出j=[a(√5-1)/2]
若a=[j(1+√5)/2]。那么a = aj,bj = aj + j
若不等于。那么a = aj+1,bj+1 = aj+1+ j + 1
若都不是,那么就不是神秘势
#include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; int main() { int a, b; while(scanf("%d %d", &a, &b) != EOF) { if(a > b) swap(a, b); int k = (sqrt(5.0)-1)/2*(double)a; double t = (double)(sqrt(5.0)+1)/2; if((int)(t*k) == a && (int)(a+k) == b) puts("0"); else if((int)(t*(k+1)) == a && (int)(a+1+k) == b) puts("0"); else puts("1"); } return 0; }
HDU 1527 取石子游戏 威佐夫博弈
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。