农业营销型网站源码,创作图片的软件,提升学历方式,wordpress耗内存题意#xff1a;
给出三堆石子(m,n,p个)#xff0c;两人每次只能取斐波那契数f[i]个#xff0c;最先取光所有石子者取胜
题目#xff1a;
任何一个大学生对菲波那契数列(Fibonacci numbers)应该都不会陌生#xff0c;它是这样定义的#xff1a; F(1)1; F(2)2; F(n)F(n…题意
给出三堆石子(m,n,p个)两人每次只能取斐波那契数f[i]个最先取光所有石子者取胜
题目
任何一个大学生对菲波那契数列(Fibonacci numbers)应该都不会陌生它是这样定义的 F(1)1; F(2)2; F(n)F(n-1)F(n-2)(n3); 所以1,2,3,5,8,13……就是菲波那契数列。 在HDOJ上有不少相关的题目比如1005 Fibonacci again就是曾经的浙江省赛题。 今天又一个关于Fibonacci的题目出现了它是一个小游戏定义如下 1、 这是一个二人游戏; 2、 一共有3堆石子数量分别是m, n, p个 3、 两人轮流走; 4、 每走一步可以选择任意一堆石子然后取走f个 5、 f只能是菲波那契数列中的元素即每次只能取12358…等数量 6、 最先取光所有石子的人为胜者
假设双方都使用最优策略请判断先手的人会赢还是后手的人会赢。
Input
输入数据包含多个测试用例每个测试用例占一行包含3个整数m,n,p1m,n,p1000。 mnp0则表示输入结束。
Output
如果先手的人能赢请输出“Fibo”否则请输出“Nacci”每个实例的输出占一行。
Sample Input
1 1 1 1 4 1 0 0 0
Sample Output
Fibo Nacci
分析
SG函数解组合游戏
SG定理 游戏“和”的SG函数等于各子游戏SG函数的Nim和。
所谓的SG值就是记录当前状态是N是P的具体值N-position表示必赢状态其SG值不为0P-position表示必输状态其SG值为0。 下面介绍怎么求SG值首先定义mex(minimal excludant)运算这是施加于一个集合的运算表示不属于mex这个集合的最小非负整数。例如mex{0,1,2,4}3、mex{2,3,5}0、mex{}0。对于一个给定的有向无环图定义关于图的每个顶点的Sprague-Grundy函数g如下 g(n)mex{ g(m) | m是n的后继 },这里的g(n)即dp[n] 拿本题的栗子来讲首先有dp[0]0f[]{1,2,3,5…}f数组存放可以抓走石子的个数(斐波那契数列)并且按升序存放 举某一堆的例子。 当n1时先手可以抓走1-f{1}个石子剩余{0}张mex{dp[0]}{0}故dp[1]1; 当n2时先手可以抓走2-f{1,2}个石子剩余{1,0}个石子mex{dp[1],dp[0]}{1,0}故dp[2]2 当n3时先手可以抓走3-f{1,2,3}个石子剩余{2,1,0}个石子mex{dp[2],dp[1],dp[0]}{2,1,0}故dp[3]3; 当n4时先手可以抓走4-f{1,2,3}个石子剩余{3,2,1}个石子mex{dp[3],dp[2],dp[1]}{3,2,1},故dp[4]0; 当n5时先手可以抓走5-f{1,2,3,5}个石子剩余{4,3,2,0}个石子mex{dp[4],dp[3],dp[2],dp[0]}{0,3,2,0},故dp[5]1 以此类推… n 0 1 2 3 4 5 6 7 8 9… dp[n] 0 1 2 3 0 1 2 3 4 5… 由上述实例我们就可以得到1~n的SG值的计算步骤如下所示 ①、使用f数组保存菲波那契数列。 ②、然后使用book数组来标记当前状态n的后继m状态。 ③、最后模拟mex运算也就是我们在集合mex中查找未被标记值的最小值将其赋值给dp(n)。 ④、不断的重复 ② - ③ 的步骤即可完成计算1~n的SG值。
关于3种SG值计算方法重点 1、可选步数为1~m的连续整数直接取模即可SG(x) x % (m1); 2、可选步数为任意步dp(x) x; 3、可选步数为一系列不连续的数用get_SG()计算 此题就是选取第3种方法来计算SG值。 若还不清楚下面的代码有步骤详解
AC代码
#includestdio.h
#includestring.h
#includealgorithm
using namespace std;
const int M1e310;
int f[M],dp[M],book[M];
int m,n,p;
/**
SG值一个点的SG值就是一个不等于它的后继点的SG的且大于等于零的最小整数。
同mex()函数。简单点来讲就是当前状态离最近一个必败点的距离。距离为0就是必败点
SG(x)mexSS是x的后继状态的SG函数值集合mex(S)表示不在S内的最小非负整数
SG值是P/N状态的具体化
*/
int main()
{f[0]1;f[1]2;for(int i2; i100; i)初始化f[i]f[i-1]f[i-2];for(int i1; iM; i)///SG函数的运用{memset(book,0,sizeof(book));///每轮到当前i就重新初始化book都为未访问状态找出不属于这个集合的最小非负整数for(int j0; f[j]i; j)///此时j值不会越界所以不考虑越界约束book[dp[i-f[j]]]1;///i-f[j]为后继状态,book[sg[i-f[j]]]收录mex集合for(int j0; jM; j)///求没有出现在mex集合中的非负最小值if(!book[j]){dp[i]j;break;//每次break退出时就取不属于mex集合的最小非负整数}}while(~scanf(%d%d%d,n,m,p)(n||m||p)){if(dp[m]^dp[n]^dp[p])/// 对于每个堆的SG函数值我们只需要异或判断结果,当dp[n]不为0时即为N-position此时先手必赢printf(Fibo\n);elseprintf(Nacci\n);}return 0;
}
