李天翼 从特殊情况考虑.pptVIP

从特殊情况考虑 复旦附中 李天翼 引子 从特殊情况考虑是一种重要的数学思想。 在算法设计中，巧妙地运用这一思想，可以取得事半功倍的效果。 问题一 (POI 03-04 Bra 改编) 问题描述 如图，给定n个门,分别编号为0至n-1。每个门可能有多个输入端，但只有一个输出端。 问题一 问题描述（续） 编号为0和1的门没有输入端，0号门始终输出0，1号门始终输出1。对于其它的门，它的输入信号中 0的个数比1的个数多时，它输出0； 1的个数比0的个数多时，它输出1； 0的个数和1的个数一样多时，它输出1/2； 保证存在符合要求的输出状态。 给定一个电路，要求尽可能多地确定每个门的输出结果。 问题一 初步思考 令Cj,i表示i号门的所有输入端中，来自j号门输出端的数量。设P(i)为i号门的输出状态。 问题一 初步思考（续） 令 ， 问题一 考虑极端情况 令Pmin(i) 和Pmax(i)分别为P(i)在所有可能的电路中能取到的最小值和最大值，它们是P(i)的极端情况。 显然，若Pmin(i)=Pmax(i) (0≤i≤n-1)，则i号门的输出状态是固定的，否则就不是固定的。 因此，我们只需要求出Pmin(i)和Pmax(i)。 问题一 一个想法 如果P(k)变大，那么所有的U(i)(0≤i≤n-1)也只能变大，而不可能变小，而对应的P(i)也是如此。 令P(i)= Pmin(i) (0≤i≤n-1)，可以得到，此时的输出状态是符合要求的。 问题一 Pmin(i)的求法 不妨先将所有的门的输出状态都标为0，此时只有1号门不正确。从1号门开始，将它的输出状态改为1。然后不断找到矛盾所在，进行迭代。由于每个门的状态最多变两次（0变1/2，1/2变1），每个门的输入的总数不超过200000，因此在不超过2*200000 =400000次迭代后，迭代就会中止。迭代终止时，有P(i)= Pmin(i) (0≤i≤n-1)。 类似的，也可以求得Pmax(i)(0≤i≤n-1)。 问题一 小结 极端情况是特殊情况的一种表现形式。题目中的许多性质，往往会通过一些具有极端性质的对象（比如本题中的极值）表现出来。这就使得我们可以以它们为重点考察对象，来寻找突破口和答案。 问 题 二 (POI 04-05 Sko 改编) 骑士在一个无限大的坐标平面上移动。他能够执行的每种移动可以用一对整数(a,b)来描述，这表示骑士可以从(x,y)移动到(x+a,y+b)或(x-a,y-b) 问 题 二 题目描述（续） 对于每个骑士，从原点出发所能够到达的点，不全在一条直线上 给定一个骑士和一些点，问这个骑士从原点出发，能到达这些点中的哪几个。 为了讨论方便，设给定骑士的第k种移动为(ak,bk)。将一个骑士从原点出发，能够到达的点称为该骑士的可行点。一个骑士的可行点的集合称为该骑士的可行点集。 问 题 二 考虑一维情况 棋盘是二维的，我们不妨先考虑比较简单的一维情况。 此时，每个骑士都在一条直线上移动，他的第i种移动(1≤i≤n)可以表示为一个整数(ai)，令r=(a1,a2,……,an)，则他能够到达横坐标为X的点的充要条件是r|X。 问 题 二 回归二维情况 对于不退化的二维情况（即骑士所能够到达的点，不全在一条直线上），可以猜想他的可行点集与满足下列三个条件之一的所有点的集合相同。 (1)r|X+Y(2)r|X+qY(3)r|pX+qY(p,q,r均为待定整数，r≠0)。 通过对简单情况的验证，易知前两种假设是错误的。对于最后一种假设，由于参数比较多，一时难以判断其是否正确。 问 题 二 猜想 设S(p,q,r)为所有满足r|pX+qY(p,q,r均为整数，r≠0)的点的集合。 考虑猜想：对于不退化的二维情况（即骑士所能够到达的点，不全在一条直线上），存在整数p,q,r，r≠0，满足骑士的可行点集与S(p,q,r)相同。 问 题 二 猜想的简化 由于n的上限是100，比较大，可以先考虑比较简单的n=2(n=2是最小的非退化情况)。可以用数学归纳法证明，只需要讨论n=2。 证明要点： 假设只有前k种移动的骑士的可行点集与S(p,q,r0)相同，设r=(pak+1+qbk+1,r0)那么有全部k+1种移动的骑士的可行点集与S(p,q,r)相同。 问 题 二 对n2的处理 假设当n=k（k为任意正整数）时猜想成立，当n=k+1时，设只有前k种移动的骑士的可行点集与S(p,q,r