博弈-SG函数.doc

/downloads156/ebook/detail696143.html /gzprogramming/blog/category/%D7%E9%BA%CF%B2%A9%DE%C4 博弈-高级兵法-SG函数先看HDU-1848任何一个大学生对菲波那契数列(Fibonacci numbers)应该都不会陌生，它是这样定义的：F(1)=1;F(2)=2;F(n)=F(n-1)+F(n-2)(n=3);所以，1,2,3,5,8,13就是菲波那契数列。今天，又一个关于Fibonacci的题目出现了，它是一个小游戏，定义如下：1、这是一个二人游戏;2、一共有3堆石子，数量分别是m, n, p个；3、两人轮流走;4、每走一步可以选择任意一堆石子，然后取走f个；5、f只能是菲波那契数列中的元素（即每次只能取1，2，3，5，8等数量）；6、最先取光所有石子的人为胜者；假设双方都使用最优策略，请判断先手的人会赢还是后手的人会赢Input输入数据包含多个测试用例，每个测试用例占一行，包含3个整数m,n,p（1=m,n,p=1000）。m=n=p=0则表示输入结束。Output如果先手的人能赢，请输出“Fibo”，否则请输出“Nacci”，每个实例的输出占一行。Sample Input1 1 11 4 10 0 0Sample OutputFiboNacci对于每次取的特殊规则，找出SG函数值，然后这些SG值做异或，异或=0就输了！下面是模版-这种题直接套模版就行-int mex1(int p) int i,t; bool g101=0; for(i=0;ik;i+) /k是fibo数组的个数 t=p-fiboi;/ fiboi是题中定义的特殊取法规则的数组（上面题里的 1， 2 ，3 ，5 ，8 ，13 ，21 ） if(t0) break; if (ft=-1) /f 表示 存放SG 函数值的数组 ft=mex1(t); gft=1; for(i=0;i+) if (!gi) return i; Mex1()函数就可以返回SG（I）的值，牛吧！直接用吧，别深挖了！还是看代码吧！/ hdu 1848#include #include #include using namespace std;int k,fibo100,f10001;int mex1(int p) int i,t; bool g101=0; for(i=0;ik;i+) /注意 i从0开始，别动i t=p-fiboi; if(t0) break; if (ft=-1) ft=mex1(t); gft=1; for(i=0;i+) /好像必须从0开始啊 if (!gi) return i; int main(int argc, char *argv) int m,n,p,s; fibo0=1; /也从0开始 ，别动 fibo1=2; for(int i=2;i=18;i+)/为啥就到18呢，因为fibo18就大于1000了，本题范围是1000 fiboi=fiboi-1+fiboi-2; k=19;/取数规则的个数 fibo的个数 sort(fibo,fibo+k); /排序 本题这句可以不用，因为fibo已经排好序了，带着好，免得错！ memset(f,-1,sizeof(f); f0=0; for(int i=1;i=1000;i+) fi=mex1(i); while(scanf(%d%d%d,&m,&n,&p) if (m=0&n=0&p=0) break; s=0; s=sfmfnfp; if (s=0) printf(Naccin); else printf(Fibon); system(PAUSE); return EXIT_SUCCESS;也就是说把mex1() 直接用就行，main() 里根据题的意思输入和输出变变就得了！这个数组名字要一致，且是公有数组！int k,fibo100,f10001;HDU 1536 大家再仔细分析下，AC 了就基本成为博弈的高手了，当然还要会博弈-第一讲同志们最好先不要看下面的代码，直接A吧，实在不行再看！先不要看噢。#include #include #include using namespace std;int k,fibo100,f10001;int mex1(int p) int i,t; bool g101=0; for(i=0;ik;i+) t=p-fiboi; if(t0) break; if (ft=-1) ft=mex1(t); gft=1; for(i=0;i+) if (!gi) return i; int main(int argc, char *argv) int m,l,s,y; while(scanf(%d,&k)!=EOF) for(int i=0;ik;i+) scanf(%d,&fiboi); if (k=0) break; sort(fibo,fibo+k); memset(f,-1,sizeof(f); f0=0; for(int i=1;i=10000;i+) fi=mex1(i); scanf(%d,&m); for(int i=1;i=m;i+) s=0; scanf(%d,&l); for(int j=1;j=