第4讲 贪心法与构造法1

1、一、贪心法 从问题的某一个初始解出发，向给定的目从问题的某一个初始解出发，向给定的目标递推。推进的每一步不是依据某一固定的标递推。推进的每一步不是依据某一固定的递推式，而是做一个当时递推式，而是做一个当时看似最佳看似最佳的贪心选的贪心选择，不断地将问题实例归纳为更小的相似的择，不断地将问题实例归纳为更小的相似的子问题，并期望通过所做的局部最优选择产子问题，并期望通过所做的局部最优选择产生出一个全局最优解。生出一个全局最优解。删数问题 键盘输入一个高精度的正整数键盘输入一个高精度的正整数N，去掉其中任意，去掉其中任意S个数个数字后剩下的数字按原左右次序将组成一个新的正整数。字后剩下的数字按原左右

2、次序将组成一个新的正整数。编程对给定的编程对给定的N和和S，寻找一种方案使得剩下的数字组，寻找一种方案使得剩下的数字组成的新数最小。成的新数最小。 输出应包括所去掉的数字的位置和组成的新的正整数。输出应包括所去掉的数字的位置和组成的新的正整数。(N不超过不超过240位位) 输入数据均不需判错。输入数据均不需判错。 试题中正整数试题中正整数N 的有效位数为的有效位数为240位，必须采用位，必须采用可含可含256个字符的字串来替代整数。个字符的字串来替代整数。 贪心选择贪心选择:使用尽可能逼尽目标的方法来逐一删去其使用尽可能逼尽目标的方法来逐一删去其中中S个数符个数符,每一步总是选择一个使剩下的数

3、最小的数每一步总是选择一个使剩下的数最小的数符删去。符删去。 按低位按低位高位的方向搜索递增区间。若不存在递高位的方向搜索递增区间。若不存在递增区间，则删尾数符；否则删递增区间的尾字符，这增区间，则删尾数符；否则删递增区间的尾字符，这样形成了一个新数串。然后回到串尾，重复上述规则，样形成了一个新数串。然后回到串尾，重复上述规则，删下一数符删下一数符依此类推，直至删除依此类推，直至删除S个数符为止。个数符为止。例如例如:N=178543,S=4,删数过程如下删数过程如下: N=1 7 8 5 4 3 1 7 5 4 3 1 5 4 3 1 4 3 1 3 readln(N); 输入数串输入数串

4、readln(S); 输入应删的数字个数输入应删的数字个数 while S0 do begin 逐一删去逐一删去S个数符个数符 i:=1; while (ilength(N) and (Ni1)and(N1=0)do delete(N,1,1);删去删去串头的无用零串头的无用零 writeln(N); 输出剩下的数码输出剩下的数码贪心法的特点贪心法的特点1.贪心选择性质贪心选择性质可通过做局部最优可通过做局部最优(贪心贪心)选择来达选择来达到全局最优解到全局最优解 贪心策略通常是自顶向下做的。第一步为一个贪心策略通常是自顶向下做的。第一步为一个贪心选择，将原问题变成一个相似的、但贪心选择，将原

5、问题变成一个相似的、但规模更小规模更小的问题，而后的每一步都是当前看似最佳的选择。的问题，而后的每一步都是当前看似最佳的选择。 这种选择可能依赖于已作出的所有选择，但不这种选择可能依赖于已作出的所有选择，但不依赖依赖有待于做的选择或子问题的解有待于做的选择或子问题的解。 从求解的全过程来看，每一次贪心选择都将当从求解的全过程来看，每一次贪心选择都将当前问题归纳为前问题归纳为更小的相似子问题更小的相似子问题，而每一个选择都，而每一个选择都仅做一次，无重复回溯过程，因此贪心法有较高的仅做一次，无重复回溯过程，因此贪心法有较高的时间效率。时间效率。2.最优子结构最优子结构问题的最优解包含了子问题的最

6、优解。问题的最优解包含了子问题的最优解。 背包问题 有一个贼在偷窃一家商店时发现有有一个贼在偷窃一家商店时发现有N件物品件物品:第件物第件物品值品值V 元，重元，重Wi 磅，磅，(1in)，此处，此处Vi 和和Wi 都是整都是整数。他希望带走的东西越值钱越好，但他的背包中最数。他希望带走的东西越值钱越好，但他的背包中最多只能装下多只能装下W磅的东西磅的东西(W为整数为整数)。有两种偷窃方式。有两种偷窃方式: 1.01背包问题背包问题 如果每件物品或被带走或被留下，小偷应该带走哪如果每件物品或被带走或被留下，小偷应该带走哪几件东西几件东西? 2.部分背包问题部分背包问题 如果允许小偷可带走某个物

7、品的一部分，小偷应该如果允许小偷可带走某个物品的一部分，小偷应该带走哪几件东西，每件东西的重量是多少带走哪几件东西，每件东西的重量是多少?采用贪心策略来解决部分背包问题采用贪心策略来解决部分背包问题: 先对每件物品计算其每磅价值先对每件物品计算其每磅价值Vi Wi ，然后按每磅，然后按每磅价值单调递减的顺序对所有物品排序。例如，总共有价值单调递减的顺序对所有物品排序。例如，总共有三件物品和一个背包三件物品和一个背包 按照一种贪心策略，窃贼开始时对具有最大的每按照一种贪心策略，窃贼开始时对具有最大的每磅价值的物品尽量多拿一些。如果他拿完了该物品后仍磅价值的物品尽量多拿一些。如果他拿完了该物品后仍

8、可以取一些其他物品时，他就再取具有次大的每磅价值可以取一些其他物品时，他就再取具有次大的每磅价值的物品，一直继续下去，直到不能取为止的物品，一直继续下去，直到不能取为止 设设List为物件序列，其中为物件序列，其中listI.k, listI.w, listI.v, listI. pper为物件为物件I的编号、的编号、重量、价值和每磅价值重量、价值和每磅价值Readln(F, N, W);读入物件数读入物件数n和背包容量和背包容量w； For i := 1 to N Do Begin 读物件读物件i的重量的重量Listi.w和价值和价值Listi.v, Listi.vper := Listi.

9、v / Listi.w Listi.k := i;计算其每磅价值并记下编号计算其每磅价值并记下编号 End;for 对对List 按每磅价值递减的顺序进行排序按每磅价值递减的顺序进行排序; V := 0; i := 1; Writeln(Num:5, Weight:9, Value:8);打印表目打印表目 While W Listi.w Do Begin依次取走当前最值钱的物件依次取走当前最值钱的物件,并累计窃走物件的价并累计窃走物件的价值和值和 W := W - Listi.w; V := v + Listi.v; 输出当前窃走的物件的序号输出当前窃走的物件的序号Listi.k 、重量、重量

10、Listi.w和价值和价值Listi.v; Inc(i); End;while V := V + W * Listi.vper;小偷带走最后一件物品的一部分小偷带走最后一件物品的一部分,累计输出总价值累计输出总价值 输出最后一件物品的序号输出最后一件物品的序号Listi.k 、被窃部分的重量、被窃部分的重量W和价值和价值W * Listi.vper输出总价值输出总价值V ; 由此可见，在部分背包问题中，当我们在考虑是否把一件物品加由此可见，在部分背包问题中，当我们在考虑是否把一件物品加到背包中时，不需要把加入该物品的子问题解与不取该物品的子到背包中时，不需要把加入该物品的子问题解与不取该物品的

11、子问题解加以比较。由这种贪心方式所形成的所有子问题是互相独问题解加以比较。由这种贪心方式所形成的所有子问题是互相独立的。立的。 若对若对01背包问题采取贪心策略的话，顺序取物品背包问题采取贪心策略的话，顺序取物品1和和2 但是从左图可以看出，最优解取的是物品但是从左图可以看出，最优解取的是物品2 2和，没有取物品和，没有取物品1 1。两种包含物品。两种包含物品1 1的的可能解都不是最优解可能解都不是最优解 加油已知一辆汽车加满油后可行驶已知一辆汽车加满油后可行驶n公里，而旅途公里，而旅途中有若干个加油站。试设计一个有次算法，中有若干个加油站。试设计一个有次算法，指出应在哪些加油站停靠加油，使沿

12、途加油指出应在哪些加油站停靠加油，使沿途加油次数最少。输入一辆汽车加满油后可行驶的次数最少。输入一辆汽车加满油后可行驶的距离距离n、加油站数、加油站数m、两地的距离、两地的距离s和每一个和每一个加油站至出发点的距离，输出汽车停靠的加加油站至出发点的距离，输出汽车停靠的加油站序号。油站序号。贪心法贪心法按照由近及远的顺序排列加油站按照由近及远的顺序排列加油站在在0位置和位置和s位置虚拟位置虚拟0站和站和m+1站站若任意相邻两站的距离超过若任意相邻两站的距离超过n，则失败退出，则失败退出 从从0站出发站出发 ，依次计算加满油后可行驶的，依次计算加满油后可行驶的最远站最远站 readln(n,m,s

13、); 输入一辆汽车加满油后可行驶的距离输入一辆汽车加满油后可行驶的距离n、加油站数、加油站数m、两地、两地的距离的距离s for i:=1 to m do输入每一个加油站至出发点的距离输入每一个加油站至出发点的距离 beginread(disi); cdi:=i end; for i:=1 to m-1 do按照由近及远的顺序排列加油站按照由近及远的顺序排列加油站 for j:=i+1 to m do if disidisj then begin tp:=cdi; cdi:=cdj; cdj:=tp; tp:=disi; disi:=disj; disj:=tp;end; dis0:=0; d

14、ism+1:=s;在在位置和位置和s位置虚拟位置虚拟站和站和m+1站站 cd0:=0; cdm+1:=m+1; for i:=0 to m do若相邻两站的距离超过若相邻两站的距离超过n，则失败退出，则失败退出 if disi+1-disin then begin writeln(Impossible.); halt end; nw:=0;从从站出发站出发 while nwm+1 do若未驶过若未驶过s距离，则循环距离，则循环 begin j:=nw+1;从从nw出发，计算加满油后可行驶的最远站出发，计算加满油后可行驶的最远站j while (jm+1) and (disj+1-disnw=n

15、) do inc(j); nw:=j;若最远站若最远站j未超出未超出s距离，则输出距离，则输出 if nwm+1 then write(cdnw, ) end;会场安排 我们要在足够多的会场里活动，一个会场在我们要在足够多的会场里活动，一个会场在同一时刻只能安排一个活动，希望使用尽可同一时刻只能安排一个活动，希望使用尽可能少的会场。输入活动数能少的会场。输入活动数n和和n个活动的开个活动的开始时间始时间si和结束时间和结束时间fi(1in),输出最少会场输出最少会场数和每个会场的活动安排。数和每个会场的活动安排。设设s,f为活动的开始序列和结束序列；为活动的开始序列和结束序列；c为会场为会场的

16、结束序列；的结束序列；贪心策略：按照结束时间的顺序排列活动。依贪心策略：按照结束时间的顺序排列活动。依次枚举每一个活动次枚举每一个活动i： 计算活动计算活动i开始前最晚结束的教室开始前最晚结束的教室l 。若活动。若活动i开开始前没有空闲的教室，则新增一个教室（始前没有空闲的教室，则新增一个教室（inc(k); ck:=fi; l:=k）；否则教室）；否则教室l使用到活动使用到活动i结束时结束时（cl:=fi ） readln(fl,n);输入活动数输入活动数nfor i:=1 to n do readln(fl,si,fi);输入输入n个活动的开始时间个活动的开始时间si和结束和结束时间时间f

17、ifor i:=1 to n-1 do按照结束时间的顺序排列活动按照结束时间的顺序排列活动 for j:=i+1 to n do if fjfithen begin change(fi,fj); change(si,sj)end;fillchar(c,sizeof(c),0);k:=0;会场数初始化会场数初始化for i:=1 to n do按照结束时间的顺序枚举每一个活动按照结束时间的顺序枚举每一个活动 begin l:=0;在活动在活动i开始前最晚结束的教室开始前最晚结束的教室l for j:=1 to k do if (cjcl)then l:=j; if l=0若活动若活动i开始前没有

18、空闲的教室，则新增一个教室开始前没有空闲的教室，则新增一个教室 then begin inc(k); ck:=fi; l:=k end else cl:=fi;教室教室l使用到活动使用到活动i结束时结束时 writeln(fl0,活动活动,i,使用教室使用教室,l,.) end; 比赛问题给定给定N名学生和名学生和K个赛场，第个赛场，第i个赛场最多有个赛场最多有Ni名学生参赛，名学生参赛，N=N1+.+NK每个赛场有一个等级值每个赛场有一个等级值Q，每个学生有一个能，每个学生有一个能力值力值P和权重和权重W，需要安排每个学生去参加竞，需要安排每个学生去参加竞赛。仅当一个学生的赛。仅当一个学生的

19、P值大于一个赛场的值大于一个赛场的Q值，值，这名学生参加这个赛场的比赛后可以有这名学生参加这个赛场的比赛后可以有WI的的收益。每个学生只能参加一个比赛。求收益最收益。每个学生只能参加一个比赛。求收益最大的参赛方案。大的参赛方案。贪心方案贪心方案 将所有学生按照权重值将所有学生按照权重值w排序，显然最优方排序，显然最优方案中，选中的人可以是案中，选中的人可以是w值最大的几个。那值最大的几个。那么我们从么我们从w值最大的开始考虑，不妨将其放值最大的开始考虑，不妨将其放入他所能参加的、等级值入他所能参加的、等级值Q最大的考场。最大的考场。 设赛场序列设赛场序列part,其中赛场其中赛场i的人数为的人

20、数为parti.N,输输入顺序为入顺序为parti.num,等级值为等级值为 parti.Q 学生序列为学生序列为data,其中学生其中学生i的能力值为的能力值为datai.P,权重为权重为datai.w,输入顺序为输入顺序为datai.num、输入每个赛场的人数、输入每个赛场的人数parti.N和等级值和等级值parti.Q，设置输入顺序，设置输入顺序parti.num ，累计总，累计总人数人数m，按照赛场等级值，按照赛场等级值parti.Q递减的顺序递减的顺序排列排列part (1ik) 2、读每个人的能力值、读每个人的能力值datai.P、权重、权重datai.w，设置输入顺序设置输入顺

21、序datai.num，按照权重，按照权重datai.w递增的顺序排列递增的顺序排列data (1im) for i := M downto 1 do 按照权重递减的顺序安排每个队员的赛场按照权重递减的顺序安排每个队员的赛场 begin j := 1;按照赛场等级值递减的顺序挑选适合队员按照赛场等级值递减的顺序挑选适合队员i的赛场的赛场 while j 0) and (partj.Q K 若没有适合队员若没有适合队员i的赛场，则按照赛场等级值递减的顺序寻找一个尚剩的赛场，则按照赛场等级值递减的顺序寻找一个尚剩队员的赛场队员的赛场j，队员，队员i参加该赛场比赛参加该赛场比赛 then begin

22、j := 1; while (partj.N = 0) do inc(j); dec(partj.N);Zdatai.num := partj.num; 赛场赛场j的队员人数减一，记的队员人数减一，记下队员下队员i所在的赛场所在的赛场 end; end; for i := 1 to M do输出输出Zi ;任务调度问题一个单位时间任务是个作业一个单位时间任务是个作业,如要在计算机上运行一个如要在计算机上运行一个程序程序,它恰覆盖一个单位的运行时间它恰覆盖一个单位的运行时间.给定一个单位时间给定一个单位时间任务的集合任务的集合S,对对S的一个调度即的一个调度即S的一个排列的一个排列,其中规定其中

23、规定了这些任务的执行顺序了这些任务的执行顺序.该调度中的第一个任务开始于该调度中的第一个任务开始于时间时间0,结束于时结束于时1;第二个任务开始于时间第二个任务开始于时间1,结束于时间结束于时间2, 单处理器上具有期限和罚款的单位时间任务调度问单处理器上具有期限和罚款的单位时间任务调度问题的输入如下题的输入如下: 1.包含包含n个单位时间任务的集合个单位时间任务的集合S=1,2,n; 2.n个取整的期限个取整的期限d1 ,dn ,(1d,n),任务任务i要求在要求在di 前完成前完成; 3.n个非负的权个非负的权(或罚款或罚款)w1 ,wn .如果任务如果任务i没在没在时间时间di 之前结束之

24、前结束,则导致罚款则导致罚款wi ; 要求找出要求找出S的一个调度的一个调度,使之最小化总的罚款使之最小化总的罚款.概念概念 迟任务迟任务调度中在规定期限后完成的任调度中在规定期限后完成的任务，试题要求迟任务的罚款总和最小化务，试题要求迟任务的罚款总和最小化; ; 早任务早任务调度中在规定期限前完成的任调度中在规定期限前完成的任务，早任务的罚款总和最大化对应问题的务，早任务的罚款总和最大化对应问题的解解两个贪心 1 1、按照罚款的单调递减顺序来安排各个子任务，使、按照罚款的单调递减顺序来安排各个子任务，使得早任务的罚款总和最大化得早任务的罚款总和最大化 2 2、在时序上保证指定任务尽早完成。实

25、现方式：、在时序上保证指定任务尽早完成。实现方式： . .按期限递增的顺序对早任务进行调度。即只按期限递增的顺序对早任务进行调度。即只要在调度中有两个分别完成于时间要在调度中有两个分别完成于时间K K和和K+1K+1的早任务的早任务i i、j j且且djdidjdi，我们就互换，我们就互换i i和和j j的位置，使得任务的位置，使得任务i i在交在交换后仍然是早的，而任务换后仍然是早的，而任务j j被移到更前的位置被移到更前的位置; ; 两个贪心 . .如果某个早任务如果某个早任务X X跟在迟任务跟在迟任务Y Y之后，我们可以交换之后，我们可以交换X X和和Y Y的位置，使得早任务先于迟任务的

26、位置，使得早任务先于迟任务; ;某一调度中早某一调度中早任务的集合构成了一个独立的任务集任务的集合构成了一个独立的任务集A A，因为，因为A A中任务中任务按期限单调递增的顺序进行调度后，没有一个任务是按期限单调递增的顺序进行调度后，没有一个任务是迟的，且迟的，且A A中期限为或更早的任务个数小于等于。中期限为或更早的任务个数小于等于。 设目前早任务个数为设目前早任务个数为num, num, 早任务集合中期限小于早任务集合中期限小于等于等于numnum的任务个数为的任务个数为t t。若。若tditdi，则当前第，则当前第i i个任务个任务作为早任务插入第作为早任务插入第num+1num+1个空

27、位。个空位。 最初，我们设所有最初，我们设所有n n个时间空位都是空的。然后按罚款的单调个时间空位都是空的。然后按罚款的单调递减顺序递减顺序( (任务任务1 1，任务，任务2 2，任务，任务3 3，任务，任务4 4，任务，任务5 5，任务，任务6 6，任，任务务7)7)来考虑各个子任务。在考虑任务来考虑各个子任务。在考虑任务j j时，如果有一个恰处于时，如果有一个恰处于或前于或前于dj dj 的时间空位仍空着，则将任务的时间空位仍空着，则将任务j j赋与最近的这样的赋与最近的这样的空位，并填入空位，并填入; ;如果不存在这样的空位，则将任务如果不存在这样的空位，则将任务j j赋与一个赋与一个还

28、未被占的、最近的空位。还未被占的、最近的空位。 按上述贪心策略选择了任务按上述贪心策略选择了任务1 1，2 2，3 3，4 4，7 7，放弃任务，放弃任务5 5，6 6。最终的最优调度为最终的最优调度为2 2，3 3，4 4，1 1，7 7，5 5，6 6， 任务1234567期限d4243146罚款w 70605040302010设设N任务个数任务个数,num目前早任务个数目前早任务个数;t罚款总和罚款总和 list任务序列。其中任务序列。其中listi.k、 listi.d、 listi.w为任务为任务I的编号的编号,期限和罚款。期限和罚款。 listi.k0,则任务则任务i为迟任务为迟任

29、务;lt辅助数组辅助数组 Pck为早任务的编号序列；为早任务的编号序列；算法如下：算法如下： 读入任务数读入任务数N; For i := 1 to N Do Begin, 读入任务读入任务i的期限的期限Listi.d和罚款和罚款Listi.w; Listi.k := I记下其序号记下其序号 End;for list序列按罚款单调递减的顺序排序序列按罚款单调递减的顺序排序 ； num := 0; For i := 1 to N Do Begin依次处理每一个任务依次处理每一个任务 t := 0;统计目前统计目前num个早任务中期限小于等于个早任务中期限小于等于num的的任务个数任务个数t For

30、 j := 1 to num Do If ListPckj.d = num Then Inc(t); If t 1) And (ListPckj.d 0 Then Begin打印迟任务的序号打印迟任务的序号Listi.k; t := t + Listi.w；End;then输出总罚款数输出总罚款数 t;二、构造法通过构造数学模型或方法解决问题。数学建模：通过沿用经典的数学思想建立起模数学建模：通过沿用经典的数学思想建立起模型；或者提取现实世界中的有效信息，用简明的型；或者提取现实世界中的有效信息，用简明的方式表达其规律，这种规律可以是一条代数公式、方式表达其规律，这种规律可以是一条代数公式、一

31、幅几何图形，一个物理原理、一个化学方程式，一幅几何图形，一个物理原理、一个化学方程式，等等。等等。直接构造问题解答：只是构造法运用的一种简直接构造问题解答：只是构造法运用的一种简单类型。它只能针对问题本身，探索其独有性质，单类型。它只能针对问题本身，探索其独有性质，不具备可推广性。不具备可推广性。构造法解题的类型 对应策略：对应策略：将问题将问题a对应另一个便于思考或有求解方法的问对应另一个便于思考或有求解方法的问题题b，化繁为简，变未知为已知。，化繁为简，变未知为已知。 分治策略：分治策略：将问题的规模逐渐减少，可明显降低解决问题复将问题的规模逐渐减少，可明显降低解决问题复杂程度。算法设计的

32、这种策略称之为分治策略，即对问题分而杂程度。算法设计的这种策略称之为分治策略，即对问题分而治之。治之。 递推的分治策略递推的分治策略 递归的分治策略递归的分治策略 在建模过程中经常使用的策略在建模过程中经常使用的策略归纳策略：归纳策略：归纳策略则是通过列举试题本身的特殊情况，经归纳策略则是通过列举试题本身的特殊情况，经过深入分析，最后概括出事物内在的一般规律，并得到一种高过深入分析，最后概括出事物内在的一般规律，并得到一种高度抽象的解题模型。度抽象的解题模型。 递推式递推式 递归式递归式 制定目标制定目标 贪心方案贪心方案 在建模过程中经常使用的策略在建模过程中经常使用的策略模拟策略：模拟策略

33、：模拟某个过程，通过改变数学模型的各种参数，模拟某个过程，通过改变数学模型的各种参数，进而观察变更这些参数所引起过程状态的变化，由此展开算法设进而观察变更这些参数所引起过程状态的变化，由此展开算法设计。模拟题没有固定的模式，一般形式有两种：计。模拟题没有固定的模式，一般形式有两种： 随机模拟：随机模拟：题目给定或者隐含某一概率。设计者利用随题目给定或者隐含某一概率。设计者利用随机函数和取整函数设定某一范围的随机值，将符合概率的随机值机函数和取整函数设定某一范围的随机值，将符合概率的随机值作为参数。然后根据这一模拟的数学模型展开算法设计。由于解作为参数。然后根据这一模拟的数学模型展开算法设计。由

34、于解题过程借助了计算机的伪随机数发生数，其随机的意义要比实际题过程借助了计算机的伪随机数发生数，其随机的意义要比实际问题中真实的随机变量稍差一些，因此模拟效果有不确定的因素；问题中真实的随机变量稍差一些，因此模拟效果有不确定的因素；模拟策略：模拟策略：过程模拟：题目不给出概率，要求编程者按照题意设计过程模拟：题目不给出概率，要求编程者按照题意设计数学模型的各种参数，观察变更这些参数所引起过程状态的变化，数学模型的各种参数，观察变更这些参数所引起过程状态的变化，由此展开算法设计。模拟效果完全取决于过程模拟的真实性和算由此展开算法设计。模拟效果完全取决于过程模拟的真实性和算法的正确性，不含任何不确

35、定因素。由于过程模拟的结果无二义法的正确性，不含任何不确定因素。由于过程模拟的结果无二义性，因此竞赛大都采用过程模拟。性，因此竞赛大都采用过程模拟。模拟的解题方法一般有三种类型模拟的解题方法一般有三种类型 直叙式模拟直叙式模拟 筛选法模拟筛选法模拟 构造法模拟构造法模拟一般方法机理分析法统计分析法根据客观事物的特性，分析其内部的机理，弄清关系，根据客观事物的特性，分析其内部的机理，弄清关系，在适当抽象的条件下，得到可以描述事物属性的数学在适当抽象的条件下，得到可以描述事物属性的数学工具。工具。我们在联赛中可以用这种方法建立数学模型，然后根我们在联赛中可以用这种方法建立数学模型，然后根据所对应的

36、算法求出解。如下图所示：据所对应的算法求出解。如下图所示：机理分析法机理分析法计算最后9位问问N位正整数中，有多少个整数的平方的最后位正整数中，有多少个整数的平方的最后9位是位是987654321？数据量：？数据量：1n106输入：输入： n输出：输出： 方案数方案数1、在、在N10时，由于题目只是问时，由于题目只是问“最后最后9位位”，所以只要在所以只要在72后加入后加入(N-10)个个“0”就可以了。就可以了。 readln(n); if n9 then begin write(72); for i:=11 to n do write(0); writeln end数列给定一个正整数给定一

37、个正整数k(3k15),k(3k15),把所有把所有k k的方幂及所有有限个互不相的方幂及所有有限个互不相等的等的k k的方幂之和构成一个递增的序列，例如，当的方幂之和构成一个递增的序列，例如，当k=3k=3时，这个序列时，这个序列是：是：1 1，3 3，4 4，9 9，1010，1212，1313，（该序列实际上就是：（该序列实际上就是：3 30 0，3 31 1，3 30 0+3+31 1，3 32 2，3 30 0+3+32 2，3 31 1+3+32 2，3 30 0+3+31 1+3+32 2，）请你求出这个序列的第请你求出这个序列的第N N项的值（用项的值（用1010进制数表示）。

38、进制数表示）。例如，对于例如，对于k=3k=3，N=100N=100，正确答案应该是，正确答案应该是981981。【输入文件】输入文件【输入文件】输入文件sequence.in sequence.in 只有只有1 1行，为行，为2 2个正整数，用一个正整数，用一个空格隔开：个空格隔开： k Nk N（k k、N N的含义与上述的问题描述一致，且的含义与上述的问题描述一致，且3k153k15，10N100010N1000）。）。【输出文件】输出文件【输出文件】输出文件sequence.out sequence.out 为计算结果，是一个正整数为计算结果，是一个正整数（在所有的测试数据中，结果均不

39、超过（在所有的测试数据中，结果均不超过2.12.1* *10109 9）。（整数前不要）。（整数前不要有空格和其他符号）。有空格和其他符号）。 题目大意求由有限个不同的求由有限个不同的k k的方幂组成的递增数列中的第的方幂组成的递增数列中的第N N项。项。算法算法1 1、递增序列的特征、递增序列的特征递增的序列由递增的序列由k k的方幂及所有有限个互不相等的的方幂及所有有限个互不相等的k k的方幂的方幂之和构成：之和构成：k k0 0，k k1 1，k k0 0+k+k1 1，k k2 2，k k0 0+k+k2 2，k k1 1+k+k2 2，k k0 0+k+k1 1+k+k2 2，其中第

40、其中第n n项指明了项指明了k k的方幂的方幂11方幂方幂loglog2 2n n中哪些方幂存在，中哪些方幂存在，哪些方幂不存在，例如第哪些方幂不存在，例如第7 7项方幂项方幂0 0、方幂、方幂1 1和方幂和方幂2 2存在，存在，其它方幂不存在，正好与二进制数其它方幂不存在，正好与二进制数111111对应。对应。 计算递增数列中第N项的方法 将将n n进行二进制数转化，得到的二进制数进行二进制数转化，得到的二进制数(n)(n)2 2。其中值为。其中值为1 1的位序号指明了第的位序号指明了第n n项中哪些项中哪些方幂存在。这些方幂之和构成了递增数列中第方幂存在。这些方幂之和构成了递增数列中第N

41、N项。例如项。例如k=3k=3，N=100N=100，N N2 2=1100100=1100100，因此递，因此递增序列的第增序列的第N N项为项为3 36 6+3+35 5+3+32 2=981=981。 算法复杂度算法复杂度O(logN)O(logN)。计算序列的第N项值ans:=0; tot:=0; ans:=0; tot:=0; 当前项的值和当前项的值和n n的二进制位初始化的二进制位初始化 while n0 do while n0 do若若n n的二进制位未分析完的二进制位未分析完 begin begin if odd(n) if odd(n) 若若n n的第的第tottot二进制位

42、为二进制位为1 1，则累计，则累计k ktottot then ans:=ans+intpower(k,tot);then ans:=ans+intpower(k,tot); inc(tot);n:=n div 2 inc(tot);n:=n div 2准备分析准备分析n n的下一个二进制的下一个二进制位位 end end输出输出ansans；传球游戏 N个人围圈玩传球游戏，开始时第一个人拿个人围圈玩传球游戏，开始时第一个人拿着球，每个人把球传给左手的第着球，每个人把球传给左手的第K个人。满个人。满足足1KN/2。求。求K的最大值，使得第一个人的最大值，使得第一个人重新拿到球之前，每个人都拿过

43、球。重新拿到球之前，每个人都拿过球。输入：输入： 数串数串n（3 N 10200)输出：输出： K的最大值的最大值规律规律 如果人数如果人数n和间隔和间隔k互质，则无论从互质，则无论从哪个位置开始传球，都能够使得每哪个位置开始传球，都能够使得每一个人都拿到球。一个人都拿到球。数学模型数学模型数学语言描述数学语言描述 给定一个整数给定一个整数N，要求一个尽可能大的整数，要求一个尽可能大的整数K，满足满足1KN/2，且，且(K, N) = 1。基本事实基本事实 (N-1, N)=1，或者说，或者说(N-p, N)p在在N为奇数的情况下为奇数的情况下 K*2=N-1 ，(K*2, N) = 1可以得

44、到可以得到(K, N)=1 K的上限的上限是是N/2直接输出直接输出N/2即可。即可。在在N为偶数的情况下为偶数的情况下第一种情况第一种情况:N是偶数且为是偶数且为4的倍数的倍数 N/2是偶数，是偶数，（ N/2 ，N）1, K= N/2不可能符合要不可能符合要求求； N/2-1是奇数，是奇数， (N/2-1, N/2)=1。K= N/2-1满满足题意。足题意。第二种情况第二种情况: N是偶数但不是是偶数但不是4的倍数的倍数 N/2-1也是偶数，也是偶数， K= N/2-1不可能是正确答案不可能是正确答案; N/2-2是奇数。根据刚才的介绍，有是奇数。根据刚才的介绍，有(N/2-2, N/2)

45、2，但，但是是N/2是奇数，所以是奇数，所以(N/2-2, N/2)=1。最后同样可以得到。最后同样可以得到(N/2-2, N)=1。 K= N/2-2满足题意。满足题意。 if (N.len = 1) and (N.data1 2)，则可，则可以通过序列中第以通过序列中第i-1个数推出第个数推出第i格是否有雷。格是否有雷。第第2格的雷数则只需要由第一格的雷数和序列格的雷数则只需要由第一格的雷数和序列第一个数推出。第一个数推出。第一格的雷数需要枚举第一格的雷数需要枚举 设设Ai表示序列中第表示序列中第i个元素，个元素，Fi表示第表示第I格的雷数。格的雷数。递推式递推式 但是但是F F1 1的值

46、还是未知的，由于每一格就是有雷和无雷两的值还是未知的，由于每一格就是有雷和无雷两种状态，显然我们可以枚举第一格雷的状态，即种状态，显然我们可以枚举第一格雷的状态，即F F1 1的值的值为为0 0或者或者1 1，这样就可以递推得到所有的，这样就可以递推得到所有的F F值。值。非法状态：非法状态： F Fi i（1=i=n1=i=n）的值不为）的值不为0 0，1 1； F Fn n+F+Fn-1n-1AAn n；如果不出现上述非法情况，就得到一种可行的分布方案，如果不出现上述非法情况，就得到一种可行的分布方案，所以最后答案不外乎所以最后答案不外乎0 0， 1 1， 2 2三种。三种。 readln

47、(n);输入地雷序列的长度输入地雷序列的长度for i := 1 to n do read(numi);输入数字序列输入数字序列numif n = 1 单独格子的情况处理单独格子的情况处理 then if num1=1 then ans:= 1 else ans:= 0 else for r := 0 to 1 do 枚举第一格是否是雷枚举第一格是否是雷 begin a1:= r; p := true;第一格有雷数第一格有雷数r，合法状态初始化，合法状态初始化 for i:=2 to n do递推各格子的地雷数并判断是否合法递推各格子的地雷数并判断是否合法 begin ai:=numi-1-a

48、i-1-ai-2;递推格子递推格子i的雷数的雷数 if(ai1)非法状态非法状态,第一格的雷数取第一格的雷数取r+1 then begin p := false; break;end; end; if p and (an + an - 1 = numn) then inc(ans);若合法且满足数字规律，则累计方案若合法且满足数字规律，则累计方案 end;writeln(ans); 装货 有一些空的柜台被排成一列，它们分别属于有一些空的柜台被排成一列，它们分别属于A或或B两家两家公司，比如可以表示成公司，比如可以表示成ABAAB，等等。，等等。 现在要将它们填上货物，填上货物的柜台不妨用加了现

49、在要将它们填上货物，填上货物的柜台不妨用加了括号的字母表示：括号的字母表示：(A)表示一个含有表示一个含有A公司产品的柜台，同公司产品的柜台，同理定义理定义(B)。现在要把初始的一排空柜台变成都有货物的。现在要把初始的一排空柜台变成都有货物的目标状态，比如目标状态，比如(B)(A)(B)(A)(B)等等。等等。 但变化是有规则的。每次变化可以选择一个空的柜台，但变化是有规则的。每次变化可以选择一个空的柜台，若是若是A，那么可以将其变为，那么可以将其变为(B)，也可以变成，也可以变成(A)BA；同样；同样若是若是B，那么可以变成，那么可以变成(A)，也可以变成，也可以变成(B)AB。根据这个。根

50、据这个规则，问有没有一种方法可以将初始状态变成目标状态。规则，问有没有一种方法可以将初始状态变成目标状态。输入：输入： 初始的空柜台状态初始的空柜台状态 有货物的目标状态（有货物的目标状态（1最终块数最终块数30000）输出：输出：yes或或no 每次注意初始状态和终止状态的第一个柜台：每次注意初始状态和终止状态的第一个柜台： 如果相同，那么显然要使用如果相同，那么显然要使用A(A)BA或是或是B(B)AB的变化方法。即初始状态下一次的柜台的变化方法。即初始状态下一次的柜台取另一家公司；取另一家公司； 如果不同，只能使用如果不同，只能使用A(B)或是或是B(A)。即比较。即比较初始状态和终止状

51、态的后一个柜台；初始状态和终止状态的后一个柜台； 这样每次可选择的规则只有一种，那么这题这样每次可选择的规则只有一种，那么这题的实质不过是模拟一个变化规则，问是否可以的实质不过是模拟一个变化规则，问是否可以从初始状态变化到终止状态而已。从初始状态变化到终止状态而已。Type Tdata = array1.Limit of char;Var data1 ,data2 : Tdata; 初始的空柜台状态和有货物的目初始的空柜台状态和有货物的目标状态标状态 Len1 , Len2 : longint;初始状态和目标状态的指针初始状态和目标状态的指针 answer : boolean;有解标志有解标志

52、注意注意:计算前计算前,将初始状态将初始状态data1和目标状态和目标状态data2倒序便倒序便于处理于处理 初始状态初始状态data1和目标状态和目标状态data2倒序；倒序； while (Len1 0) and (Len1 = Len2) do若初始状态未搜索完且目若初始状态未搜索完且目标状态指针在初始状态指针右方标状态指针在初始状态指针右方 if data1Len1data2Len2若初始状态和目标状态的当前字符若初始状态和目标状态的当前字符不同，则左移两指针，比较初始状态和终止状态的后一个柜台不同，则左移两指针，比较初始状态和终止状态的后一个柜台 then begin dec(Len

53、1); dec(Len2) end else begin若初始状态和目标状态的当前字符相同，则右移初始若初始状态和目标状态的当前字符相同，则右移初始状态指针，初始状态下一次的柜台取另一家公司状态指针，初始状态下一次的柜台取另一家公司 inc(Len1); if data1Len1 - 1=A若原位置为若原位置为A，则其右位置改为，则其右位置改为B；否则其右位置改为否则其右位置改为A then data1Len1 := B else data1Len1 := A; dec(Len2);左移目标状态指针左移目标状态指针 end; answer := (Len1 = 0) and (Len2 = 0

54、);若初始状态和目标状态同时若初始状态和目标状态同时调整完，则返回调整完，则返回true； if answer then writeln(YES) else writeln(NO); 身高 给定给定N个人的身高，从个人的身高，从1950mm至至2050mm不等，平均身高却正好是不等，平均身高却正好是2000mm。要求。要求找到这些队员的一个排列，满足对任意找到这些队员的一个排列，满足对任意K任意连续任意连续K个球员，他们的总身高和个球员，他们的总身高和2000*K mm相差不超过相差不超过100mm。猜想 如果能保证从第一个球员开始数任意连续个如果能保证从第一个球员开始数任意连续个（设为（设为

55、K个）球员，他们的身高总和与个）球员，他们的身高总和与2000*K mm相差不超过相差不超过50mm，那么这个序列就一定满，那么这个序列就一定满足题目的要求：设部分和为足题目的要求：设部分和为Si，若任意，若任意|Si-2000i|50，那么任意，那么任意ji，则队员，则队员i.队员队员j满足满足|(SjSi)-2000(j-i)| =|(Sj-2000j)(Si-2000i)|50*2=100满足题意。满足题意。构造数列构造数列1 1、所有数据减去基数、所有数据减去基数20002000，部分和需要满足的要求，部分和需要满足的要求是：任意是：任意|S|Si i|50|50、将、将N N个处理后

56、的数据分组：负数一组，非负数一个处理后的数据分组：负数一组，非负数一组。首先可以确定的是组。首先可以确定的是S S0 0为为0 0。假设已经构造出了数。假设已经构造出了数列的前列的前i i个数，即已经知道了个数，即已经知道了S Si i ：如果：如果S Si i是负数，是负数，则在非负数中任意选择一个作为第则在非负数中任意选择一个作为第( (i i+1)+1)个数。由个数。由于新加入的数不超过于新加入的数不超过5050，因此，因此S Si+1i+1一定不超过一定不超过5050；如；如果果S Si i是非负数，那么就在负数中任意选择一个（或是非负数，那么就在负数中任意选择一个（或者可以选择非负数组中的者可以选择非负数组中的0 0）作为第）作为第( (i i+1)+1)个数，这个数，这样也能保证样也能保证S Si+1i+1的绝对值不超过的绝对值不超过5050。问题：是否每次一定都能选择到一个呢？是不是问题：是否每次一定都能选择到一个呢？是不是可能待选集合为空呢？可能待选集合为空呢？ 不可能。因为如果不可能。因为如果S Si i是负数，而待