《浅谈数形结合思想在信息学竞赛中的应用》由会员分享，可在线阅读，更多相关《浅谈数形结合思想在信息学竞赛中的应用（12页珍藏版）》请在金锄头文库上搜索。
1、浅谈数形结合思想在信息学竞赛中的应用 安徽 周源第 1 页 共 12 页浅谈数形结合思想在信息学竞赛中的应用安徽 周源目录目录 .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附录
2、 .11关于 2003 年上海市选拔赛题 Sequence .11题意简述 .11分析 .11论文附件 .12参考文献 .12浅谈数形结合思想在信息学竞赛中的应用 安徽 周源第 2 页 共 12 页摘要数与形是数学中两个最古老而又最基本的对象，数形结合又是一种重要的数学思想。本文主要以当今信息学奥赛中几道试题为例，从以形助数和以数助形两个侧重点讨论了数形结合思想在信息学竞赛解题中广阔的应用前景。最后文章分析指出数形结合思想的两个重要特性并由此提出“数形结合”重在有机的结合，希望对同学们在实际比赛中灵活的运用数形结合思想有一些帮助。关键字信息学竞赛 数学思想 数形结合思想以数助形 以形助数辩证矛
3、盾 多元性 个体差异性思维、编程、时间、空间复杂度浅谈数形结合思想在信息学竞赛中的应用 安徽 周源第 3 页 共 12 页引子数与形是数学中两个最古老而又最基本的对象，数形结合又是一种重要的数学思想。在当今信息学竞赛中，某些纷繁复杂的试题背后，往往蕴含着丰富的几何背景，而计算几何类问题却又需要借助计算机强大的实数运算能力。正如华罗庚先生所说的“数形结合千般好” ，在算法和程序设计中，巧妙地运用数形结合思想，可以顺利的破解问题，化难为易，找到问题的解题思路。数形结合思想常包括以形助数、以数助形两个方面。以形助数正如前文所述，一些试题中繁杂的代数关系身后往往隐藏着丰富的几何背景，而借助背景图形的性
4、质，可以使那些原本复杂的数量关系和抽象的概念，显得直观，从而找到设计算法的捷径。例一Raney 引理的证明题意简述设整数序列 A = Ai, i=1, 2, , N，且部分和 Sk=A1+Ak，序列中所有的数字的和 SN=1。证明：在 A 的 N 个循环表示 1中，有且仅有一个序列 B，满足 B 的任意部分和 Si均大于零。分析先来看一个例子，若有序列 A = ，其 6 个循环表示为1. 2. 3. 4. 5. 6. 其中只有第 4 个序列，部分和为 3, 1, 1, 2, 6, 1，满足成为序列 B 的条件。若要用一般的代数或是组合方法来证明这个有趣的结论，似乎无从下手，但若要想到了用“形”
5、来帮忙，问题就简单多了。目标图形化周期性的推广 A 序列，得到一个无穷序列，便于观察其循环表示，得到：1 先设一个序列是环状的，则从其任意一个字符处断开以后形成的非环序列即为该序列的一个循环表示。浅谈数形结合思想在信息学竞赛中的应用 安徽 周源第 4 页 共 12 页同时计算这个序列的部分和 Si，因为这个序列是周期性的，因此对于所有的 k0，均有 Sk+N=Sk+1。如果做出这个函数的图像，则可以说函数有一个“平均斜率”为 ：每沿横轴正方向走 N 个单位，函数值就增加 1。于是如下图所1示，可以用两条斜率为 的直线“夹住”函数包含的所有点：图 1 无穷序列的部分和函数图像图示中 N=6，且使
6、用了上文举的例子。注意较低的那条直线，在每连续的N 个单位长度中，它与函数图像有且仅有一个交点，这是因为斜率是 的直线N1在每 N 个单位长度中最多到达一次整数点。这个交点是在这以后的 N 个点中的最低值，因此由此处的后一个位置导出的循环表示的所有部分和均为正数。而同时每连续 N 个单位长度仅有一个交点也证明了解的唯一性。小结一个简单的几何论证就证明了著名的 Raney 引理，其简练是其他方法不能企及的。Raney 引理有很广泛的应用，Catalan 数以及扩展 Catalan 数的组合公式就可以用该引理轻松解决。比如今年上海市选拔赛第二天比赛中的序列(Sequence)以及 OIBH 练习赛
7、中的项链，使用 Raney 引理都是最简单的方法之一。 2用几何图形辅助思考，不只停留在组合计数这一类中，更渗透在算法设计和优化的每一个分支中，近年来流行的“斜率优化”法是另一个很好的例子。例二最大平均值问题(USACO 2003 March Open)题意简述读入一列正数，a 1, a2, , aN，以及一个数 F。定义 ，1),(ijaiavej2 用 Raney 引理解答 Sequence 的过程，详见附录。浅谈数形结合思想在信息学竞赛中的应用 安徽 周源第 5 页 共 12 页ij。求 Maxave(a, b), 1a, bN ，且 ab- F+1，即求一段长度大于等于 F 且平均值最
8、大的子串。范围：FN10 5。分析简单的枚举算法可以这样描述：每次枚举一对满足条件的(a, b)，即 ab-F+1，检查 ave(a, b)，并更新当前最大值。然而这题中 N 很大，N 2 的枚举算法显然不能使用，但是能不能优化一下这个效率不高的算法呢？答案是肯定的。目标图形化首先一定会设序列 ai的部分和： Si=a1+a2+ai， ，特别的定义 S0=0。这样可以很简洁的表示出目标函数 ！)1(),(ijSave如果将 S 函数绘在平面直角坐标系内，这就是过点 Sj和点 Si-1 直线的斜率！于是问题转化为：平面上已知 N+1 个点，P i(i, Si)，0iN，求横向距离大于等于 F 的
9、任意两点连线的最大斜率。构造下凸折线有序化一下，规定对 ik(Pj, Pk)，就很容易可以证明 Pj点是多余的。浅谈数形结合思想在信息学竞赛中的应用 安徽 周源第 6 页 共 12 页区 区 区 区 区 区 2区区区1区区区xyPjPiPk图 2若 k(Pt, Pj) k(Pt, Pi)，那么可以看出，P t点一定要在直线 PiPj的上方，即阴影所示的 1 号区域。同理若 k(Pt, Pj) k(Pt, Pk)，那么 Pt点一定要在直线 PjPk的下方，即阴影所示的 2 号区域。综合上述两种情况，若 PtPj的斜率同时大于 PtPi和 PtPk的，P t点一定要落在两阴影的重叠部分，但这部分显
10、然不满足开始时 tj 的假设。于是，P t落在任何一个合法的位置时，P tPj的斜率要么小于 PtPi，要么小于 PtPk，即不可能成为最大值，因此 Pj点多余，完全可以从检查集合中删去。这个结论告诉我们，任何一个点 Pt的检查集合中，不可能存在一个对最优结果有贡献的上凸点，因此我们可以删去每一个上凸点，剩下的则是一个下凸折线。最后需要在这个下凸折线上找一点与 Pt点构成的直线斜率最大显然这条直线是在与折线相切时斜率最大，如图所示。 yxPt图 3维护下凸折线这一小节中，我们的目标是：用尽可能少的时间得到每一个检查点的下凸浅谈数形结合思想在信息学竞赛中的应用 安徽 周源第 7 页 共 12 页折线。算法首先从 PF开始执行：它是检查集合非空的最左边的一个点，集合内仅有一个元素 P0，而这显然满足下凸折线的要求，接着向右不停的检查新的点：PF+1, PF+2, , PN。检查的过程中，维
