算法合集之《构造——解题的最短路径法》.ppt

构造——解题的最短路径法
构造法——解题的“最短路径”
构造法及其特点
常用的构造法
构造法的优、缺点
Back
构造法及其特点
什么叫构造法:
直接列举出满足条件的对象或反例,导致结论的肯定与否定,间接构造某种对应关系,使问题根据需要进行转化的方法。
构造法绝不是简单的尝试,也不是一时的运气
构造法使用的前提:存在性
构造法特别适用于竞赛中求单个可行解的题目
Back
常用的构造法
直接构造
分类构造
归纳构造
Back
构造法的优、缺点
优点:
时空复杂度小,编程复杂度小
缺点:
思维复杂度大
Back
直接构造
一种直接对目标对象进行考察的构造方法。
探索是直接构造的灵魂,在构造的背后,往往隐蔽着反反复复的尝试。
实际应用中,首先对于目标对象进行观察,发现一般性的规律,加以概括总结后运用至构造中。
在熟悉的事物中寻找,在特殊的事物中寻找,接合目标,不断地调整甚至改变方案,直至实现构造
例一:三臂起重机(1)
给出了三个数p、q、n,要构造若干个三元组,符合以下四个要求:
(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个自然数。 n≤300000,p+q≤60000。
例一:三臂起重机(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,5)
(3,4,7)
(6,9,10)
(8,11,12)
……
容易得出下面类似贪心的方法:
设已经构造了s个三元组(x1,y1,z1)、(x2,y2,z2)、……(xs,ys,zs),满足x1<x2<……<xs。
取上面s个三元组中没有出现过的最小自然数r
r+p没有出现过(xs+1,ys+1,zs+1)=(r,r+p,r+p+q)
r+p出现过(xs+1,ys+1,zs+1)=(r,r+q,r+p+q)
例一:三臂起重机(3)
这个方法马上被下面的例子推翻:
p=3,q=2
(1,4,6)
(2,5,7)
(3,?,8)
?处无论填5还是6均已出现过
但是如果换一种填法:
p=2,q=3
(1,3,6)
(2,4,7)
(5,8,10)
(9,11,14)
……
交换一下p、q的位置,再应用上面的填法
启发我们,应用上述填法的条件是:p≤q,即当p>q时,先交换p、q的位置。这仅仅是一个猜想,需要经过实践以及证明。
经过许多尝试,这种构造法仍然满足要求。因此,我们猜测本题完整的构造方法如下:
例一:三臂起重机(4)
若p>q,则交换p、q的值,不影响构造的结果。
设已经构造了s个三元组(x1,y1,z1)、(x2,y2,z2)、……(xs,ys,zs),满足x1<x2<……<xs。
取上面s个三元组中没有出现过的最小自然数r
r+p没有出现过(xs+1,ys+1,zs+1)=(r,r+p,r+p+q)
r+p出现过(xs+1,ys+1,zs+1)=(r,r+q,r+p+q)
从题面上看来,p、q的位置应当是对称的,为什么会需要假设“p≤q”的情况呢?