下载文档原格式
摘抄自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 - 郑暾《平衡规划——浅析一类平衡思想的应用》。
二分法与统计问题淮阴中学李睿[关键字]线段树二叉树二分法[摘要]我们经常遇到统计的问题。
这些问题的特点是，问题表现得比较简单，一般是对一定范围内的数据进行处理，用基本的方法就可以实现，但是实际处理的规模却比较大，粗劣的算法只能导致低效。
为了解决这种困难，在统计中需要借助一些特殊的工具，如比较有效的数据结构来帮助解决。
本文主要介绍的是分治的思想结合一定的数据结构，使得统计的过程存在一定的模式，以到达提高效率的目的。
首先简要介绍线段树的基础，它是一种很适合计算几何的数据结构，同时也可以扩充到其他方面。
然后将介绍IOI2001中涉及的一种特殊的统计方法。
接着将会介绍一种与线段树有所不同的构造模式，它的形式是二叉排序树，将会发现这种方法是十分灵活的，进一步，我们将略去对它的构造，在有序表中进行虚实现。
目录一线段树1.1 线段树的构造思想1.2 线段树处理数据的基本方法1.3 应用的优势1.4 转化为对点的操作二一种解决动态统计的静态方法2.1 问题的提出2.2 数据结构的构造和设想2.3 此种数据结构的维护2.4 应用的分析三在二叉排序树上实现统计3.1 构造可用于统计的静态二叉排序树3.2 进行统计的方法分析3.3 一个较复杂的例子四虚二叉树4.1 虚二叉树实现的形态4.2 一个具体的例子4.3 最长单调序列的动态规划优化问题[正文]一 线段树在一类问题中，我们需要经常处理可以映射在一个坐标轴上的一些固定线段，例如说映射在OX 轴上的线段。
由于线段是可以互相覆盖的，有时需要动态地取线段的并，例如取得并区间的总长度，或者并区间的个数等等。
一个线段是对应于一个区间的，因此线段树也可以叫做区间树。
1.1线段树的构造思想线段树处理的是一定的固定线段，或者说这些线段是可以对应于有限个固定端点的。
处理问题的时候，首先抽象出区间的端点，例如说N 个端点ti(1≤i ≤N)。
那么对于任何一个要处理的线段（区间）[a,b]来说，总可以找到相应的i,j ，使得ti=a,tj=b,1≤i ≤j ≤N 。
BZOJ20482009国家集训队书堆数学算法题⽬⼤意：经典的物理上的桌边堆书问题，初中物理⽼师以前还讲过，只是仅仅记住了结论。
没关系，简单证明⼀下就好⾸先我们设由上⾄下第i本书⽐它以下那本书多伸出去的长度为a[i]，前缀和为s[i]，那么我们要求的就是s[n]为了简化问题我们设⼀本书的长度为1如果n=1a[1]=1/2，毫⽆疑义然后考虑两本书两本书的时候，重⼼明显在距以下那本书左端点的3/4处，故a[2]=1-3/4=1/4好的我知道了。
第⼀本是1/2，第⼆本是1/4。
那么第三本就是1/8！这样想的同学都仅仅过了例⼦。
我们考虑三本书的情况这个是怎么算的呢？⾸先先算三本书的重⼼距第三本书左端点的距离第⼀本书的重⼼为1/4 + 1/2 + 1/2第⼆本书的重⼼为1/4 + 1/2第三本书的重⼼为 1/2于是我们能够得到三本书的重⼼位置为(1/4*2+1/2+1/2*3)/3=1/2*2/3+1/2于是a[3]=1-(1/2*2/3+1/2)=1/2-1/2*2/3=1/2*(1-2/3)=1/2*1/3=1/6然后四本书的情况就不⽤多说了吧讨论四本书的重⼼距第四本书左端点的距离第⼀本书的重⼼位置为：1/6 + 1/4 + 1/2 + 1/2第⼆本书的重⼼位置为：1/6 + 1/4 + 1/2第三本书的重⼼位置为：1/6 + 1/2第四本书的重⼼位置为： 1/2于是四本书重⼼位置为(1/6*3+1/4*2+1/2+1/2*4)/4=1/2*3/4+1/2a[4]=1-(1/2*3/4+1/2)=1/2-1/2*3/4=1/2*(1-3/4)=1/2*1/4=1/8以此类推，我们有a[i]=1/2i那么这个东西怎么求和呢？n<=10^18，O(n)肯定是不现实的我们考虑调和级数极限公式lim(n->+∞)1/1+1/2+1/3+...+1/n = ln(n+1)+r当中r为欧拉常数近似值约为0.57721566490153286060651209但这是极限公式对于n⽐較⼩的情况误差会⽐較⼤所以当n⽐較⼩的时候O(n)暴⼒出解 n⽐較⼤的时候套⽤公式分界线理论上O(n)能过去即可 1000W左右就能够可是这题精度实在太低所以1W就能过去 0MS出解然后就⽔过去了。
浅析信息学中的“分”与“合”福建省福州第三中学杨沐目录【摘要】..................................................................... 错误!未定义书签。
【关键字】................................................................. 错误!未定义书签。
【正文】..................................................................... 错误!未定义书签。
一、引言............................................................... 错误!未定义书签。
二、例题分析 ...................................................... 错误!未定义书签。
[例一]牛奶模版 ............................................ 错误!未定义书签。
[例二]树的重建 ............................................ 错误!未定义书签。
[例三]最优序列 ............................................ 错误!未定义书签。
三、总结............................................................... 错误!未定义书签。
【感谢】..................................................................... 错误!未定义书签。
【参考文献】............................................................. 错误!未定义书签。
2009年国家集训队几道试题的另解
单墫
【期刊名称】《中等数学》
【年(卷),期】2010(000)008
【摘要】@@ 每年华东师范大学出版社都要出一本<走向IMO*数学奥林匹克试题集锦>,其中收集了当年国家集训队的测试题与选拔考试题.虽然这些题较难,但解法值得讨论.
【总页数】5页(P10-14)
【作者】单墫
【作者单位】南京师范大学数学系,210097
【正文语种】中文
【中图分类】G424.79
【相关文献】
1.一道2009年Serbia国家集训队试题的推广 [J], 朱纯刚
2.一道国家集训队测试题的另解及思考 [J], 朱天明
3.另解三道中国国家集训队选拔考试题 [J], 卢梓潼
4.2009年中国国家集训队几道试题另解 [J], 邹明
5.另解一道中国国家集训队选拔考试题 [J], 万喜人
因版权原因，仅展示原文概要，查看原文内容请购买。
2009年中国数学奥林匹克国家集训队协作体练习题（一）答案1、已知非负实数x ，y ，z 满足41332222=+++++z y x z y x ①，求z y x ++的最大值与最小值．解：由①式及均值不等式，得427()22223121⎪⎭⎫ ⎝⎛++++⎪⎭⎫ ⎝⎛+=z y x ()2331+++≥z y x ， ∴23≤++z y x ，当且仅当1=x ，21=y ，0=z 时等号成立故z y x ++的最大值为23．由于z y x ++的最大值是在“中值”，即23121+=+=+z y x 时取得，故可猜测其最小值应在“边值”，即0==y x ，2322-=z 时取得，下面利用局部调整法求解．固定z ，并记()A z y x =⎪⎭⎫ ⎝⎛+-=++⎪⎭⎫ ⎝⎛+22223427121（常数），则 ()12121212+⎪⎭⎫ ⎝⎛++=⎪⎭⎫⎝⎛+++y x A y x ．将x ，y 调整为0，y x +因为有()()121021212++⎪⎭⎫ ⎝⎛+≥+⎪⎭⎫ ⎝⎛+y x y x∴调整后，2121⎪⎭⎫⎝⎛+++y x 不增，即y x +不增于是，可令0=x ，则由①式可得()42623122=⎪⎭⎫ ⎝⎛+++z y ． 类似地，再将y ，z 调整为0，z y +，仍可得z y +也不增．故当0==y x ，2322-=z 时，z y x ++取得最小值2322-．另解：当0==y x ，2322-=z 时，2322-=++z y x又由x ，y ，z 0≥及①式，可得()()z y x z y x +++++32()yx zx yz xy z y x z y x ++++++++++=223222241332222=+++++≥z y x z y x ， 即()()41332≥+++++z y x z y x解得2223+-≥++z y x 或2223--≤++z y x （舍去）综上所述，z y x ++的最小值为2322-．2、设常数N n ∈，2≥n ，求最大的实数λ，使不等式()n n n a a a a a 21212++++≥- λ ①对所有正整数n a a a <<< 21成立．解：（先猜后证）当i a i =()n i ≤≤1时，由①式可得142--≤n n λ．下面证明()n n n a a a a n n a 21421212++++--≥- ②对所有正整数n a a a <<< 21成立．由整数的疏密性，知()k n a a n k --≤，n k ≤≤1，所以()[]∑∑-=-=----≤--1111142142n k kn k kk n an n an n()()⎥⎦⎤⎢⎣⎡-----=211142n n a n n n n()()242---=n n a n n()()22141++----=n n n a a a n()()2211-+---≤n n n a a a （∵1+<≤n n a a n ）n n a a 22-=此即②式． 综上所述，142max --=n n λ．3、设1a ，2a ，…，6a ；1b ，2b ，…，6b ；1c ，2c ，…，6c 都是1，2，3，4，5，6的排列，求∑=61i i i i c b a 的最小值．解：记∑==61i ii ic b aS ，则6616i i i i c b a S =∏⋅≥=()63!66⋅==!66=572=160>．下面证明：161>S ．注意到222111,,c b a c b a 这6个数的几何平均值为512，且2751226<<．所以这6个数中必有一个不小于27，也必有一个不大于26.又1，2，3，4，5，6中任三个数（允许重复）之积都不等于26. ∴其中的不大于26的数必不大于25. 不妨设27111≥c b a ，25222≤c b a ，则()()()66655544433322211122221112c b a c b a c b a c b a c b a c b a c b a c b a S +++++-=()66655544433322211122222527c b a c b a c b a c b a c b a c b a +++-≥()661232533i i i i c b a =∏⋅⨯+-≥()5725332+-=33057252-+=161>故由整数的疏密性，知162≥S ．另一方面，当()()6,5,4,3,2,1,61=a a ，()()2,1,6,3,4,5,61=b b ，()()2,6,1,3,4,5,61=c c 时，162=S ． 故162min =S ．4、给定正整数3>k ，记集合{}是非负整数、、z y x z y x S k k k ++=，将集合S 中的数从小到大排列，得到一个数列{}n a ，即有<<<<<=+1210n n a a a a ．求证：31118⎪⎭⎫ ⎝⎛-+⋅≤-k n k n n aa a ， ,5,4,3=n ．分析：要适当处理数列中的项与k k k z y x ++之间的关系．——利用x 、y 、z的存在性得到．证明：对于01>+n a ，N x ∈∃，使()kn k x a x 11+≤<+． ①对于01>-+k n x a ，N y ∈∃，使()kk n k y x a y 11+≤-<+．②对于01>--+k k n y x a ，N z ∈∃，使()kk k n k z y x a z 11+≤--<+． ③即N z y x ∈∃,,，使()kk k n k k k z y x a z y x 11+++≤<+++．再由数列的定义，知k k k n z y x a ++≥． ∴()k kn n z z a a -+≤-+11．且由①、②、③知，()k kk y y z -+<1，()k kk x x y -+<1． 又3≥n ，∴21≥+n a ．于是由①知1≥x ．∴()()kk k k k k k k kx C C C x x x 211211⋅<+++≤-+-- ． 当1≥y 且1≥z 时，同理有()kk kkyyy 211⋅≤-+-，()k k k kz z z 211⋅≤-+-∴k k k y z 21⋅<-，k k k x y 21⋅<-． ∴n n a a -+1()()kkk kk kk kkyzz z 2221111⋅⋅<⋅<-+≤---()()()kk k k k kk kk k k xy 222221111111111⋅⋅⋅<⋅⋅=-⎪⎭⎫ ⎝⎛--⋅--⎪⎭⎫ ⎝⎛--()kk kk k k x2221121112⋅⋅⋅=-+-⎪⎭⎫ ⎝⎛--()211132⎪⎭⎫ ⎝⎛--⋅<k k kx ．且当0=y 或0=z 时，上式也成立，故()2111312⎪⎭⎫ ⎝⎛--+⋅<-k k kn n xa a ．又由k k k k n x z y x a ≥++≥， ∴31118⎪⎭⎫ ⎝⎛-+⋅<-k n k n n aa a ．5、设k 为正整数，Z A ⊆，若存在Z x x x k ∈,,,21 ，使得对j i ≠∀，有()()φ=++A x A x j i，则称A 为一个k 集，其中{}A a a x A x ∈+=+．证明：若t A A A ,,,21 分别为t k k k ,,,21 集，且Z A A A t = 21，则111121≥+++tk k k ．证明：定义()∑≥∈=,αααA A xx P ，这里10<<x ．由Z A A A t = 21，知()xx x x P ti A i -=+++≥∑=11121①对每一个i A ，由于i A 是i k 集，所以存在整数ik i i i S S S ,,,21，使得()()φ=++i i i i A S A Sv u，v u =∀ ○*不妨设0≥wi S （i k w ≤≤1），则由○*知()()ik iiii S S S A xxxx P +++⋅ 21展开式中的项两两不同，从而()()xxx xxxx P ik iiii S S S A -=+++≤+++⋅111221②由①、②得11121≥+++∑=ti S S S ik iiixxx③在③式中，让+→1x ，则有111≥∑=ti ik．2009年中国数学奥林匹克国家集训队协作体练习题（四）1、已知非负实数x ，y ，z 满足41332222=+++++z y x z y x ①，求z y x ++的最大值与最小值．2、设常数N n ∈，2≥n ，求最大的实数λ，使不等式()n n n a a a a a 21212++++≥- λ ①对所有正整数n a a a <<< 21成立．3、设1a ，2a ，…，6a ；1b ，2b ，…，6b ；1c ，2c ，…，6c 都是1，2，3，4，5，6的排列，求∑=61i i i i c b a 的最小值．4、给定正整数3>k ，记集合{}是非负整数、、z y x z y x S k k k ++=，将集合S 中的数从小到大排列，得到一个数列{}n a ，即有<<<<<=+1210n n a a a a ．求证：31118⎪⎭⎫ ⎝⎛-+⋅≤-k n k n n a a a ， ,5,4,3=n ．5、设k 为正整数，Z A ⊆，若存在Z x x x k ∈,,,21 ，使得对j i ≠∀，有()()φ=++A x A x j i，则称A 为一个k 集，其中{}A a a x A x ∈+=+．证明：若t A A A ,,,21 分别为t k k k ,,,21 集，且Z A A A t = 21，则111121≥+++tk k k ．。
浅析竞赛中一类数学期望问题的解决方法福建省福州第八中学汤可因摘要期望在我们生活中有着十分广泛的应用，而对于我们信息学奥赛也出现了不少求解期望值的问题。
本文对于竞赛中涉及求离散型随机变量的数学期望的题目所使用的常用方法归纳成为两大类，并进行了总结与分析。
关键字期望递推动态规划方程组目录引言 (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 )(。
数学归纳法与解题之道山西省实验中学张昆玮教练：唐文斌胡伟栋2008年12月16日引言我们在学习算法的时候，总会有这样那样的疑惑：如此之多的浑然天成的算法，是怎样想到的？这些算法巧诚巧矣，可它们为什么是正确的呢？其实林林总总的算法背后，无不隐藏着真正的解题之道。
解题之道博大精深，该从何谈起？上面的疑惑又该如何解决？两千五百多年前，著名的哲学家和思想家老子对道之本质参透得可谓淋漓尽致。
引文中他给我们的答案是：参悟解题之道，从数学归纳法开始。
摘要本文简述了数学归纳法的相关理论，并结合作者的解题实践，以一些经典问题与竞赛题目为例，从证明算法正确性、构造性算法、与算法优化的关系等几个方面介绍了数学归纳法在信息学竞赛中的应用，讨论了数学归纳法的实用性与适用范围，以及归纳式算法设计相关的其他一些延伸与拓展。
目录●引言 (1)●摘要 (1)●目录 (2)●关于数学归纳法 (3)简短的回顾 (3)基本的定理、概念与方法 (3)是总结更是探索 (5)●在证明算法正确性上的应用 (6)贪心算法 (6)其他算法 (7)●在构造性算法中的应用 (8)数据结构的恢复性构造 (9)策略与解决方案的构造 (12)●数学归纳法与算法优化 (14)巧妙选择归纳对象 (14)力求完善归纳基础 (16)慎重选择归纳方向 (16)适当加强归纳假设 (17)●启发作用与美学价值 (19)●问题与缺陷 (19)理论上是否欠完备 (20)应用上是否较繁琐 (20)不适用的问题 (20)●后记 (21)●题目来源 (21)关于数学归纳法简短的回顾数学归纳法原理的发现可以追溯到公元1494年意大利数学家Francesco Maurolico 的著作Arithmeticorum libri duo 。
作为皮亚诺公理系统的应用，它自诞生之日就受到广泛关注。
同时，作为应对与正整数相关的问题的一种通用而简洁的处理方法，数学归纳法在许多算术、逻辑问题的解决中都占有核心地位。
浅谈数形结合思想在信息学竞赛中的应用安徽省芜湖一中周源目录目录 (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)摘要数与形是数学中两个最古老而又最基本的对象，数形结合又是一种重要的数学思想。
本文主要以当今信息学奥赛中几道试题为例，从以形助数和以数助形两个侧重点讨论了数形结合思想在信息学竞赛解题中广阔的应用前景。
最后文章分析指出数形结合思想的两个重要特性并由此提出“数形结合”重在有机的结合，希望对同学们在实际比赛中灵活的运用数形结合思想有一些帮助。
关键字信息学竞赛数学思想数形结合思想以数助形以形助数辩证矛盾多元性个体差异性思维、编程、时间、空间复杂度引子数与形是数学中两个最古老而又最基本的对象，数形结合又是一种重要的数学思想。
在当今信息学竞赛中，某些纷繁复杂的试题背后，往往蕴含着丰富的几何背景，而计算几何类问题却又需要借助计算机强大的实数运算能力。
正如华罗庚先生所说的“数形结合千般好”，在算法和程序设计中，巧妙地运用数形结合思想，可以顺利的破解问题，化难为易，找到问题的解题思路。
数形结合思想常包括以形助数、以数助形两个方面。
以形助数正如前文所述，一些试题中繁杂的代数关系身后往往隐藏着丰富的几何背景，而借助背景图形的性质，可以使那些原本复杂的数量关系和抽象的概念，显得直观，从而找到设计算法的捷径。
