【题目来源】http://acm.hdu.edu.cn/showproblem.php?pid1846【题目描述】十年前读大学的时候中国每年都要从国外引进一些电影大片其中有一部电影就叫《勇敢者的游戏》英文名称Zathura一直到现在我依然对于电影中的部分电脑特技印象深刻。今天大家选择上机考试就是一种勇敢brave的选择这个短学期我们讲的是博弈game专题所以大家现在玩的也是“勇敢者的游戏”这也是我命名这个题目的原因。当然除了“勇敢”我还希望看到“诚信”无论考试成绩如何希望看到的都是一个真实的结果我也相信大家一定能做到的~各位勇敢者要玩的第一个游戏是什么呢很简单它是这样定义的1、 本游戏是一个二人游戏;2、 有一堆石子一共有n个3、 两人轮流进行;4、 每走一步可以取走1…m个石子5、 最先取光石子的一方为胜如果游戏的双方使用的都是最优策略请输出哪个人能赢。【输入格式】输入数据首先包含一个正整数C(C100)表示有C组测试数据。每组测试数据占一行包含两个整数n和m1n,m1000n和m的含义见题目描述。【输出格式】如果先走的人能赢请输出“first”否则请输出“second”每个实例的输出占一行。【输入样例】223 24 3【输出样例】firstsecond【数据范围】C1001n,m1000【算法分析】● 巴什博弈Bash game是一种涉及 2 名玩家的双人博弈属于公平组合游戏ICG的典型例子。 博弈中有一堆总数为 n 的物品2 名玩家轮流从中拿取物品每次至少拿 1 件至多拿 m 件不能不拿最终将物品拿完者获胜。1n≤m 时由于一次最少拿一个最多拿 m 个甲可以一次拿完先手赢。2nm1 时无论甲拿走多少个 1~m 个剩下的都多于 1 个且少于或等于 m 个乙都能一次拿走剩余的石子后手取胜。● Bash 博弈胜负判定每次取 1m 个取走最后一个石子的胜1如果 n%(m1) 0即 n 是 m1 的整数倍那么不管甲拿多少记作 k其中 1≤k≤m乙都拿 m1-k 个使剩下的永远是 m1 的整数倍直到最后的 m1 个所以后拿的乙一定赢后手赢。2如果 n%(m1) ! 0即 n 不是 m1 的整数倍还有余数 r那么甲拿走 r 个剩下的是 m1 的倍数这样就转移到了情况1相当于甲乙互换结果是先拿的甲赢先手赢。● 巴什博弈Bash GameSG 值完整推导1游戏规则有一堆 n 个石子两人轮流取石子每次可以取 1~m 颗不能不取取走最后一颗石子者获胜。2定义SG(x) 表示剩余石子数为 x 时的 SG 函数值。3SG 函数定义SG(x) mex{ SG(y) | y 是 x 的一步后继状态 }。其中mex(S) 表示集合 S 中最小的非负整数。一步后继状态从 x 拿走 k1≤k≤m颗石子到达状态 x - k。4边界条件x0没有石子是必败态当前玩家无操作可做。没有后继状态后继集合为空集 ∅。SG(0)mex(∅)0。5计算小例子找规律设 m3每次可取 1, 2, 3 颗x1后继为 1-10后继 SG 集合为 {SG(0)}{0}则得 SG(1)mex{0}1 x2后继为 2-112-20后继 SG 集合为 {SG(1),SG(0)}{1,0}则得 SG(2)mex{0,1}2 x3后继为 3-123-213-30后继 SG 集合为 {SG(2),SG(1),SG(0)}{2,1,0}则得 SG(3)mex{0,1,2}3 x4后继为 4-134-224-31后继 SG 集合为 {SG(3),SG(2),SG(1)}{3,2,1}则得 SG(4)mex{1,2,3}0 x5后继为 5-145-235-32后继 SG 集合为 {SG(4),SG(3),SG(2)}{0,3,2}。则得 SG(5)mex{0,2,3}1 x6后继为 6-156-246-33后继 SG 集合为 {SG(5),SG(4),SG(3)}{1,0,3}。则得 SG(6)mex{0,1,3}2 x7后继为 7-167-257-34后继 SG 集合为 {SG(6),SG(5),SG(4)}{2,1,0}。则得 SG(7)mex{0,1,2}3 x8后继为 8-178-268-35后继 SG 集合为 {SG(7),SG(6),SG(5)}{3,2,1}。则得 SG(8)mex{1,2,3}0 观察规律 (m3)SG(0)0SG(1)1SG(2)2SG(3)3SG(4)0SG(5)1G(6)2SG(7)3SG(8)0…。 猜想一般式SG(n)n mod (m1)。证明略。【算法代码一SG函数写法】注意当n10^4时如下 SG 函数写法的代码是安全的。否则极易触发 Segmentation Fault 及 TLE。#include iostream #include cstring using namespace std; const int N1e35; int sg[N]; bool st[N]; void SG(int n,int m) { sg[0]0; for(int i1; in; i) { memset(st,0,sizeof st); for(int j1; jm ji; j) { st[sg[i-j]]true; } int mex0; while(st[mex]) mex; sg[i]mex; } } int main() { int T; cinT; while(T--) { int n,m; cinnm; SG(n,m); if(sg[n]!0) coutfirst\n; else coutsecond\n; } return 0; } /* in: 2 23 2 4 3 out: first second */【算法代码二非SG函数写法】#include iostream using namespace std; int main() { int T; cinT; while(T--) { int n,m; cinnm; if(n%(m1)0) { coutsecond\n; } else coutfirst\n; } return 0; } /* in: 2 23 2 4 3 out: first second */【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/163572528https://blog.csdn.net/hnjzsyjyj/article/details/158802453
