《解题的最短路径》由会员分享，可在线阅读，更多相关《解题的最短路径（32页珍藏版）》请在金锄头文库上搜索。
1、IOI2002冬令营讲稿冬令营讲稿解题的最短路径解题的最短路径构造法构造法IOI2002冬令营讲稿冬令营讲稿构造法构造法解题的解题的“最短路径最短路径”l构造法及其特点l常用的构造法l构造法的优、缺点BackIOI2002冬令营讲稿冬令营讲稿构构造法及其特点造法及其特点什么叫构造法： 直接列举出满足条件的对象或反例，导致结论的肯定与否定，间接构造某种对应关系，使问题根据需要进行转化的方法。 构造法绝不是简单的尝试,也不是一时的运气构造法使用的前提：存在性构造法特别适用于竞赛中求单个可行解的题目BackIOI2002冬令营讲稿冬令营讲稿常常用的构造法用的构造法l直接构造l分类构造l归纳构造Bac
2、kIOI2002冬令营讲稿冬令营讲稿构造法的优、缺点构造法的优、缺点 优点：时空复杂度小，编程复杂度小 缺点：思维复杂度大BackIOI2002冬令营讲稿冬令营讲稿直接构造直接构造l一种直接对目标对象进行考察的构造方法。l探索是直接构造的灵魂，在构造的背后，往往隐蔽着反反复复的尝试。l实际应用中，首先对于目标对象进行观察，发现一般性的规律，加以概括总结后运用至构造中。l在熟悉的事物中寻找，在特殊的事物中寻找，接合目标，不断地调整甚至改变方案，直至实现构造IOI2002冬令营讲稿冬令营讲稿例一：三臂起重机（例一：三臂起重机（1 1） 给出了三个数p、q、n，要构造若干个三元组，符合以下四个要求：
3、 （1）三元组必须具备形式（i，i+p，i+p+q）（i，i+q，i+p+q）之一。 （2）所有三元组中的元素不得超过n+p+q。 （3）1，2，n+p+q这n+p+q个数每个至多出现一次。 （4）这些三元组必须涵盖1，2，n这n个自然数。 n300000，p+q60000。IOI2002冬令营讲稿冬令营讲稿例一：三臂起重机（例一：三臂起重机（2）很自然想到构造法。观察以下几个例子：p=1,q=1(1,2,3)(4,5,6)(7,8,9)p=2,q=4(1,3,7)(2,4,8)(5,9,11)(6,10,12)p=3,q=1(1,4,5)(2,3,6)(7,10,11)p=1,q=3(1,2
4、,5)(3,4,7)(6,9,10)(8,11,12)容易得出下面类似贪心的方法：设已经构造了s个三元组（x1,y1,z1)、（x2,y2,z2)、（xs,ys,zs)，满足x1x2q时，先交换p、q的位置。这仅仅是一个猜想，需要经过实践以及证明。 经过许多尝试，这种构造法仍然满足要求。因此，我们猜测本题完整的构造方法如下：IOI2002冬令营讲稿冬令营讲稿例一：三臂起重机（例一：三臂起重机（4 4）若pq，则交换p、q的值，不影响构造的结果。设已经构造了s个三元组（x1,y1,z1)、（x2,y2,z2)、（xs,ys,zs)，满足x1x2xs。取上面s个三元组中没有出现过的最小自然数r1.
5、r+p没有出现过 (xs+1,ys+1,zs+1)=(r,r+p,r+p+q)2.r+p出现过 (xs+1,ys+1,zs+1)=(r,r+q,r+p+q)从题面上看来，p、q的位置应当是对称的，为什么会需要假设“pq” 的情况呢？IOI2002冬令营讲稿冬令营讲稿例一：三臂起重机（例一：三臂起重机（5 5）证明：若r+p出现过，那么r+q必定未出现。反证法，设r+p、r+q均已出现。1.r+q=xi+p（1is），qpr=xi+p-qxi，与r是“前s个三元组中未出现的最小自然数”矛盾2.r+q=xi+p+q（1is），r=xi+p，xi+p未出现，与“若r+p未出现，则优先选择r+p”矛盾
6、IOI2002冬令营讲稿冬令营讲稿例一：小结例一：小结构造需要反复尝试构造需要反复尝试IOI2002冬令营讲稿冬令营讲稿例二：例二：区间染色问题（区间染色问题（1 1） 给出了n个区间，已知对于t0,t1的任一点，都至少被一个区间所覆盖，要求对其中若干个区间进行染色，使得仅被一个染色区间覆盖的区域长度不少于2/3(t1-t0)。123如：对下面的三个区间进行染色，红色部分为仅被一个染色区间覆盖的区域IOI2002冬令营讲稿冬令营讲稿例二：区间染色问题例二：区间染色问题（2 2）设这n个区间为a1，b1，a2，b2，an，bn，且a1a2an去除操作去除操作前提：不存在无解情况删除目的：区间之间
7、的关系更简单明了a1a2anb1b2bnb1a3b2，b2a4b3，bn-2anbn-1IOI2002冬令营讲稿冬令营讲稿例二：区间染色问题例二：区间染色问题（3 3）1)取a1，b1、a3，b3、a5，b5这些编号为奇数的区间。2)取a2，b2、a4，b4、a6，b6这些编号为偶数的区间。3)取a1，b1、a2，b2、a3，b3全部的n个区间。IOI2002冬令营讲稿冬令营讲稿例二：区间染色问题例二：区间染色问题（4 4）只需证：若l1、l22(t1-t0)-4/3(t1-t0)=2/3(t1-t0)变形得：这就证明了：l1、l2、l3中间必然有一个不小于2/3(t1-t0)，上述构造成立。
8、IOI2002冬令营讲稿冬令营讲稿例例二：小结二：小结 本题采用的方法特别之处在于：同时构造了多组情形，证明必然有一组符合要求。 对于某些题目，很难直接给出一种“必行”的构造方法，这时就需要我们为它“量身定做”多个构造方法，相辅相成。某种构造成立导出结论的成立；不成立却为其他的构造法创造了条件。构造D成立构造A不成立构造B不成立构造C不成立BackIOI2002冬令营讲稿冬令营讲稿分类构造分类构造当所研究的问题包含有多种可能情况，并难以统一处理时，就需按所有可能出现的各种情况分类进行讨论，得出各种情况的相应结论，最后综合总结出问题的正确解答，这种方法称为分类法。 分类构造是分类的思想与构造法相
9、结合的产物，简单说来，就是在分类的基础上进行构造。分类构造的步骤如下：对问题进行分类针对每一类进行构造合成整个问题的解分析问题性质 分类的各种思想在这里同样可以得到很好的应用，如按照剩余系分类（奇偶分类）、按照数据大小分类、按照题目中所涉及到的定义概念分类、按照参数的变化等等。 IOI2002冬令营讲稿冬令营讲稿例三：棋盘遍历问题（例三：棋盘遍历问题（1 1）有一个n*n的正方形，某人从(x，y)出发，要求出一条符合要求的路线，经过每个格子一次且仅一次。路线尽可能简单，转弯尽可能少迂回状折线左图是n=4，x=2，y=2的情况特点：在边界处的方向与n、x、y的奇偶性有关IOI2002冬令营讲稿冬
10、令营讲稿例三：棋盘遍历问题（例三：棋盘遍历问题（2 2）n是偶数，不妨设x、y均为奇数，否则适当地旋转、翻转棋盘。 一旦n、x、y的奇偶性确定，路线在边界处的情况就可以唯一确定IOI2002冬令营讲稿冬令营讲稿例三：棋盘遍历问题（例三：棋盘遍历问题（3 3）n为奇数i.x、y奇偶性相同，不妨设x、y均为偶数，否则适当地旋转、翻转棋盘IOI2002冬令营讲稿冬令营讲稿例三：棋盘遍历问题（例三：棋盘遍历问题（4 4）n为奇数ii.x、y奇偶性不同，此时问题无解iii.先对棋盘进行黑白二染色，如左图n为奇数遍历棋盘要走奇数步终止点是黑格x为奇数、y为偶数出发点是白格黑格数=白格数n为奇数黑格数=白格
11、数+1矛盾IOI2002冬令营讲稿冬令营讲稿例三：小结例三：小结本题的分类并不是凭空得来的，而是基于“迂回性折线”的特点。这种路线到了边界处会出现不同的情形，需要我们区别对待。构造的分类标准构造的分类标准与与选择的构造方法选择的构造方法息息相关息息相关。BackIOI2002冬令营讲稿冬令营讲稿归纳构造归纳构造这里所说的归纳就是指数学归纳法。数学归纳法一直被人们津津乐道，因为有限的几步，跨越了无限的空间。它被频繁采用并衍生出多种形式：如第二归纳法、多起点归纳法、曲线归纳法等等。 归纳构造利用了归纳的思想，是构造法的一个经典的实现形式。在竞赛中，采用得比较普遍的仍然是一般归纳法+构造法的形式。在
12、这里，我们概括出这种方法一般的步骤如下：构 造 i=1的情况假设i=j已经构造出来，构造i=j+1的情况利用归纳法，推广到i=n的情况IOI2002冬令营讲稿冬令营讲稿例四：赛程安排问题（例四：赛程安排问题（1 1） 有2m个选手，每一天安排若干场比赛，且每个选手每天仅可以参加一场比赛，试给出一种赛程的安排表，使得在2m-1天内任意两个选手都至少比赛过一场。 第一天第二天第 2m-1天第2m天选手1选手2选手2m-1选手2m分析：将赛程表设计成如下2m*2m的矩阵(除去第一行），记为Pm。IOI2002冬令营讲稿冬令营讲稿例四：赛程安排问题（例四：赛程安排问题（2 2）容易知道，这个矩阵有以下
13、几个特点：1)第i行第一列的数为i，2)第i行的数的并集等于1，2，3，2m3)第j列的数的并集等于1，2，3，2m4)若第i行第j列的数字为k，那么第k行第j列的数字为i。 采用归纳构造的基本思想是：首先构造出Pm，在Pm的基础上构造出Pm+1。 Pm+1是一个2m+1*2m+1的矩阵，启发我们将它均分成四个2m*2m的矩阵，实现从Pm到Pm+1的过渡。为了适应规模的增大，对于Pm中的元素进行适当的加减运算。IOI2002冬令营讲稿冬令营讲稿例四：赛程安排问题（例四：赛程安排问题（3 3）ABCD设Pm已经填好，将Pm+1均分为四份A、B、C、D。令A=D=Pm，B=C=Pm+2m（表示把P
14、m中的元素都加上2m后形成的新矩阵）。可以验证，这样构造出来的矩阵仍然满足要求1）、2）、3）、4）。根据这张表可以给出相应的赛程安排。PmPm+2mPm+2mPmPm+1=IOI2002冬令营讲稿冬令营讲稿例四：赛程安排问题（例四：赛程安排问题（4 4） 有2n个选手参加比赛。已知两个选手比赛时总是强的一方胜，且不会出现某两个选手一样强的情况。每个选手每天至多同一个对手比赛。试给出一种赛程的安排表，使得在n*(n+1)/2天内确定所有选手的强弱。 分析：为了方便起见，用AB表示选手A比选手B强。 首先尝试一般的归纳构造： 设结论对于n成立，考虑n+1时，共2n+1名选手分为两个组A、B，每组
15、2n个人，由归纳假设，只需n*(n+1)/2天即可确定两个组各自的顺序，假设已经排 成 ： A1A2A3A2n， B1B2B3B2n， 那 么 现 在 要 在(n+1)*(n+2)/2-n*(n+1)/2=n+1天内完成两个组的合并。 这一步是整个问题的关键所在，也是问题的瓶颈！IOI2002冬令营讲稿冬令营讲稿例四：赛程安排问题（例四：赛程安排问题（5 5） 问题转化为： 已已知知A A1 1AA2 2AA3 3AA2 2n n，B B1 1BB2 2BB3 3BB2 2n n，在在n+1n+1天天之之内内确确定定这这2 2n+1n+1个个人人的的顺序。顺序。 这一步仍然需要采用归纳法来解决
16、。经过许多次尝试，我们发现一般的归纳构造在“分合”这一步上都无法胜任。想到数学归纳法的一个常用技巧加强命题加强命题！命题加强为： k+l=2k+l=2n n（k k、l l、n n均为正整数），已知均为正整数），已知A A1 1AA2 2AA3 3A Ak k，B B1 1BB2 2BB3 3B Bl l，决定这决定这2 2n n名选手强弱只需名选手强弱只需n n天。天。 上述命题仍然可以采用归纳构造来解决。IOI2002冬令营讲稿冬令营讲稿例四：赛程安排问题（例四：赛程安排问题（6 6）当n=1时，k=l=1，安排A1B1，结论显然成立。假设对于n时已经有了安排方法，考虑n+1的情况。不妨设
17、kl，k+l=2n+1。安排第一天的比赛如下： 设Aj是编号最小的负于对手的选手，即A1、A2、Aj-1都取胜，Aj、Aj+1、Ak都负于对手。可以推出结论： A1A2Aj-1B2n-j+2 B2n-j+3B2n-1 B2nBl B1B2B2n-j+1AjAj+1AkIOI2002冬令营讲稿冬令营讲稿例四：赛程安排问题（例四：赛程安排问题（7 7）把这2n名选手分为两组：强组：A1A2Aj-1，B1B2B2n-j+1共2n名。弱组：AjAj+1Ak，B2n-j+2 B2n-j+3B2n-1 B2nBl，共2n名。 容易看出，强组中的任一人均比弱组中的任一人强。 由归纳假设，两组均只需n天（并列
18、进行）就可以确定组内的强弱，又由于强组全体排在弱组前，故整体名次也确定。加上初始时用的一天时间，总共n+1天，这2n+1名选手名次确定，结论对于n+1时也成立。 加强后的结论成立，故之前的结论也成立。回到原来的问题，就很容易解决了。由上述结论推出，A1A2A3A2n，B1B2B3B2n，只需n+1天就可以合并这两个组。总共需要的天数为n*(n+1)/2+(n+1)=(n+1)*(n+2)/2，即n+1时也可以完成赛程安排。IOI2002冬令营讲稿冬令营讲稿例例四：小结四：小结 上面的两个赛程安排问题都是运用归纳构造的典型。前者很容易就能实现从m-1到m的过渡，但后者则需要加强命题，并两次使用归纳构造。 加强命题是数学中一种常用的方法，在加强结论的同时，归纳假设的条件也增强了，为解题铺平了道路。构造中综合运用数学的各种方法构造中综合运用数学的各种方法Back
