国家集训队2009论文集组合游戏略述——浅谈
- 格式：pdf
- 大小：616.94 KB
- 文档页数：24
文档推荐
-
组合游戏略述——浅谈SG游戏的若干拓展及变形页数:48
-
国家集训队论文分类整理页数:5
-
组合游戏略述——浅谈SG游戏的若干拓展及变形页数:34
-
国家集训队2009论文集组合游戏略述——浅谈页数:24
下载文档原格式
合集下载
NOI国家集训队论文分类(至2008)(摘抄自C博客)
摘抄自C博客组合数学计数与统计2001 - 符文杰：《Pólya原理及其应用》2003 - 许智磊：《浅谈补集转化思想在统计问题中的应用》2007 - 周冬：《生成树的计数及其应用》2008 - 陈瑜希《Pólya计数法的应用》数位问题2009 - 高逸涵《数位计数问题解法研究》2009 - 刘聪《浅谈数位类统计问题》动态统计2004 - 薛矛：《解决动态统计问题的两把利刃》2007 - 余江伟：《如何解决动态统计问题》博弈2002 - 张一飞：《由感性认识到理性认识——透析一类搏弈游戏的解答过程》2007 - 王晓珂：《解析一类组合游戏》2009 - 曹钦翔《从“k倍动态减法游戏”出发探究一类组合游戏问题》2009 - 方展鹏《浅谈如何解决不平等博弈问题》2009 - 贾志豪《组合游戏略述——浅谈SG游戏的若干拓展及变形》母函数2009 - 毛杰明《母函数的性质及应用》拟阵2007 - 刘雨辰：《对拟阵的初步研究》线性规划2007 - 李宇骞：《浅谈信息学竞赛中的线性规划——简洁高效的单纯形法实现与应用》置换群2005 - 潘震皓：《置换群快速幂运算研究与探讨》问答交互2003 - 高正宇：《答案只有一个——浅谈问答式交互问题》猜数问题2003 - 张宁：《猜数问题的研究:<聪明的学生>一题的推广》2006 - 龙凡：《一类猜数问题的研究》数据结构数据结构2005 - 何林：《数据关系的简化》2006 - 朱晨光：《基本数据结构在信息学竞赛中的应用》2007 - 何森：《浅谈数据的合理组织》2008 - 曹钦翔《数据结构的提炼与压缩》结构联合2001 - 高寒蕊：《从圆桌问题谈数据结构的综合运用》2005 - 黄刚：《数据结构的联合》块状链表2005 - 蒋炎岩：《数据结构的联合——块状链表》2008 - 苏煜《对块状链表的一点研究》动态树2006 - 陈首元：《维护森林连通性——动态树》2007 - 袁昕颢：《动态树及其应用》左偏树2005 - 黄源河：《左偏树的特点及其应用》跳表2005 - 魏冉：《让算法的效率“跳起来”！——浅谈“跳跃表”的相关操作及其应用》2009 - 李骥扬《线段跳表——跳表的一个拓展》SBT2007 - 陈启峰：《Size Balance Tree》线段树2004 - 林涛：《线段树的应用》单调队列2006 - 汤泽：《浅析队列在一类单调性问题中的应用》哈希表2005 - 李羽修：《Hash函数的设计优化》2007 - 杨弋：《Hash在信息学竞赛中的一类应用》Splay2004 - 杨思雨：《伸展树的基本操作与应用》图论图论2005 - 任恺：《图论的基本思想及方法》模型建立2004 - 黄源河：《浅谈图论模型的建立与应用》2004 - 肖天：《“分层图思想”及其在信息学竞赛中的应用》网络流2001 - 江鹏：《从一道题目的解法试谈网络流的构造与算法》2002 - 金恺：《浅谈网络流算法的应用》2007 - 胡伯涛：《最小割模型在信息学竞赛中的应用》2007 - 王欣上：《浅谈基于分层思想的网络流算法》2008 - 周冬《两极相通——浅析最大—最小定理在信息学竞赛中的应用》最短路2006 - 余远铭：《最短路算法及其应用》2008 - 吕子鉷《浅谈最短径路问题中的分层思想》2009 - 姜碧野《SPFA算法的优化及应用》欧拉路2007 - 仇荣琦：《欧拉回路性质与应用探究》差分约束系统2006 - 冯威：《数与图的完美结合——浅析差分约束系统》平面图2003 - 刘才良：《平面图在信息学中的应用》2007 - 古楠：《平面嵌入》2-SAT2003 - 伍昱：《由对称性解2-SAT问题》最小生成树2004 - 吴景岳：《最小生成树算法及其应用》2004 - 汪汀：《最小生成树问题的拓展》二分图2005 - 王俊：《浅析二分图匹配在信息学竞赛中的应用》Voronoi图2006 - 王栋：《浅析平面Voronoi图的构造及应用》偶图2002 - 孙方成：《偶图的算法及应用》树树2002 - 周文超：《树结构在程序设计中的运用》2005 - 栗师：《树的乐园——一些与树有关的题目》路径问题2009 - 漆子超《分治算法在树的路径问题中的应用》最近公共祖先2007 - 郭华阳：《RMQ与LCA问题》划分问题2004 - 贝小辉：《浅析树的划分问题》数论欧几里得算法2009 - 金斌《欧几里得算法的应用》同余方程2003 - 姜尚仆：《模线性方程的应用——用数论方法解决整数问题》搜索搜索2001 - 骆骥：《由“汽车问题”浅谈深度搜索的一个方面——搜索对象与策略的重要性》2002 - 王知昆：《搜索顺序的选择》2005 - 汪汀：《参数搜索的应用》启发式2009 - 周而进《浅谈估价函数在信息学竞赛中的应用》优化2003 - 金恺：《探寻深度优先搜索中的优化技巧——从正方形剖分问题谈起》2003 - 刘一鸣：《一类搜索的优化思想——数据有序化》2006 - 黄晓愉：《深度优先搜索问题的优化技巧》背包问题2009 - 徐持衡《浅谈几类背包题》匹配2004 - 楼天城：《匹配算法在搜索问题中的巧用》概率概率2009 - 梅诗珂《信息学竞赛中概率问题求解初探》数学期望2009 - 汤可因《浅析竞赛中一类数学期望问题的解决方法》字符串字符串2003 - 周源：《浅析“最小表示法”思想在字符串循环同构问题中的应用》多串匹配2004 - 朱泽园：《多串匹配算法及其启示》2006 - 王赟：《Trie图的构建、活用与改进》2009 - 董华星《浅析字母树在信息学竞赛中的应用》后缀数组2004 - 许智磊：《后缀数组》2009 - 罗穗骞《后缀数组——处理字符串的有力工具》字符串匹配2003 - 饶向荣：《病毒的DNA———剖析一道字符匹配问题解析过程》2003 - 林希德：《求最大重复子串》动态规划动态规划2001 - 俞玮：《基本动态规划问题的扩展》2006 - 黄劲松：《贪婪的动态规划》2009 - 徐源盛《对一类动态规划问题的研究》状态压缩2008 - 陈丹琦《基于连通性状态压缩的动态规划问题》状态设计2008 - 刘弈《浅谈信息学中状态的合理设计与应用》树形DP2007 - 陈瑜希：《多角度思考创造性思维——运用树型动态规划解题的思路和方法探析》优化2001 - 毛子青：《动态规划算法的优化技巧》2003 - 项荣璟：《充分利用问题性质——例析动态规划的“个性化”优化》2004 - 朱晨光：《优化，再优化！——从《鹰蛋》一题浅析对动态规划算法的优化》2007 - 杨哲：《凸完全单调性的加强与应用》计算几何立体几何2003 - 陆可昱：《长方体体积并》2008 - 高亦陶《从立体几何问题看降低编程复杂度》计算几何思想2004 - 金恺：《极限法——解决几何最优化问题的捷径》2008 - 程芃祺《计算几何中的二分思想》2008 - 顾研《浅谈随机化思想在几何问题中的应用》圆2007 - 高逸涵：《与圆有关的离散化》半平面交2002 - 李澎煦：《半平面交的算法及其应用》2006 - 朱泽园：《半平面交的新算法及其实用价值》矩阵矩阵2008 - 俞华程《矩阵乘法在信息学中的应用》高斯消元2002 - 何江舟：《用高斯消元法解线性方程组》数学方法数学思想2002 - 何林：《猜想及其应用》2003 - 邵烜程：《数学思想助你一臂之力》数学归纳法2009 - 张昆玮《数学归纳法与解题之道》多项式2002 - 张家琳：《多项式乘法》数形结合2004 - 周源：《浅谈数形结合思想在信息学竞赛中的应用》黄金分割2005 - 杨思雨：《美，无处不在——浅谈“黄金分割”和信息学的联系》其他算法遗传算法2002 - 张宁：《遗传算法的特点及其应用》2005 - 钱自强：《关于遗传算法应用的分析与研究》信息论2003 - 侯启明：《信息论在信息学竞赛中的简单应用》染色与构造2002 - 杨旻旻：《构造法——解题的最短路径》2003 - 方奇：《染色法和构造法在棋盘上的应用》一类问题区间2008 - 周小博《浅谈信息学竞赛中的区间问题》序2005 - 龙凡：《序的应用》系2006 - 汪晔：《信息学中的参考系与坐标系》物理问题2008 - 方戈《浅析信息学竞赛中一类与物理有关的问题》编码与译码2008 - 周梦宇《码之道—浅谈信息学竞赛中的编码与译码问题》对策问题2002 - 骆骥：《浅析解“对策问题”的两种思路》优化算法优化2002 - 孙林春：《让我们做得更好——从解法谈程序优化》2004 - 胡伟栋：《减少冗余与算法优化》2005 - 杨弋：《从<小H的小屋>的解法谈算法的优化》2006 - 贾由：《由图论算法浅析算法优化》程序优化2006 - 周以苏：《论反汇编在时间常数优化中的应用》2009 - 骆可强《论程序底层优化的一些方法与技巧》语言C++2004 - 韩文弢：《论C++语言在信息学竞赛中的应用》策略策略2004 - 李锐喆：《细节——不可忽视的要素》2005 - 朱泽园：《回到起点——一种突破性思维》2006 - 陈启峰：《“约制、放宽”方法在解题中的应用》2006 - 李天翼：《从特殊情况考虑》2007 - 陈雪：《问题中的变与不变》2008 - 肖汉骏《例谈信息学竞赛分析中的“深”与“广”》倍增2005 - 朱晨光：《浅析倍增思想在信息学竞赛中的应用》二分2002 - 李睿：《二分法与统计问题》2002 - 许智磊：《二分，再二分！——从Mobiles(IOI2001)一题看多重二分》2005 - 杨俊：《二分策略在信息学竞赛中的应用》调整2006 - 唐文斌：《“调整”思想在信息学中的应用》随机化2007 - 刘家骅：《浅谈随机化在信息学竞赛中的应用》非完美算法2005 - 胡伟栋：《浅析非完美算法在信息学竞赛中的应用》2008 - 任一恒《非完美算法初探》提交答案题2003 - 雷环中：《结果提交类问题》守恒思想2004 - 何林：《信息学中守恒法的应用》极限法2003 - 王知昆：《浅谈用极大化思想解决最大子矩形问题》贪心2008 - 高逸涵《部分贪心思想在信息学竞赛中的应用》压缩法2005 - 周源：《压去冗余缩得精华——浅谈信息学竞赛中的“压缩法”》逆向思维2005 - 唐文斌：《正难则反——浅谈逆向思维在解题中的应用》穷举2004 - 鬲融：《浅谈特殊穷举思想的应用》目标转换2002 - 戴德承：《退一步海阔天空——“目标转化思想”的若干应用》2004 - 栗师：《转化目标在解题中的应用》类比2006 - 周戈林：《浅谈类比思想》分割与合并2006 - 俞鑫：《棋盘中的棋盘——浅谈棋盘的分割思想》2007 - 杨沐：《浅析信息学中的“分”与“合”》平衡思想2008 - 郑暾《平衡规划——浅析一类平衡思想的应用》。
组合游戏略述——浅谈SG游戏的若干拓展及变形
策略
将偶环删去，将奇环替换成一条边！！！ 将偶环删去，将奇环替换成一条边！！！
2011-3-11
第25页 25页
石家庄二中 贾志豪
Cutting Edges游戏
环的处理成为关键 惊人发现， 惊人发现，
任何奇环的SG值为 任何奇环的 值为1 值为 任何偶环的SG值为 值为0 任何偶环的 值为
策略
将偶环删去，将奇环替换成一条边！！！ 将偶环删去，将奇环替换成一条边！！！
Cutting Edges游戏
证明猜想（数学归纳法） 证明猜想（数学归纳法）
以树中节点个数作为阶段； 以树中节点个数作为阶段； 一个节点和两个节点显然成立； 一个节点和两个节点显然成立； 假设N个节点时成立 个节点时成立， 假设 个节点时成立，
情况一： 情况一：若去掉与根节点相连的边 情况二： 情况二：若去掉G’中的边
G’ G’
根节点
定理： 定理：SG(G)=SG(G’)+1
根节点
中间节点
至多有N 至多有N个点
由归纳假设
至多有N 至多有N-1个点
SG值为 到SG( G’ )-1， 值为0到 值为 ， 取不到SG( G’ ) 取不到 2011-3-11
SG值为 到SG(G’ )，取不 值为1到 值为 ， ’ )+1 到SG(G石家庄二中 贾志豪 15页 第15页
Cutting Edges游戏
环的处理成为关键 惊人发现， 惊人发现，
任何奇环的SG值为 任何奇环的 值为1 值为 任何偶环的SG值为 值为0 任何偶环的 值为
根节点
2011-3-11 第23页 23页
根节点
石家庄二中 贾志豪
Cutting Edges游戏
国家集训队2009论文集信息学竞赛中概率问题
年的NOI中都出现了与概率有关 在05,06,08年的 , , 年的 中都出现了与概率有关 的试题
2 22
全文总览
样本空间 连续型随机变量 随机变量 离散型随机变量
SPOJ RNG SGU Random Shooting SRM 349 LastMarble UVA Randomness
3 22
要用到的定义
1 fi ( [x-Ri, j-Ri+1]x ) = ∫x R i R f i 1 ( t )dt [j-Ri+1,j] [j,x] i
x
P
P
f i1 (t )
f i (x)
19 22
j-Ri j-Ri+1
j j+1
t
j
j+1
x
本题总结
在解决本题的过程中,我们遇到了这样的困难: 在解决本题的过程中,我们遇到了这样的困难: N个随机变量代表着 维空间,较为抽象 个随机变量代表着N维空间 个随机变量代表着 维空间, 两个解法都从N较小的情况开始分析 较小的情况开始分析, 两个解法都从 较小的情况开始分析,发现规律
23 22
用归纳法, 用归纳法,当N=1时,V((0,+∞),x) = x显然 时 显然 符合结论. 符合结论. 设当N=2,3,…,k-1时都有结论成立,那么 时都有结论成立, 设当 时都有结论成立 N=k时,V([0,+∞), [0,+∞),…, [0,+∞),x)就是 时 就是 一个k维锥体的 维体积, 维锥体的k维体积 一个 维锥体的 维体积,椎体的底面面积 是 ( kx 1)! 同时我们知道体积就是截面面积的积分值, 同时我们知道体积就是截面面积的积分值, 而对与锥体的顶点距离为h的截面而言 的截面而言, 而对与锥体的顶点距离为 的截面而言,其 截面面积 (kx 1)! ( h ) 为,所以 所以 x x h 1 x x ( ) dh= ( 0) = V([0,+∞), [0,+∞),…, [0,+∞),x) = ∫ (k 1)! x (k 1)! k k! ■
2 22
全文总览
样本空间 连续型随机变量 随机变量 离散型随机变量
SPOJ RNG SGU Random Shooting SRM 349 LastMarble UVA Randomness
3 22
要用到的定义
1 fi ( [x-Ri, j-Ri+1]x ) = ∫x R i R f i 1 ( t )dt [j-Ri+1,j] [j,x] i
x
P
P
f i1 (t )
f i (x)
19 22
j-Ri j-Ri+1
j j+1
t
j
j+1
x
本题总结
在解决本题的过程中,我们遇到了这样的困难: 在解决本题的过程中,我们遇到了这样的困难: N个随机变量代表着 维空间,较为抽象 个随机变量代表着N维空间 个随机变量代表着 维空间, 两个解法都从N较小的情况开始分析 较小的情况开始分析, 两个解法都从 较小的情况开始分析,发现规律
23 22
用归纳法, 用归纳法,当N=1时,V((0,+∞),x) = x显然 时 显然 符合结论. 符合结论. 设当N=2,3,…,k-1时都有结论成立,那么 时都有结论成立, 设当 时都有结论成立 N=k时,V([0,+∞), [0,+∞),…, [0,+∞),x)就是 时 就是 一个k维锥体的 维体积, 维锥体的k维体积 一个 维锥体的 维体积,椎体的底面面积 是 ( kx 1)! 同时我们知道体积就是截面面积的积分值, 同时我们知道体积就是截面面积的积分值, 而对与锥体的顶点距离为h的截面而言 的截面而言, 而对与锥体的顶点距离为 的截面而言,其 截面面积 (kx 1)! ( h ) 为,所以 所以 x x h 1 x x ( ) dh= ( 0) = V([0,+∞), [0,+∞),…, [0,+∞),x) = ∫ (k 1)! x (k 1)! k k! ■
算法合集之《组合游戏略述——浅谈SG游戏的若干拓展及变形》
对“最有利”的解释：本文所说的最有利，是指对于当前要做出决 策的游戏者，如果他存在一种决策，使得后手进入到一个无论怎样做出 决策都一定会输的的状态，那么结局一定是当前的游戏者胜！
中国有句古话——“智者千虑，必有一失”，而组合游戏中的游戏者 却可以做到“运筹帷幄，决胜千里”。不得不说，正是组合游戏中的“智 者”吸引着我们去探索、发觉组合游戏中的魅力！
1.2 组合游戏中状态空间向图的转化
我们可以将组合游戏中的每一个状态抽象成图中的一个点，将每一 步决策抽象成图中的一条边。我们将这个图称为该组合游戏的游戏图。
这样，对于组合游戏中的每一次对弈，我们都可以将其抽象成游戏 图中的一条从某一顶点到出度为 0 的点的路径。
组合游戏向图的转化，并不单单只是为了寻找一种对应关系，它可
1《由感性认识到理性认识——透析一类搏弈游戏的解答过程 》，张一飞，国家集训队 2002 论文 2《解析一类组合游戏》，.王晓珂，国家集训队 2007 论文
第 1 页 共 24 页
IOI2009 中国国家集训队论文
贾志豪 石家庄二中
每一个模型都有详细的证明。大多数人在学习信息学时存在的问题是 “知其然，不知其所以然”，因为大多数的比赛模式是只要求结果而不 要求过程。但这会使我们对一个事物“只知表皮，不知深髓”，如果将 一个我们知道的问题稍加变形的话，我们可能就不会了。这个问题在组 合游戏中体现得尤其突出。因此笔者对于文中的每一个定理都给出了证 明，希望读者对文中的思想“知其然，知其所以然”。
显然不是！！！
因为我们不光要考虑算法的正确性，还要考虑算法的时空开销，而 上述方法显然没有考虑算法的时空开销，上述方法的瓶颈在于没有充分 利用 SG-组合游戏问题的特殊性质。
我们先引出游戏的和的概念。
中国有句古话——“智者千虑，必有一失”，而组合游戏中的游戏者 却可以做到“运筹帷幄，决胜千里”。不得不说，正是组合游戏中的“智 者”吸引着我们去探索、发觉组合游戏中的魅力！
1.2 组合游戏中状态空间向图的转化
我们可以将组合游戏中的每一个状态抽象成图中的一个点，将每一 步决策抽象成图中的一条边。我们将这个图称为该组合游戏的游戏图。
这样，对于组合游戏中的每一次对弈，我们都可以将其抽象成游戏 图中的一条从某一顶点到出度为 0 的点的路径。
组合游戏向图的转化，并不单单只是为了寻找一种对应关系，它可
1《由感性认识到理性认识——透析一类搏弈游戏的解答过程 》，张一飞，国家集训队 2002 论文 2《解析一类组合游戏》，.王晓珂，国家集训队 2007 论文
第 1 页 共 24 页
IOI2009 中国国家集训队论文
贾志豪 石家庄二中
每一个模型都有详细的证明。大多数人在学习信息学时存在的问题是 “知其然，不知其所以然”，因为大多数的比赛模式是只要求结果而不 要求过程。但这会使我们对一个事物“只知表皮，不知深髓”，如果将 一个我们知道的问题稍加变形的话，我们可能就不会了。这个问题在组 合游戏中体现得尤其突出。因此笔者对于文中的每一个定理都给出了证 明，希望读者对文中的思想“知其然，知其所以然”。
显然不是！！！
因为我们不光要考虑算法的正确性，还要考虑算法的时空开销，而 上述方法显然没有考虑算法的时空开销，上述方法的瓶颈在于没有充分 利用 SG-组合游戏问题的特殊性质。
我们先引出游戏的和的概念。
从“k倍动态减法游戏”出发探究一类组合游戏问题
1(if _(m, n) _ is _ an _ N position ) NP(m,n)= ，NP(m,n)关于 n 单调不减。 0(if _(m, n) _ is _ a _ P position )
这是因为若正整数 m0、n0 使得 NP(m0,n0)=1，则对于任意 n>n0,m=m0 都有 NP(m,n)=1。这是因为，状态(m0,n0)时玩家可以完成的操作，在状态(m,n)也允许 操作（这利用了 n>n0） ，且到达相同的状态(这利用 m=m0)。
NOI2009 冬令营论文
从“k 倍动态减法游戏”出发探究一类组合游戏问题
摘
要
组合游戏是指，信息完全轮流操作的双人游戏。本文将从一个游戏——k 倍 动态减法游戏（k-based dynamic subtraction game）的解答出发，讨论游戏中的一 个重要分支——组合游戏， 并探讨解决这一类的问题的高效方法。探索的过程力 求兼顾游戏论中的普遍真理以及问题的独特性质。 作为一篇信息学的论文， 本文将着重讨论与组合游戏有关的相关算法和这些 算法时间复杂性分析， 而不是游戏论中的一些经典的理论、典型的游戏实例或者 一些存在性的证明。 “k 倍动态减法游戏”在 k 为一般正实数的情况，在 2002 年的国家集训队 论文中已经给出 O(S3)的算法，本文将在第 4．1 节给出一个优化到 O(S)的算法。 “Nim 积”运算是利用 SG 函数解决游戏论问题的必要工具之一。本文将在 第 4．4．5 节给出一个 O(log2x)的计算“Nim 积”的算法。 2008 年的 BOI（Baltic Olympiad in Informatics）中 knight 一题就是游戏论问 题，官方解答给出了 O(n3)的算法，但没有给出算法时间复杂度的证明。本文在 第 5 章提出了对这个 O(n3)的上界的质疑，并举出了质疑的确实依据，举出反例 证明了官方解答时间复杂度估计的错误之处。 同时， 本文经过对算法进一步优化， 得到了一个 O(n2)的算法。 上面这些内容都是原创的独立研究成果。
这是因为若正整数 m0、n0 使得 NP(m0,n0)=1，则对于任意 n>n0,m=m0 都有 NP(m,n)=1。这是因为，状态(m0,n0)时玩家可以完成的操作，在状态(m,n)也允许 操作（这利用了 n>n0） ，且到达相同的状态(这利用 m=m0)。
NOI2009 冬令营论文
从“k 倍动态减法游戏”出发探究一类组合游戏问题
摘
要
组合游戏是指，信息完全轮流操作的双人游戏。本文将从一个游戏——k 倍 动态减法游戏（k-based dynamic subtraction game）的解答出发，讨论游戏中的一 个重要分支——组合游戏， 并探讨解决这一类的问题的高效方法。探索的过程力 求兼顾游戏论中的普遍真理以及问题的独特性质。 作为一篇信息学的论文， 本文将着重讨论与组合游戏有关的相关算法和这些 算法时间复杂性分析， 而不是游戏论中的一些经典的理论、典型的游戏实例或者 一些存在性的证明。 “k 倍动态减法游戏”在 k 为一般正实数的情况，在 2002 年的国家集训队 论文中已经给出 O(S3)的算法，本文将在第 4．1 节给出一个优化到 O(S)的算法。 “Nim 积”运算是利用 SG 函数解决游戏论问题的必要工具之一。本文将在 第 4．4．5 节给出一个 O(log2x)的计算“Nim 积”的算法。 2008 年的 BOI（Baltic Olympiad in Informatics）中 knight 一题就是游戏论问 题，官方解答给出了 O(n3)的算法，但没有给出算法时间复杂度的证明。本文在 第 5 章提出了对这个 O(n3)的上界的质疑，并举出了质疑的确实依据，举出反例 证明了官方解答时间复杂度估计的错误之处。 同时， 本文经过对算法进一步优化， 得到了一个 O(n2)的算法。 上面这些内容都是原创的独立研究成果。
算法合集之《数学归纳法与解题之道》
结构归纳法
结构归纳法是应用在数理逻辑、计算机科学、图论和一些其他数学领域中的一种特殊 化的数学归纳法，一般用来解决非线性问题。通俗地说，如果要证明的一组基于结构的命 题之间有一个“拓扑序”（通常定义为问题的规模），那么我们往往可以从空集出发进行 归纳证明或构造。例如，树形结构上我们每次去掉根将问题规约到几个较小的子问题，图 论算法中每次处理一条边就能不断减小问题的规模……如果对于一个规模足够小的问题我 们能够解决，我们就完美的解决了原问题。 不同于一般的数学归纳法，结构归纳法的正确性依赖于“最小数原理”的推广：假设 存在反例，那一定会有最小的反例，但是运用上述论证减小其规模可得一个反例，它的规 模比最小的反例更小，这样就产生了矛盾。因此假设不成立，结构归纳法是正确的。
基本的定理、概念与方法
第一数学归纳法
P 1 True 任意给定关于自然数的命题 P n ，若 ，那么，命题对所有 * P n P n 1 n N
自然数均成立。 形象地说， 如果把整个自然数集想象成一串多米诺骨牌， P 1 True 这个要求就推倒 了其中的第一块，因此有时被形象地称之为“奠基”；我们通常称为归纳的是其中证明
IOI2009 中国国家集训队论文 数学归纳法与解题之道 张昆玮
3
关于数学归纳法
简短的回顾
数学归纳法原理的发现可以追溯到公元 1494 年意大利数学家 Francesco Maurolico 的著作 Arithmeticorum libri duo。作为皮亚诺公理系统的应用，它自诞生之日就受到广 泛关注。同时，作为应对与正整数相关的问题的一种通用而简洁的处理方法，数学归纳法 在许多算术、逻辑问题的解决中都占有核心地位。即使是一些难于解决的问题，应用数学 归纳法大多可以化简问题描述，理清其本质，为接下来的解答铺平道路。 由于其固有的递归性，构造性和美学价值，数学归纳法是中学课本与学科竞赛中的热 门话题。特别地，信息学竞赛中的算术、逻辑、拓扑、数论以及组合数学相关的问题层出 不穷，我们有理由相信，数学归纳法，以及由数学归纳法衍生的结构归纳法等构造性证明 方法在信息学的算法设计中，同样会有其用武之地。
国家集训队2009论文集浅析字母树在信息学竞
浅析字母树在信息学竞赛中的应用浙江省绍兴市第一中学董华星二〇〇八年十二月目录摘要 (3)关键字 (3)前言 (3)正文 (4)1.预备知识 (4)1.1.试题分析 (4)1.2.结构简介 (5)2.字母树在串的快速检索中的应用 (7)3.字母树在“串”排序方面的应用 (9)4.字母树在减少无效转移方面的应用 (11)5.字母树在最长公共前缀问题的应用 (13)5.1.串的最长公共前缀问题 (13)5.2.数字相关的公共前缀问题 (14)6.拓展思考 (16)6.1.字母树应用的扩展 (16)6.2.字母树的局限 (16)7.总结 (17)参考文献 (17)附录 (18)1.单词查找树 (18)2.感谢名单 (20)感谢 (21)字母树（又叫单词查找树、Trie树，Trie Tree），构造简单，并能很好地处理和“串”相关的检索（Retrieval）问题。
本文从此着手，归纳了笔者的学习经验，详细论述了其在快速查找、排序、优化转移等方面的常见应用，并对其扩展做了提示。
关键字字母树快速检索“串”排序无效转移最长公共前缀问题前言当我们走进图书馆的阅览室寻找书时，会不Array由自主地根据书架上的分类标签寻找自己所喜好的书籍；当打开电脑中的资源管理器时，我们会看到一层一层的目录结构。
它们的存在，方便了我们生活中的一个重要的问题——检索。
在信息学竞赛（Olympiad in Informatics，简称OI）的学习过程中，我们也经常会遇到关于“检索”的问题。
而通常采用的不借助任何数据结构（Data Structure）的的枚举方法，虽然简单易写，但往往存在着效率低下的弊端。
那我们如何才能图一资源管理器通过简单的途径提高算法中的检索效率？接下来笔者将浅析并推荐一种数据结构——字母树，借助它我们便能够很好地处理与“串”相关的检索问题。
1.预备知识为了更深入地让读者了解这种数据结构，本文首先将对其进行一番具体介绍并说明其构造。
国家集训队2009论文集后缀数组——处理字符
后缀数组 罗穗骞
例 10：长度不小于 k 的公共子串的个数(pku3415) ……………23 2．4 多个字符串的相关问题 …………………………………………………23
例 11：不小于 k 个字符串中的最长子串(pku3294) ……………………24 例 12：每个字符串至少出现两次且不重叠的最长子串(spoj220)……24 例 13：出现或反转后出现在每个字符串中的最长子串(pku3294)……24 三、结束语 …………………………………………………………………………25 参考文献 ……………………………………………………………………………25 致谢 …………………………………………………………………………………25
目录
后缀数组 罗穗骞
摘要 …………………………………………………………………………………4 关键字 ………………………………………………………………………………4 正文 …………………………………………………………………………………4 一、后缀数组的实现 …………………………………………………………………4
符 串 r 的 从 第 i 个 字 符 开 始 的 后 缀 表 示 为 Suffix(i) ， 也 就 是 Suffix(i)=r[i..len(r)]。
大小比较：关于字符串的大小比较，是指通常所说的“字典顺序”比较，也 就是对于两个字符串 u、v，令 i 从 1 开始顺次比较 u[i]和 v[i]，如果 u[i]=v[i]则令 i 加 1，否则若 u[i]<v[i]则认为 u<v，u[i]>v[i]则认为 u>v （也就是 v<u），比较结束。如果 i>len(u)或者 i>len(v)仍比较不出结果，那 么 若 len(u)<len(v) 则 认 为 u<v ， 若 len(u)=len(v) 则 认 为 u=v ， 若 len(u)>len(v)则 u>v。
国家集训队2007论文集5.杨沐《浅析信息学中
浅析信息学中的“分”与“合”福建省福州第三中学杨沐目录【摘要】..................................................................... 错误!未定义书签。
【关键字】................................................................. 错误!未定义书签。
【正文】..................................................................... 错误!未定义书签。
一、引言............................................................... 错误!未定义书签。
二、例题分析 ...................................................... 错误!未定义书签。
[例一]牛奶模版 ............................................ 错误!未定义书签。
[例二]树的重建 ............................................ 错误!未定义书签。
[例三]最优序列 ............................................ 错误!未定义书签。
三、总结............................................................... 错误!未定义书签。
【感谢】..................................................................... 错误!未定义书签。
【参考文献】............................................................. 错误!未定义书签。
国家集训队论文：浅谈信息学竞赛中的“0”和“1”
01
树状数组中 的每一个元 素的编号变 成了二制
02
编码，再通过 这些二进制编 码末尾的0的 个数来
03
决定存储什 么信息，假 设节点编号 为x，那么这
04
个节点存储 数据的区间 为2k（其中 k为x二进制
05
末尾0 的个 数）个元素 。
06
又由于每个十进制 数转化成二进制位 的话，1的个数最 多只有O(logN)个， 所以，复杂度只有 O(logN)。
2k：X and –X
具体操作：
1 插入或删除： While
2 查询： While x>0
x<=max do
do
Begin
Begin
C[x]:=c[x]+ delta;
Sum:=sum+ c[x];
X:=x+(x and –x);
X:=x-(x and –x);
End;
End;
单击添加标题
Add a title
•模型转化 Add a title
•01二叉树
例题一： Matrix
有一个M*N的矩阵，每一 个格子中的数是1或0，初 始时为0。有两种操作：
修改一个子矩阵， 将子矩阵中的数字 全部01取反。
查询第x行第y列的 格子中的数字。
01
02
如果给定的是一 个长度为N的一 排格子。
从而达到转十为二，事半功倍的效果！
欢迎提问~
Thank You！
每次询问的时候只 需计算出Sumx就可 以 求出第x个格子被修 改过几次。
查询
01 寻根溯源
02
用上面的方法看 看能否解决原来 的问题。
推而广之
怎么办呢？？？
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
组合游戏略述——浅谈SG游戏的若干拓展及变形石家庄二中贾志豪前言组合游戏是近几年新兴起的博弈游戏，随着张一飞学长关于组合游戏的论文的面世，组合游戏问题开始在国内信息学竞赛这片沃土上生根发芽，与大家一起成长、成熟、成才。
最为马上要离开高中信息学舞台的高三学生，我一直希望能为学弟学妹们留下一些我自己的心得，于是这篇论文应运而生！！！这篇论文的一些思想是我早在一年前节开始构思的，感谢计算机学会为我提供这样一个舞台，能让我的论文为更多的人所知道；同时感谢在我写论文时无私帮助过我的所有人，谢谢你们！！！先介绍一下论文的主要内容：第一章作为论文的理论基础，主要从欣赏的角度引入了SG函数、游戏图、NIM游戏等概念，重点谈我对组合游戏尤其是SG函数的体会、理解；第二章主要介绍了几种不同规则的组合游戏以及相应的应对策略，旨在告诉读者，游戏规则变化之后，我们应该如何去分析新的规则、解决新的模型；第三章主要介绍了几种竞赛中常见的组合模型，并将“她”们成功的转化成了NIM模型。
鉴于这篇论文的内容较多，在这里给读者提供一些阅读建议：第一章由于篇幅原因，并没有给出SG函数、NIM游戏解法的详细证明过程，对于刚刚接触组合游戏的读者，建议先阅读一些关于SG函数的资料（张一飞关于博弈游戏的论文1、王晓柯关于组合游戏的论文2就很不错），然后再从论文的第一章看起，相信你一定会很有收获；第二、三章是论文的重头戏，如题目所言，分别谈SG游戏的拓展和变形，对于钟情于组合游戏的读者，可以重点看一看第三章，相信一定不会让你失望！！！这篇论文主要有两个特点：基本没有例题但处处是例子。
为了让读者更好的理解论文中的思想，笔者在选题目的时候刻意将题目的背景剥掉，只剩下一个“光溜溜”的数学模型，这样读者在阅读论文时，就不必花精力去考虑背景向模型的转化，可以全身心去理解笔者想要传达的思想。
但读者不必去担心没有地方练习，笔者将这几年的自己做过的组合游戏题收录在了论文的附录里。
1《由感性认识到理性认识——透析一类搏弈游戏的解答过程》，张一飞，国家集训队2002论文2《解析一类组合游戏》，.王晓珂，国家集训队2007论文每一个模型都有详细的证明。
大多数人在学习信息学时存在的问题是“知其然，不知其所以然”，因为大多数的比赛模式是只要求结果而不要求过程。
但这会使我们对一个事物“只知表皮，不知深髓”，如果将一个我们知道的问题稍加变形的话，我们可能就不会了。
这个问题在组合游戏中体现得尤其突出。
因此笔者对于文中的每一个定理都给出了证明，希望读者对文中的思想“知其然，知其所以然”。
为了方便大家阅读，我将论文中所有的定理表述做成了“HELLO WORLD”将所有的定义表述做成了“HELLO WORLD”，希望这样的改动能引起大家的注意和兴趣。
目录感谢 (4)Chapter 1 (5)1.1本论文讨论的范围 (5)1.2组合游戏中状态空间向图的转化 (6)1.3简介SG函数 (6)1.4定义NIM-模型 (7)Chapter 2 (9)2.1走完最后一步者输——Anti-SG游戏和SJ定理 (9)2.2可以将一堆石子分成多堆——Multi-SG游戏 (14)2.3每一个可以移动的棋子都要移动——Every-SG游戏 (14)Chapter 3 (18)3.1翻硬币游戏 (18)3.2无向图删边游戏 (19)3.2.1树的删边游戏 (19)3.2.2 Christmas Game(PKU3710) (21)3.2.3 无向图的删边游戏 (23)参考资料 (24)附录 (24)关键字SG函数NIM模型Anti游戏Multi游戏Every游戏翻硬币游戏删边游戏证明拓展感谢谨以此论文献给：●我的初中同班同学，集训队队员，对ppt内容提出宝贵意见的李骥扬同学●我的高中同班同学，集训队队员，给论文指出多处缺点的武森同学●我的学长，北京大学学生，认真修改过我论文ppt的周先达同学●我的学长，复旦大学学生，认真阅读过论文修订版的杨敏达同学●在我生病时送我去医院，认真辅导我信息学的韩日旺老师●在我上高一时及时指出我的缺点，辛勤辅导我信息学的李晶老师●与我交流论文内容的唐文斌、胡伟栋教练向以上所有人表示我最诚挚的谢意！！！谢谢所有在我信息学道路上对我有帮助的人！！！●C hapter 11.1本论文讨论的范围本论文主要讨论一类组合游戏问题的解法，这列问题具有如下特征：●游戏有两个人参与，二者轮流做出决策。
且这两个人的决策都对自己最有利。
●当有一人无法做出决策时游戏结束，无法做出决策的人输。
无论二者如何做出决策，游戏可以在有限步内结束。
●游戏中的同一个状态不可能多次抵达。
且游戏不会有平局出现。
●任意一个游戏者在某一确定状态可以作出的决策集合只与当前的状态有关，而与游戏者无关。
这样一类游戏可以用SG函数解决，我们将其称之为SG-组合游戏。
对“最有利”的解释：本文所说的最有利，是指对于当前要做出决策的游戏者，如果他存在一种决策，使得后手进入到一个无论怎样做出决策都一定会输的的状态，那么结局一定是当前的游戏者胜！中国有句古话——“智者千虑，必有一失”，而组合游戏中的游戏者却可以做到“运筹帷幄，决胜千里”。
不得不说，正是组合游戏中的“智者”吸引着我们去探索、发觉组合游戏中的魅力！1.2组合游戏中状态空间向图的转化我们可以将组合游戏中的每一个状态抽象成图中的一个点，将每一步决策抽象成图中的一条边。
我们将这个图称为该组合游戏的游戏图。
这样，对于组合游戏中的每一次对弈，我们都可以将其抽象成游戏图中的一条从某一顶点到出度为0的点的路径。
组合游戏向图的转化，并不单单只是为了寻找一种对应关系，它可以帮助我们淡化游戏的实际背景，强化游戏的数学模型，更加突出游戏的数学本质！1.3简介SG函数SG函数是对游戏图中每一个节点的评估函数。
它的定义如下：fmexvf=图中有一条从uvu(|){)(的边}到其中，mex（minimal excludant）是定义在整数集合上的操作。
它的自变量是任意整数集合，函数值是不属于该集合的最小自然数。
kkmex∈∉A=∧k|Am in{}}{N事实上，所有的SG-组合游戏都存在相应的游戏图，我们完全可以根据游戏图的拓扑关系来逐一算出每一个状态点的SG函数（事实上我们只需要知道该状态点的SG函数值是否为0）。
这样，我们就可以知道对于某一个状态，是先手必胜局还是先手必败局。
这是不是说明我们已经将SG-组合游戏完满解决了呢？显然不是！！！因为我们不光要考虑算法的正确性，还要考虑算法的时空开销，而上述方法显然没有考虑算法的时空开销，上述方法的瓶颈在于没有充分利用SG-组合游戏问题的特殊性质。
我们先引出游戏的和的概念。
[定义]游戏的和：考虑任意多个同时进行的SG-组合游戏，这些SG-组合游戏的和是这样一个SG-组合游戏，在它进行的过程中，游戏者可以任意挑选其中的一个单一游戏进行决策，最终，没有办法进行决策的人输。
■上述方法在计算K个单一SG-组合游戏的和时，所消耗的时间、空间复杂度是分别计算这K个单一SG-组合游戏所消耗的时间、空间复杂度的乘积。
但如果我们能更好的利用SG-组合游戏的性质的话，我们可以将上一段的最后一字——“积”——改成“和”。
这就是我们继续研究SG-函数的意义，也是这篇论文的意义所在。
最后我们直接给出SG函数的性质：（1）对于任意的局面，如果它的SG值为0，那么它的任何一个后继局面的SG值不为0；（2）对于任意的局面，如果它的SG值不为0，那么它一定有一个后继局面的SG值为0。
1.4定义NIM-模型为了不使读者对本篇论文失去兴趣，我特意将介绍取石子游戏的内容换成小字，对这部分内容已经很熟悉的读者可以直接略过。
取石子游戏即著名的nim游戏，游戏规则如下：⏹桌子上有N堆石子，游戏者轮流取石子。
⏹每次只能从一堆中取出任意数目的石子，但不能不取。
⏹取走最后一个石子者胜。
这道题每一堆石子的SG函数值很显然为该堆石子的数目，根据SG函数的特点，最后所有堆石子的SG函数的和__⊕1=⊕⊕_SGSGnSGtot...SG_2最后，先手胜当且仅当该值为0。
证明从略。
取石子游戏虽然是组合游戏中一道最基础的题目，但是它却代表了一类经典的组合模型。
事实上，每一个简单SG-组合游戏都可以完全等效成一堆数目为K 的石子，其中K为该简单游戏的SG函数值。
这样的等效是充要的。
[定理]在我们每次只能进行一步操作的情况下，对于任何的游戏的和，我们若将其中的任一单一SG-组合游戏换成数目为它的SG值的一堆石子，该单一SG-组合游戏的规则变成取石子游戏的规则（可以任意取，甚至取完），则游戏的和的胜负情况不变。
这是SG函数的基本性质，证明可参阅相关资料。
定理的一个变形是：若只考虑游戏的和，我们可以将其中的任一游戏换成SG值相等的其他游戏，游戏的和的SG函数值不变。
定理告诉我们，在考虑游戏的和时，每一个单一游戏的具体细节是可以被忽略的，我们所关心的只是SG函数值。
所以我们可以将组成它的所有子游戏换成相应数目的一堆石子。
这样，所有的游戏的和都等价成nim游戏。
为了以后论文的方便，我们将以后的所有例题都抽象成NIM-模型。
抽象成NIM-模型后，剩下的问题就是我们所熟悉的nim游戏了。
●C hapter 22.1走完最后一步者输——Anti-SG游戏和SJ定理在谁走完最后一步谁输时，如何判断输赢？刚拿到这个问题，大多数人可能会认为要颠覆传统的SG函数解法，设计新的评估函数。
我们不妨先从最本质的nim游戏寻找突破口。
[定义]（anti-nim游戏）⏹桌子上有N堆石子，游戏者轮流取石子。
⏹每次只能从一堆中取出任意数目的石子，但不能不取。
⏹取走最后一个石子者败。
[结论]先手必胜当且仅当：（1）所有堆的石子数都为1且游戏的SG值为0；（2）有些堆的石子数大于1且游戏的SG值不为0。
[证明]游戏分两种情况：●有N个堆，每个堆只有一个石子。
显然，先手必胜当且仅当N为偶数。
●其他情况。
（1）当SG不为0时若还有至少两堆石子的数目大于1，则先手将SG值变为0即可；若只有一堆石子数大于1，则先手总可以将状态变为有奇数个1。
所以，当SG不为0时先手必胜。
（2）当SG为0时至少有两堆石子的数目大于1，则先手决策完之后，必定至少有一堆的石子数大于1，且SG值不为0，由上段的论证我们可以发现，此时，无论先手如何决策，都只会将游戏带入先手必胜局，所以先手必败。
■上述关于anti-nim游戏的推导只对anti-nim这一简单游戏成立。
因为我们在证明SG函数性质时，用到了这样一个性质SG值为0的局面不一定为终止局面。
所以，上述论证能否推广到所有SG-组合游戏，我们是需要从新给出论证的。
我们现在已经充分了解到了nim游戏与SG函数之间的内在联系，所以我们很自然的会想到下述命题：[命题]先手必胜当且仅当：（1）所有单一游戏的SG值小于2且游戏的SG值为0；（2）存在单一游戏的SG值大于1且游戏的SG值不为0。