国家集训队2009论文集slide

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

1 2
《由感性认识到理性认识——透析一类搏弈游戏的解答过程 》 ，张一飞，国家集训队 2002 论文 《解析一类组合游戏》 ，.王晓珂，国家集训队 2007 论文 第 1 页 共 24 页
IOI2009 中国国家集训队论文
贾志豪 石家庄二中

每一个模型都有详细的证明。大多数人在学习信息学时存在的问题是 “知其然，不知其所以然” ，因为大多数的比赛模式是只要求结果而不 要求过程。但这会使我们对一个事物“只知表皮，不知深髓” ，如果将 一个我们知道的问题稍加变形的话，我们可能就不会了。这个问题在组 合游戏中体现得尤其突出。因此笔者对于文中的每一个定理都给出了证 明，希望读者对文中的思想“知其然，知其所以然” 。
1.4 定义 NIM-模型
为了不使读者对本篇论文失去兴趣，我特意将介绍取石子游戏的内 容换成小字，对这部分内容已经很熟悉的读者可以直接略过。
取石子游戏即著名的 nim 游戏，游戏规则如下： 桌子上有 N 堆石子，游戏者轮流取石子。 每次只能从一堆中取出任意数目的石子，但不能不取。 取走最后一个石子者胜。
IOI2009 中国国家集训队论文
贾志豪 石家庄二中
组合游戏略述 ——浅谈 SG 游戏的若干拓展及变形
石家庄二中 贾志豪
前言
组合游戏是近几年新兴起的博弈游戏， 随着张一飞学长关于组合游戏的论文 的面世， 组合游戏问题开始在国内信息学竞赛这片沃土上生根发芽，与大家一起 成长、成熟、成才。最为马上要离开高中信息学舞台的高三学生，我一直希望能 为学弟学妹们留下一些我自己的心得，于是这篇论文应运而生！ ！ ！ 这篇论文的一些思想是我早在一年前节开始构思的， 感谢计算机学会为我提 供这样一个舞台， 能让我的论文为更多的人所知道；同时感谢在我写论文时无私 帮助过我的所有人，谢谢你们！ ！ ！ 先介绍一下论文的主要内容：第一章作为论文的理论基础，主要从欣赏的角 度引入了 SG 函数、游戏图、NIM 游戏等概念，重点谈我对组合游戏尤其是 SG 函 数的体会、 理解； 第二章主要介绍了几种不同规则的组合游戏以及相应的应对策 略，旨在告诉读者，游戏规则变化之后，我们应该如何去分析新的规则、解决新 的模型；第三章主要介绍了几种竞赛中常见的组合模型，并将“她”们成功的转 化成了 NIM 模型。 鉴于这篇论文的内容较多， 在这里给读者提供一些阅读建议：第一章由于篇 幅原因，并没有给出 SG 函数、NIM 游戏解法的详细证明过程，对于刚刚接触组 合游戏的读者，建议先阅读一些关于 SG 函数的资料（张一飞关于博弈游戏的论 文1、王晓柯关于组合游戏的论文2就很不错） ，然后再从论文的第一章看起，相信 你一定会很有收获；第二、三章是论文的重头戏，如题目所言，分别谈 SG 游戏 的拓展和变形，对于钟情于组合游戏的读者，可以重点看一看第三章，相信一定 不会让你失望！ ！ ！ 这篇论文主要有两个特点： 基本没有例题但处处是例子。为了让读者更好的理解论文中的思想，笔 者在选题目的时候刻意将题目的背景剥掉，只剩下一个“光溜溜 ”的数 学模型，这样读者在阅读论文时，就不必花精力去考虑背景向模型的转 化，可以全身心去理解笔者想要传达的思想。但读者不必去担心没有地 方练习，笔者将这几年的自己做过的组合游戏题收录在了论文的附录 里。

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

第 2 页 共 15 页
IOI2004 国家集训队论文 栗师
பைடு நூலகம்
21 41 4 -2 2 -2 输出样例 TAK NIE
2.1 确定算法模型。
看到题目，最 容易想 到的算法是广 搜。从当前已知能 够到达 的格子 出发 ， 按照马的走法，扩展出另外一些能到达的格子，一直扩展下去，最后判断是不 是扩展完了所有的棋盘。 很快会 发现这 种做法是不行 的，棋盘上 格子的个数是无限的，不能 判断 能 够到达所有的格子。但这个困难马上就有了解决的办法，显然只要判断超级马 是否能到达开始点的 4 个相邻格。因为如果能够到达这 4 个格子，那么必然能 够到达棋盘上的任意一个位置。 问题解决了没 有？没 有。虽然最终 目标 只需要判断四 个格子 ，但是，它 在 走到这 4 个格子的过程中经过的点可能会有很多个。更糟糕的是，当问题无解 时，无法进行正确的判断，最后实现算法时造成死机。 如果把 无限的 棋盘变 成相当大的有界棋盘，看 它在这个有界 棋盘上能否 到 达这 4 个格子。但这仍然是无用功，这个有界棋盘会有很大，这样时间效率很 低，算法也缺乏证明。 尝试各种图论算法、 动态规划、贪心等 ，最后 都以意 料之中的结果—— 失 败而告终。 要得到高效的算法，似乎只有一条出路：数学思想。 要用数 学思想 解题， 先要建立数学 模型 。以超级马最 开始的 格子为 原点 建 立平面坐标系。然后把马的一种动作用一个平面向量 Pi 来表示，Pi=(xi,yi)。那 么，我们要判断，对于任意的 x,y，是否都存在一组 c1,c2,c3……cn(ci>=0,1≤i≤n)， 使得 ∑ ci Pi = ( x, y ) 。
i=2 k k
所 以 存 在 整 数 序 列 d2,d3……dk 使
∑d g

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

把握本质，灵活运用——动态规划的深入探讨浙江省萧山中学来煜坤【关键字】动态规划构思实现【摘要】本文讨论了动态规划这一思想的核心内容和其基本特点，探讨了动态规划思想的适用范围，动态规划子问题空间和递推关系式确立的一般思路。

通过例子说明在子问题确立过程中的一些问题的解决办法：通过加强命题或适当调节确定状态的变量等手段帮助建立动态规划方程，通过预处理使动态规划的过程容易实现等。

接着，分析动态规划实现中可能出现的空间溢出问题及一些解决办法。

总结指出，动态规划这一思想，关键还在于对不同的问题建立有效的数学模型，在把握本质的基础上灵活运用。

一、引言动态规划是一种重要的程序设计思想，具有广泛的应用价值。

使用动态规划思想来设计算法，对于不少问题往往具有高时效，因而，对于能够使用动态规划思想来解决的问题，使用动态规划是比较明智的选择。

能够用动态规划解决的问题，往往是最优化问题，且问题的最优解(或特定解)的局部往往是局部问题在相应条件下的最优解，而且问题的最优解与其子问题的最优解要有一定的关联，要能建立递推关系。

如果这种关系难以建立，即问题的特定解不仅依赖于子问题的特定解，而且与子问题的一般解相关，那么，一方面难以记录下那么多的“一般解”，另一方面，递推的效率也将是很低的；此外，为了体现动态规划的高时效，子问题应当是互相重叠的，即很多不同的问题共享相同的子问题。

(如果子问题不重叠，则宜使用其它方法，如分治法等。

) 动态规划一般可以通过两种手段比较高效地实现，其一是通过自顶向下记忆化的方法，即通过递归或不递归的手段，将对问题最优解的求解，归结为求其子问题的最优解，并将计算过的结果记录下来，从而实现结果的共享；另一种手段，也就是最主要的手段，通过自底向上的递推的方式，由于这种方式代价要比前一种方式小，因而被普遍采用，下面的讨论均采用这种方式实现。

动态规划之所以具有高时效，是因为它在将问题规模不断减小的同时，有效地把解记录下来，从而避免了反复解同一个子问题的现象，因而只要运用得当，较之搜索而言，效率就会有很大的提高。

[Key Words]
Network Flow, Maximum Flow, Minimum Cut, Maximum Weight Closure of a Graph, Finding
a Maximum Density Sub Graph, Minimum Weight Vertex Covering Set and Maximum Weight
第 2 页 共 45 页
[][Library]Thesis
最小割模型在信息学竞赛中的应用
Amber
3.1. 引入 Introduction...........................................................................................................16 3.2. 构造 Construction of Algorithm ....................................................................................17 3.3. 证明 Proof......................................................................................................................17 3.4. 应用 Application............................................................................................................19
knowledge of minimum cut model. The thesis sets focus on researching that is in four aspects: 1. the application based on the

浅谈几类背包题浙江省温州中学徐持衡指导老师：舒春平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有关，可以用滚动数组来节省程序的空间复杂度。

证明：⑴必要性 设 T 是最小 k 度限制生成树，则Ⅰ,Ⅱ显然成立。 以下证明 Ⅲ：由Ⅰ,Ⅱ
可知如果(+a1,-b2)和(+a2,-b1)都是 T 的可行交换，则有ω(b2)≤ω(a1),ω(b1)≤ω (a2)，故ω(b1)+ω(b2)≤ω(a1)+ω(a2); 否则，或者(+a1,-b2)或者(+a2,-b1)不是 T 的 可行交换，根据引理 1，T’=T+{a1,a2}-{b1,b2}仍然是 T 的 k 度限制生成树，则ω (T)≤ω(T’),故ω(b1)+ω(b2)≤ω(a1)+ω(a2)。 ⑵充分性
综上，求最小 k 度限制生成树算法总的时间复杂度为 O(Vlog2V+E+kV)。
3、次小生成树
3.1、次小生成树的定义
设 G=(V,E,w)是连通的无向图，T 是图 G 的一个最小生成树。如果有另一棵树 T1，满 足不存在树 T’,ω（T’）<ω（T1） ，则称 T1 是图 G 的次小生成树。
3.2、求解次小生成树的算法
通过上述定理，我们就有了解决次小生成树问题的基本思路。 首先先求该图的最小生成树 T。时间复杂度 O(Vlog2V+E) 然后，求 T 的邻集中权值和最小的生成树，即图 G 的次小生成树。 如果只是简单的枚举，复杂度很高。首先枚举两条边的复杂度是 O(VE)，再判断该交换是否 可行的复杂度是 O(V)，则总的时间复杂度是 O(V2E)。这样的算法显得很盲目。经过简单的 分析不难发现，每加入一条不在树上的边，总能形成一个环，只有删去环上的一条边，才能 保证交换后仍然是生成树，而删去边的权值越大，新得到的生成树的权值和越小。我们可以 以此将复杂度降为 O(VE)。这已经前进了一大步，但仍不够好。 回顾上一个模型——最小度限制生成树，我们也曾面临过类似的问题，并且最终采用动态规 划的方法避免了重复计算，使得复杂度大大降低。对于本题，我们可以采用类似的思想。首 先做一步预处理，求出树上每两个结点之间的路径上的权值最大的边，然后，枚举图中不在

眼科病床的合理安排摘要病床的安排是每一个医院面临的重要问题，病床安排的不合理会带来病人满意度的降低，医院运转效率的下降以及资源的严重浪费。

本文首先通过对数据的处理和分析得到各类病患到达、入院、出院各项数据的分布规律并完成了对每类病患的入院时间合理预测，然后医院病床安排的合理性进行了指标体系的建立与评价，最后通过优化模型给出了新的病床分配方案。

针对问题一，初步猜想各类病人的就医人数、门诊后等待入院时间和住院时间是正态分布，我们将Excel处理过的附表数据输入到SPSS软件中进行非参数检验，验证其分布规律。

其中部分指标由于数据量的局限性，得到与正态分布相异的结果，我们将其分布比例用饼状图统计出来，可以看出其分布规律。

针对问题二，为了在医院管理中对服务质量进行正确分析，对病床安排的合理性进行正确分析，我们确定了四个评价指标：病床的利用率、周转率和病患的平均等待入院时间、平均住院时间。

由于数据的时滞性影响，选取2008/8/7-2008/9/11的数据进行各项指标的计算。

运用层次分析法算出各项指标在评价体系中的权重系数，最终根据模糊综合评判法，得到对该医院的评价：评语优良中差隶属度0.17100．5630.266按照隶属度最大原则，可以认为该医院的病床安排的合理性为“中”。

针对问题三，根据附表中的数据归纳出该院病人等待入院时间基本符合正态分布，依据这一分布建立各类病人的等待入院时间分布模型，取随机变量为，求出固有数据在这一范围的概率为99.74%，可以认为此时的随机变量范围具有代表性,从而得出不同病人的等待入院时间范围，多次带入实例检验通过后得到最终范围：病症白内障双眼白内障青光眼视网膜疾病外伤预计等待入院时间范围9.46~15.859.99~15.038.63~15.899.37~15.731针对问题四，由于外伤是急诊，为了使医院更人性化，我们这里将外伤病人单独拿出来分析。

利用统计学原理，计算出满足所有外伤疾病患者都有床位可住的最小床位比例。

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 状态。

动态规划的特点及其应用安徽张辰【关键词】动态规划阶段【摘要】动态规划是信息学竞赛中的常见算法，本文的主要内容就是分析它的特点。

文章的第一部分首先探究了动态规划的本质，因为动态规划的特点是由它的本质所决定的。

第二部分从动态规划的设计和实现这两个角度分析了动态规划的多样性、模式性、技巧性这三个特点。

第三部分将动态规划和递推、搜索、网络流这三个相关算法作了比较，从中探寻动态规划的一些更深层次的特点。

文章在分析动态规划的特点的同时，还根据这些特点分析了我们在解题中应该怎样利用这些特点，怎样运用动态规划。

这对我们的解题实践有一定的指导意义。

【正文】动态规划是编程解题的一种重要的手段，在如今的信息学竞赛中被应用得越来越普遍。

最近几年的信息学竞赛，不分大小，几乎每次都要考察到这方面的内容。

因此，如何更深入地了解动态规划，从而更为有效地运用这个解题的有力武器，是一个值得深入研究的问题。

要掌握动态规划的应用技巧，就要了解它的各方面的特点。

首要的，是要深入洞悉动态规划的本质。

§1动态规划的本质动态规划是在本世纪50年代初，为了解决一类多阶段决策问题而诞生的。

那么，什么样的问题被称作多阶段决策问题呢？§1.1多阶段决策问题说到多阶段决策问题，人们很容易举出下面这个例子。

[例1]多段图中的最短路径问题：在下图中找出从A1到D1的最短路径。

仔细观察这个图不难发现，它有一个特点。

我们将图中的点分为四类（图中的A、B、C、D），那么图中所有的边都处于相邻的两类点之间，并且都从前一类点指向后一类点。

这样，图中的边就被分成了三类（A→B、B→C、C→D）。

我们需要从每一类中选出一条边来，组成从A1到D1的一条路径，并且这条路径是所有这样的路径中的最短者。

从上面的这个例子中，我们可以大概地了解到什么是多阶段决策问题。

更精确的定义如下：多阶段决策过程，是指这样的一类特殊的活动过程，问题可以按时间顺序分解成若干相互联系的阶段，在每一个阶段都要做出决策，全部过程的决策是一个决策序列[1]。

浅谈数形结合思想在信息学竞赛中的应用安徽省芜湖一中周源目录目录 (1)摘要 (2)关键字 (2)引子 (3)以形助数 (3)[例一]Raney引理的证明 (3)[题意简述] (3)[分析] (3)目标图形化 (3)小结 (4)[例二]最大平均值问题(USACO 2003 March Open) (4)[题意简述] (4)[分析] (5)目标图形化 (5)构造下凸折线 (5)维护下凸折线 (6)最后的优化：利用图形的单调性 (7)小结 (7)以数助形 (7)[例三]画室(POI oi V Stage I) (8)[题意简述] (8)[分析] (8)目标数值化 (9)动态规划解题 (9)小结 (10)总结 (10)附录 (11)关于2003年上海市选拔赛题Sequence (11)[题意简述] (11)[分析] (11)论文附件 (12)参考文献 (12)摘要数与形是数学中两个最古老而又最基本的对象，数形结合又是一种重要的数学思想。

本文主要以当今信息学奥赛中几道试题为例，从以形助数和以数助形两个侧重点讨论了数形结合思想在信息学竞赛解题中广阔的应用前景。

最后文章分析指出数形结合思想的两个重要特性并由此提出“数形结合”重在有机的结合，希望对同学们在实际比赛中灵活的运用数形结合思想有一些帮助。

关键字信息学竞赛数学思想数形结合思想以数助形以形助数辩证矛盾多元性个体差异性思维、编程、时间、空间复杂度引子数与形是数学中两个最古老而又最基本的对象，数形结合又是一种重要的数学思想。

在当今信息学竞赛中，某些纷繁复杂的试题背后，往往蕴含着丰富的几何背景，而计算几何类问题却又需要借助计算机强大的实数运算能力。

正如华罗庚先生所说的“数形结合千般好”，在算法和程序设计中，巧妙地运用数形结合思想，可以顺利的破解问题，化难为易，找到问题的解题思路。

数形结合思想常包括以形助数、以数助形两个方面。

以形助数正如前文所述，一些试题中繁杂的代数关系身后往往隐藏着丰富的几何背景，而借助背景图形的性质，可以使那些原本复杂的数量关系和抽象的概念，显得直观，从而找到设计算法的捷径。

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

后缀数组 罗穗骞
例 10：长度不小于 k 的公共子串的个数(pku3415) ……………23 2．4 多个字符串的相关问题 …………………………………………………23
例 11：不小 于 k 个字符串中的最长子串(pku3294) ……………………24 例 12：每个字符串至少出现两次且不重叠的最长子串(spoj220)……24 例 13：出现或反转后出现在每个字符串中的最长子串(pku3294)……24 三、结束语 …………………………………………………………………………25 3．1 总结 ………………………………………………………………………25 3．2 参考文献 …………………………………………………………………25 3．3 致谢 ………………………………………………………………………25
１．２倍增算法
对每个字符开始的长度为 2k 的子字符串进行排序，求出排名，即 rank 值 。k 从 0 开始，每次加 1，当 2k 大于 n 以后，每个字符开始的长度为 2k 的子字符串 便相当于所有的后缀。并且这些子字符串都一定已经比较出大小，即 rank 值中 没有相同的值，那么此时的 rank 值就是最后的结果。每一次排序都利用上次长 度为 2k-1 的字符串的 rank 值，那么长度为 2k 的字符串就可以用两个长度为 2k-1 的字符串的排名作为关键字表示，然后进行基数排序，便得出了长度为 2k 的字 符串的 rank 值。以字符串“aabaaaab”为例，整个过程如图 2 所示。其中 x、y 是表示长度为 2k 的字符串的两个关键字。
例 1：最长公共前缀 ……………………………………………………17 2．2 单个字符串的相关问题 …………………………………………………17
2．2．1 重复子串 ………………………………………………………17 例 2：可重叠最长重复子串 ………………………………………17 例 3：不可重叠最长重复子串（pku1743）…………………………18 例 4：可重叠的最长重复子串（pku3261）…………………………19

浅谈用极大化思想解决最大子矩形问题福州第三中学王知昆【摘要】本文针对一类近期经常出现的有关最大（或最优）子矩形及相关变形问题，介绍了极大化思想在这类问题中的应用。

分析了两个具有一定通用性的算法。

并通过一些例题讲述了这些算法选择和使用时的一些技巧。

【关键字】矩形，障碍点，极大子矩形【正文】一、问题最大子矩形问题：在一个给定的矩形网格中有一些障碍点，要找出网格内部不包含任何障碍点，且边界与坐标轴平行的最大子矩形。

这是近期经常出现的问题，例如冬令营2002的《奶牛浴场》，就属于最大子矩形问题。

Winter Camp2002,奶牛浴场题意简述：（原题见论文附件）John要在矩形牛场中建造一个大型浴场，但是这个大型浴场不能包含任何一个奶牛的产奶点，但产奶点可以出在浴场的边界上。

John的牛场和规划的浴场都是矩形，浴场要完全位于牛场之内，并且浴场的轮廓要与牛场的轮廓平行或者重合。

要求所求浴场的面积尽可能大。

参数约定：产奶点的个数S不超过5000,牛场的范围N×M不超过30000×30000。

二、定义和说明首先明确一些概念。

1、定义有效子矩形为内部不包含任何障碍点且边界与坐标轴平行的子矩形。

如图所示，第一个是有效子矩形（尽管边界上有障碍点），第二个不是有效子矩形（因为内部含有障碍点）。

2、极大有效子矩形：一个有效子矩形，如果不存在包含它且比它大的有效子矩形，就称这个有效子矩形为极大有效子矩形。

（为了叙述方便，以下称为极大子矩形）3、定义最大有效子矩形为所有有效子矩形中最大的一个（或多个）。

以下简称为最大子矩形。

三、极大化思想【定理1】在一个有障碍点的矩形中的最大子矩形一定是一个极大子矩形。

证明：如果最大子矩形A不是一个极大子矩形，那么根据极大子矩形的定义，存在一个包含A且比A更大的有效子矩形，这与“A是最大子矩形”矛盾，所以【定理1】成立。

四、从问题的特征入手，得到两种常用的算法定理1虽然很显然，但却是很重要的。

集训队论文答辩(罗 剑桥)
目录
• 引言 • 研究方法与实验设计 • 研究结果与讨论 • 结论与建议 • 参考文献
01
CATALOGUE
引言
背景介绍
当前社会对环境保护的重视程度不断 提高，环境问题已成为全球关注的焦 点。
为了解决这些问题，政府、企业和个 人需要采取积极有效的措施，加强环 境保护和治理。
数据支持结论
所有的数据和分析均支持我们的研究结论，这增加了结论的可信度。
创新性
本研究在某些方面具有一定的创新性，为该领域的研究提供了新的视 角和思路。
局限性
尽管本研究取得了一些成果，但仍存在一些局限性，需要在未来的研 究中加以改进。
对未来研究的建议
深入研究领域
建议进一步深入研究本领域的某些特定问题，以深化理解。
比较不同文化背景下的现象和问题，揭示文化差 异对研究结果的影响。
实验设计
实验目的
明确实验所要解决的问题和目标，确保实验 具有针对性和实际意义。
实验变量
定义实验所涉及的自变量、因变量和控制变 量，明确实验变量的测量方法和工具。
实验对象
确定实验所涉及的样本范围和选取标准，确 保样本具有代表性和可靠性。
结果呈现
以图表、表格等形式呈现分析结果，使结论 更加直观和易于理解。
03
CATALOGUE
研究结果与讨论
研究结果
总结词
研究结果清晰、准确、完整，数据支 持有力。
详细描述
本研究通过对XXX进行研究，得出了 XXX的结论。这些结果对于理解XXX 具有重要意义，并且与已有研究相比 有所创新。
结果分析
02
CATALOGUE
研究方法与实验设计
研究方法