资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,火星人,and jams,数,火星人,【,问题描述,】,人类终于登上了火星的土地并且见到了神秘的火星人。人类和火星人都无法理解对方的语言，但是我们的科学家发明了一种用数字交流的方法。这种交流方法是这样的，首先，火星人把一个非常大的数字告诉人类科学家，科学家破解这个数字的含义后，再把一个很小的数字加到这个大数上面，把结果告诉火星人，作为人类的回答。,火星人用一种非常简单的方式来表示数字,掰手指。火星人只有一只手，但这只手上有成千上万的手指，这些手指排成一列，分别编号为,1,，,2,，,3,。火星人的任意两根手指都能随意交换位置，他们就是通过这方法计数的。一个火星人用一个人类的手演示了如何用手指计数。如果把五根手指,拇指、食指、中指、无名指和小指分别编号为,1,，,2,，,3,，,4,和,5,，当它们按正常顺序排列时，形成了,5,位数,12345,，当你交换无名指和小指的位置时，会形成,5,位数,12354,，当你把五个手指的顺序完全颠倒时，会形成,54321,，在所有能够形成的,120,个,5,位数中，,12345,最小，它表示,1,；,12354,第二小，它表示,2,；,54321,最大，它表示,120,。下表展示了只有,3,根手指时能够形成的,6,个,3,位数和它们代表的数字：,三进制数,123,132,213,231,312,321,代表的数字,1,2,3,4,5,6,现在你有幸成为了第一个和火星人交流的地球人。一个火星人会让你看他的手指，科学家会告诉你要加上去的很小的数。你的任务是，把火星人用手指表示的数与科学家告诉你的数相加，并根据相加的结果改变火星人手指的排列顺序。输入数据保证这个结果不会超出火星人手指能表示的范围。,【,输入文件,】,输入文件,martian.in,包括三行，第一行有一个正整数,N,，,表示火星人手指的数目（,1 N 10000,）。,第二行是一个正整数,M,，,表示要加上去的小整数（,1 M 100,）。,下一行是,1,到,N,这,N,个整数的一个排列，用空格隔开，表示火星人手指的排列顺序。,【,输出文件,】,输出文件,martian.out,只有一行，这一行含有,N,个整数，表示改变后的火星人手指的排列顺序。每两个相邻的数中间用一个空格分开，不能有多余的空格。,算法分析,n,个数有,n!,个排列方案，这些排列方案的递增顺序如下所示,1,，,2,，,，,n-1,，,n,n,，,n-1,，,2,，,1,一共有,n!,个排列方案。给出一个整数,m,，,从最小排列,1,，,2,，,，,n-1,，,n,出发，按照递增方向变换,m,次后得出的排列即为其解。例如,n=5,，,m=3,最直接的办法是在生成递增的,n!,个排列方案的基础上，根据,m,寻找目标排列。这个算法的时间效率为,O(n!log(n!),，,能处理的数据范围是,n10,。,另一种算法是通过递归将,n!,排列变换成对应的顺序值，根据,m,找出对应的排列，其算法的时间效率为,O(n,2,),，,数据范围变为,n20,。,如果在此基础上采用高精度，则可扩大数据范围至,n50,，,但算法效率降至,O(n,3,),。,但问题是，题目给定的数据范围是,N10000,，,显然，这些算法都是不理想的。,置换方法,设排列方案,A=a,1,a,2,a,n,。,按照递增顺序得出的排列方案,A,的下一个排列方案，称之为,A,的一个置换。如果能够直接找出置换方法的话，则从当前排列出发，连续进行,m,次置换便可得出问题的解。显然，这个算法的空间效率是完全能够达到要求，因为可以采用数组存储排列方案（静态数据区的容量为,64K,）。,而时间效率则取决于置换速度。下面，我们给出一个时间效率为,O,（,n*,logn,）,的置换方法：,由右而左扫描递减区间的前驱元素,a,i,(a,i,a,i+2,a,n,),。,在递减区间,a,i+1,a,n,中寻找大于,a,i,且与,a,i,最接近的元素,a,k,（即,a,k,-a,i,=,），,a,i,与,a,k,交换，并对递减区间进行递增排序，由此得出的排列即为,a,1,a,i,a,k,a,n,的下一个置换。,1 4 6 2 9,5,8 7 3,a,i,(a,i,a,i+2,a,n,),5,是递减区间,8 7 3,的前驱元素，该区间寻找大于,5,且与,5,最接近的元素是,7,。,5,和,7,交换，递减区间,8,5,3,按递增排序，生成的下一个排列为,1 4 6 2 9,7,3 5 8,显然，该排列为,1 4 6 2 9,5,8 7 3,的一个置换。,readln(n,m,);,输入火星人的手指数和待加上去的小整数,for i:=1 to n do read(ai);,输入火星人手指的排列顺序,t:=0;,置换次数初始化,while tm do,若置换次数未达到,m，,则循环,begin,if an-1an,若尾部两个数是递增的，则交换，并累计置换次数,then begin an-1an;t:=t+1;endthen,else begin,由右而左计算递减区间的前驱指针,k,for k:=n,downto,1 do if ak0)then,breake,;,alak;,t:=t+1,累计置换次数,for i:=k+1 to n-1 do,递增排序,ak+1,an,for j:=i+1 to n do if aiajthen ai aj);,endelse,end;while,for i:=1 to n-1 do write(ai,);,writeln(an,);,输出改变后的火星人手指的排列顺序,m,次置换的时间代价是,O,（,m*n*,logn,）,Jam,的计数法,Jam,是个喜欢标新立异的科学怪人。他不使用阿拉伯数字计数，而是使用小写英文字母计数，他觉得这样做，会使世界更加丰富多彩。在他的计数法中，每个数字的位数都是相同的（使用相同个数的字母），英文字母按原先的顺序，排在前面的字母小于排在它后面的字母。我们把这样的“数字”称为,Jam,数字。在,Jam,数字中，每个字母互不相同，而且从左到右是严格递增的。每次，,Jam,还指定使用字母的范围，例如，从,2,到,10,，表示只能使用,b,c,d,e,f,g,h,i,j,这些字母。如果再规定位数为,5,，那么，紧接在,Jam,数字“,bdfij,”,之后的数字应该是“,bdghi,”,。（,如果我们用,U,、,V,依次表示,Jam,数字“,bdfij,”,与“,bdghi,”,，则,UV,，,且不存在,Jam,数字,P,，使,UPV,）。,你的任务是：对于从文件读入的一个,Jam,数字，按顺序输出紧接在后面的,5,个,Jam,数字，如果后面没有那么多,Jam,数字，那么有几个就输出几个。,【,输入文件,】,输入文件,counting.in,有,2,行，第,1,行为,3,个正整数，用一个空格隔开：,s t w,（,其中,s,为所使用的最小的字母的序号，,t,为所使用的最大的字母的序号。,w,为数字的位数，这,3,个数满足：,1st26,2wt-s,）,第,2,行为具有,w,个小写字母的字符串，为一个符合要求的,Jam,数字。,所给的数据都是正确的，不必验证。,【,输出文件,】,输出文件,counting.out,最多为,5,行，为紧接在输入的,Jam,数字后面的,5,个,Jam,数字，如果后面没有那么多,Jam,数字，那么有几个就输出几个。每行只输出一个,Jam,数字，是由,w,个小写字母组成的字符串，不要有多余的空格。,题目大意,给出一个字符串，输出它字典序后面,5,个字符串，要求字符串从左往右严格递增，而且字符串中的字符在给定范围内。,计算第,i,位的最大字母序号,由于,Jam,数字有,w,位，且按照递增顺序排列，因此第,w,位的最大字母序号为,t,，第,w-1,位的最大字母序号为,t-1,，,，,由右而左依次递减。显然，第,i,位的最大字母序号为,t+i-w,，对应的字符为,chr(ord(a)-1+t+i-w),。,计算字典序后面的一个字符串,设当前的,Jam,数为,ans,。,由右而左计算未达到最大字母的位置,l,Ansi=chr(ord(a)-1+t+i-w)(l+1in),Anslchr(ord(a)-1+t+l-w),；,则位置,l,的序数加,1,（,ansl=chr(ord(ansl)+1),），且后缀字符的序数依次递增,1,（,ansi=chr(ord(ansi-1)+1),，,l+1in,）。算法复杂度,O(1),。,设,初始的,Jam,数字为,st,;,后继的,Jam,数字为,ans,;,紧接在输入的,Jam,数字后面的,Jam,数字个数为,tot,；,调整的起始位置为,l,ans,:=,st,;,后继的,Jam,数字初始化,tot:=1;,紧接在输入的,Jam,数字后面的,Jam,数字个数初始化,ed:=false;,结束标志初始化,ll,:=,length(st,);,记录初始的,Jam,数字长度,while(not ed)and(tot0)do,dec(l,);,若当前位达到最大字符，则左移,if l0,若,l,未达到最大字符，则设未结束标志，后继的,Jam,数字个数,+1,。该,Jam,数字的,l,位的序数,+1,，且后面字符的序数,+1,依次递增,1,then begin,ed:=,false;inc(tot);ansl,:=chr(ord(ansl)+1);,for i:=l+1 to,ll,do,ansi,:=chr(ord(ansi-1)+1);,writeln(ans,),输出后继的,Jam,数字,end,end;,
展开阅读全文