当前位置:首页 >> 学科竞赛 >>

day2基础算法noip培训


基础算法策略
长沙市第一中学 曹利国

算法效率的评价
? ?

算法的评估 有时求解同一个问题常常有多种可用的 算法,在一定的条件下当然要选择使用 好的算法。用什么方法评估算法的好坏 呢?通常使用算法复杂性这一概念来评 估算法。

算法评价
?

算法执行时间需通过

依据该算法编制的 程序在计算机上运行时所消耗的时间来 度量。而度量一个程序的执行时间通常 有两种方法:
? ?

事后统计的方法 事前分析估算的方法

算法评价
?

一个用高级程序语言编写的程序在计算机上运 行时所消耗的时间取决于下列因素: ① 依据的算法选用何种策略; ② 问题的规模.例如求100以内还是1000以内的 素数; ③ 书写程序的语言.对于同一个算法,实现语言 的级别越高,执行效率就越低; ④ 编译程序所产生的机器代码的质量; ⑤ 机器执行指令的速度。

算法评价
?

?

一个算法是由控制结构(顺序、分支和循环三种)和 原操作(指固有数据类型的操作)构成的,则算法时 间取决于两者的综合效果。 为了便于比较同一问题的不同算法,通常的做法是, 从算法中选取一种对于所研究的问题(或算法类型) 来说是基本运算的原操作,以该基本操作重复执行的 次数作为算法的时间度量。

算法评价
?

?

一般情况下,算法中基本操作重复执行的 次数是问题规模 n 的某个函数 f ( n ),算 法的时间量度记作 T(n)= O(f(n)) 它表示问题规模 n 的增大,算法执行时间 的增长率和f(n)的增长率相同,称作算 法的渐进时间复杂度,简称时间复杂度。

算法评价
?

?

例如:在下列三个程序段中, ① x:=x+1 ② for i:=1 to n do x:=x+1; ③ for j:=1 to n do for k:=1 to n do x:=x+1 含基本操作“x增1”的语句x:=x+1的频度分别为1,n 和 n2 ,则这三个程序段的时间复杂度分别为O(1 ), O ( n ), O ( n2 ),分别称为常量阶、线性阶 和平方阶。

算法评价
?

算法还可能呈现的时间复杂度有:对数阶 O ( log n ),指数阶 O ( 2n )等。在 n 很大时 , 不同数量级时间复杂度显然有 O ( 1 ) <O ( log n)<O(n)<O(nlog n)<O(n2)< O( n3)<O(2n),可以看出,在算法设计时, 我们应该尽可能选用多项式阶O(nk)的算法, 而不希望用指数阶的算法。

算法评价
?

?

由于算法的时间复杂度考虑的只是对于问题规模 n 的增长率,则在难以计算基本操作执行次数 ( 或语 句频度)的情况下,只需求出它关于 n的增长率或阶 即可。 例如,在下列程序段中: for i:=2 to n do for j:=2 to i-1 do x:=x+1 语句x:=x+1执行次数关于n的增长率为n2,它是语句 频度表达式(n-1)(n-2)/2中增长最快的一项。

算法评价
?

?

类似于算法的时间复杂度,以空间复杂度作为 算法所需存储空间的量度,记作 S(n)=O(f(n)) 其中n为问题的规模(或大小)。一个上机执行的 程序除了需要存储空间来寄存本身所用指令、 常数、变量和输入数据外,也需要一些对数据 进行操作的工作单元和存储一些为实现计算所 需信息的辅助空间。

算法评价
评价一个数学模型有以下几个原则: 1.时间复杂度 一个好的算法一般效率比较高。在竞赛 中,试题常常会做一些算法运行时间上的限 制。这就要求我们所建立的数学模型对应算 法的效率一定要符合要求。这也是最重要的 一个原则。
?

算法评价
?

2.空间复杂度 出于计算机自身的限制,程序在运行时一 般只被提供有限的内存空间。这也就要求我们 建立模型时顾及到这一点。但对于模型对应的 算法来说,并不是要求空间越低越好,只要不 超过内存限制就可以了。

算法评价
?

3.编程复杂度 相对而言,“编程复杂度”的要求 要略低一些。但是在竞赛中,如果建立 的算法实现起来十分繁琐,自然不利于 比赛。所以,在建立模型时(特别是在 竞赛中)这点也要纳入考虑之中。

算法评价
?

一道题目可能对应几种不同思想的模型, 就要根据评价模型的标准来衡量一下,确 定一个模型作为分析方向。这时的评价标 准除了上述的时间、空间、编程复杂度三 个标准外,还要加上一个思维的复杂度。

算法评价
?

所谓思维的复杂度,是指思考所耗费的时间和 精力。如果我们确定了一个模型作为分析的方 向(没有考虑思维复杂度),从问题原型到该 数学模型的建模过程却十分复杂,导致思维耗 费时间长,精力多,那自然是不合算的。总的 来说,对于多种数学模型的选择,我们遵循“ 边分析,边选择”的原则。

影响算法效率的因素
? ?

问题的算法模型的建立 问题的数据结构选择

第一部分

枚举策略

枚举策略的基本思想
?

枚举法,又称穷举法,指在一个有 穷的可能的解的集合中,一一枚举 出集合中的每一个元素,用题目给 定的检验条件来判断该元素是否符 合条件,若满足条件,则该元素即 为问题的一个解;否则,该元素就 不是该问题的解。

枚举策略的基本思想
?

?

枚举方法也是一种搜索算法,即对问题 的所有可能解的状态集合进行一次扫描 或遍历。在具体的程序实现过程中,可 以通过循环和条件判断语句来完成。 枚举法常用于解决“是否存在”或“有 多少种可能”等类型的问题。例如,求 解不定方程的问题就可以采用列举法。

虽然枚举法本质上属于搜索策略,但是它与回溯法有所不同。因为适用 枚举法求解的问题必须满足两个条件: ⑴可预先确定每个状态的元素个数n;
⑵状态元素a1,a2,…,an的可能值为一个连续的值域。


ai1— 状 态 元 素 ai 的 最 小 值 ; aik— 状 态 元 素 ai 的 最 大 值 (1≤i≤n) , 即 a11≤a1≤a1k,a21≤a2≤a2k, ai1≤ai≤aik,……,an1≤an≤ank

for a1←a11 to a1k do
fo a2←a21 to a2k do for ai←ai1 to aik do …………………… ……………………

for an←an1 to ank do
if 状态(a1,…,ai,…,an)满足检验条件 then 输出问题的解;

枚举策略的基本思想
?

枚举法的特点是算法比较简单,在用枚 举法设计算法时,重点注意优化,减少 运算工作量。将与问题有关的知识条理 化、完备化、系统化,从中找出规律, 减少枚举量。

枚举方法的优化
枚举算法的时间复杂度:状态总数*单个状态的耗时 ? 主要优化方法: ⑴ 减少状态总数 ⑵ 降低单个状态的考察代价 ? 优化过程从以下几个方面考虑: ⑴ 枚举对象的选取 ⑵ 枚举方法的确定 ⑶ 采用局部枚举或引进其他算法

巧妙填数
?

将1~9这九个数字填入九个空格中。每一横行 的三个数字组成一个三位数。如果要使第二行 的三位数是第一行的两倍, 第三行的三位数是 第一行的三倍, 应怎样填数。如图
1 9 2

3 5

8 7

4 6

分析
?

?

本题目有9个格子,要求填数,如果不考虑问题给出的 条件,共有9!=362880种方案,在这些方案中符合问 题条件的即为解。因此可以采用枚举法。 但仔细分析问题,显然第一行的数不会超过400,实际 上只要确定第一行的数就可以根据条件算出其他两行 的数了。这样仅需枚举400次。

算式
设有下列的算式:
208 ------------□□ ) □□□□ □□ ------------□□□ □□□ ------------1

要求:求出□中的数字,并打印出完整的算式。

枚举方法的优化
【分析】此题找不到很好的方法,于是考 虑枚举法。 ?本题中,待填数字的空格共有14个,每个 格子中都可填0..9这10个数字。若对14个 格子都进行0..9十个数字逐一枚举,枚举量 是1014,不可能在指定的时间内得出结果。 ?优化方法:减少枚举量,找出适当的元素 进行枚举。

枚举方法的优化
由数学知识知道,在除法中只要知道被除 数、除数、商和余数中的任意三部分就可 以求得第四部分。本题已知商和余数,只 要知道被除数或除数,整个算式也就确定 下来了。而被除数和除数,分别是4位数和 2位数。我们只需枚举除数。枚举量降为 102=100,这个时间复杂度是完全可以承 受的。
?

方格填数
方格填数问题。 ?如图所示形状的八个 方格中填入1-8这八个 数字,使得相邻的和对 角线上的数字之差不为 1,编程求解所有的填 法方案和总数。
B1

B2 B5

B3 B6
B8

B4 B7

枚举方法的优化
【分析】将1至8填入到B1至B8中,总共有8!=

40320种填法。该问题的枚举总量为8!个。 由于B3和B6这两个方格与其相邻的格子共有6个 ,放入这两个格子中的数,必须和六个数不连续 ,这样的两个数只有1和8。B1,B3,B6,B8这 四个格子中仅仅有两种可能放法,即:2,8,1 ,7和7,1,8,2。挖掘出这一隐含条件之后, B2,B4,B5,B7四个格子中的数就只能从3,4 ,5,6这四个数中进行选择,整个问题的枚举总 量将变得只有2*4!=48种,从而大大地减少了 枚举量,提高枚举效率。

枚举算法的应用
二进制数的分类 若将一个正整数转化为二进制数后,0的个数多于 1的个数的这类数称为A类数,否则称为B类数。 例如: (13)10=(1101)2, 13为B类数; (10)10=(1010)2 10为B类数; (24)10=(11000)2 24为A类数; 程序要求:求出1~1000之中(包括1与1000), 全部A、B两类数的个数。

枚举算法的应用
?

【分析】此题是一道统计类题目。解决

统计问题的一个常用方法是枚举法:逐一 枚举所有情况,同时进行统计,枚举结束 时,统计也完成,得到结果。 ?具体对本题而言,采用枚举法的正确性与 可行性是显然的,而本题的数据规模又仅 为1~1000,所以采用逐一枚举方法进行 统计的时间复杂度是完全可以接受的。

01统计
?

将问题的数据规模扩充到求1到m(m<=1030) 中A类数的个数。

分析
?

?

本题是统计问题,但使用1~m的循环来逐个 判断显然耗时过多,对于m较大时无法在规定 的时间内出解。所以我们希望通过分类统计 的方法,进一步抽象问题,得到可行的算法: 根据二进制数的前缀来分类是合理的,既没 有重复也没有遗漏。当m的二进制数长度为n 时,最多有2n种类型,即2(log2m +1) 种 ,比穷举m种类型有了很大进步。

?

设m=(112)10=(1110000)2,求1~m的A类数个数。可以将112 个数分为以下几类:

?

数字形式为(111xxxx)2
这一类数只有1个,即(1110000)2,是A类数

?

数字形式为(110xxxx)2
设4个填数位置填0的个数为S0,填1的个数为S1,则S0 + S1 + 3 = 7,若为A类数,则S0 + 1 > S1 + 2,可以取S0 = 4 S1 = 0;S0 = 3 S1 = 1.这一类数中的A类数个数:(4 4)

+ (3 4)

?
? ?

数字形式为(10xxxxx)2

设5个填数位置填0的个数为S0,填1的个数为S1,则S0 + S1 + 2 = 7 若为A类数,则S0 + 1 > S1 + 1,可以取S0 = 5 S1 = 0;S0 = 4 S1 = 1;S0 = 3 S1 = 2.这一类数中的A类数个数: (55) + (45) + (35)

?
?

数字形式为(0xxxxxx)2

? ? ? ? ?

这一类数字的分析与前几类略有不同,因为前几类二进制数的位数都是7,而 这一类数还需对位数进行讨论: (1)1位数,即(1)2,不是A类数 (2)2位数,即(1x)2,(10)2和(11)2都不是A类数 (3)3位数,即(1xx)2,A类数个数为(22) =1 (4)4位数,即(1xxx)2,A类数个数为(33) =1 (5)5位数,即(1xxxx)2,A类数个数为 (44)+ (34)=5

枚举对象的确定
圆桌骑士(IOI试题) 在一个8*8的棋盘上,有一个国王和若干 个武士。其中,国王走一字步,骑士走 马步。若国王与骑士相会在同一点上, 国王可以选择让骑士背他走。求一个点, 使所有的骑士和国王相距在这个点上的 所走的步数最少。

枚举算法的应用

【分析】此题可从3个方面考虑: 分治、枚举、数学方法。 ? 由于无法将这个问题划分为各自独立的小问题来 解决,分治显然是不行的。又因武士和国王位置 的不固定性和其走法的差异,推导不出一个数学 公式。因此考虑使用枚举,需要枚举的三个要点: 1、最后的汇聚点。 2、国王与背他的骑士的汇聚点。 3、国王与背他的骑士。

枚举算法的应用
?

?

国王最多只会与一个骑士结合,因为骑士的最终 目标也是最终汇聚点,一旦国王与某个骑士汇合 后,即马上可与其结合,剩下的只需要将所有的 骑士汇合就可以了。更没有必要在中途中有将国 王托付给其他的骑士。 这样我们估算一下时间 为O(8*8*8*8*63)=O(36*10^4),完全可 以承受。 另外,我们需要预先将2点之间走马字步的距离 计算出来。可以使用Floyd或是Bfs。

?

算法流程:
dis[x1,y1,x2,y2]--(x1,y1)(x2,y2)之间的距离。 For I:=1 to 8 do{枚举汇合点} For j:=1 to 8 do begin All :=所有骑士到这一点的和; Best:=min(best,all+国王到汇聚点的步数) For x:=1 to 8 do {枚举武士国王的相会点} For y:=1 to 8 do begin For kk:=1 to k do {枚举与国王结合的武士} If dis[knight[kk].x,knight[kk].y,x,y]<min then begin Min:= dis[knight[kk].x,knight[kk].y,x,y]; Mink:=k; End; End; Now:= all-mink武士走到汇合点的距离+ mink武士走到汇聚 点的距离+ 国王走到汇聚点的距离+从汇聚点到汇合点的距离; Best:=min(best,now) End;

局部枚举
例题:求第一、第二、第三最短路问题

局部枚举
例题:新年好 重庆城里有n个车站,m条双向公路连接其 中的某些车站。每两个车站最多用一条公路 直接相连,从任何一个车站出发都可以经过 一条或多条公路到达其他车站,但不同的路 径需要花费的时间可能不同。在一条路上花 费的时间等于路径上所有公路需要的时间之 和。

?

佳佳的家在车站1,他有五个亲戚,分别 住在车站a,b,c,d,e。过年了,他需要从 自己的家出发,拜访每个亲戚(顺序任 意),给他们送去节日的祝福。怎样走, 才需要最少的时间?

分析
这一题中的边数远小于n2,所以复杂度也 只有nlogn+m 算法框架是: (1)用5次最短路,计算出6个点两两之 间的距离 (2)枚举5个结点的全排列,找到一个使 得总路程长度最短的方案。

第二部分

递推策略

递推的概念与基本思想
给定一个数的序列H0,H1,…,Hn,…若存在 整数n0,使当n>n0时,可以用等号(或大 于号、小于号)将Hn与其前面的某些项 Hi(0<i<n)联系起来,这样的式子就叫 做递推关系。

解决递推问题的一般步骤
? ?

?

建立递推关系式 确定边界条件 递推求解

递推的形式
?

顺推法和倒推法

递推的应用分类
?
? ? ?

一般递推问题 组合计数类问题 一类博弈问题的求解 动态规划问题的递推关系

递推的应用(一般递推问题)
例题1 : Hanoi塔问题 . Hanoi塔由n个大小不同的圆盘和三根木柱a,b,c组成。开始时, 这n个圆盘由大到小依次套在a柱上,如图1所示。要求把a柱上n 个圆盘按下述规则移到c柱上:
(1)一次只能移一个圆盘; (2)圆盘只能在三个柱上存放; (3)在移动过程中,不允许大盘压小盘。

问将这n个盘子从a柱移动到c柱上,总计需要移动多少个盘次? a b c

递推的应用(一般递推问题)
例题1 : Hanoi塔问题 . Hanoi塔由n个大小不同的圆盘和三根木柱a,b,c组成。开始时, 这n个圆盘由大到小依次套在a柱上,如图1所示。要求把a柱上n 个圆盘按下述规则移到c柱上:
(1)一次只能移一个圆盘; (2)圆盘只能在三个柱上存放; (3)在移动过程中,不允许大盘压小盘。

问将这n个盘子从a柱移动到c柱上,总计需要移动多少个盘次? a b c

分析
?

设hn为n 个盘子从a柱移到c柱所需移动的盘次。显然,当 n=1时,只需把a 柱上的盘子直接移动到c柱就可以了,故 h1=1。当n=2时,先将a柱上面的小盘子移动到b柱上去;然 后将大盘子从a柱移到c 柱;最后,将b柱上的小盘子移到c 柱上,共记3个盘次,故h2=3。以此类推,当a柱上有 n(n>=2)个盘子时,总是先借助c柱把上面的n-1个盘子移动 到b柱上,然后把a柱最下面的盘子移动到c柱上;再借助a 柱把b柱上的n-1个盘子移动到c柱上;总共移动hn-1+1+hn-1 个盘次。
∴hn=2hn-1+1 边界条件:h1=1

?

?

递推的应用(一般递推问题)
例2:实数数列 一个实数数列共有n项,已知 ai=(ai-1-ai+1)/2+d,(1<i<n) (n<60) 键盘输入n,d,a1,an,m,输出am。 输入数据均不需判错。

分析
根据公式ai=(ai-1-ai+1)/2+d 变形得,ai+1=ai-1-2ai+2d,因此 该数列的通项公式为:ai=ai-2-2ai-1+2d,已知a1,如果能求 出a2,这样就可以根据公式递推求出am
∵ ai=ai-2-2ai-1+2d ……(1) =ai-2-2(ai-3-2ai-2+2d)+2d =-2ai-3+5(ai-4-2ai-3+2d)-2d =5ai-4-12ai-3+8d ……

一直迭代下去,直到最后,可以建立ai和a1与a2的关系式。

分析
设ai=Pia2+Qid+Ria1,我们来寻求Pi,Qi,Ri的变化规律。 ∵ ai=ai-2-2ai-1+2d ∴ ai=Pi-2a2+Qi-2d+Ri-2a1-2(Pi-1a2+Qi-1d+Ri-1a1)+2d =(Pi-2-2Pi-1)a2+(Qi-2-2Qi-1+2)d+(Ri-2-2Ri-1)a1 ∴ Pi=Pi-2-2Pi-1 ……② Qi=Qi-2-2Qi-1+2 ……③ Ri=Ri-2-2Ri-1 ……④ 显然,P1=0 Q1=0 R1=1 (i=1) P2=1 Q2=0 R2=0 (i=2) 将初值P1Q1R1和P2Q2R2代入②③④可以求出PnQnRn ∵ an=Pna2+Qnd+Rna1 ∴ a2=(an-Qnd+Rna1)/Pn 然后根据公式①递推求出am,问题解决。

改进算法
但仔细分析,上述算法有一个明显的缺陷:在求由于在求a2要运用除法,因 此会存在实数误差,这个误差在以后递推求am的过程又不断的扩大。在 实际中,当m超过30时,求出的am就明显偏离正确值。显然,这种算法虽 简单但不可靠。 为了减少误差,我们可设计如下算法: ∵ ai=Pia2+Qid+Ria1 =Pi-1a3+Qi-1d+Ri-1a2 =Pi-2a4+Qi-2d+Ri-2a3 …… =Pi-2+kak+Qi-2+kd+Ri-2+kak-1 ∴ an=Pn-k+2ak+Qn-k+2d+Rn-k+2ak-1 ak=(an-Qn-k+2d+Rn-k+2ak-1)/Pn-k+2 ……⑤ 根据公式⑤,可以顺推a2、a3、…、aM。虽然仍然存在实数误差,但由于Pnk+2递减,因此最后得出的am要比直接利用公式①精确得多。

递推的应用(一般递推问题)
例题:贮油点。 一辆重型卡车欲穿过1000公里的沙漠,卡车耗汽油为1升/公 里,卡车总载油能力为500公升。显然卡车装一次油是过不了 沙漠的。因此司机必须设法在沿途建立若干个贮油点,使卡车 能顺利穿过沙漠。试问司机如怎样建立这些贮油点?每一贮油 点应存储多少汽油,才能使卡车以消耗最少汽油的代价通过沙 漠? ? 编程计算及打印建立的贮油点序号,各贮油点距沙漠边沿出发 的距离以及存油量。格式如下:
? ? ? ?

No. Distance(k.m.) 1 × × 2 × × … ……

Oil(litre) ×× ×× ……

分析
? ? ?

?

设Way[i]——第i个贮油点到终点(i=0)的距离; oil[i]——第i个贮油点的贮油量; 我们可以用倒推法来解决这个问题。从终点向始点倒推 ,逐一求出每个贮油点的位置及存油量。 从贮油点i向贮油点i+1倒推的方法是:卡车在贮油点i和 贮油点i+1间往返若干次。卡车每次返回i+1点时应该正 好耗尽500公升汽油,而每次从i+1点出发时又必须装足 500公升汽油。两点之间的距离必须满足在耗油最少的 条件下,使i点贮足i*500公升汽油的要求(0≦i≦n-1) 。

倒推第一步

?

?

第一个贮油点i=1应距终点i=0处500km,且在 该点贮藏500公升汽油,这样才能保证卡车能由 i=1处到达终点i=0处,这就是说 Way[1]=500;oil[1]=500;

倒推第二步
为了在i=1处贮藏500公升汽油,卡车至少从I=2处开两趟 满载油的车至i=1处,所以i=2处至少贮有2*500公升汽油 ,即oil[2]=500*2=1000;另外,再加上从i=1返回至i=2 处的一趟空载,合计往返3次。三次往返路程的耗油量按 最省要求只能为500公升,即d1,2=500/3km, Way[2]=Way[1]+d1,2=Way[1]+500/3

倒推第三步
?

?

为了在I=2处贮藏1000公升汽油,卡车至少从I=3处开三 趟满载油的车至I=2处。所以I=3处至少贮有3*500公升 汽油,即oil[3]=500*3=1500。加上I=2至I=3处的二趟 返程空车,合计5次。路途耗油亦应500公升,即 d23=500/5, Way[3]=Way[2]+d2,3=Way[2]+500/5;

倒推第k步
? ?

?

…… 为了在i=k处贮藏k*500公升汽油,卡车至少从i=k+1处开 k趟满载车至i=k处,即oil[k+1]=(k+1)*500=oil[k]+500 ,加上从i=k返回i=k+1的k-1趟返程空间,合计2k-1次。 这2k-1次总耗油量按最省要求为500公升,即 dk,k+1=500/(2k-1) Way[k+1]=Way[k]+dk,k+1=Way[k]+500/(2k-1);

i=n的情形
?

i=n至始点的距离为1000-Way[n],oil[n]=500*n。为了在 i=n处取得n*500公升汽油,卡车至少从始点开n+1次满载车 至I=n,加上从I=n返回始点的n趟返程空车,合计2n+1次, 2n+1趟的总耗油量应正好为(1000-Way[n])*(2n+1),即 始点藏油为oil[n]+(1000-Way[n])*(2n+1)。

递推的应用(组合计数)
Catalan数
定义:一个凸n边形通过不相交于n边形内部 的对角线把n边形拆分成若干三角形的不同 拆分数。

分析
?

设Cn表示凸n边形的拆分方案总数。由题目中的要求可知一个 凸n边形的任意一条边都必然是一个三角形的一条边,边P1 Pn 也不例外,再根据“不在同一直线上的三点可以确定一个三 角形”,只要在P2,P3,……,Pn-1点中找一个点Pk(1<k<n), 与P1、Pn 共同构成一个三角形的三个顶点,就将n边形分成了 三个不相交的部分(如图3所示),我们分别称之为区域①、区 域②、区域③,其中区域③必定是一个三角形,区域①是一 个凸k边形,区域②是一个凸n-k+1边形。
P2 ① P1 ③ ② Pn 图3 Pn--1 Pk P3

分析
?

区域①的拆分方案总数是Ck,区域②的拆分方案数为Cn-k+1, 故包含△P1PkPn的n 边形的拆分方案数为CkCn-k+1种,而Pk可 以是P2,P3,……,Pn-1 种任一点,根据加法原理,凸n边形的 n ?1 三角拆分方案总数为 ? Ci Cn?i ?1 , 同时考虑到计算的方便, 约定边界条件C2=1。 i ?2
P2 ① P1 ③ ② Pn 图4 Pn--1 Pk P3

分析

?C C
i ?2 i

n ?1

=C( 2n , n ) / ( n + 1)
n ?i ?1

具体实现时,若直接用上述公式计算,对数字的精度要 求较高。可将其化为递推式

2 * (2n ? 1) f ( n) ? f (n ? 1) n ?1
再进行递推计算,并且注意类型的定义要用comp型。

Catalan数的应用(部分和序列)
? ?

n个+1,n个-1构成2n项 a1,a2,a3,a4,,,,,,a2n 其部分和满足 a1+a2+......ak (k=1,2,3,...2n)>=0的数列个 数。

Catalan数的应用(加括号)
序列a1a2..ak的元素顺序保持不变,按不同结 合方式插入合法圆括号对的方案数。 n=4 (a((bc)d)) (a(b(cd))) ((ab)(cd)) (((ab)c)d) ((a(bc))d)

Catalan数的应用(栈 NOIp2003)
一个操作数序列,从1,2,一直到n,栈A的深度大于n。现在可 以进行两种操作: 1.将一个数,从操作数列的头端移至栈的头端 (对应栈的 push操作)2.将一个数,从栈的头端移至输出序列的 尾端(对应栈的 pop操作)。使用这两种操作,由一个操作数序列 就可以得到一系列的输出序列,下表为由1 2 3 生成序列2 3 1 的过 程。

步骤
操作数 序列 栈 输出序 列

0
123

1
23 1

2
3 21

3
3 1 2

4
31 2

5
1 23

6

231

分析
任务: 你的程序将对给定的 n ,计算并输出由操作数序列 1 , 2,……,n经过操作可能得到的输出序列总数。 结合定义我们很容易能发现:如果进栈看成 1 ,出栈看成 0,在 任何一位上累计的“0”的个数不大于累计的“1”的个数,因为必 须在栈里有数的情况下才能向外弹数。

原题转化为——n个1和n个0组成一个2n位的二进制数,要求从 左到右扫描,“0” 的累计数不大于“ 1” 的累计数,求满足条件 的数有多少。

递推的应用(组合计数)
错排问题(经典问题) n个数,分别为1~n,排成一个长度为n的排 列。若每一个数的位置都与数的本身不相等, 则称这个排列是一个错排。例如,n=3 ,则错 排有2 3 1、3 1 2。编写程序,求n的错排个数 。

分析
我们设k个元素的错位全排列的个数记做:W(k)。
四个元素的错位排列 W(4) 我们用穷举法可以找到 如下9个:

(4 , 3 , 2 , 1)(3 , 4 , 1 , 2)(2 , 1 , 4 , 3) (4 , 1 , 2 , 3)(3 , 4 , 2 , 1)(3 , 1 , 4 , 2) (4,3,1,2)(2,4,1,3)(2,3,4,1) 它们有什么规律呢?

分析
通过反复的试验,我们发现事实上有两种方式产生错位排列: A.将k与(1,2,?,k-1)的某一个数互换,其他k-2个数进行 错排,这样可以得到(k-1)×W(k-2)个错位排列。 B.另一部分是将前k-1个元素的每一个错位排列(有W(k-1) 个 ) 中 的 每 一 个 数 与 k 互 换 , 这 样 可 以 得 到 剩 下 的 (k - 1)×W(k-1) 个错位排列。

根据加法原理,我们得到求错位排列的递推公式W(k):

W(k) = (k–1) * [W(k–1)+W(k–2)]

递推的应用(博弈问题)
例题3:走直线棋问题。有如下所示的一个编号为1到 n的方格:
1 2 3 4 5 … … N-1 N

现由计算机和人进行人机对奕,从1到n,每次可以 走k个方格,其中k为集s={a1,a2, a3,....am}中的元 素(m<=4),规定谁最先走到第 n格为胜,试设计一个人 机对奕方案,摸拟整个游戏过程的情况并力求计算机尽 量不败。

分析
题设条件:若谁先走到第 N 格谁将获胜,例如,假设 S={1,2},从第N格往前倒推,则走到第N-1格或第N-2格 的一方必败,而走到第N-3格者必定获胜,因此在N,S 确定后,棋格中每个方格的胜、负或和态(双方都不能 到达第N格)都是可以事先确定的。将目标格置为必胜 态,由后往前倒推每一格的胜负状态,规定在自己所处 的当前格后,若对方无论走到哪儿都必定失败,则当前 格为胜态,若走后有任一格为胜格,则当前格为输态, 否则为和态。

分析
设 1 表示必胜态, -1 表示必败态, 0 表示和态或表示无法到 达的棋格。 例如,设N=10,S={1,2},则可确定其每个棋格的状态如下所 示:
1 -1 -1 1 -1 -1 1 -1 -1 1

而N=10,S={2,3}时,其每格的状态将会如下所示:
0 -1 -1 0 1 0 -1 -1 0 1

有了棋格的状态图后,程序应能判断让谁先走,计算机选 择必胜策略或双方和(双方均不能到达目标格)的策略下棋, 这样就能保证计算机尽可能不败。

递推的应用(动态规划中的递推
16 4 3 6 4 4 3 12 7 0 0 4 人 6 0 0 0 3 2

例4:方格取数 4 -5 ? 在一个n×m的方格中,m 6 0 为奇数,放置有n×m个数 5 3 ,如图,方格中间的下方有 -1 7 一人,此人可按照五个方 向前进但不能越出方格,见 0 -1 右下图。 ? 人每走过一个方格必须取 此方格中的数。要求找到 一条从底到顶的路径,使 其数相加之和为最大。输 出和的最大值。

-1 -2

3
0 7 12

6
-2 -5 4

8
7 6 2

分析
?

? ? ?

我们用坐标(x,y)唯一确定一个点,其中(m,n)表示图的右上角 ,而人的出发点是,受人前进方向的限制,能直接到达点(x,y) 的点只有(x+2,y-1),(x+1,y-1),(x,y-1),(x-1,y-1),(x2,y-1)。到点(x,y)的路径中和最大的路径必然要从(m/2,0)到 (x+2,y-1),(x+1,y-1),(x,y-1),(x-1,y-1),(x-2,y-1)的 几条路径中产生,既然要求最优方案,当然要挑一条和最大的 路径,关系式如下: Fx,y= Max{Fx+2,y-1 ,Fx+1,y-1,Fx,y-1,Fx-1,y-1,Fx-2,y-1}+Numx,y, 其中Numx,y 表示(x,y) 点上的数字。 边界条件为: F m / 2 ,0 ? 0
? ?

Fx,0 ? ?? (1 ? x ? m且x ? ?m / 2?)

动态规划与递推的关系
?
?

上题实质上是采用动态规划来求解,那么与递 推动态规划之间到底是什么关系呢? 我们不妨画个图(如下图)。而通常人们理解 的递推关系就是一般递推关系,故认为动态 规划与递推关系是两个各自独立的个体。
递推关系 一般递 推关系

动态 规划

动态规划与递推的关系
?

?

1、一般递推边界条件很明显,动态规划边界条件 比较隐蔽,容易被忽视 2、一般递推数学性较强,动态规划数学性相对较 弱 3、一般递推一般不划分阶段,动态规划一般有较 为明显的阶段

第三部分 递归
?

一个函数、过程、概念或数学结构, 如果在其定义或说明内部又直接或 间接地出现有其本身的引用,则称 它们是递归的或者是递归定义的。 在程序设计中,过程或函数直接或 者间接调用自己,就被称为递归调 用。

递归的概念与基本思想
?

? ?

?

递归过程是借助于一个递归工作栈来实 现的 问题向一极推进,这一过程叫做递推; 而问题逐一解决,最后回到原问题,这 一过程叫做回归。 递归的过程正是由递推和回归两个过程 组成。

递归的概念与基本思想
用递归算法求 n! 定义:函数 fact( n ) fact( n-1 则有 fact( n ) 已知 fact( 1 )

= n! ) = ( n-1 )! = n fact( n-1 ) = 1

下面画出了调用和返回的递归示意图

A B fact(3) 调用 fact(2) C 调用 =3*fact(2) =2*fact(1) fact(1) =3*2 =2*1 =1 =6 =2 返回 E 返回 D

84

递归的概念与基本思想
递归实现的代价是巨大的栈空间的耗费,那 是因为过程每向前递推一次,程序将本层的实在 变量(值参和变参)、局部变量构成一个“工作 记录”压入工作栈的栈顶,只有退出该层递归时, 才将这一工作记录从栈顶弹出释放部分空间。由 此可以想到,减少每个“工作记录”的大小便可 节省部分空间。例如某些变参可以转换为全局变 量,某些值参可以省略以及过程内部的精简。

示例:求a[1..n]的最大者。 有如下过程: Procedure findmax(i:integer;var max:integer); var j:integer; begin max:=a[i]; if i=n then exit else begin findmax(i+1,j); if j>max then max:=j; end;

递归的概念与基本思想

中的变参 max 完全可以省略。将上述方法修改可得下 面的算法:
Procedure findmax(i:integer); begin if i=n then exit else begin findmax(i+1); if a[i]>max then max:=a[i]; end; end;

递归的概念与基本思想 起始状态就是调用 findmax(1,max), 而像上述过程

递归的概念与基本思想
起始状态就是调用findmax(1) ,max为全局 变量,同时还减少了一个局部变量的使用。尽管 这只是一个很简单的例子,在本例中不做精简, 程序也还是能通过,但它精简的原则对其它使用 递归的程序而言却是同样适用的。特别是在递归 过程出现堆栈溢出情况时就应该考虑这一问题。

递归的概念与基本思想
?

采用递归方法编写的问题解决程序具有 结构清晰,可读性强等优点,且递归算 法的设计比非递归算法的设计往往要容 易一些,所以当问题本身是递归定义的, 或者问题所涉及到的数据结构是递归定 义的,或者是问题的解决方法是递归形 式的时候,往往采用递归算法来解决。

递归的应用
? ?

? ?

解决搜索问题 处理递归定义或解决方法为递归方式的 问题 实现分治思想 用于输出动态规划的中间过程

递归的应用(搜索树)
?

树结构是由递归定义的。因此,在解决与 树有关的问题时,常常可以采用递归的方 法。因为搜索产生的节点成树状结构,所 以可以用递归方法解决。这类例子很多, 如“N后”问题,哈密顿回路,图的可着 色性等等。

递归的应用
例题:钢板分割问题。设有一块正方形的钢板, 现需将它分成n个小正方形。例如,当: n=2 不可能有解。 n=3 不可能有解。 n=4 可分成4个小正方形钢板。 n=5 不可能有解。 n=6 即一个大的加五个小的。 n=7 即三个较大的加四个小的。 n=8 即一个大的加七个小的。 问题为任给n,求出分成n个小正方形的方法。

递归的应用
【分析】经过分析就可以得出: (1)按n=4的方法将1个小正方形分成4个,则 增加了3个正方形。 (2)以n=6为基础,由(1)可以得出n=9,12, 15,??????。 (3)以n=7为基础,由(1)可以得出n=10, 13,16,??????。 (4)以n=8为基础,由(1)可以得出n=11, 14,17,??????。 由此可以得出如下的递归算法:

递归的应用
procedure devide(i:integer); Begin if n>8 then begin 分解成四小块; 对于其中一块devide(n-3) end else case n of 6: 按n=6分割; 7: 按n=7分割; 8: 按n=8分割; end; End;

递归的应用(实现分治思想)
不难发现,在各种时间复杂度为nlogn排序方法中,大 都采用了递归的形式。因为无论是分治合并排序,还 是堆排序、快速排序,都存在有分治的思想。只要分 开处理,就可以采用递归。其实进行分治,也是一个 建树的过程。

递归的应用(例题分析)
例题2:剔除多余括号
键盘输入一个含有括号的四则运算表达式,可能含有多余的括 号,编程整理该表达式,去掉所有多余括号,原表达式中所有变量 和运算符相对位置保持不变,并保持原表达式等价。 分析: 首先考虑人处理这个问题的方法,就是依靠符号来判断是否可 以去括号。括号的前后,以及括号内的符号,都需要考虑。因此, 可以按照人的处理方法,从最外层处理起,一层一层的去掉括号, 这便是分治的思想。而由于每次分治的处理过程基本相同,用递归 最为合适。

递归的应用(例题分析)
在递归过程中,对于正在处理的表达式s,如果s本身最 外层就是多余括号,则去括号,并处理括号内的表达式(递 归调用);否则,可沿该表达式中的最低级运算符p,将其 拆为两个表达式,分别进行处理(递归调用),并获得左右 两表达式中的最低级运算符c1,c2,通过与p的比较,确定是 否应添加括号。 递归的终止条件为:s是变量。

递归的应用(例题分析)
? ? ?

例如,处理表达式‘((a+b)*f)-(i/j)’,过程如下: ‘((a+b)*f)-(i/j)’,‘-’ ‘((a+b)*f),’*’ ‘(i/j),’/’ ‘i/j’,’/’ ‘f’,’ ‘ ‘i’,’ ‘ ‘j’,’ ‘

? ?

‘(a+b)*f),’*’ ‘(a+b)’,’+’

?

‘a+b’,’+’ ‘a’,’ ‘ ‘b’,’ ‘
?

最后得出结果:‘(a+b)*f-i/j’。

递归的应用(输出动态规划的中间过程)
动态规划对空间要求较高,若要保存中间过程用于输 出,则可能要增加一倍的空间需求。此时,如果采用 递归输出,就完全不需要浪费这宝贵的空间。

例题:最佳航线问题
你在加拿大航空公司组织的一次竞赛中获奖,奖品是一张免费机票, 可在加拿大旅行,从最西的一个城市出发,单方向从西向东经若干城市到 达最后一个城市(必须到达最东的城市),然后在单方向从东向西飞回起 点(可途径若干城市)。除起点城市外,任何城市只能访问一次。起点城 市被访问两次:出发一次,返回一次。除指定的航线外,不允许乘其他航 线,也不允许使用其他交通工具。 求解的问题是:给定城市表列及两城市之间的直通航线,请找出一条 旅行航线,在满足上述限制条件下,使访问的城市尽可能多。

例题分析:最佳航线问题
对这一问题,我们采用了动态规划的方法。 假设城市已按从西到东编号,数组dist[i,j] 表示城市i到城市n,再到 城市j的所有可行方案中,最多能够访问的城市数目。逆推关系式为: dist[n,n]=1; dist[i,j]=dist[j,i]; dist[i,j]=max(dist[i,k])+1; (j<i,j<k<=n,且存在航线k─j) 如果要记录中间过程,就必须再开辟一个二维数组,就会导致程序可 完成的数据规模降低。而采用递归求出路径后再输出,编程并未增加多 少难度,而可处理的数据量却大大增加了。求路径的过程完全按照倒推 的方法,利用dist数组得出往返的路线。

? ? ? ?



第四部分

贪心方法

贪心方法的基本思想
? ?

?

贪心是一种解题策略,也是一种解题思想 使用贪心方法需要注意局部最优与全局最优的 关系,选择当前状态的局部最优并不一定能推 导出问题的全局最优 利用贪心策略解题,需要解决两个问题: ? 该题是否适合于用贪心策略求解 ? 如何选择贪心标准,以得到问题的最优解

适用于贪心策略求解的问题的特点
适用于贪心策略求解的问题必须具有最优 子结构的性质,但并不是所有具有最优子 结构的问题都可以用贪心策略求解。因为 贪心往往是盲目的,需要使用更理性的方 法——动态规划(例如“0-1背包问题”与 “部分背包问题”)

贪心方法的应用
例题1:节点网络。 现有一个N!个节点的网络,每个节点的编 号都是编号(A1A2A3…AN)序列的一个置 换。对于任意两个节点S和T,如果T的编 号是由S编号的首位与除首位外的编号中任 一位交换所得 ,则S和T之间有一条边,求 从给定节点S走到节点(A1A2A3…AN)所需 经过的最少边数。其中,n≤100。

贪心方法的应用
例如n=3的情况:

(A1A2A3) (A2A3A1) (A3A1A2)

(A1A3A2) (A2A1A3) (A3A2A1)

贪心方法的应用
【分析】从题意表面上看,本题是一 个求最短路径的问题,但题设中的 N≤100,也就是说图中最多有100! 个节点,采用二维关系的图结构根本 无法存贮这众多的状态。通过问题的 本质分析,可以将问题转化为一个序 列的最优转化问题。

贪心方法的应用
采用贪心策略: 每次让一个节点归位或为下一步工作做准备。 其具体步骤为: ? 若序列中第一个点为Ax (x≠1),则将第一个点 和第x个点交换。这便完成了让一个点归位的 工作; ? 若第一个是A1,则任找一个编号与位置不相 符的点,并与之交换。这样下一步便可让交 换到1号位置的点归位。

贪心方法的应用
下面看一个n=4,初始序列为(A3A4A1A2)的推演过程:

(A3A4A1A2) 第一个点为A3≠A1,将第3个点A1与A3交换 (A1A4A3A2) 第一个点A1已归位,但第二个点为A4≠A2, 将第2个点 A4与A1交换 (A4A1A3A2) 第一个点为A4≠A1,将第4个点A2与A4交换 (A2A1A3A4) 第一个点为A2≠A1,将第2个点A1与A2交换 (A1A2A3A4) 已经符合要求了

一共经过4步完成。

例题2 排序问题
排序是计算机科学中一个常见任务。有一种特殊的排序,最多 只有3个关键字。例如,试图对这次竞争的奖牌榜排序时,就 只有3个关键字,所有的金牌获得者在最前面,随后是获银牌 者,最后是铜牌获得者。 本题中用1,2,3分别表示3个关键字,需将它们按升序排列。 排序是通过一系列对换操作实现的。一次操作可以交换两个数 的位置。 子任务A 请写一个程序,对于一个给定的只含有关键字的序列,计 算最少需要几次对换操作就可以将其按升序排列。 子任务B 输出一种最少次数的对换方案。

分析
如果要我们自己来手算的话,势必会先找到一对数,使 其交换位置后正好都回到应该在的位置,例如数串 111232333,我们发现第5位上的3与第6位上的2正好反过来 了。把它们交换就可以得到排序后的数串。又因为这样的一 次交换使两个数回到正确的位置,这说明这次交换已经发挥 了它的最大功效,一定不是多余的,虽然是要求最少的交换 次数也绝不能少了这样的交换。 到这里我们发现这道题可以用贪心法来做。

不断地寻找这样的一对数,直至找不到为止。但是注意, 还有一种更加普遍的情况我们没有考虑,也就是虽然存在 错位了的数,但是找不到互换位置可以符合以上要求的两 个数。例如:113221332中,第3位上的3,第6位上的1, 第9位上的2,都是错位的,但不管取他们三个中的哪两个 交换,通通都不能使两个数都归原位。这个时候,我们只 好放弃一个,只保证一个数可以归原位,于是交换1与2, 数串变成113222331,这时再交换3与1,就用两次交换对 该数列排完了序。

问题变形
给定 N 个不同的正整数,每次只能交换两个相邻的 数,如何一住校的交换次数使得其变成升序?

贪心方法的应用(贪心标准)
例题:d-规则问题。 对任意给定的m(m∈N+)和n(n∈N+),满足m<n,构造一 初始集合:P={x|m≤x≤n,x∈N+}(m,n≤100) 现定义一种d规则如下:若存在a∈P,且存在K∈N+ ,K>1, 使得K?a∈P,则修改P为:P=P-{y|y=s?a,s∈N+ } ,并 称该d规则具有分值a。现要求编制一个程序,对输入的 m,n值,构造相应的初始集合P,对P每应用一次d规则就 累加其相应的分值,求能得到最大累加分值的d规则序列, 输出每次使用d规则时的分值和集合p的变化过程。

贪心方法的应用
【分析】 初看这一问题,很容易想到用贪心策略来求解,即选择 集合中最大的可以删除的数开始删起,直到不能再删除 为止,而且通过一些简单的例子来验证,这一贪心标准 似乎也是正确的 ,例如,当 m=3 , n=10 时,集合 P = {3,…,10} ,运用上述“贪心标准”可以得到这一问题的 正确的最优解d=5+4+3=12,即其d-规则过程如下: 1. a=5 P={3,4,6,7,8,9} d=5 2. a=4 P={3,6,7,9} d=5+4=9 3. a=3 p={7} d=5+4+3=12

贪心方法的应用
但是,如果再仔细地分析一个例子,当m=3,n =18时,如果还是使用上述“贪心标准”,则得 到问题的d-规则总分为d=35,其d-规则序列为 (9,8,7,6,5),而实际上可以得到最大d-规则总 分为d=38,其对应的d-规则序列为 (9,8,7,6,3,5)。 为什么会出现这样的反例呢?这是因为,问题中 要使得d-规则总分d值越大,不光是要求每一个d 分值越大越好,也要求取得的d分值越多越好。 因此,本题不能采用纯粹的贪心策略求解。

贪心方法的应用
【改进】 将原算法基础上进行改进。下面给出新的算法: 1. 建立集合P={m..n} 2. 从n div 2到m每数构造一个集合c[i],包含该数在P中 的所有倍数(不包括i本身) 3. 从n div 2起找到第一个元素个数最少但又不为空的集 合c[i] 4. 在d分值中加上i 5. 把i及c[i]集合从P集中删除,更新所有构造集合的元素 6. 检查所有构造集合,若还有非空集合,则继续3步骤, 否则打印、结束

贪心方法的应用
下面看m=3, n=18时的推演过程: 1. 初始P={3..18} 2. 找到i=9, c[i]={18}, P={3..8,10..17} 3. 找到i=8, c[i]={16}, P={3..7,10..15,17} 4. 找到i=7, c[i]={14}, P={3..6,10..13,15,17} 5. 找到i=6, c[i]={12}, P={3..5,10,11,13,15,17} 6. 找到i=3, c[i]={15}, P={4,5,10,11,13,17} 7. 找到i=5, c[i]={10}, P={4,11,13,17} 到此所有构造集合全部为空,d=9+8+7+6+3+5=38

例题分析:田忌赛马问题
中国古代的历史故事“田忌赛马”是为大家所熟 知的。话说齐王和田忌又要赛马了,他们各派出N 匹马,每场比赛,输的一方将要给赢的一方200两 黄金,如果是平局的话,双方都不必拿出钱。现 在每匹马的速度值是固定而且已知的,而齐王出 马也不管田忌的出马顺序。请问田忌该如何安排 自己的马去对抗齐王的马,才能赢取最多的钱?

正整数n (n <= 2000) ,表示双方 马的数量。

分析
?

?

?

?

不妨用贪心思想来分析一下问题。因为田忌掌握有比赛的“主 动权”,他总是根据齐王所出的马来分配自己的马,所以这里 不妨认为齐王的出马顺序是按马的速度从高到低出的。由这样 的假设,我们归纳出如下贪心策略: 1、如果田忌剩下的马中最强的马都赢不了齐王剩下的最强的 马,那么应该用最差的一匹马去输给齐王最强的马。 2、如果田忌剩下的马中最强的马可以赢齐王剩下的最强的马 ,那就用这匹马去赢齐王剩下的最强的马。 3、如果田忌剩下的马中最强的马和齐王剩下的最强的马打平
的话,可以选择打平或者用最差的马输掉比赛。

?

?

光是打平的话,如果齐王马的速度分别是1 2 3,田 忌马的速度也是1 2 3,每次选择打平的话,田忌一 分钱也得不到,而如果选择先用速度为1的马输给 速度为3的马的话,可以赢得200两黄金。 光是输掉的话,如果齐王马的速度分别是1 3,田忌 马的速度分别是2 3,田忌一胜一负,仍然一分钱也 拿不到。而如果先用速度为3的马去打平的话,可 以赢得200两黄金。

?

通过上述的三种贪心策略,我们可以发现 ,如果齐王的马是按速度排序之后,从高 到低被派出的话,田忌一定是将他马按速 度排序之后,从两头取马去和齐王的马比 赛。有了这个信息之后,动态规划的模型 也就出来了!

Dp求解
?

? ? ?

设f[i,j]表示齐王按从强到弱的顺序出马和田忌进行了i 场比赛之后,从“头”取了j匹较强的马,从“尾”取 了i-j匹较弱的马,所能够得到的最大盈利。 状态转移方程如下: F[I,j]=max{f[i-1,j]+g[n-(i-j)+1,i],f[i-1,j-1]+g[j,i]} 其中g[i,j]表示田忌的马和齐王的马分别按照由强到弱 的顺序排序之后,田忌的第i匹马和齐王的第j匹马赛 跑所能取得的盈利,胜为200,输为-200,平为0。

贪心方法的应用(贪心标准证 明)
例题:射击竞赛 射击的目标是一个由R?C(2≤R≤C≤1000)个小方 格组成的矩形网格。每一列恰有2个白色的小方 格和R-2个黑色的小方格。行从顶至底编号为 1~R,列从左至右编号为1~C。射击者可射击C 次。 在连续的C次射击中,若每列恰好有一个白色的 方格被射中,且不存在无白色方格被射中的行, 这样的射击才是正确的。 如果存在正确的射击方法,则要求找到它。

贪心方法的应用
射击的选择有2C种,符 合要求的却很少。要解 决问题,还需从正确的 射击方法的特征入手。

贪心方法的应用
【方法一】网络流算法

我们将表示列的点编号为1到C,表示行的点编号为C+1 到C+R,如果一个白色方格处在第i行第j列,那么从点j向 点C+i连一条弧,弧的容量为1。再增设一个源点S,从点 S往点1到C间各连一条弧,弧的容量为1,又设一个汇点T, 从点C+1到点C+R向汇点T连一条弧,弧的容量为1,那 么从源点S到汇点T求最大流,求出的最大流量即为最多 可以射击到的行数。各条流的路线则描述了具体的射击 方案。 可以看出,如果用网络流求出的最大流量比R小,则问题 无解,否则我们可以先根据网络流的结果求出该二分图 的具体匹配方案。

贪心方法的应用
源:
S 红色的连线流量为1 1 2 3 4

列:

蓝色的连线流量为0
选择的射击格即为: (1,3), (2,1), (3,2), (4,4)

行:

1

2

3 T

4

汇:

贪心方法的应用
网络流算法经过优化,时间复杂度可以达 到O(C?(n+4C+4R)) 上述网络流算法虽然可以通过全部数据, 但编程复杂度很高,而且极易出错,一不 小心就会因为一个小错误影响整个程序。

贪心方法的应用
【方法二】贪心方法
1. 统计所有行包含的白格数 2. 从还没有射击格的行中选出一个白格数最少的

3. 检查所选的行
1. 若所选行的白格数为0,则输出无解; 2. 否则从所选行的白格中任选一个作为射击格,并将与该格同

列的另一个白格所处行的白格数减1

4. 返回到第2步,直到所有的行都有射击格。
5. 若还有列没有选射击格,则在该列任选一白格作为射

击格即可

贪心方法的应用
上面的贪心方法非常高效: 时间复杂度为O(R?C),如果在程序中使用 堆优化,时间复杂度将降为O(R?log2C)。 空间复杂度是线性的,而且非常容易实现。 现在关键的问题就是——如何证明它的正 确性?

贪心方法的应用
【证明】
用h[i]表示第i行的白格数。如果最开始的时候: ? min{h[i]}=0: 第i行已经没有办法找到可作为射击格的白格,那么 问题只能无解。 ? min{h[i]}=1: 那么第i行的这一个白格必须要作为射击格,否则将 因第i行没有射击格而造成问题无解。 ? min{h[i]}≥2: 那么在这一行任选一个白格,顶多只会造成剩余行 中有一行h值为1,再处理那一行,最多也只会再造成剩余行中有 一行h值为1,如此往复,将保持h值为1的行数不超过1行,最后 最坏的情况也是造成最后一行的h值为1,继续下去所有行就都已 选取了射击格了。 因此,如果原问题有解,该贪心方法一定能找到一种正确的方案。 由此可以证明,此贪心方法是正确的。

例题分析
? ?

买彩票(tickt.exe) 电视里面正放着“抽百万大奖,赢幸福生活 ”的宣传广告,bird看后也想去试试手气, 当然,作为经济学院的高材生,他可不屑只 是单纯的去碰运气。经过他的一番分析,发 现,商家在彩票里面做了手脚,使得每个抽 奖点的中奖概率不是完全一样的,而且随着 时间的变化而变化,不过这种变化是有规律 的。

?

?

对于第I个抽奖点,最开始的中奖概率是百万 分之Pi,以后每抽一张彩票后都要重新排队, 花费的时间是T分钟,每抽一次减少的概率为 Di。 由于可怜的bird还有一大堆的作业没做,他只 能抽出H个小时去买彩票。由于抽奖地点都在 一路公共汽车的线路上,所以怕麻烦的bird决 定按车站顺序抽奖。

?

?

当然,bird可以从任意一站开始抽奖,对于 经过的抽奖点可以买彩票,也可以不买。 假设从第I个抽奖点到第I+1个抽奖点需要 做Ci分钟的汽车。 Bird希望能在有限的H个小时内获得最好的 运气——即抽奖的概率和最大。

? ?

?

?

?

输入: 第一行为一个整数n,表示抽奖点的个数, 1<=n<=200 第二行是两个整数H和T,1<=H<=10, 1<=T<=60。 接下来的n行,每行3个整数,分别是Pi,Di,C (Cn=0)。1<=Pi<=10000,Di<=Pi, 1<=Ci<=600。 输出:

? ? ? ? ?

?

样例数据 input.txt 2 1 20 200 100 10 300 200 0

output.txt 500

?

样例说明: 首先,bird从1号开始抽奖, 花费20分钟,得到概率200,然后坐车到2 号,花费10分钟,再花20分钟得到概率300 ,概率和是500,花费50分钟。

?

此题最初可能想到用搜索,不过如果仔细分析 题目会发现其实用贪心就可以解了。虽然中奖 的概率会不断变化,但概率只和在该抽奖地点 的抽奖次数有关,和抽奖的总次数以及时间无 关。

?

所以,我们可以枚举起始S和终点T的抽奖 地点,则在路上花费的时间可以求出,那 么在这个范围内的抽奖,可以看作bird能 瞬间转移,那么我们只需将此范围内的抽 奖概率排序,取前若干个,使得花费的时 间不超过时限。很容易证明,这种方法是 最优的。

?

此题的贪心关键是要先确定一个范围, 然后针对具体的范围贪心。贪心法的隐 秘性还是比较强的。

例题分析(骆驼商队)
?

有N个城市,编号为1……N。在一些城市之间有路可通,有路 就有商队。但是在不同的城市之间经商所得的收益不同,在 下面的这个N=4的例子中,在城市1和城市2之间进行一次交 易可以获得40枚金币,在城市2和3之间交易一次可以获得50 枚金币,规定在任意两个城市之间,这样的交易只能进行一 次。给出这个大陆的地图和每两个城市之间的贸易值(如果 这两个城市之间有路可通的话),你需要指挥你的N支商队 进行一次经商,使得这N支商队在这次经商中获得的总收益 最大。注意:你的每支商队只能进行一次交易,即它们只能 从它们所在的城市到达一个相邻的城市。当然,它们也可以 不进行任何交易。

分析
?

本题转化成模型就是:在一个无向图中,对 于每个点,取一条和它相关联的边(如果这 样的边存在的话),使得取出来的所有边的 权和最大。

?

首先,如果这个图是不连通的,那么它的各 个连通分量之间是没有任何联系的。对这些 连通分量中的问题可以分别独立地解决,合 并起来就是整个问题的解。所以我们在下面 的讨论中假定图是连通的。

?

直观地考虑,如果图中存在度为1的点,那么就把这 一点上的唯一的一条边分配给这个点(将某条边“分 配”给某个点的含义是:将这条边作为和这一点相关 联的边取出来,同时这一点就失效了,因为和它相关 联的其他边都不能再取了)。如果不存在这样的点, 那么此时有两种情况:一种是边数等于点数,那么这 个图就是一个环,这时可以取出图中所有的边;一种 是边数大于点数,那么就可以把这个图中权最小的一 条边直接删去,因为这条边“显然”不会被取到的。

贪心算法(用于连通图):
? ? ? ? ?

?

1、如果图中只有一个点,直接结束算法。 2、如果图中存在度为1的点,执行3;否则转4。 3、任意找一个度为1的点v,将v上的唯一一条边分配给它。转2。 4、如果图中的边数等于点数,执行5;否则转6。 5、设图中的点数(也就是边数)为n。任取一条边e1,将它分配给它的 两个端点中的任意一个v1;然后将v1上的另一条边e2分配给e2的另一个端 点v2;将v2上的另一条边e3分配给e3的另一个端点v3;……如此重复直到 将en分配给vn,即图中所有的边都已分配,结束算法。 6、将图中权最小的边不分配而直接删去。如果此时图仍然连通,则转2 ;否则对这个图的两个连通分量分别执行本算法

贪心方法的推广
?

贪心与其它算法结合
? ?

搜索的最优化剪枝( 生日蛋糕) 优化动态规划( Peter的快餐店) 最优方法不一定是最好方法 想不到最优解法就用较优解法

?

贪心方法与解题策略
? ?

贪心与其它算法结合
例题:Peter的快餐店(贪心与动态规划) Peter最近在R市新开了一家快餐店。 该快餐店准 备推出一种套餐,每套由A个汉堡、B个薯条和C 个饮料组成。为了提高产量,Peter引进了N条生 产线。所有生产线都可以生产汉堡、薯条和饮料, 由于每条生产线一天能工作的时间是有限的、不 同的,而汉堡、薯条和饮料的单位生产时间又不 同,Peter需要知道,怎样安排才能是一天中生产 的套餐量最大。假设一天中汉堡、薯条和饮料的 产量均不超过100个,且生产线总数小于等于10。

贪心与其它算法结合
【分析】用p1、p2、p3分别表示汉堡、薯条和饮 料的单位生产时间, t[i] 表示第 i 条生产线每天的 生产时间, p[i,j,k] 表示用前 i 条生产线生产 j 个汉 堡、 k 个薯条的情况下,最多能生产的饮料数, r[i,j,k] 表示用第 i条生产线生产 j 个汉堡、 k个薯条 的情况下,最多能生产的饮料数,则 p[i,j,k]=max{p[i-1,j1,k1]+r[i,j-j1,k-k1]} ((j-j1)?p1+(k-k1)?p2<t[i]) 通过对该算法的时间复杂度分析,最坏的情况下 时间复杂度将达到109,是相当费时的。

贪心与其它算法结合
现在加入贪心方法,用贪心方法作预处理 : ? 首先计算出一天生产套数的上限值:min{100 div A,100 div B,100 div C} ? 接着,用贪心方法计算出这N条生产线可以生产的套数, 并与上限比较,大于或等于则输出上限值并退出,否 则再调用动态规划。因为贪心方法的代价很低,这里 甚至可以使用多次贪心标准不同的贪心方法,取其最 大值。 ? 在运行动态规划的过程中,也可以每完成一阶段工作 便与上限值进行比较,将贪心思想充分融入到动态规 划过程中,这样以来,便可望在动态规划完成前提前 结束程序。

贪心方法小结
贪心作为一种解题思路,虽然有时无法证 明它的正确性,但在无法找到其他算法的 时候,不失为一种好方法。并且,贪心与 其他算法的结合,可以对其他算法起到优 化作用。

第四部分

分治策略

分治思想
分治(divide-and-conquer)就是“分而治之” 的意思,其实质就是将原问题分成n个规模较 小而结构与原问题相似的子问题;然后递归 地解这些子问题,最后合并其结果就得到原 问题的解。其三个步骤如下; 1. 分解(Divide):将原问题分成一系列子问题。 2. 解决(Conquer):递归地解各子问题。若子问 题足够小,则可直接求解。 3. 合并(combine);将子问题的结果合并成原问 题的解。
?

分治思想
如果在将规模为n的问题分成k个不同子 集合的情况下,能得到k个不同的可分别求 解的子问题,其中1<k<=n,而且在求出 了这些子问题的解之后,还可找到适当的方 法把它们合并成整个问题的解,那么,具备 上述特性的问题可考虑使用分治策略设计求 解。这种设计求解的思想就是将整个问题分 成若干个小问题后分而治之。

分治思想
问题S 问题的分解

问题S1

问题S2

……

问题Si

……

问题Sn

子问题求解

S1的解

S2的解

……

Si的解

……

Sn的解

子集解的合并

问题 S的解 S

分治思想
?

?

由分治法所得到的子问题与原问题具有相同 的类型。如果得到的子问题相对来说还太大, 则可反复使用分治策略将这些子问题分成更 小的同类型子问题,直至产生出不用进一步 细分就可求解的子问题。分治求解可用一个 递归过程来表示。 要使分治算法效率高,关键在于如何分割? 一般地,出于一种平衡原则,总是把大问题 分成K个规模尽可能相等的子问题,但也有例 外,如求表的最大最小元问题的算法,当n= 6时,等分定量成两个规模为3的子表L1和L2 不是最佳分割。

分治的应用
解决一类求方程的根的问题 解决真假硬币的称量问题 基于NLgN算法效率的排序和查找问题

分治的应用(求方程的根)
例题1: 一元三次方程求解 有形如:ax3+bx2+cx+d=0这样的一个一元三次方程。 给出该方程中各项的系数(a,b,c,d均为实数),并 约定该方程存在三个不同实根(根的范围在-100至 100之间),且根与根之差的绝对值>=1。要求由小 到大依次在同一行输出这三个实根(根与根之间留有 空格),并精确到小数点后4位。 提示:记方程f(x)=ax3+bx2+cx+d,若存在2个数x1和x2, 且x1<x2,f(x1)*f(x2)<0,则在(x1,x2)之间一定有一 个根。 样例 输入:1 -5 -4 20 输出:-2.00 2.00 5.00

分析
?

?

?

如果精确到小数点后两位,可用简单的枚举法: 将x从-100.00 到100.00(步长0.01) 逐一枚举, 得到20000个 f(x),取其值与0最接近的三个f(x), 对应的x即为答案。而题目已改成精度为小数点后 4位,枚举算法时间复杂度将达不到要求。 直接使用求根公式,极为复杂。加上本题的提示 给我们以启迪:采用二分法逐渐缩小根的范围, 从而得到根的某精度的数值。 具体方法如下:

分析
A、当已知区间(a,b)内有一个根时,用二分法求根, 若区间(a,b)内有根,则必有f(a)· f(b)<0。重复执 行如下的过程: (1)若a+0.0001>b或f((a+b)/2)=0,则可确定根 为(a+b)/2并退出过程; (2)若f(a)* f((a+b)/2)<0,则由题目给出的定理 可知根在区间(a,(a+b)/2)中,故对区间重复该过 程; (3)若f(a)* f((a+b)/2)>0 ,则必然有f((a+b)/2)* f(b)<0 ,根在((a+b)/2,b)中,对此区间重复该 过程。 ? 执行完毕,就可以得到精确到0.0001的根。

分析
B、求方程的所有三个实根 ? 所有的根的范围都在-100至100之间,且根与根之 差的绝对值>=1。因此可知:在[-100,-99]、[-99,98]、……、[99,100]、[100,100]这201个区间 内,每个区间内至多只能有一个根。即:除区间 [100,100]外,其余区间[a,a+1],只有当f(a)=0 或f(a)· f(a+1)<0时,方程在此区间内才有解。若 f(a)=0 ,解即为a;若f(a)· f(a+1)<0 ,则可以利用 A中所述的二分法迅速出找出解。 ? 如此可求出方程的所有的解。

分治的应用(求方程的根)
例题2: 输入m,n,p,a,b,求方程f(x)=mx+nx-px=0在 [a,b]内的根。m,n,p,a,b均为整数,且a<b;m,n,p 都大于等于1。如果有根,则输出,精确到1E-11;如果无方 程根,则输出“NO”。 【样例】 equation.in equation.out 23412 1.5071265916E+00 2.9103830457E-11

分析
?

由于f(x)单调递增函数,对于一个单调递增(或递减)函数,判 断在[a, b]范围内是否有解,解是多少。常用的一种方法叫“ 迭代法”,也就是“二分法”。先判断f(a)·f(b)≤0,如果满 足则说明在[a, b]范围内有解,否则无解。如果有解再判断x =(a+b)/2是不是解,如果是则输出解,结束程序,否则我们 采用二分法,将范围缩小到[a, x)或(x, b],究竟在哪一半区 间里有解,则要看是f(a)·f(x)<0还是f(x)·f(b)<0。
对于y x,我们需要用换底公式把它换成exp(xln(y))

分治的应用(分段处理)
? ? ?

?
? ? ?

例题3:取余运算(mod.exe) 输入b,p,k的值,编程计算bp mod k的值。其中的b,p,k*k为长整 型数。 【输入输出样例】 mod.in 2 10 9 mod.out 2^10 mod 9=7

分析
1、用高精度计算比较烦 2、转而用其他方法求解 (1)取模运算的一个规律:a*b mod k=(a mod k)*(b mod k) mod k (2)运用规律可以把样例数据分解:b19=b2*9+1=b 9b9b ,其中的指数9可以继续分解为2×4+1,4再分解程2×2 +0,2=1×2+0,1=0×1+1。反过来,我们可以从0 出发,通过乘以2再加上1或0推得1,2,4,9,19,然后 依次以这些数为指数的自然数除以k的余数。

分析
(3)不难看出,前面乘以2后要加上的1或0就是该数对应 二进制数各位上的数字1或0。如,19=(10011)2 。 求解的过程也就是将二进制数还原为十进制数的过程。 (4)综上所述,该题可采用分治得思想进行递推求解。

分治的应用(分段处理)
例题:求“逆序对”。 给定一整数数组A=(A1,A2,…An), 若i<j且 Ai>Aj,则<I,j>就为一个逆序对。例如数组 (3,1,4,5,2)的逆序对有 <3,1>,<3,2>,<4,2>,<5,2>。问题是,输入 n和A数组,统计逆序对数目。 1<=n<=30000。

分析
? ? ? ? ?

?

原始的解决方案(双重循环) C:=0; For i:=1 to n -1 do for j:=i+1 to n do if a[i]>a[j] then c:=c+1; 时间复杂度为O(n2)

分析
采用二分法求解: 记数列a[st,ed]的逆序对数目为D(st,ed); mid=[(st+ed)/2],则有:
D(st,ed)=D(st,mid)+D(mid+1,ed)+F(st.mid,ed). 其中F(st,mid,ed)表示一个数取自A[st,mid],令一 个数取自A[mid+1,ed]的逆序对数目。

分析
?

?
?

若要求计算d值的同时数列A已排序,设I,j指 针分别已排序的A[st,med)和A(mid+1,ed)中 的一个元素,若满足: A[mid+1],…A[j-1]均小于A[j],但A[i]>A[j] 则j-mid-1必须计入F,顺序移动I,j指针即可 完成合并。

分治的应用(称量问题)

找出伪币
?

?

给你一个装有1 6枚硬币的袋子。1 6枚硬币 中有一个是伪造的,并且那个伪造的硬币比 真的硬币要轻一些。你的任务是找出这枚伪 造的硬币。 为了帮助你完成这一任务,将提供一台可用 来比较两组硬币重量的仪器,比如天平。利 用这台仪器,可以知道两组硬币的重量是否 相同。

方法1
?

任意取1枚硬币,与其他硬币进行比较,若发现 轻者,这那枚为伪币。最多可能有15次比较。

方法2
?

将硬币分为8组,每组2个,每组比较一次,若发 现轻的,则为伪币。最多可能有8次比较。

方法3

分析
?

?

? ?

上述三种方法,分别需要比较15次,8次,4次, 那么形成比较次数差异的根本原因在哪里? 方法1:每枚硬币都至少进行了一次比较,而有 一枚硬币进行了15次比较 方法2:每一枚硬币只进行了一次比较 方法3:将硬币分为两组后一次比较可以将硬 币的范围缩小到了原来的一半,这样充分地利 用了只有1枚伪币的基本性质。

分治的应用(解的合并)
?

例题6:赛程问题。有n个编号为1到n 的运动 员参加某项运动的单循环比赛,即每个运动员 要和所有其他运动员进行一次比赛。试为这n 个运动员安排一个比赛日程,使得每个运动员 每天只进行一场比赛,且整个比赛在n-1天内 结束。输入运动员人数n(n<=10000),输 出一个n阶方阵A[1..N,0..N-1],当J>0时, A[I,J]表示第I名运动员在第J天的比赛对手。

?

由于N个运动员要进行单循环比赛,且在N-1天 内要结束全部比赛,经过分析,当且仅当N为2的整 次幂时,问题才有解,当然解是不唯一的。这样可以 将运动员分成两组: 1,2,…,N/2 和 N/2+1,N/ 2+2,…,N。给第一组运动员安排一个比赛日程,得 到一个N/2阶的方阵A1;同时给第二组的运动员安 排一个比赛日程,同样会得到一个N/2阶的一个方 阵A2。考虑到比赛的性质,设定第I个运动员在某一 天的比赛对手为第K个运动员,则第K个运动员在同 一天的比赛对手必然是第I个运动员,即若有 A[I,J]=K,则A[K,J]=I。因此原问题的解(一个N 阶方阵)可以由分解后的两个子问题的解,合并起来。 同时每一个子问题又可以按照上述的二分法分解下去, 直至每个组中仅有2个运动员时为止。

? ? ? ? ? ? ? ? ? ? ? ?

procedure arrangment(K,N:integer); {从K号运动员起的共N员运动员单循环比赛日程表的过程} begin if n=2 then {处理只有2名运动员的情况,递归终止条件} begin A[K,0]:=K;A[K,1]:=K+1; A[K+1,0]:=K+1; A[K+1,1]:=K; end else begin arrangment(K,N div 2); arrangment(K + N div 2,N div 2); {递归分解原问题与求解子问题}
for I:=K to K +(N div 2) –1 do {合并子问题的解,构造原问题的解 A[I,J]} for J:=(N div 2) to N-1 do A[I,J]:=A[I+(N div 2),J-(N div 2)]; for I:=K+(N div 2) to K +N –1 do for J:=(N div 2) to N-1 do A[I,J]:=A[I-(N div 2),J-(N div 2)]; end; end;

? ? ? ? ? ? ?

例题分析:消除隐藏线
?

在计算机辅助设计(CAD)中,有一个经典问题: 消除隐藏线(被其它图形遮住的线段)。你需 要设计一个软件,帮助建筑师绘制城市的侧视 轮廓图。为了方便处理,限定所有的建筑物都 是矩形的,而且全部建立在同一水平面上。每 个建筑物用一个三元组表示(Li,Hi,Ri)其中Li和Ri 分别是建筑物i 的左右边缘坐标,Hi是建筑物i的 高度。

?

下面左图中的建筑物分别用如下三元组表示 :

?

下面图中的城市侧视轮廓线用如下的序列表 示:
(1,11,3,13,9,0,12,7,16,3,19,18,22,3,23,13,2 9,0)

?

分析
?

本题其实是矩形覆盖问题的特殊情形—— 固定了矩形的下边界。本题可以使用矩形 切割或者离散化加上线段树解决,但是前 者的时间复杂度在最坏情况下可能达到 O(n3),而后者的编程实现比较复杂。

?

?

要求n个矩形的轮廓,先将这n个矩形分成 两个大小相等的部分,分别求其轮廓,然 后再将这两个轮廓合并。 规模为1的问题可以直接解决。具体来说, 如果这个矩形的三元组表示为(L,H,R),那 么其轮廓为(L,H,R,0)。

?

对于规模为k的问题,假设得到了两个规模为 k/2的轮廓,分别为A和B,我们如何得到合并 后的轮廓C?首先,容易证明轮廓C的每一个 横坐标,都来源于轮廓A和B的横坐标,而不 会产生新的坐标值。因此,我们只需计算A和 B中所有涉及到的横坐标在C中的高度。

?

由于轮廓C中的横坐标值要求有序,我们可以 仿照归并排序的方法,用两个指针扫描轮廓A 和B。具体的方法是,设指针i指向轮廓A的当 前横坐标,指针j指向轮廓B的当前横坐标。 (1)如果指针i指向的横坐标较小,那么将这一横坐
标加入到C中,且在C中的高度为A中第i个横坐标对 应的高度与B中第j-1个横坐标对应的高度的最大值 。然后将指针i向后移一位;指针j指向的横坐标较小 的情况则类似处理。

?

?

(2)如果两个指针指向的横坐标相同,此时只 需将这一横坐标加入到C中一次,且高度为 两指针指向高度的最大值,然后将两指针同 时向后移一位。 (3)最后,需要扫描一遍轮廓C,将相邻的高 度相同的横坐标合并。

?

分析时间复杂度,T(n)=O(nlogn)。空间方 面,由于递归的层数为O(logn),每一层需 要保存O(n)的空间,所以总的空间复杂度 为O(nlogn)。

例题:三色二叉树
?

见文本。


相关文章:
NOIP2015提高组day1第二题解题报告
NOIP2015提高组day1第二题解题报告_学科竞赛_高中教育_教育专区。NOIP2015提高组...对于本题来说,60%大概就是 O(n^2)的算法了,一般是裸的暴力回溯或 者是...
NOIP基本算法模块
NOIP基本算法模块_学科竞赛_初中教育_教育专区。基本算法模块 For NOIP2007 Billy...Kruskal——以边为基础读入: procedure kruskal; var set1,set2,vetex_pointer...
NOIP算法整理
还有一些非常非常基础的 比如链表啊什么的就直接没有写上 (别问我为什么整理了...begin NOIP 算法总结 9 山东省广饶一中 杨庆礼 if a[i*2]<=a[i*2+1]...
Noip_2013_提高组_Day2_解题报告
Noip_2013_提高组_Day2_解题报告_计算机软件及应用_IT/计算机_专业资料。第二...算法优化后,再一次编写程序,O(n)的时间复杂度,当然是顺利 AC 了,代码如 下...
NOIP初赛复习——算法2
NOIP初赛复习——算法2_理学_高等教育_教育专区。OK NOIP 算法总结 BY.W.X ...雅礼中学朱全民动归讲稿 安阳一中各种算法讲稿 基础算法总结(杨帅) matrix67 的各种...
noip算法总结2016
凸包 计算几何中最基本也是最重要同时也是非常有用的...经典例题 HNOI2007day1 最小矩形覆盖 (维护凸包上...1/2 相关文档推荐 NOIP算法总结 by Nap 69页 ...
Noip常用算法大全
Noip 常用算法大全一、数论算法 1.求两数的最大...[1]:=false; i:=2; while i<50000 do begin ...最短路径可在求解第 n-1 最短路径的基础上求解。...
Noip 2013 提高组 Day2 解题报告
Noip 2013 提高组 Day2 解题报告_学科竞赛_高中教育_教育专区。Noip 2013 提高组 Day2 解题报告 Noip 2013 Day2 解题报告 --By GreenCloudS 第一题:积木大赛...
NOIP算法总结
NOIP算法总结_电脑基础知识_IT/计算机_专业资料。NOIP 算法总结 BY.W.X 吃了、还得睡 (一)数论 1.最大公约数,最小公倍数 2.筛法求素数 3. mod 规律...
2014 NOIP算法快速入门教程(中国计算机学会编)
2014 NOIP 算法快速入门 中国计算机学会编 2014 中国计算机学会 2014 算法基础篇...在 n 很大时,不同数量级的时间复杂度有:O(1)< O(log n)<O(n)< 2 ...
更多相关标签:
noip2015提高组day2 | noip2016day2 | noip2016提高组day2 | noip2015 day2 | noip2015day2解题报告 | noip2014提高组day2 | noip2014day2 | noip2012day2 |