国家集训队2009论文集组合游戏略述——浅谈

摘抄自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 - 郑暾《平衡规划——浅析一类平衡思想的应用》。

策略
将偶环删去，将奇环替换成一条边！！！ 将偶环删去，将奇环替换成一条边！！！
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游戏

年的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! ■

对“最有利”的解释：本文所说的最有利，是指对于当前要做出决 策的游戏者，如果他存在一种决策，使得后手进入到一个无论怎样做出 决策都一定会输的的状态，那么结局一定是当前的游戏者胜！
中国有句古话——“智者千虑，必有一失”，而组合游戏中的游戏者 却可以做到“运筹帷幄，决胜千里”。不得不说，正是组合游戏中的“智 者”吸引着我们去探索、发觉组合游戏中的魅力！
1.2 组合游戏中状态空间向图的转化
我们可以将组合游戏中的每一个状态抽象成图中的一个点，将每一 步决策抽象成图中的一条边。我们将这个图称为该组合游戏的游戏图。
这样，对于组合游戏中的每一次对弈，我们都可以将其抽象成游戏 图中的一条从某一顶点到出度为 0 的点的路径。
组合游戏向图的转化，并不单单只是为了寻找一种对应关系，它可
1《由感性认识到理性认识——透析一类搏弈游戏的解答过程 》，张一飞，国家集训队 2002 论文 2《解析一类组合游戏》，.王晓珂，国家集训队 2007 论文
第 1 页 共 24 页
IOI2009 中国国家集训队论文
贾志豪 石家庄二中
每一个模型都有详细的证明。大多数人在学习信息学时存在的问题是 “知其然，不知其所以然”，因为大多数的比赛模式是只要求结果而不 要求过程。但这会使我们对一个事物“只知表皮，不知深髓”，如果将 一个我们知道的问题稍加变形的话，我们可能就不会了。这个问题在组 合游戏中体现得尤其突出。因此笔者对于文中的每一个定理都给出了证 明，希望读者对文中的思想“知其然，知其所以然”。
显然不是！！！
因为我们不光要考虑算法的正确性，还要考虑算法的时空开销，而 上述方法显然没有考虑算法的时空开销，上述方法的瓶颈在于没有充分 利用 SG-组合游戏问题的特殊性质。
我们先引出游戏的和的概念。

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)的算法。 上面这些内容都是原创的独立研究成果。

结构归纳法
结构归纳法是应用在数理逻辑、计算机科学、图论和一些其他数学领域中的一种特殊 化的数学归纳法，一般用来解决非线性问题。通俗地说，如果要证明的一组基于结构的命 题之间有一个“拓扑序”（通常定义为问题的规模），那么我们往往可以从空集出发进行 归纳证明或构造。例如，树形结构上我们每次去掉根将问题规约到几个较小的子问题，图 论算法中每次处理一条边就能不断减小问题的规模……如果对于一个规模足够小的问题我 们能够解决，我们就完美的解决了原问题。 不同于一般的数学归纳法，结构归纳法的正确性依赖于“最小数原理”的推广：假设 存在反例，那一定会有最小的反例，但是运用上述论证减小其规模可得一个反例，它的规 模比最小的反例更小，这样就产生了矛盾。因此假设不成立，结构归纳法是正确的。
基本的定理、概念与方法
第一数学归纳法
P 1 True 任意给定关于自然数的命题 P n ，若 ，那么，命题对所有 * P n P n 1 n N
自然数均成立。 形象地说， 如果把整个自然数集想象成一串多米诺骨牌， P 1 True 这个要求就推倒 了其中的第一块，因此有时被形象地称之为“奠基”；我们通常称为归纳的是其中证明
IOI2009 中国国家集训队论文 数学归纳法与解题之道 张昆玮
3
关于数学归纳法
简短的回顾
数学归纳法原理的发现可以追溯到公元 1494 年意大利数学家 Francesco Maurolico 的著作 Arithmeticorum libri duo。作为皮亚诺公理系统的应用，它自诞生之日就受到广 泛关注。同时，作为应对与正整数相关的问题的一种通用而简洁的处理方法，数学归纳法 在许多算术、逻辑问题的解决中都占有核心地位。即使是一些难于解决的问题，应用数学 归纳法大多可以化简问题描述，理清其本质，为接下来的解答铺平道路。 由于其固有的递归性，构造性和美学价值，数学归纳法是中学课本与学科竞赛中的热 门话题。特别地，信息学竞赛中的算术、逻辑、拓扑、数论以及组合数学相关的问题层出 不穷，我们有理由相信，数学归纳法，以及由数学归纳法衍生的结构归纳法等构造性证明 方法在信息学的算法设计中，同样会有其用武之地。

浅析字母树在信息学竞赛中的应用浙江省绍兴市第一中学董华星二〇〇八年十二月目录摘要 (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.预备知识为了更深入地让读者了解这种数据结构，本文首先将对其进行一番具体介绍并说明其构造。

后缀数组 罗穗骞
例 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。

浅析信息学中的“分”与“合”福建省福州第三中学杨沐目录【摘要】..................................................................... 错误!未定义书签。

【关键字】................................................................. 错误!未定义书签。

【正文】..................................................................... 错误!未定义书签。

一、引言............................................................... 错误!未定义书签。

二、例题分析 ...................................................... 错误!未定义书签。

[例一]牛奶模版 ............................................ 错误!未定义书签。

[例二]树的重建 ............................................ 错误!未定义书签。

[例三]最优序列 ............................................ 错误!未定义书签。

三、总结............................................................... 错误!未定义书签。

【感谢】..................................................................... 错误!未定义书签。

【参考文献】............................................................. 错误!未定义书签。

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
用上面的方法看 看能否解决原来 的问题。
推而广之
怎么办呢？？？

浅谈几类背包题浙江省温州中学徐持衡指导老师：舒春平2008年12月目录摘要 (3)关键字 (3)正文 (4)一、引言 (4)二、背包的基本变换 (5)①完全背包 (5)②多次背包 (5)③单调队列优化☆ (6)三、其他几类背包问题 (8)①树形依赖背包（获取学分）☆ (8)②PKU3093☆ (11)四、总结 (12)附录 (13)参考文献 (13)文中原题 (13)摘要背包问题作为一个经典问题在动态规划中是很基础的一个部分，然而以0-1背包问题为原题，衍生转变出的各类题目，可以说是千变万化，当然解法也各有不同，如此就有了继续探究的价值。

本文就4道背包变化的题做一些探讨研究，提出本人的一些做法，希望能起到抛砖引玉的作用。

关键字动态规划背包优化正文一、引言背包问题是运筹学中的一个经典的优化难题，是一个NP-完全问题，但其有着广泛的实际应用背景，是从生活中一个常见的问题出发展开的：一个背包，和很多件物品，要在背包中放一些物品，以达到一定的目标。

在信息学中，把所有的数据都量化处理后，得到这样的一个问题：0-1 背包问题：给定n 件物品和一个背包。

物品i的价值是W i，其体积为V i，背包的容量为C。

可以任意选择装入背包中的物品，求装入背包中物品的最大总价值。

在选择装入背包的物品时，对每件物品i ，要么装入背包，要么不装入背包。

不能将物品i 多次装入背包，也不能只装入部分物品i （分割物品i）。

因此，该问题称为0-1 背包问题。

用于求解0-1背包问题的方法主要有回溯算法、贪婪算法、遗传算法、禁忌搜索算法、模拟退火算法等。

在高中阶段，我们所谓的经典0-1背包问题，保证了所有量化后的数据均为正整数，即是一个特殊的整数规划问题，本文中如无特殊说明均以此为前提。

其经典的O(n*C)动规解法是：状态是在前i件物品中，选取若干件物品其体积总和不大于j，所能获得的最大价值为F i[j]，当前的决策是第i件物品放或者不放，最终得到转移方程：F i[j] = F i-1[j] (V i>j>=0)F i[j] = max{ F i-1[j] , F i-1[j-V i]+W i } (C>=j>=V i)其中由于F i只与F i-1有关，可以用滚动数组来节省程序的空间复杂度。

来回顾一下这次优化，他解决了在初版程序代码中出现的重复寻址的问题，而获得了 期望中效率的提升，从本质上说仍然属于逻辑层面的优化。这次优化是在 C 语言层面编写， 也能够在 C 语言层面进行解释的。
第二次优化
继续前面的思路，很难再想出什么有效的优化了，这就是我们的终点吗？ 其实游戏才刚刚开始，下面给出第二个优化：
下面是本文所有程序都会用到的计时函数的 C 代码： #define ull uns ret; __asm__ __volatile__ ("rdtsc\n\t":"=A"(ret):); return ret; }
第一次优化
开始着手寻找程序可优化之处，首先发现'a[i]'被提及了两次，重复计算地址在这个 小循环中的开销也是不可忽略的，那么第一版的优化我们尝试来进行普通的循环和寻址的优 化：
为什么要学习底层优化 在 OI 竞赛中，算法是考察的重点。底层实现看起来并不重要，确实提升空间也相对较 小，但当我们设计的算法有一些先天缺陷时，或许对底层做细致的优化能对我们有很大的帮 助，在后文中会展示一些实际的例子。 在竞赛之外，学习底层的东西，能让我们更深入地认识眼前的机器，即使在使用高级 语言书写程序时，脑海中也会自然投射出底层发生的事情，从而能够写出质量更高的代码。 在这篇论文前期准备、实验研究、总结规律到最终成文的过程中，我学到了太多的东 西，这些东西在我们平时为 OI 竞赛编程的过程中是很难看到的，而我也相信，这些东西在 为大家所广泛认识之后，同样能够服务于竞赛，实际地提升成绩。
编译器版本: gcc 4.3.2
汇编器版本: GNU assembler 2.18.93.20081009
连接器版本: GNU ld 2.18.93.20081009

组合数学论文1700字_组合数学毕业论文范文模板组合数学论文1700字(一)：浅谈“组合数学”的研究性教学方法【摘要】组合数学是计算机相关专业的一门专业课程，其内容抽象，形式化程度高，如何提高该课程的教学水平，使学生真正学懂并不断提高逻辑思维和抽象思维能力是该课程教学研究和探讨的重点.【关键词】研究性教学；组合数学；启发式学习伴随着信息时代的来临，特别是计算机科学技术的迅猛发展，计算机相关专业课程的学习方法研究成为热点.组合数学作为一门应用性较强的数学分支，对于高校特别是计算机相关专业学生，培养他们运用组合数学方法分析和解决相关问题的能力已经成为必要.如何在教学过程中提高学生学习组合数学的兴趣，建立组合数学的逻辑思维并用于解决实际问题是教育工作者需要思考的问题.一、课程特点与现状分析组合数学在计算机科学、信息科学中具有重要的地位，是理科及工科院校的一门必修课，其发展改变了传统数学中分析和代数占统治地位的局面.组合数学主要研究符合一定条件的组态对象、计数及构造等方面的问题，主要内容包括排列与组合、容斥原理及其应用、递推关系、生成函数、鸽巢原理和Polya定理等.然而，組合数学课程中概念、定理、性质和证明非常多而且都比较抽象，形式化程度高，学生在学习、理解和应用时比较困难.因此，需要通过研究性教学方法来激发和增强学生的学习兴趣，从而培养和增强学生的抽象思维、逻辑思维和理论联系实际的综合能力.二、研究性教学改革与实践（一）研究性教学理念研究性教学是目前高等教育教学研究的一个热点方向[1]，它是一种教师指导下的以学生为主体的自主学习和实践过程，包含了教与学两个方面：前者以教师为主导，在课堂教学中创设一种类似科学研究的情境或途径，把凝结在知识点背后的思想、方法和创新过程揭示出来，在引导学生学习和掌握新知识的同时，又能受到知识创新和科学研究方法的熏陶和训练；后者指学生在教师指导下，以科学研究的方式查阅资料、搜集信息，并通过分组协作和讨论来完成指定项目或问题的一种主动的、独创性的学习活动[2].（二）教学改革的目标通过启发式教学方法进行组合数学教学，锻炼学生的论证能力，用组合数学的思想培养学生分析问题和解决问题的能力，使学生能得到严格的逻辑推理与抽象思维能力的锻炼，了解数学中的抽象思维、建立数学模型与计算机科学实践之间的内在联系，不仅提高专业开发能力，而且为其他课程的学习打好数学基础.（三）研究性教学改革的实施方案根据组合数学的课程要求，在整个教学改革过程中，按照教学内容分成三个层次来安排：1.第一层次为基础知识的学习在研究性教学改革中，对课程的教学内容进行凝练和概括，对学时分配进行了优化.对于基础知识的学习依然采用传统的教学方法，夯实基础.2.第二层次为综合应用知识的学习为了加强学生综合应用知识的能力，对学生进行了分组，让每组学生独立完成设置好的一些案例.通过这些案例的研究性教学和讨论，可以使学生明白学习的目标不只是为了记住结论、公式、定理，而是会运用知识解决问题，真正由“学会”变为“会学”，这才是研究性教学的根本所在.3.第三层次为创新知识的学习为了培养学生创新能力，设置多个创新性课题，旨在探索并建立以问题和课题为核心的教学模式，激发学生的创新思维和创新意识，逐渐掌握思考问题、解决问题的方法，提高其创新实践的能力.三、研究性教学效果分析在组合数学的研究性教学开展中，经过不懈努力，取得了一定成果和效果.1.教师方面：教育的观念变了，教师在教学过程中真正成为学生学习的组织者、参与者、帮助者、引导者和促进者，从备课到上课，先进的教学理论得以实施，教学案例也是新颖而且有价值的.2.学生方面：改变了学生学习的方式，一改“在听中学”的单一方式，创造“在做中学”“在尝试中学”等多种学习方式；二改学生被动的学习态度；三改学生接受式学习的习惯，大力开展研究性学习；四改学生机械模仿的习惯，帮助学生进行创造性的有意义的学习.学生接受了新的教学法，能够按要求撰写学案，懂得了要合作学习，分享成果，也明白探究过程对个人的发展起到了积极的作用.四、结论通过开展组合数学课程的研究性教学改革，不仅较好地激发了学生学习的兴趣，更重要的是使学生深刻认识和领会到严谨的逻辑思维和高度的抽象思维及形式化表示在计算机科学发展及应用计算机求解等一些复杂的深层次问题中的作用.组合数学毕业论文范文模板(二)：基于组合数学课程的小班化教学改革实践[摘要]小班化教学，也称“小班化教育”，是指减少班级人数、缩小班级规模、降低师生比例，以有利于教师提高教学质量。

1．2．组合游戏需要解决的问题
由于组合游戏是一个双方博弈的游戏， 所以对于一个游戏的研究一般需要回
共 44 页-第 2 页
NOI2009 冬令营论文
从“k 倍动态减法游戏”出发探究一类组合游戏问题
答两个问题：谁有必胜策略？必胜策略是什么？ 而在信息竞赛学的问题中需要解决的问题，也与此相对应，分三个层次： （1）判断谁有必胜策略； （2）寻找单回合的必胜选择； （3）维护多回合的必胜选择（交互题涉及） 。
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)。
S ( x) S ( y) 1 ，所以 S ( x) (T ( x)) 。有很多例子中， S ( x) (T ( x)) ，下文中
将会提及的“捡石子游戏”就是一个这样的例子；但是，在更多的游戏中
S ( x) (T ( x)) ，例如在本文主要讨论的“k 倍动态减法游戏”， S ( x) (T ( x) 2 ) ，
3．2．NP 状态定理：
定理： P 状态是“胜利终止状态”或者它的一切后继都为 N 状态， N 状态是“失 败终止状态”或拥有至少一个后继是 P 状态。
3．3．通式的动态规划解法
根据上面的定理，可以利用动态规划求得每个状态是 P 状态还是 N 状态。 具体的实现方法，可以按照图的拓扑逆序倒推（常用方法） ，也可以从初状态出 发进行记忆化搜索（这个留在后面讨论） 。用递推实现，我们不难设计出下面算 法： 步骤 1：把所有“胜利终止状态”标记为 P 状态，“失败终止状态”标记为 N 状 态。 步骤 2：找到所有的未定状态中，所有后继都被确定是 N 状态的状态，设置 为 P 状态。

2
IOI2009 冬令营论文 方展鹏
正文
一、引言
在信息学竞赛中，博弈问题十分常见，下面就是一个例子： 引例：Green Hackenbush（经典问题） 给出 n 棵竹子，高度分别为 a1, a2 … an，玩家 L 和 R 打算在这些竹子上面玩 砍竹子游戏，规则如下： 1、两人轮流操作，玩家 L 先手； 2、对于每次操作，先选定一棵高度不为 0 的竹子，然后砍掉该竹子的某一 段，并且将与竹子底部不相连的部分也去掉； 3、最先无法进行操作的人输。 假设玩家 L 和 R 都采取最优策略，请问对于给出的局面谁会获胜。
关键字
不平等博弈问题 Surreal Number 局面分析 递推 迭代
目录
摘要................................................................................................................................ 1 关键字............................................................................................................................ 1 目录................................................................................................................................ 1 正文................................................................................................................................ 3 一、引言................................................................................................................ 3 二、另辟蹊径........................................................................................................ 4 2.1 Surreal Number 介绍 .......................................................................... 4 2.1.1 Surreal Number 的构造 ........................................................... 4 2.1.2 Surreal Number 的一些基本定理........................................... 6 2.1.3 Surreal Number 的运算法则................................................... 6

浅析竞赛中一类数学期望问题的解决方法福建省福州第八中学汤可因摘要期望在我们生活中有着十分广泛的应用，而对于我们信息学奥赛也出现了不少求解期望值的问题。

本文对于竞赛中涉及求离散型随机变量的数学期望的题目所使用的常用方法归纳成为两大类，并进行了总结与分析。

关键字期望递推动态规划方程组目录引言 (3)预备知识 (3)一、期望的数学定义 (3)二、期望的线性性质 (3)三、全概率公式 (4)四、条件期望与全期望公式 (4)一、利用递推或动态规划解决 (4)例题一：聪聪与可可 (5)分析 (5)小结 (6)例题二：Highlander (6)分析 (6)小结 (8)例题三：RedIsGood (8)分析 (8)小结 (9)二、建立线性方程组解决 (10)引入 (10)分析 (10)需要注意的地方 (12)例题四：First Knight (12)分析 (12)例题五：Mario (15)分析 (15)总结 (16)参考文献 (17)引言数学期望亦称为期望，期望值等，在概率论和统计学中，一个离散型随机变量的期望值是试验中每次可能结果的概率乘以其结果的总和。

而期望在我们生活中有着十分广泛的应用。

例如要设计一个彩票或赌博游戏，目标为赢利，那么计算能得到的钱以及需要付出的钱的期望，它们的差则需要大于0。

又例如对于是否进行一项投资的决策，可以通过分析总结得出可能的结果并估算出其概率，得到一个期望值而决定是否进行。

期望也许与每一个结果都不相等，但是却是我们评估一个事情好坏的一种直观的表达。

正因为期望在生活中有如此之多的应用，对于我们信息学奥赛也出现了不少求解期望值的问题。

而其中大多数又均为求离散型随机变量的数学期望。

本文对于这类题目所会涉及到的常用方法进行了归纳，总结与分析。

预备知识一、期望的数学定义如果X 是一个离散的随机变量，输出值为 x 1, x 2, ...， 和输出值相应的概率为p 1, p 2, ... （概率和为1）, 那么期望值 ∑=ii i x p X E )(。

1
IOI2009 中国国家集训队论文
长沙市雅礼中学 漆子超
【目录】
【序言】........................................................................................................................ 3 【正文】........................................................................................................................ 4 一.树的分治算法.................................................................................................... 4 基于点的分治：.............................................................................................. 4 基于边的分治：.............................................................................................. 4 效率分析：...................................................................................................... 5 【例 1】树中点对统计................................................................................... 8 算法分析................................................................................................... 8 【例 2】Free Tour 2 ...................................................................................... 10 算法分析................................................................................................. 10 【本节小结】................................................................................................ 13 二．树的路径剖分算法：................................................................................... 14 【例 3】Query On a Tree.............................................................................. 14 算法分析................................................................................................. 14 引入路径剖分......................................................................................... 14 轻重边路径剖分..................................................................................... 15 【例 4】黑白树 ........................................................................................... 17 算法分析................................................................................................. 17 【小结】........................................................................................................ 18 路径剖分与树的分治的联系：.................................................................... 19 【例 5】Query On a Tree Ⅳ ........................................................................ 20 算法分析................................................................................................. 20 【本节小结】................................................................................................ 23 三．树的分治的进一步探讨：........................................................................... 24 如何改进基于边的分治的时间复杂度........................................................ 24 使用基于边的分治解决【例 2】................................................................. 26 使用基于边的分治解决【例 5】................................................................. 27 四．全文总结....................................................................................................... 28 【参考文献】.............................................................................................................. 29 【感谢】...................................................................................................................... 29 【附录】...................................................................................................................... 29