第4讲-贪心法与构造法1课件

贪心法与构造法一、贪心法 从问题的某一个初始解出发，向给定的从问题的某一个初始解出发，向给定的目标递推。推进的每一步不是依据某一固定目标递推。推进的每一步不是依据某一固定的递推式，而是做一个当时的递推式，而是做一个当时看似最佳看似最佳的贪心的贪心选择，不断地将问题实例归纳为更小的相似选择，不断地将问题实例归纳为更小的相似的子问题，并期望通过所做的局部最优选择的子问题，并期望通过所做的局部最优选择产生出一个全局最优解。产生出一个全局最优解。删数问题键键盘盘输输入入一一个个高高精精度度的的正正整整数数N，去去掉掉其其中中任任意意S个个数数字字后后剩剩下下的的数数字字按按原原左左右右次次序序将将组组成成一一个个新新的的正正整整数数。编编程程对对给给定定的的N和和S，寻寻找找一一种种方方案案使使得得剩剩下下的的数数字字组组成的新数最小。成的新数最小。输输出出应应包包括括所所去去掉掉的的数数字字的的位位置置和和组组成成的的新新的的正正整整数数。(N不超过不超过240位位)输入数据均不需判错。输入数据均不需判错。试题中正整数试题中正整数N的有效位数为的有效位数为240位，必须采用位，必须采用可含可含256个字符的字串来替代整数。个字符的字串来替代整数。贪心选择贪心选择:使用尽可能逼尽目标的方法来逐一删去其使用尽可能逼尽目标的方法来逐一删去其中中S个数符个数符,每一步总是选择一个使剩下的数最小的数每一步总是选择一个使剩下的数最小的数符删去。符删去。按低位按低位高位的方向搜索递增区间。若不存在递高位的方向搜索递增区间。若不存在递增区间，则删尾数符；否则删递增区间的尾字符，这增区间，则删尾数符；否则删递增区间的尾字符，这样形成了一个新数串。然后回到串尾，重复上述规则，样形成了一个新数串。然后回到串尾，重复上述规则，删下一数符删下一数符依此类推，直至删除依此类推，直至删除S个数符为止。个数符为止。例如例如:N=178543,S=4,删数过程如下删数过程如下:N=17854317543154314313readln(N);输入数串输入数串readln(S);输入应删的数字个数输入应删的数字个数whileS0dobegin逐一删去逐一删去S个数符个数符i:=1;while(ilength(N)and(Ni1)and(N1=0)do delete(N,1,1);删删去去串头的无用零串头的无用零writeln(N);输出剩下的数码输出剩下的数码贪心法的特点贪心法的特点1.贪贪心心选选择择性性质质可可通通过过做做局局部部最最优优(贪贪心心)选选择择来来达达到全局最优解到全局最优解贪贪心心策策略略通通常常是是自自顶顶向向下下做做的的。第第一一步步为为一一个个贪贪心心选选择择，将将原原问问题题变变成成一一个个相相似似的的、但但规规模模更更小小的问题，而后的每一步都是当前看似最佳的选择。的问题，而后的每一步都是当前看似最佳的选择。这这种种选选择择可可能能依依赖赖于于已已作作出出的的所所有有选选择择，但但不不依赖依赖有待于做的选择或子问题的解有待于做的选择或子问题的解。从从求求解解的的全全过过程程来来看看，每每一一次次贪贪心心选选择择都都将将当当前前问问题题归归纳纳为为更更小小的的相相似似子子问问题题，而而每每一一个个选选择择都都仅仅做做一一次次，无无重重复复回回溯溯过过程程，因因此此贪贪心心法法有有较较高高的的时间效率。时间效率。2.最优子结构最优子结构问题的最优解包含了子问题的最优解。问题的最优解包含了子问题的最优解。背包问题有有一一个个贼贼在在偷偷窃窃一一家家商商店店时时发发现现有有N件件物物品品:第第件件物物品品值值V元元，重重Wi磅磅，(1in)，此此处处Vi和和Wi都都是是整整数数。他他希希望望带带走走的的东东西西越越值值钱钱越越好好，但但他他的的背背包包中中最最多多只只能能装装下下W磅磅的的东东西西(W为为整整数数)。有有两两种种偷偷窃窃方方式式:1.01背包问题背包问题如如果果每每件件物物品品或或被被带带走走或或被被留留下下，小小偷偷应应该该带带走走哪哪几件东西几件东西?2.部分背包问题部分背包问题如如果果允允许许小小偷偷可可带带走走某某个个物物品品的的一一部部分分，小小偷偷应应该该带走哪几件东西，每件东西的重量是多少带走哪几件东西，每件东西的重量是多少?采用贪心策略来解决部分背包问题采用贪心策略来解决部分背包问题:先先对对每每件件物物品品计计算算其其每每磅磅价价值值ViWi，然然后后按按每每磅磅价价值值单单调调递递减减的的顺顺序序对对所所有有物物品品排排序序。例例如如，总总共共有有三件物品和一个背包三件物品和一个背包按按照照一一种种贪贪心心策策略略，窃窃贼贼开开始始时时对对具具有有最最大大的的每每磅磅价价值值的的物物品品尽尽量量多多拿拿一一些些。如如果果他他拿拿完完了了该该物物品品后后仍仍可可以以取取一一些些其其他他物物品品时时，他他就就再再取取具具有有次次大大的的每每磅磅价价值值的物品，一直继续下去，直到不能取为止的物品，一直继续下去，直到不能取为止设设List为为物物件件序序列列，其其中中listI.k,listI.w,listI.v,listI.pper为为物物件件I的的编编号号、重重量、价值和每磅价值量、价值和每磅价值Readln(F,N,W);读入物件数读入物件数n和背包容量和背包容量w；Fori:=1toNDoBegin读物件读物件i的重量的重量Listi.w和价值和价值Listi.v,Listi.vper:=Listi.v/Listi.wListi.k:=i;计算其每磅价值并记下编号计算其每磅价值并记下编号End;for对对List按每磅价值递减的顺序进行排序按每磅价值递减的顺序进行排序;V:=0;i:=1;Writeln(Num:5,Weight:9,Value:8);打印表目打印表目WhileWListi.wDoBegin依依次次取取走走当当前前最最值值钱钱的的物物件件,并并累累计计窃窃走走物物件件的的价价值和值和W:=W-Listi.w;V:=v+Listi.v;输出当前窃走的物件的序号输出当前窃走的物件的序号Listi.k、重量重量Listi.w和价值和价值Listi.v;Inc(i);End;whileV:=V+W*Listi.vper;小偷带走最后一件物品的一部分小偷带走最后一件物品的一部分,累计输出总价值累计输出总价值输出最后一件物品的序号输出最后一件物品的序号Listi.k、被窃部分的重量被窃部分的重量W和价值和价值W*Listi.vper输出总价值输出总价值V;由此可见，在部分背包问题中，当我们在考虑是否把一件物品加由此可见，在部分背包问题中，当我们在考虑是否把一件物品加到背包中时，不需要把加入该物品的子问题解与不取该物品的子到背包中时，不需要把加入该物品的子问题解与不取该物品的子问题解加以比较。由这种贪心方式所形成的所有子问题是互相独问题解加以比较。由这种贪心方式所形成的所有子问题是互相独立的。立的。若对若对01背包问题采取贪心策略的话，顺序取物品背包问题采取贪心策略的话，顺序取物品1和和2但但是是从从左左图图可可以以看看出出，最最优优解解取取的的是是物物品品2 2和和，没没有有取取物物品品1 1。两两种种包包含含物物品品1 1的的可能解都不是最优解可能解都不是最优解加油已知一辆汽车加满油后可行驶已知一辆汽车加满油后可行驶n公里，而旅途公里，而旅途中有若干个加油站。试设计一个有次算法，中有若干个加油站。试设计一个有次算法，指出应在哪些加油站停靠加油，使沿途加油指出应在哪些加油站停靠加油，使沿途加油次数最少。输入一辆汽车加满油后可行驶的次数最少。输入一辆汽车加满油后可行驶的距离距离n、加油站数、加油站数m、两地的距离、两地的距离s和每一个和每一个加油站至出发点的距离，输出汽车停靠的加加油站至出发点的距离，输出汽车停靠的加油站序号。油站序号。贪心法贪心法按照由近及远的顺序排列加油站按照由近及远的顺序排列加油站在在0位置和位置和s位置虚拟位置虚拟0站和站和m+1站站若任意相邻两站的距离超过若任意相邻两站的距离超过n，则失败退出，则失败退出从从0站出发站出发，依次计算加满油后可行驶的，依次计算加满油后可行驶的最远站最远站readln(n,m,s);输入一辆汽车加满油后可行驶的距离输入一辆汽车加满油后可行驶的距离n、加油站数、加油站数m、两地、两地的距离的距离sfori:=1tomdo输入每一个加油站至出发点的距离输入每一个加油站至出发点的距离beginread(disi);cdi:=iend;fori:=1tom-1do按照由近及远的顺序排列加油站按照由近及远的顺序排列加油站forj:=i+1tomdoifdisidisjthenbegintp:=cdi;cdi:=cdj;cdj:=tp;tp:=disi;disi:=disj;disj:=tp;end;dis0:=0;dism+1:=s;在在位置和位置和s位置虚拟位置虚拟站和站和m+1站站cd0:=0;cdm+1:=m+1;fori:=0tomdo若相邻两站的距离超过若相邻两站的距离超过n，则失败退出，则失败退出ifdisi+1-disinthenbeginwriteln(Impossible.);haltend;nw:=0;从从站出发站出发whilenwm+1do若未驶过若未驶过s距离，则循环距离，则循环beginj:=nw+1;从从nw出发，计算加满油后可行驶的最远站出发，计算加满油后可行驶的最远站jwhile(jm+1)and(disj+1-disnw=n)doinc(j);nw:=j;若最远站若最远站j未超出未超出s距离，则输出距离，则输出ifnwm+1thenwrite(cdnw,)end;会场安排我们要在足够多的会场里活动，一个会场在我们要在足够多的会场里活动，一个会场在同一时刻只能安排一个活动，希望使用尽可同一时刻只能安排一个活动，希望使用尽可能少的会场。输入活动数能少的会场。输入活动数n和和n个活动的开个活动的开始时间始时间si和结束时间和结束时间fi(1in),输出最少会场输出最少会场数和每个会场的活动安排。数和每个会场的活动安排。设设s,f为活动的开始序列和结束序列；为活动的开始序列和结束序列；c为会场为会场的结束序列；的结束序列；贪心策略：按照结束时间的顺序排列活动。依贪心策略：按照结束时间的顺序排列活动。依次枚举每一个活动次枚举每一个活动i：计算活动计算活动i开始前最晚结束的教室开始前最晚结束的教室l。若活动。若活动i开开始前没有空闲的教室，则新增一个教室（始前没有空闲的教室，则新增一个教室（inc(k);ck:=fi;l:=k）；否则教室）；否则教室l使用到活动使用到活动i结束时结束时（cl:=fi）readln(fl,n);输入活动数输入活动数nfori:=1tondoreadln(fl,si,fi);输入输入n个活动的开始时间个活动的开始时间si和结束和结束时间时间fifori:=1ton-1do按照结束时间的顺序排列活动按照结束时间的顺序排列活动forj:=i+1tondoiffjfithenbeginchange(fi,fj);change(si,sj)end;fillchar(c,sizeof(c),0);k:=0;会场数初始化会场数初始化fori:=1tondo按照结束时间的顺序枚举每一个活动按照结束时间的顺序枚举每一个活动beginl:=0;在活动在活动i开始前最晚结束的教室开始前最晚结束的教室lforj:=1tokdoif(cjcl)thenl:=j;ifl=0若活动若活动i开始前没有空闲的教室，则新增一个教室开始前没有空闲的教室，则新增一个教室thenbegininc(k);ck:=fi;l:=kendelsecl:=fi;教室教室l使用到活动使用到活动i结束时结束时writeln(fl0,活动活动,i,使用教室使用教室,l,.)end;比赛问题给定给定N名学生和名学生和K个赛场，第个赛场，第i个赛场最多有个赛场最多有Ni名学生参赛，名学生参赛，N=N1+.+NK每个赛场有一个等级值每个赛场有一个等级值Q，每个学生有一个能，每个学生有一个能力值力值P和权重和权重W，需要安排每个学生去参加竞赛。，需要安排每个学生去参加竞赛。仅当一个学生的仅当一个学生的P值大于一个赛场的值大于一个赛场的Q值，这名值，这名学生参加这个赛场的比赛后可以有学生参加这个赛场的比赛后可以有WI的收益。的收益。每个学生只能参加一个比赛。求收益最大的参每个学生只能参加一个比赛。求收益最大的参赛方案。赛方案。贪心方案贪心方案将所有学生按照权重值将所有学生按照权重值w排序，显然最优方排序，显然最优方案中，选中的人可以是案中，选中的人可以是w值最大的几个。那值最大的几个。那么我们从么我们从w值最大的开始考虑，不妨将其放值最大的开始考虑，不妨将其放入他所能参加的、等级值入他所能参加的、等级值Q最大的考场。最大的考场。设赛场序列设赛场序列part,其中赛场其中赛场i的人数为的人数为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，设置输入顺序，设置输入顺序datai.num，按照权重，按照权重datai.w递增的顺序排列递增的顺序排列data(1im)fori:=Mdownto1do按照权重递减的顺序安排每个队员的赛场按照权重递减的顺序安排每个队员的赛场beginj:=1;按照赛场等级值递减的顺序挑选适合队员按照赛场等级值递减的顺序挑选适合队员i的赛场的赛场whilej0)and(partj.QK若没有适合队员若没有适合队员i的赛场，则按照赛场等级值递减的顺序寻找一个尚剩的赛场，则按照赛场等级值递减的顺序寻找一个尚剩队员的赛场队员的赛场j，队员，队员i参加该赛场比赛参加该赛场比赛thenbeginj:=1;while(partj.N=0)doinc(j);dec(partj.N);Zdatai.num:=partj.num;赛场赛场j的队员人数减一，记的队员人数减一，记下队员下队员i所在的赛场所在的赛场end;end;fori:=1toMdo输出输出Zi;任务调度问题一一个个单单位位时时间间任任务务是是个个作作业业,如如要要在在计计算算机机上上运运行行一一个个程程序序,它它恰恰覆覆盖盖一一个个单单位位的的运运行行时时间间.给给定定一一个个单单位位时时间间任任务务的的集集合合S,对对S的的一一个个调调度度即即S的的一一个个排排列列,其其中中规规定定了了这这些些任任务务的的执执行行顺顺序序.该该调调度度中中的的第第一一个个任任务务开开始始于于时时间间0,结结束束于于时时1;第第二二个个任任务务开开始始于于时时间间1,结结束束于于时时间间2,单单处处理理器器上上具具有有期期限限和和罚罚款款的的单单位位时时间间任任务务调调度度问问题的输入如下题的输入如下:1.包含包含n个单位时间任务的集合个单位时间任务的集合S=1,2,n;2.n个个取取整整的的期期限限d1,dn,(1d,n),任任务务i要要求求在在di前完成前完成;3.n个个非非负负的的权权(或或罚罚款款)w1,wn.如如果果任任务务i没没在时间在时间di之前结束之前结束,则导致罚款则导致罚款wi;要求找出要求找出S的一个调度的一个调度,使之最小化总的罚款使之最小化总的罚款.概念概念 迟任务迟任务调度中在规定期限后完成的任调度中在规定期限后完成的任务，试题要求迟任务的罚款总和最小化务，试题要求迟任务的罚款总和最小化;早任务早任务调度中在规定期限前完成的任调度中在规定期限前完成的任务，早任务的罚款总和最大化对应问题的务，早任务的罚款总和最大化对应问题的解解两个贪心 1 1、按照罚款的单调递减顺序来安排各个子任务，使、按照罚款的单调递减顺序来安排各个子任务，使得早任务的罚款总和最大化得早任务的罚款总和最大化 2 2、在时序上保证指定任务尽早完成。实现方式：、在时序上保证指定任务尽早完成。实现方式：.按期限递增的顺序对早任务进行调度。即只按期限递增的顺序对早任务进行调度。即只要在调度中有两个分别完成于时间要在调度中有两个分别完成于时间K K和和K+1K+1的早任务的早任务i i、j j且且djdj didi，我们就互换，我们就互换i i和和j j的位置，使得任务的位置，使得任务i i在交在交换后仍然是早的，而任务换后仍然是早的，而任务j j被移到更前的位置被移到更前的位置;两个贪心 .如果某个早任务如果某个早任务X X跟在迟任务跟在迟任务Y Y之后，我们可以交换之后，我们可以交换X X和和Y Y的位置，使得早任务先于迟任务的位置，使得早任务先于迟任务;某一调度中早任某一调度中早任务的集合构成了一个独立的任务集务的集合构成了一个独立的任务集A A，因为，因为A A中任务按中任务按期限单调递增的顺序进行调度后，没有一个任务是迟期限单调递增的顺序进行调度后，没有一个任务是迟的，且的，且A A中期限为或更早的任务个数小于等于。中期限为或更早的任务个数小于等于。设目前早任务个数为设目前早任务个数为num,num,早任务集合中期限小于早任务集合中期限小于等于等于numnum的任务个数为的任务个数为t t。若。若ttdidi，则当前第，则当前第i i个任务作个任务作为早任务插入第为早任务插入第num+1num+1个空位。个空位。最初，我们设所有最初，我们设所有n n个时间空位都是空的。然后按罚款的单调个时间空位都是空的。然后按罚款的单调递减顺序递减顺序(任务任务1 1，任务，任务2 2，任务，任务3 3，任务，任务4 4，任务，任务5 5，任务，任务6 6，任，任务务7)7)来考虑各个子任务。在考虑任务来考虑各个子任务。在考虑任务j j时，如果有一个恰处于时，如果有一个恰处于或前于或前于djdj 的时间空位仍空着，则将任务的时间空位仍空着，则将任务j j赋与最近的这样的赋与最近的这样的空位，并填入空位，并填入;如果不存在这样的空位，则将任务如果不存在这样的空位，则将任务j j赋与一个赋与一个还未被占的、最近的空位。还未被占的、最近的空位。按上述贪心策略选择了任务按上述贪心策略选择了任务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为迟任务为迟任务;lt辅助数组辅助数组Pck为为早任务的编号序列；早任务的编号序列；算法如下：算法如下：读入任务数读入任务数N;Fori:=1toNDoBegin,读入任务读入任务i的期限的期限Listi.d和罚款和罚款Listi.w;Listi.k:=I记下其序号记下其序号End;forlist序列按罚款单调递减的顺序排序序列按罚款单调递减的顺序排序；num:=0;Fori:=1toNDoBegin依次处理每一个任务依次处理每一个任务t:=0;统计目前统计目前num个早任务中期限小于等于个早任务中期限小于等于num的的任务个数任务个数tForj:=1tonumDoIfListPckj.d=numThenInc(t);Ift1)And(ListPckj.d0ThenBegin打印迟任务的序号打印迟任务的序号Listi.k;t:=t+Listi.w；End;then输出总罚款数输出总罚款数t;二、构造法通过构造数学模型或方法解决问题。数数学学建建模模：通通过过沿沿用用经经典典的的数数学学思思想想建建立立起起模模型型；或或者者提提取取现现实实世世界界中中的的有有效效信信息息，用用简简明明的的方方式式表表达达其其规规律律，这这种种规规律律可可以以是是一一条条代代数数公公式式、一一幅幅几几何何图图形形，一一个个物物理理原原理理、一一个个化化学学方方程程式式，等等。等等。直直接接构构造造问问题题解解答答：只只是是构构造造法法运运用用的的一一种种简简单单类类型型。它它只只能能针针对对问问题题本本身身，探探索索其其独独有有性性质质，不具备可推广性。不具备可推广性。构造法解题的类型对对应应策策略略：将将问问题题a对对应应另另一一个个便便于于思思考考或或有有求求解解方方法法的的问问题题b，化繁为简，变未知为已知。化繁为简，变未知为已知。分分治治策策略略：将将问问题题的的规规模模逐逐渐渐减减少少，可可明明显显降降低低解解决决问问题题复复杂杂程程度度。算算法法设设计计的的这这种种策策略略称称之之为为分分治治策策略略，即即对对问问题题分分而而治之。治之。递推的分治策略递推的分治策略递归的分治策略递归的分治策略在建模过程中经常使用的策略在建模过程中经常使用的策略归归纳纳策策略略：归归纳纳策策略略则则是是通通过过列列举举试试题题本本身身的的特特殊殊情情况况，经经过过深深入入分分析析，最最后后概概括括出出事事物物内内在在的的一一般般规规律律，并并得得到到一一种种高高度抽象的解题模型。度抽象的解题模型。递推式递推式递归式递归式制定目标制定目标贪心方案贪心方案在建模过程中经常使用的策略在建模过程中经常使用的策略模模拟拟策策略略：模模拟拟某某个个过过程程，通通过过改改变变数数学学模模型型的的各各种种参参数数，进进而而观观察察变变更更这这些些参参数数所所引引起起过过程程状状态态的的变变化化，由由此此展展开开算算法法设设计。模拟题没有固定的模式，一般形式有两种：计。模拟题没有固定的模式，一般形式有两种：随随机机模模拟拟：题题目目给给定定或或者者隐隐含含某某一一概概率率。设设计计者者利利用用随随机机函函数数和和取取整整函函数数设设定定某某一一范范围围的的随随机机值值，将将符符合合概概率率的的随随机机值值作作为为参参数数。然然后后根根据据这这一一模模拟拟的的数数学学模模型型展展开开算算法法设设计计。由由于于解解题题过过程程借借助助了了计计算算机机的的伪伪随随机机数数发发生生数数，其其随随机机的的意意义义要要比比实实际际问题中真实的随机变量稍差一些，因此模拟效果有不确定的因素；问题中真实的随机变量稍差一些，因此模拟效果有不确定的因素；模拟策略：模拟策略：过过程程模模拟拟：题题目目不不给给出出概概率率，要要求求编编程程者者按按照照题题意意设设计计数数学学模模型型的的各各种种参参数数，观观察察变变更更这这些些参参数数所所引引起起过过程程状状态态的的变变化化，由由此此展展开开算算法法设设计计。模模拟拟效效果果完完全全取取决决于于过过程程模模拟拟的的真真实实性性和和算算法法的的正正确确性性，不不含含任任何何不不确确定定因因素素。由由于于过过程程模模拟拟的的结结果果无无二二义义性，因此竞赛大都采用过程模拟。性，因此竞赛大都采用过程模拟。模拟的解题方法一般有三种类型模拟的解题方法一般有三种类型 直叙式模拟直叙式模拟 筛选法模拟筛选法模拟 构造法模拟构造法模拟一般方法机理分析法统计分析法根根据据客客观观事事物物的的特特性性，分分析析其其内内部部的的机机理理，弄弄清清关关系系，在在适适当当抽抽象象的的条条件件下下，得得到到可可以以描描述述事事物物属属性性的的数数学学工具。工具。我我们们在在联联赛赛中中可可以以用用这这种种方方法法建建立立数数学学模模型型，然然后后根根据所对应的算法求出解。如下据所对应的算法求出解。如下图图所示：所示：机理分析法机理分析法计算最后9位问问N位正整数中，有多少个整数的平方的最后位正整数中，有多少个整数的平方的最后9位是位是987654321？数据量：？数据量：1n106输入：输入：n输出：输出：方案数方案数1、在、在N10时，由于题目只是问时，由于题目只是问“最后最后9位位”，所以只要在所以只要在72后加入后加入(N-10)个个“0”就可以了。就可以了。readln(n);ifn9thenbeginwrite(72);fori:=11tondowrite(0);writelnend数列给定一个正整数给定一个正整数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进制数表示）。进制数表示）。例如，对于例如，对于k=3k=3，N=100N=100，正确答案应该是，正确答案应该是981981。【输入文件输入文件】输入文件输入文件sequence.insequence.in 只有只有1 1行，为行，为2 2个正整数，用一个正整数，用一个空格隔开：个空格隔开：k Nk N（k k、N N的含义与上述的问题描述一致，且的含义与上述的问题描述一致，且3k153k15，10N100010N1000）。）。【输出文件输出文件】输出文件输出文件sequence.outsequence.out 为计算结果，是一个正整数为计算结果，是一个正整数（在所有的测试数据中，结果均不超过（在所有的测试数据中，结果均不超过2.1*102.1*109 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，其中第其中第n n项指明了项指明了k k的方幂的方幂1 1方幂方幂loglog2 2n n中哪些方幂存在，中哪些方幂存在，哪些方幂不存在，例如第哪些方幂不存在，例如第7 7项方幂项方幂0 0、方幂、方幂1 1和方幂和方幂2 2存在，存在，其它方幂不存在，正好与二进制数其它方幂不存在，正好与二进制数111111对应。对应。计算递增数列中第N项的方法 将将n n进行二进制数转化，得到的二进制数进行二进制数转化，得到的二进制数(n)(n)2 2。其中值为。其中值为1 1的位序号指明了第的位序号指明了第n n项中哪些项中哪些方幂存在。这些方幂之和构成了递增数列中第方幂存在。这些方幂之和构成了递增数列中第N 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(logNO(logN)。计算序列的第N项值ansans:=0;tot:=0;:=0;tot:=0;当前项的值和当前项的值和n n的二进制位初始化的二进制位初始化 while n0 do while n0 do若若n n的二进制位未分析完的二进制位未分析完 begin begin if if odd(nodd(n)若若n n的第的第tottot二进制位为二进制位为1 1，则累计，则累计k ktottot then then ansans:=:=ans+intpower(k,totans+intpower(k,tot););inc(tot);ninc(tot);n:=n div 2:=n div 2准备分析准备分析n n的下一个二进制位的下一个二进制位 end end输出输出ansans；传球游戏N个人围圈玩传球游戏，开始时第一个人拿个人围圈玩传球游戏，开始时第一个人拿着球，每个人把球传给左手的第着球，每个人把球传给左手的第K个人。满个人。满足足1KN/2。求。求K的最大值，使得第一个人的最大值，使得第一个人重新拿到球之前，每个人都拿过球。重新拿到球之前，每个人都拿过球。输入：输入：数串数串n（3N10200)输出：输出：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可以得到可以得到(K,N)=1K的上限的上限是是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)2，但，但是是N/2是奇数，所以是奇数，所以(N/2-2,N/2)=1。最后同样可以得到。最后同样可以得到(N/2-2,N)=1。K=N/2-2满足题意。满足题意。if(N.len=1)and(N.data12)，则可，则可以通过序列中第以通过序列中第i-1个数推出第个数推出第i格是否有雷。格是否有雷。第第2格的雷数则只需要由第一格的雷数和序列格的雷数则只需要由第一格的雷数和序列第一个数推出。第一个数推出。第一格的雷数需要枚举第一格的雷数需要枚举设设Ai表示序列中第表示序列中第i个元素，个元素，Fi表示第表示第I格的雷数。格的雷数。递推式递推式但是但是F F1 1的值还是未知的，由于每一格就是有雷和无雷两的值还是未知的，由于每一格就是有雷和无雷两种状态，显然我们可以枚举第一格雷的状态，即种状态，显然我们可以枚举第一格雷的状态，即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(n);输入地雷序列的长度输入地雷序列的长度fori:=1tondoread(numi);输入数字序列输入数字序列numifn=1单独格子的情况处理单独格子的情况处理thenifnum1=1thenans:=1elseans:=0elseforr:=0to1do枚举第一格是否是雷枚举第一格是否是雷begina1:=r;p:=true;第一格有雷数第一格有雷数r，合法状态初始化，合法状态初始化fori:=2tondo递推各格子的地雷数并判断是否合法递推各格子的地雷数并判断是否合法beginai:=numi-1-ai-1-ai-2;递推格子递推格子i的雷数的雷数if(ai1)非法状态非法状态,第一格的雷数取第一格的雷数取r+1thenbeginp:=false;break;end;end;ifpand(an+an-1=numn)theninc(ans);若合法且满足数字规律，则累计方案若合法且满足数字规律，则累计方案end;writeln(ans);装货有一些空的柜台被排成一列，它们分别属于有一些空的柜台被排成一列，它们分别属于A或或B两家两家公司，比如可以表示成公司，比如可以表示成ABAAB，等等。，等等。现在要将它们填上货物，填上货物的柜台不妨用加了现在要将它们填上货物，填上货物的柜台不妨用加了括号的字母表示：括号的字母表示：(A)表示一个含有表示一个含有A公司产品的柜台，公司产品的柜台，同理定义同理定义(B)。现在要把初始的一排空柜台变成都有货物。现在要把初始的一排空柜台变成都有货物的目标状态，比如的目标状态，比如(B)(A)(B)(A)(B)等等。等等。但变化是有规则的。每次变化可以选择一个空的柜台，但变化是有规则的。每次变化可以选择一个空的柜台，若是若是A，那么可以将其变为，那么可以将其变为(B)，也可以变成，也可以变成(A)BA；同样；同样若是若是B，那么可以变成，那么可以变成(A)，也可以变成，也可以变成(B)AB。根据这个。根据这个规则，问有没有一种方法可以将初始状态变成目标状态。规则，问有没有一种方法可以将初始状态变成目标状态。输入：输入：初始的空柜台状态初始的空柜台状态有货物的目标状态（有货物的目标状态（1最终块数最终块数30000）输出：输出：yes或或no每次注意初始状态和终止状态的第一个柜台：每次注意初始状态和终止状态的第一个柜台：如果相同，那么显然要使用如果相同，那么显然要使用A(A)BA或是或是B(B)AB的变化方法。即初始状态下一次的柜台的变化方法。即初始状态下一次的柜台取另一家公司；取另一家公司；如果不同，只能使用如果不同，只能使用A(B)或是或是B(A)。即比较。即比较初始状态和终止状态的后一个柜台；初始状态和终止状态的后一个柜台；这样每次可选择的规则只有一种，那么这题这样每次可选择的规则只有一种，那么这题的实质不过是模拟一个变化规则，问是否可以的实质不过是模拟一个变化规则，问是否可以从初始状态变化到终止状态而已。从初始状态变化到终止状态而已。TypeTdata=array1.Limitofchar;Vardata1,data2:Tdata;初始的空柜台状态和有货物的目初始的空柜台状态和有货物的目标状态标状态Len1,Len2:longint;初始状态和目标状态的指针初始状态和目标状态的指针answer:boolean;有解标志有解标志注意注意:计算前计算前,将初始状态将初始状态data1和目标状态和目标状态data2倒序便倒序便于处理于处理初始状态初始状态data1和目标状态和目标状态data2倒序；倒序；while(Len10)and(Len1=Len2)do若初始状态未搜索完且目若初始状态未搜索完且目标状态指针在初始状态指针右方标状态指针在初始状态指针右方ifdata1Len1data2Len2若初始状态和目标状态的当前字符若初始状态和目标状态的当前字符不同，则左移两指针，比较初始状态和终止状态的后一个柜台不同，则左移两指针，比较初始状态和终止状态的后一个柜台thenbegindec(Len1);dec(Len2)endelsebegin若初始状态和目标状态的当前字符相同，则右移初始若初始状态和目标状态的当前字符相同，则右移初始状态指针，初始状态下一次的柜台取另一家公司状态指针，初始状态下一次的柜台取另一家公司inc(Len1);ifdata1Len1-1=A若原位置为若原位置为A，则其右位置改为，则其右位置改为B；否则其右位置改为；否则其右位置改为Athendata1Len1:=Belsedata1Len1:=A;dec(Len2);左移目标状态指针左移目标状态指针end;answer:=(Len1=0)and(Len2=0);若初始状态和目标状态同时若初始状态和目标状态同时调整完，则返回调整完，则返回true；ifanswerthenwriteln(YES)elsewriteln(NO);身高给定给定N个人的身高，从个人的身高，从1950mm至至2050mm不等，平均身高却正好是不等，平均身高却正好是2000mm。要求。要求找到这些队员的一个排列，满足对任意找到这些队员的一个排列，满足对任意K任意连续任意连续K个球员，他们的总身高和个球员，他们的总身高和2000*Kmm相差不超过相差不超过100mm。猜想如果能保证从第一个球员开始数任意连续个如果能保证从第一个球员开始数任意连续个（设为（设为K个）球员，他们的身高总和与个）球员，他们的身高总和与2000*Kmm相差不超过相差不超过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个处理后的数据分组：负数一组，非负数一组。个处理后的数据分组：负数一组，非负数一组。首先可以确定的是首先可以确定的是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是负数，而待选集合中非是负数，而待选集合中非负数集合为空，剩下只能选择负数，那么最终负数集合为空，剩下只能选择负数，那么最终得到的得到的S SN N一定是负数，这和题目中给出的所有一定是负数，这和题目中给出的所有队员平均身高恰好为队员平均身高恰好为20002000，即，即S SN N=0=0的条件不符。的条件不符。同理可以讨论另外一种情况。同理可以讨论另外一种情况。数据结构数据结构ConstConstLimit=6001;Limit=6001;，C=5000;C=5000;TypeType TdataTdata=record=record负数序列或正数序列负数序列或正数序列 total:integer;total:integer;序列长度序列长度 data:array1.Limit of data:array1.Limit of序列序列 record record与平均高度的差值和序号与平均高度的差值和序号 number,number,position:integerposition:integer;end;end;end;end;TanswerTanswer=array1.Limit of integer;=array1.Limit of integer;VarVar nagetivenagetive,positive:Tdatapositive:Tdata;负数序列（低于平均高度的序列）负数序列（低于平均高度的序列）和正数序列（高于平均高度的序列）和正数序列（高于平均高度的序列）answer :answer :TanswerTanswer;满足条件的排列满足条件的排列、根据输入信息构造负数序列、根据输入信息构造负数序列nagetivenagetive 和正数序列和正数序列positivepositive序列。序列。NagetiveNagetive序列的尾元素的序列的尾元素的numbernumber值为；值为；positivepositive序列的尾元序列的尾元素的素的numbernumber值为，保证两个序列的元素全部取完。值为，保证两个序列的元素全部取完。、now:=0;now:=0;部分和初始化部分和初始化 p1:=1;p2:=1;p1:=1;p2:=1;分别指向负数序列和正数序列的第一个元素分别指向负数序列和正数序列的第一个元素 for i:=1 to for i:=1 to nagetive.totalnagetive.total+positive.totalpositive.total do do if now+positive.datap1.number=50 if now+positive.datap1.number=50 若部分和计入正数序若部分和计入正数序列的第列的第p1p1个元素后，小于等于个元素后，小于等于5050，则该元素进入排队序列，则该元素进入排队序列 then begin then begin answeriansweri:=positive.datap1.position;:=positive.datap1.position;inc(nowinc(now,positive.datap1.number);,positive.datap1.number);累计部分和累计部分和 inc(p1);inc(p1);指向正数序列的下一个元素指向正数序列的下一个元素 end end else begin else begin否则负数序列的第否则负数序列的第p2p2个元素进入排队序列个元素进入排队序列 answeriansweri:=nagetive.datap2.position;:=nagetive.datap2.position;inc(nowinc(now,nagetive.datap2.number);,nagetive.datap2.number);累计部分和累计部分和 inc(p2);inc(p2);指向负数序列的下一个元素指向负数序列的下一个元素 end;end;、for i:=1 to for i:=1 to positive.total+nagetive.totalpositive.total+nagetive.total do do输出输出answeriansweri