“分层图思想”及其在信息学竞赛中的应用 天津市南开中学肖天 【摘要】本文通过对几道信息学竞赛题的解决，提出了一种解决问题的建模思想——分层图思想。该思想通过挖掘问题性质，将原问题抽象得出的图复 制为若干层并连接形成更大的图，使本来难以用数学语言表达得图论模 型变得简明严谨，为进一步解决问题打下了良好的基础。 【关键字】分层图思想图论数学模型最短路信息学竞赛 【正文】 1 引论 人们在借助计算机解决一个实际问题时，无非就是详细地告诉计算机应该怎么做，使它能通过人们给定的输入得到人们想要的输出。由于一般的计算机只能处理数字信号，所以只有把实际问题转化为数学问题，计算机才能帮助我们。这一步就是建立数学模型。 数学模型的建立在通过计算机解决问题的过程中非常重要。它把计算机无法理解的问题加以转化，使一切事物量化，最终变为只含数学过程的问题。它是人脑与计算机沟通的桥梁。不仅如此，数学模型的好坏直接影响着人与计算机之间的信息交流，影响着计算机对问题的“理解”。好的数学模型能够抓住问题的本质，表述简捷明了，易于人们找到有效的解决方法，并通过编制程序的方式将解决方法告诉计算机；相反，对于同一个问题，如果数学模型不能抓住问题本质，人们就可能无法解决问题，或者找不到有效的方法，更不用提告诉计算机如何做了。 由于建立数学模型是为了解决问题，所以人们在做这项工作时往往希望把问题归结为已经很好解决的经典问题或若干这样问题的有机结合。这样，只要应用前人的研究成果就可以了。比如，排序、求图的单源最短路、网络流等等都是经典问题，前人不仅给出一般解法，而且对各种特殊情况和变形作了深入的研究。但事情并不总像人们希望的那样，有的问题即使可以归结为已有问题，在其中加入一些干扰因素后，原有性质就会发生改变，原来建立起的数学模型难以再用严谨的数学语言表达。这样问题中的部分图论问题可以用本文提出的“分层图思想”解决。 该思想注重对原问题性质的挖掘，通过对原问题数学模型的扩展，将干扰因素融入新的数学模型之中，恢复了模型的严谨性，进而与已解决问题产生联系，得到有效算法。
摘抄自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 - 李骥扬《线段跳表——跳表的一个拓展》 SBT 2007 - 陈启峰：《Size Balance Tree》 线段树 2004 - 林涛：《线段树的应用》 单调队列 2006 - 汤泽：《浅析队列在一类单调性问题中的应用》 哈希表 2005 - 李羽修：《Hash函数的设计优化》 2007 - 杨弋：《Hash在信息学竞赛中的一类应用》 Splay 2004 - 杨思雨：《伸展树的基本操作与应用》
动态规划算法的优化技巧 福州第三中学毛子青 [关键词] 动态规划、时间复杂度、优化、状态 [摘要] 动态规划是信息学竞赛中一种常用的程序设计方法，本文着重讨论了运用动态规划思想解题时时间效率的优化。全文分为四个部分，首先讨论了动态规划时间效率优化的可行性和必要性，接着给出了动态规划时间复杂度的决定因素，然后分别阐述了对各个决定因素的优化方法，最后总结全文。 [正文] 一、引言 动态规划是一种重要的程序设计方法，在信息学竞赛中具有广泛的应用。 使用动态规划方法解题，对于不少问题具有空间耗费大、时间效率高的特点，因此人们在研究动态规划解题时更多的注意空间复杂度的优化，运用各种技巧将空间需求控制在软硬件可以承受的范围之内。但是，也有一部分问题在使用动态规划思想解题时，时间效率并不能满足要求，而且算法仍然存在优化的余地，这时，就需要考虑时间效率的优化。 本文讨论的是在确定使用动态规划思想解题的情况下，对原有的动态规划解法的优化，以求降低算法的时间复杂度，使其能够适用于更大的规模。 二、动态规划时间复杂度的分析 使用动态规划方法解题，对于不少问题之所以具有较高的时间效率，关键在于它减少了“冗余”。所谓“冗余”，就是指不必要的计算或重复计算部分，算法的冗余程度是决定算法效率的关键。动态规划在将问题规模不断缩小的同时，记录已经求解过的子问题的解，充分利用求解结果，避免了反复求解同一子问题的现象，从而减少了冗余。 但是，动态规划求解问题时，仍然存在冗余。它主要包括：求解无用的子问题，对结果无意义的引用等等。 下面给出动态规划时间复杂度的决定因素： 时间复杂度=状态总数*每个状态转移的状态数*每次状态转移的时间[1] 下文就将分别讨论对这三个因素的优化。这里需要指出的是：这三者之间不是相互独立的，而是相互联系，矛盾而统一的。有时，实现了某个因素的优化，另外两个因素也随之得到了优化；有时，实现某个因素的优化却要以增大另一因素为代价。因此，这就要求我们在优化时，坚持“全局观”，实现三者的平衡。 三、动态规划时间效率的优化 3.1 减少状态总数 我们知道，动态规划的求解过程实际上就是计算所有状态值的过程，因此状态的规模直接影响到算法的时间效率。所以，减少状态总数是动态规划优化的重要部分，本节将讨论减少状态总数的一些方法。
左偏树的特点及其应用 广东省中山市第一中学黄源河 【摘要】 本文较详细地介绍了左偏树的特点以及它的各种操作。 第一部分提出可并堆的概念，指出二叉堆的不足，并引出左偏树。第二部分主要介绍了左偏树的定义和性质。第三部分详细地介绍了左偏树的各种操作，并给出时间复杂度分析。第四部分通过一道例题，说明左偏树在当今信息学竞赛中的应用。第五部分对各种可并堆作了一番比较。最后总结出左偏树的特点以及应用前景。 【关键字】左偏树可并堆优先队列 【目录】 一、引言 (2) 二、左偏树的定义和性质 (2) 2.1 优先队列，可并堆 (2) 2.1.1 优先队列的定义 (2) 2.1.2 可并堆的定义 (2) 2.2 左偏树的定义 (3) 2.3 左偏树的性质 (4) 三、左偏树的操作 (5) 3.1 左偏树的合并 (5) 3.2 插入新节点 (7) 3.3 删除最小节点 (8) 3.4 左偏树的构建 (8) 3.5 删除任意已知节点 (9) 3.6 小结 (12) 四、左偏树的应用 (13) 4.1 例——数字序列（Baltic 2004） (13) 五、左偏树与各种可并堆的比较 (15) 5.1 左偏树的变种——斜堆 (15) 5.2 左偏树与二叉堆的比较 (16) 5.3 左偏树与其他可并堆的比较 (16) 六、总结 (18)
【正文】 一、引言 优先队列在信息学竞赛中十分常见，在统计问题、最值问题、模拟问题和贪心问题等等类型的题目中，优先队列都有着广泛的应用。二叉堆是一种常用的优先队列，它编程简单，效率高，但如果问题需要对两个优先队列进行合并，二叉堆的效率就无法令人满意了。本文介绍的左偏树，可以很好地解决这类问题。 二、左偏树的定义和性质 在介绍左偏树之前，我们先来明确一下优先队列和可并堆的概念。 2.1优先队列，可并堆 2.1.1优先队列的定义 优先队列(Priority Queue)是一种抽象数据类型(ADT)，它是一种容器，里面有一些元素，这些元素也称为队列中的节点(node)。优先队列的节点至少要包含一种性质：有序性，也就是说任意两个节点可以比较大小。为了具体起见我们假设这些节点中都包含一个键值(key)，节点的大小通过比较它们的键值而定。优先队列有三个基本的操作：插入节点(Insert)，取得最小节点(Minimum) 和删除最小节点(Delete-Min)。 2.1.2可并堆的定义 可并堆(Mergeable Heap)也是一种抽象数据类型，它除了支持优先队列的三个基本操作(Insert, Minimum, Delete-Min)，还支持一个额外的操作——合并操作： H ← Merge(H1,H2) Merge( ) 构造并返回一个包含H1和H2所有元素的新堆H。 前面已经说过，如果我们不需要合并操作，则二叉堆是理想的选择。可惜合并二叉堆的时间复杂度为O(n)，用它来实现可并堆，则合并操作必然成为算法的瓶颈。左偏树(Leftist Tree)、二项堆(Binomial Heap) 和Fibonacci堆(Fibonacci Heap) 都是十分优秀的可并堆。本文讨论的是左偏树，在后面我们将看到各种可并堆的比较。
1999年 陈宏- 数据结构的选择与算法效率——从IOI98试题PICTURE谈起 来煜坤- 把握本质，灵活运用——动态规划的深入探讨 齐鑫- 搜索方法中的剪枝优化 邵铮- 数学模型的建立、比较和应用 石润婷- 隐蔽化、多维化、开放化──论当今信息学竞赛中数学建模的灵活性睢》?- 准确性、全面性、美观性——测试数据设计中的三要素 周咏基- 论随机化算法的原理与设计 2000年 陈彧- 信息学竞赛中的思维方法 方奇- 动态规划 高寒蕊- 递推关系的建立及在信息学竞赛中的应用 郭一- 数学模型及其在信息学竞赛中的应用 江鹏- 探索构造法解题模式 李刚- 动态规划的深入讨论 龙翀- 解决空间规模问题的几种常用的存储结构 骆骥- 数学模型的建立和选择 施遥- 人工智能在围棋程序中的应用 肖洲- 数据结构的在程序设计中的应用 谢婧- 规模化问题的解题策略 徐串- 论程序的调试技巧 徐静- 图论模型的建立与转化 杨江明- 论数学策略在信息学问题中的应用 杨培- 非最优化算法初探 张辰- 动态规划的特点及其应用 张力- 类比思想在解题中的应用 张一飞- 冗繁削尽留清瘦——浅谈信息的充分利用 2001年 高寒蕊- 从圆桌问题谈数据结构的综合运用 符文杰- Pólya原理及其应用 高岳- 中等硬度解题报告 江鹏- 从一道题目的解法试谈网络流的构造与算法 刘汝佳- 搬运工问题的启示 李益明- 计算几何的相关问题 李源- 树的枚举 骆骥- 由“汽车问题”浅谈深度搜索的一个方面——搜索对象与策略的重要性毛子青- 动态规划算法的优化技巧 俞玮- 基本动态规划问题的扩展 张一飞- 求N!的高精度算法 2002年 戴德承- 退一步海阔天空——“目标转化思想”的若干应用
NOI国家集训队论文分类（至2008） 摘抄自C博客 组合数学 计数与统计 2001 - 符文杰：《Polya原理及其应用》 2003 -许智磊：《浅谈补集转化思想在统计问题中的应用》 2007 -周冬：《生成树的计数及其应用》 2008 - 陈瑜希《Polya计数法的应用》 数位问题 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 -李骥扬《线段跳表——跳表的一个拓展》 SBT 2007 - 陈启峰：《Size Bala nee Tree 》 线段树 2004 -林涛：《线段树的应用》 单调队列 2006 -汤泽：《浅析队列在一类单调性问题中的应用》 哈希表 2005 - 李羽修：《Hash函数的设计优化》 2007 - 杨弋：《Hash在信息学竞赛中的一类应用》 Splay 2004 -杨思雨：《伸展树的基本操作与应用》
置换群快速幂运算 研究与探讨 江苏省苏州中学 潘震皓 [关键词] 置换 循环 分裂 合并 [摘要] 群是一个古老的数学分支，近几年来在程序设计中置换群得到了一定的应用。本文针对置换群的特点提出了线性时间的幂运算算法，并举例说明了优化后算法的效果。 [正文] 一、引言 置换群是一种优秀的结构，在程序设计中，它的大部分基本操作，时间和空间复杂度都是线性的，甚至有的还是常数的。所以一个问题如果能够抽象归结为一个置换群模型的话，往往能够在程序设计中轻松地解决。但是对于整幂运算来说，似乎只能通过反复做乘法来获得O(k*乘法)或是O(logk*乘法)的算法；而对于分数幂运算，则找不到较好的方法实现。 二、置换群的整幂运算 2.1 整幂运算的一个转化 在置换群中有一个定理：设e T k =， （T 为一置换，e 为单位置换（映射函数为x x f =)(的置换）），那么k 的最小正整数解是T 的拆分的所有循环长度的最小公倍数。 或者有个更一般的结论：设e T k =， （T 为一循环，e 为单位置换），那么k 的最小正整数解为T 的长度。 我们知道，单位置换就是若干个只含单个元素的循环．．．．．．．．．的并。也就是说，长度为l 的循环，l 次的幂，把所有元素都完全分裂了。这是为什么呢？ 我们来做一个试验：(下面的置换均以循环的连接表示) 设n=6，那么3 26 )(T T =。任取一T=(1 3 5 2 4 6)，来做一遍乘法： ()() 36 2 45 1 34 126565432134 1 2 6 51265431265436543211265436543211265436543212 =???? ??=???? ?????? ??=???? ?????? ??=T 分裂成了2份！而且这2份恰好是T 的奇数项和偶数项！（注意可以写成(1 5 4)(3 2 6)）
浅谈数位类统计问题 山东省青岛第二中学刘聪 【摘要】 在信息学竞赛中，有一类与数位有关的区间统计问题。这类问题往往具有比较浓厚的数学味道，无法暴力求解，需要在数位上进行递推等操作。本文通过几个例子，简要介绍了解决此类问题的基本思想和方法。 【关键字】 数位区间统计递推树二进制 【正文】 在信息学竞赛中，有这样一类问题：求给定区间中，满足给定条件的某个D进制数或此类数的数量。所求的限定条件往往与数位有关，例如数位之和、指定数码个数、数的大小顺序分组等等。题目给定的区间往往很大，无法采用朴素的方法求解。此时，我们就需要利用数位的性质，设计log(n)级别复杂度的算法。解决这类问题最基本的思想就是“逐位确定”的方法。下面就让我们通过几道例题来具体了解一下这类问题及其思考方法。 【例题1】Amount of degrees (ural 1057) 题目大意： 求给定区间[X,Y]中满足下列条件的整数个数：这个数恰好等于K个互不相等的B的整数次幂之和。例如，设X=15，Y=20，K=2，B=2，则有且仅有下列三个数满足题意： 17 = 24+20， 18 = 24+21， 20 = 24+22。 输入：第一行包含两个整数X和Y。接下来两行包含整数K和B。 输出：只包含一个整数，表示满足条件的数的个数。 数据规模：1 ≤ X ≤ Y ≤ 231?1，1 ≤ K ≤ 20，2 ≤ B ≤ 10。 分析： 所求的数为互不相等的幂之和，亦即其B进制表示的各位数字都只能是0和1。因此，我们只需讨论二进制的情况，其他进制都可以转化为二进制求解。 很显然，数据范围较大，不可能采用枚举法，算法复杂度必须是log(n)级别，因此我们要从数位上下手。
线段树的应用 广西柳铁一中林涛 【摘要】 在竞赛解题中，常遇到与区间有关的操作，比如统计若干矩形并的面积，记录一个区间的最值、总量，并在区间的插入、删除和修改中维护这些最值、总量。 线段树拥有良好的树形二分结构，能够高效的完成这些操作，本文将介绍线段树的各种操作以及一些推广。 本文通过3个例子：《蛇》、《空心长方体》、《战场统计系统》，讲述线段树中基本的插入、删除、查找操作，和不规则的修改和删除操作，以及到二维的推广。 关键字：线段树二分子树收缩叶子释放面积树 【正文】 1. 线段树的定义及特征 定义1：线段树 一棵二叉树，记为T (a,b)，参数a,b表示该节点表示区间[a,b]。区间的长度b-a记为L。递归定义T[a,b]： 若L>1 ：[a, (a+b) div 2]为T的左儿子 [(a+b) div 2,b]为T的右儿子。 若L=1 ：T为一个叶子节点。 表示区间[1, 10]的线段树表示如下： (以下取对数后均向上取整) 定理1：线段树把区间上的任意一条线段都分成不超过2log L条线段 证明：(1)在区间(a，b)中，对于线段(c，d)，如果(c<=a) 或(d>=b)，那么线段在(a，b)中被分为不超过log(b-a)。 用归纳法证明，如果是单位区间，最多被分为一段，成立。 如果区间(a，b)的左儿子与右儿子成立，那么如果当c<=a时， 1．若d<=(a+b)div2那么相当与其左儿子分该线段，所分该线段数树不超过log((a+b)div 2-a)，即不超过log(b-a),成立。
2．若d>(a+b) div 2那么相当于该线段被分为它左儿子表示的线段，加上右儿子分该线段，线段数不超过1+log(b-(a+b) div 2),也不超过 log(b-a)，成立。 对于d>=b的情况证明类似，不再赘述。 (2)在区间(a,b)中，对于任意线段也用归纳法证明。 对于单位区间，最多分为一段，成立。 若(a，b)的左儿子与右儿子均成立，则对于线段(c，d) 1．若d<=(a+b)div 2 则该区间所分该线段等于其左儿子区间所分该线段，线段数小于log((a+b) div 2-a)<2log(b-a)，成立。 2．若c>(a+b) div 2 则该区间所分该线段等于其右儿子区间所分该线段，线段数小于log(b-(a+b) div 2)<2log(b-a)，成立。 3．若1、2均不成立，则此线段在左儿子区间分该线段满足d>V.Lson.b,分该线段数不超过log(b-(a+b) div 2)，而在右儿子区间分该线段满 足c<=V.Rson.a,分该线段不超过log((a+b) div 2-1)，所以在该区间 分该线段不超过2log(b-a)，成立。 这个结论为线段树能在O(log L)的时间内完成一条线段的插入、删除、查找等工作，提供了理论依据。 【例题一】蛇1 在平面上有N个点，现在要求一些线段，使其满足以下要求： a．这些线段必须闭合 b．线段的端点只能是这N个点 c．交于一点的两条线段成90度角 d．线段都必须平行于坐标轴 e．所有线段除在这N个点外不自交 f．所有线段的长度之和必须最短 如果存在这样的线段，则输出最小长度，否则输出0。 【问题分析】 从该题的要求入手，先构出符合要求的图，再解决线段长度之和最小的问题。1．题目显然要求一个以给定的N个点为顶点的N多边形。所有线段都要和坐标轴平行，所以每个点只能与上下左右四个点相连。由于与一个点相连的两条线段成90度，每个顶点必须与一条平行于X轴和一条平行于Y轴的线段相连。 2．将所有点排序后发现，在同一水平线上的点中，设这些点为P1，P2，P3，P4……Pn，P1要有一条平行于X轴的线段与其相连，就必须连它右边的点——P2，而P3如果再连P2，P2就有两条平行于X轴的线段和它相连，所以P3只能连P4，P5只能连P6……，同一垂直线上的点也是如此，所以线段的构造是唯一的，那么最小长度的问题就解决了。 3．由于解是唯一的，而是否相连只要广度扩展就可以判断了，所以关键在于判断由上述方法所构出线段是否合法——满足线段不在N个点之外自交： 1Saratov State University Problem Archive, 1028, Snake. 本题考查了基本的插入、删除和查找
NOI 国家集训队论文分类（至2008） 摘抄自 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- 李骥扬《线段跳表——跳表的一个拓展》 SBT 2007 - 陈启峰：《Size Balance Tree 》线段树 2004- 林涛：《线段树的应用》 单调队列 2006- 汤泽：《浅析队列在一类单调性问题中的应用》哈希表2005- 李羽修：《Hash 函数的设计优化》 2007- 杨弋：《Hash 在信息学竞赛中的一类应用》 Splay 2004- 杨思雨：《伸展树的基本操作与应用》 图论 图论 2005- 任恺：《图论的基本思想及方法》
伸展树的基本操作与应用 安徽省芜湖一中杨思雨 目录 【关键字】 (2) 【摘要】 (2) 【引言】 (2) 【伸展树的基本操作】 (2) 伸展操作Splay(x,S) (3) 伸展树的基本操作 (4) 时间复杂度分析 (5) 【伸展树的应用】 (7) 【总结】 (8) 【参考书目】 (9) 【附录】 (9)
【关键字】 伸展树基本操作应用 【摘要】 本文主要介绍了伸展树的基本操作以及其在解题中的应用。全文可以分为以下四个部分。 第一部分引言，主要说明了二叉查找树在信息学竞赛中的重要地位，并且指出二叉查找树在某些情况下时间复杂度较高，进而引出了在时间复杂度上更为优秀的伸展树。 第二部分介绍了伸展树的基本操作。并给出了对伸展树时间复杂度的分析和证明，指出伸展树的各种基本操作的平摊复杂度均为O(log n)，说明伸展树是一种较平衡的二叉查找树。 第三部分通过一个例子介绍了伸展树在解题中的应用，并将它与其它树状数据结构进行了对比。 第四部分指出了伸展树的优点，总结全文。 【引言】 二叉查找树（Binary Search Tree）能够支持多种动态集合操作。因此，在信息学竞赛中，二叉排序树起着非常重要的作用，它可以被用来表示有序集合、建立索引或优先队列等。 作用于二叉查找树上的基本操作的时间是与树的高度成正比的。对一个含n 各节点的完全二叉树，这些操作的最坏情况运行时间为O(log n)。但如果树是含n个节点的线性链，则这些操作的最坏情况运行时间为O(n)。而有些二叉查找树的变形，其基本操作在最坏情况下性能依然很好，比如红黑树、A VL树等等。 本文将要介绍的伸展树（Splay Tree），也是对二叉查找树的一种改进，虽然它并不能保证树一直是“平衡”的，但对于伸展树的一系列操作，我们可以证明其每一步操作的平摊复杂度都是O(log n)。所以从某种意义上说，伸展树也是一种平衡的二叉查找树。而在各种树状数据结构中，伸展树的空间要求与编程复杂度也都是很优秀的。 【伸展树的基本操作】 伸展树是二叉查找树的一种改进，与二叉查找树一样，伸展树也具有有序性。即伸展树中的每一个节点x都满足：该节点左子树中的每一个元素都小于x，而其右子树中的每一个元素都大于x。与普通二叉查找树不同的是，伸展树可以自我调整，这就要依靠伸展操作Splay(x,S)。
论随机化算法的原理与设计 上海市控江中学周咏基 [关键字] 随机化算法，稳定性 [摘要] 本文提出了一种新的解决信息学问题的算法——随机化算法，并讨论了其原理与设计方法。论文首先给出随机化算法的定义，说明了由于“运气”的影响，必须对随机化算法的稳定性进行分析。然后分“随机不影响算法的执行结果”，“随机影响执行结果的正确性”，“随机影响执行结果的优劣”三种情况，以从基本算法到竞赛试题中用随机化算法有效解决问题的例子，详细分析了三种情况的随机化算法的原理与设计方法。最后总结出随机化算法的基本原理和共同性质，提出设计随机化算法的一般方法，并指出随机化算法的适用范围和一个有效的随机化算法应具备的特点。 [正文] 1．引论 在这篇论文中，我们将研究一种新概念的算法——随机化算法。顾名思义，随机化就是指使用了随机函数。这里的随机函数不妨是Borland Pascal(或Turbo Pascal)中的RANDOM(N)，其返回值为[0,N-1]中的某个整数，且返回每个整数都是等概率的[1]。 一个含有随机函数的算法很可能[2]受到不确定因素的支配。人们通常认为，一个受到不确定因素支配的算法肯定不是一个有效的算法——正是在这种思维方式的支配下，随机化算法一直被冷落——但是，在接下来的讨论中，我们将看到完全相反的事情发生：对于一些特定的问题，随机化算法恰恰成了十分有效的解题工具，有时甚至比一般的非随机化算法做得更好。 随机化算法的定义 随机化算法是这样一种算法，在算法中使用了随机函数，且随机函数的返回值直接或间接地影响了算法的执行流程或执行结果。 根据这个定义，并不是所有的用了随机函数的算法都可称为随机化算法。例如，某个算法包含 i RANDOM(N)，
浅谈几类背包题 浙江省温州中学徐持衡指导老师：舒春平 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有关，可以用滚动数组来节省程序的空间复杂度。以下就是经典算法的伪代码。 1.FOR i: = 1 TO n 2. FOR j: = C DOWNTO V i 3. Max ( F[ j ] , F[ j-V i ] + W i ) → F[ j ] 4. END FOR 5.END FOR
数学模型的建立、比较和应用 苏州中学邵铮 关键字: 数学模型算法母函数 【摘要】 数学模型是解决实际问题的一种基本工具。将实际问题抽象成一个数学模型，运用数学工具进行求解，并将结果应用于具有相同特征的一类问题中，是解决问题的一种基本的途径。本文首先介绍了数学模型的一些性质，然后建立了三种不同的数学模型来求解一个问题，将三种数学模型相互比较，得出数学模型抽象性与高效性之间的关系，再将数学模型推广应用于另两个问题的求解，得出数学模型抽象性与可推广性之间的关系，最后总结全文，揭示出有关数学模型的一些普遍规律。 一、引论 实际问题往往是纷繁而复杂的，而其中的规律也是隐藏着的，要想直接用计算机来求解实际问题往往有一定的困难。计算机擅长的是解决数学问题。因此，我们有必要将实际问题抽象成数学模型，然后再用计算机来对数学模型进行求解。 与实际问题相比，数学模型有以下几个性质： 抽象性：数学模型是实际问题的一种抽象，它去除了实际问题中与问题的求解无关的部分，简明地体现了问题的本质。这一点是下面两个性质的基础。 高效性：数学模型中各个量之间的关系更为清晰，容易从中找到规律，从而提高求解的效率。由于这一点是由数学模型的抽象性决定的，因此数学模型的抽象化程度对数学模型效率的高低有重要的影响，这一点将在第二部分中详细阐述。 可推广性：数学模型可以推广到具有相同性质的一类问题中。换句话说，解决了一个数学模型就解决了一类实际问题。这里的“相同性质”是指相同的本质，表面看似毫不相干的问题可能有着相同的本质。由于这一点也是由数学模型的抽象性决定的，因此数学模型的抽象化程度对数学模型的推广范围也有重要的影响，这一点将在第三部分中详细阐述。 二、数学模型的建立和比较 由于考虑问题的角度不同，面对同一个实际问题，可能建立起各种各样的数学模型。在各种数学模型中，我们要寻找的是效率高的模型。模型的效率同模型的抽象化程度有关，下面从一个实例中来分析它们之间的具体关系。 【多边形分割问题】将一个凸n边形用n-3条互不相交的对角线分割为n-2
浅谈用极大化思想解决最大子矩形问题 福州第三中学王知昆 【摘要】 本文针对一类近期经常出现的有关最大（或最优）子矩形及相关变形问题，介绍了极大化思想在这类问题中的应用。分析了两个具有一定通用性的算法。并通过一些例题讲述了这些算法选择和使用时的一些技巧。 【关键字】矩形，障碍点，极大子矩形 【正文】 一、问题 最大子矩形问题：在一个给定的矩形网格中有一些障碍点，要找出网格内部不包含任何障碍点，且边界与坐标轴平行的最大子矩形。 这是近期经常出现的问题，例如冬令营2002的《奶牛浴场》，就属于最大子矩形问题。 Winter Camp2002,奶牛浴场 题意简述：（原题见论文附件） John要在矩形牛场中建造一个大型浴场，但是这个大型浴场不能包含任何一个奶牛的产奶点，但产奶点可以出在浴场的边界上。John的牛场和规划的浴场都是矩形，浴场要完全位于牛场之内，并且浴场的轮廓要与牛场的轮廓平行或者重合。要求所求浴场的面积尽可能大。 参数约定：产奶点的个数S不超过5000,牛场的范围N×M不超过30000×30000。 二、定义和说明 首先明确一些概念。 1、定义有效子矩形为内部不包含任何障碍点且边界与坐标轴平行的子矩形。如图所示，第一个是有效子矩形（尽管边界上有障碍点），第二个不是有效子矩形（因为内部含有障碍点）。
2、极大有效子矩形：一个有效子矩形，如果不存在包含它且比它大的有效子矩形，就称这个有效子矩形为极大有效子矩形。（为了叙述方便，以下称为极大子矩形） 3、定义最大有效子矩形为所有有效子矩形中最大的一个（或多个）。以下简称为最大子矩形。 三、极大化思想 【定理1】在一个有障碍点的矩形中的最大子矩形一定是一个极大子矩形。 证明：如果最大子矩形A不是一个极大子矩形，那么根据极大子矩形的定义，存在一个包含A且比A更大的有效子矩形，这与“A是最大子矩形”矛盾，所以【定理1】成立。 四、从问题的特征入手，得到两种常用的算法 定理1虽然很显然，但却是很重要的。根据定理1，我们可以得到这样一个解题思路：通过枚举所有的极大子矩形，就可以找到最大子矩形。下面根据这个思路来设计算法。 约定：为了叙述方便，设整个矩形的大小为n×m，其中障碍点个数为s。 算法1 算法的思路是通过枚举所有的极大子矩形找出最大子矩形。根据这个思路可以发现，如果算法中有一次枚举的子矩形不是有效子矩形、或者不是极大子矩形，那么可以肯定这个算法做了“无用功”，这也就是需要优化的地方。怎样保证每次枚举的都是极大子矩形呢，我们先从极大子矩形的特征入手。 【定理2】：一个极大子矩形的四条边一定都不能向外扩展。更进一步地说，一个有效子矩形是极大子矩形的充要条件是这个子矩形的每条边要么覆盖了一个障碍点，要么与整个矩形的边界重合。
浅谈数形结合思想在信息学竞赛中的应用 安徽省芜湖一中周源 目录 目录 (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)
摘要 数与形是数学中两个最古老而又最基本的对象，数形结合又是一种重要的数学思想。 本文主要以当今信息学奥赛中几道试题为例，从以形助数和以数助形两个侧重点讨论了数形结合思想在信息学竞赛解题中广阔的应用前景。 最后文章分析指出数形结合思想的两个重要特性并由此提出“数形结合”重在有机的结合，希望对同学们在实际比赛中灵活的运用数形结合思想有一些帮助。 关键字 信息学竞赛数学思想数形结合思想 以数助形以形助数 辩证矛盾多元性个体差异性 思维、编程、时间、空间复杂度
引子 数与形是数学中两个最古老而又最基本的对象，数形结合又是一种重要的数学思想。 在当今信息学竞赛中，某些纷繁复杂的试题背后，往往蕴含着丰富的几何背景，而计算几何类问题却又需要借助计算机强大的实数运算能力。正如华罗庚先生所说的“数形结合千般好”，在算法和程序设计中，巧妙地运用数形结合思想，可以顺利的破解问题，化难为易，找到问题的解题思路。 数形结合思想常包括以形助数、以数助形两个方面。 以形助数 正如前文所述，一些试题中繁杂的代数关系身后往往隐藏着丰富的几何背景，而借助背景图形的性质，可以使那些原本复杂的数量关系和抽象的概念，显得直观，从而找到设计算法的捷径。 [例一]Raney引理的证明 [题意简述] 设整数序列A = {A i, i=1, 2, …, N}，且部分和S k=A1+…+A k，序列中所有的数字的和S N=1。 证明：在A的N个循环表示1中，有且仅有一个序列B，满足B的任意部分和S i均大于零。 [分析] 先来看一个例子，若有序列A = <1, 4, -5, 3, -2, 0>，其6个循环表示为 1.<1, 4, -5, 3, -2, 0> 2.<4, -5, 3, -2, 0, 1> 3.<-5, 3, -2, 0, 1, 4> 4.<3, -2, 0, 1, 4, -5> 5.<-2, 0, 1, 4, -5, 3> 6.<0, 1, 4, -5, 3, -2> 其中只有第4个序列，部分和为3, 1, 1, 2, 6, 1，满足成为序列B的条件。 若要用一般的代数或是组合方法来证明这个有趣的结论，似乎无从下手，但若要想到了用“形”来帮忙，问题就简单多了。 目标图形化 周期性的推广A序列，得到一个无穷序列，便于观察其循环表示，得到： 1先设一个序列是环状的，则从其任意一个字符处断开以后形成的非环序列即为该序列的一个循环表示。
分治算法在树的路径问题中的应用 【摘要】 树作为一类特殊的数据结构，在信息学中有着极为重要的作用，各类关于树的题目在竞赛中更是屡见不鲜。本文选取了近几年出现的关于树的路径的题目，并结合例题讲解了分治算法在此类问题上的应用。 【关键字】 树路径路径剖分分治数据结构
【目录】 【序言】 (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)
树被定义为没有圈的连通图，具有以下几个性质： 1.在树中去掉一条边后所得的图是不连通的。 2.在树中添加一条边后所得的图一定存在圈。 3.树的每一对顶点U和V之间有且仅有一条路径。 由于树具有一般图所没有的特点，因此在竞赛中有着更加广泛的应用，尤其是关于树中路径的问题，即一类以路径为询问对象的题目，更是频繁的出现在各种比赛中，每一个有志于OI及ACM的选手都应该掌握这类问题的算法。 分治，指的是分而治之，即将一个问题分割成一些规模较小的相互独立的子问题，以便各个击破。我们常见的是在一个线性结构上进行分治，而在本文中我们将会讲解分治算法在树结构上的运用，称之为树的分治算法。 分治往往与高效联系在一起，而树的分治正是一种用来解决树的路径问题的高效算法。 下面让我们一起来感受树的分治算法的美妙吧。