藍(lán)橋杯練習(xí)系統(tǒng)算法訓(xùn)練習(xí)題加答案解析java版本

1、算法訓(xùn)練編號(hào)：ALGO-1題目：區(qū)間k大數(shù)查詢列關(guān)鍵字：排序查找類型：普通試題問題描述給定一個(gè)序列，每次詢問序列中第l個(gè)數(shù)到第r個(gè)數(shù)中第K大的數(shù)是哪個(gè)。輸入格式第一行包含一個(gè)數(shù)n表示序列長度。第二行包含n個(gè)正整數(shù)，表示給定的序列。第三個(gè)包含一個(gè)正整數(shù)m表示詢問個(gè)數(shù)。接下來m行，每行三個(gè)數(shù)l,r,K，表示詢問序列從左往右第I個(gè)數(shù)到第r個(gè)數(shù)中，從大往小第K大的數(shù)是哪個(gè)。序列元素從1開始標(biāo)號(hào)。輸出格式總共輸出m行，每行一個(gè)數(shù)，表示詢問的答案。樣例輸入5123452152232樣例輸出42數(shù)據(jù)規(guī)模與約定對(duì)于30%的數(shù)據(jù)，n,m<=100；對(duì)于100%的數(shù)據(jù)，n,m<=1000；保證k<

2、;=(r-l+1)，序列中的數(shù)<=1000000。本題的Java參考代碼如下：importclassMainprivatestaticBufferedInputStreamin=newBufferedInputStream;publicstaticvoidmain(Stringargs)throwsIOExceptionintnums=newintreadInt();for(inti=0;i<i+)numsi=readInt();for(inti=readInt();i>0;i-)inta=readInt();intb=readInt();intc=readInt();int

3、tn=newintb-a+1;for(intj=0;j<j+)tnj=numsa-1+j;(tn);privatestaticintreadInt()throwsIOExceptioninti,sum=0;while(i=()&48)!=48|i>57);for(;(i&56)=48|(i&62)=56;i=()sum=sum*10+(i&15);returnsum;編號(hào)：ALGO-2題目：最大最小公倍數(shù)關(guān)鍵字：貪心類型：普通試題問題描述已知一個(gè)正整數(shù)N,問從1N中任選出三個(gè)數(shù)，他們的最小公倍數(shù)最大可以為多少。輸入格式輸入一個(gè)正整數(shù)N。輸出格式輸出一

4、個(gè)整數(shù)，表示你找到的最小公倍數(shù)。樣例輸入9樣例輸出504數(shù)據(jù)規(guī)模與約定1 <=N<=1000000。本題的Java參考代碼如下：importclassMainpublicstaticvoidmain(Stringargs)Scannersc=newScanner;intn=();longanser=1;switch(n)case95152:;publicclassMainpublicstaticvoidmain(Stringargs)throwsIOExceptionBufferedReaderbfr=newBufferedReader(newInputStreamReader);

5、Strings=().split("+");intK=(s0);intL=(s1);intf=newintLK;inti,j,k,sum=0;for(j=0;j<K;j+)f0j=1;f00=0;if(L>1)for(i=1;i<L;i+)for(j=0;j<K;j+)for(k=0;k<K;k+)if(k!=j-1&&k!=j+1)fij+=fi-1k;fij%=07;for(j=0;j<K;j+)sum+=fL-1j;sum%=07;編號(hào)：ALGO-4題目：節(jié)點(diǎn)選擇關(guān)鍵字：樹形動(dòng)態(tài)規(guī)劃類型：普通試題問題描述有一棵n個(gè)節(jié)

6、點(diǎn)的樹，樹上每個(gè)節(jié)點(diǎn)都有一個(gè)正整數(shù)權(quán)值。如果一個(gè)點(diǎn)被選擇了，那么在樹上和它相鄰的點(diǎn)都不能被選擇。求選出的點(diǎn)的權(quán)值和最大是多少？輸入格式第一行包含一個(gè)整數(shù)n。接下來的一行包含n個(gè)正整數(shù)，第i個(gè)正整數(shù)代表點(diǎn)i的權(quán)值。接下來一共n-1行，每行描述樹上的一條邊。輸出格式輸出一個(gè)整數(shù)，代表選出的點(diǎn)的權(quán)值和的最大值。樣例輸入51 23451 2132 42 5樣例輸出12樣例說明選擇3、4、5號(hào)點(diǎn)，權(quán)值和為3+4+5=12。數(shù)據(jù)規(guī)模與約定對(duì)于20%的數(shù)據(jù)，n<=20。對(duì)于50%的數(shù)據(jù)，n<=1000。對(duì)于100%的數(shù)據(jù)，n<=100000。權(quán)值均為不超過1000的正整數(shù)。本題的Java參

7、考代碼如下：import.*;import.*;publicclassMainfinalstaticintMAX_N=100010;xt)intv=Ei.v;if(visv)continue;Ed=true;statop+=v;visv=true;if(Ed)continue;-top;for(inti=headu;i+1!=0;i=Ei.nxt)intv=Ei.v;dpv0+=(dpu0,dpu1);dpv1+=dpu0;voidrun()throwsIOExceptionintn=();for(inti=1;i<=n;+i)dpi1=();(head,-1);for(inti=1;i

8、<n;+i)intu=();intv=();add(u,v);add(v,u);dfs(1,-1);intans=(dp10,dp11);(ans);();publicstaticvoidmain(Stringargs)throwsIOExceptionnewMain().run();Main()cin=newInputReader;Jimport.*;classMainstaticintn,m;staticintu;staticintv;staticintw;staticintd;staticintfirst;staticintnext;staticQueue<Integer&g

9、t;q=newLinkedList<Integer>();staticbooleaninq;publicstaticvoidmain(Stringargs)throwsIOExceptioninti;BufferedReaderbfr=newBufferedReader(newInputStreamReader);Stringstr=();Strings=("s");n=(s0);m=(s1);n+;m+;u=newintm;v=newintm;w=newintm;first=newintn;next=newintm;d=newintn;inq=newboole

10、ann;for(i=1;i<n;i+)firsti=-1;for(i=1;i<m;i+)str=();s=("");ui=(s0);vi=(s1);wi=(s2);nexti=firstui;firstui=i;spfa(1);for(i=2;i<n;i+)publicstaticvoidspfa(ints)inti,x;for(i=2;i<n;i+)di=;(s);while(!()x=();inqx=false;for(i=firstx;i!=-1;i=nexti)if(dvi>dx+wi)dvi=dx+wi;if(!inqvi)inqvi

11、=true;(vi);編號(hào)：ALGO-6題目：安慰奶牛關(guān)鍵字：最小生成樹類型：普通試題問題描述FarmerJohn變得非常懶，他不想再繼續(xù)維護(hù)供奶牛之間供通行的道路。道路被用來連接N個(gè)牧場，牧場被連續(xù)地編號(hào)為1到N每一個(gè)牧場都是一個(gè)奶牛的家。FJ計(jì)劃除去P條道路中盡可能多的道路，但是還要保持牧場之間的連通性。你首先要決定那些道路是需要保留的N-1條道路。第j條雙向道路連接了牧場Sj和Ej(1<=Sj<=N;1<=Ej<=N;Sj!=Ej)，而且走完它需要Lj的時(shí)間。沒有兩個(gè)牧場是被一條以上的道路所連接。奶牛們非常傷心，因?yàn)樗齻兊慕煌ㄏ到y(tǒng)被削減了。你需要到每一個(gè)奶牛的住處

12、去安慰她們。每次你到達(dá)第i個(gè)牧場的時(shí)候(即使你已經(jīng)到過)，你必須花去Ci的時(shí)間和奶牛交談。你每個(gè)晚上都會(huì)在同一個(gè)牧場(這是供你選擇的)過夜，直到奶牛們都從悲傷中緩過神來。在早上起來和晚上回去睡覺的時(shí)候，你都需要和在你睡覺的牧場的奶牛交談一次。這樣你才能完成你的交談任務(wù)。假設(shè)FarmerJohn采納了你的建議，請(qǐng)計(jì)算出使所有奶牛都被安慰的最少時(shí)間。輸入格式第1行包含兩個(gè)整數(shù)N和P。接下來N行，每行包含一個(gè)整數(shù)Ci。接下來P行，每行包含三個(gè)整數(shù)Sj,Ej和Lj。輸出格式輸出一個(gè)整數(shù),所需要的總時(shí)間(包含和在你所在的牧場的奶牛的兩次談話時(shí)間)。樣例輸入571010206301 252 3524123

13、 41725153 56樣例輸出176數(shù)據(jù)規(guī)模與約定5<=N<=10000，N-1<=P<=100000，0<=Lj<=1000，1<=Ci<=1,000。本題的Java參考代碼如下：importReader3staticBufferedReaderreader;staticStringTokenizertokenizer;staticvoidinit(InputStreaminput)reader=newBufferedReader(newInputStreamReader(input);tokenizer=newStringTokenizer

14、("");staticStringnext()throwsIOExceptionwhile(!()tokenizer=newStringTokenizer();return();staticintnextInt()throwsIOExceptionreturn(next();staticdoublenextDouble()throwsIOExceptionreturn(next();classKruskalDuiinta,b,l;publicclassMain/*paramargs*throwsIOException*/staticintfather=newint10000

15、0;staticArrayList<KruskalDui>path=newArrayList<KruskalDui>();publicstaticintgetfather(intx)if(x!=fatherx)fatherx=getfather(fatherx);returnfatherx;publicstaticvoid_qst_w(intl,intr)inti=l,j=r,mw=(i+j)/2).l;while(i<=j)while(i).l<mw)i+;while(j).l>mw)j-;if(i<=j)(path,i,j);i+;j-;if

16、(l<j)_qst_w(l,j);if(i<r)_qst_w(i,r);publicstaticvoidmain(Stringargs)throwsIOExceptionJfy=getfather(k).b);if(fx!=fy)fatherfx=fy;result+=(k).l;count+;k+;編號(hào)：ALGO-7題目：逆序?qū)﹃P(guān)鍵字：平衡二叉樹類型：普通試題問題描述Alice是一個(gè)讓人非常愉躍的人!他總是去學(xué)習(xí)一些他不懂的問題，然后再想出許多稀奇古怪的題目。這幾天，Alice又沉浸在逆序?qū)Φ目鞓樊?dāng)中，他已近學(xué)會(huì)了如何求逆序?qū)?duì)數(shù)，動(dòng)態(tài)維護(hù)逆序?qū)?duì)數(shù)等等題目，他認(rèn)為把這些題讓你做

17、簡直是太沒追求了，于是，經(jīng)過一天的思考和完善，Alice終于拿出了一道他認(rèn)為差不多的題目：有一顆2n-1個(gè)節(jié)點(diǎn)的二叉樹，它有恰好n個(gè)葉子節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)上寫了一個(gè)整數(shù)。如果將這棵樹的所有葉子節(jié)點(diǎn)上的數(shù)從左到右寫下來，便得到一個(gè)序列a1an?，F(xiàn)在想讓這個(gè)序列中的逆序?qū)?shù)量最少，但唯一的操作就是選樹上一個(gè)非葉子節(jié)點(diǎn)，將它的左右兩顆子樹交換。他可以做任意多次這個(gè)操作。求在最優(yōu)方案下，該序列的逆序?qū)?shù)最少有多少。Alice自己已近想出了題目的正解，他打算拿來和你分享，他要求你在最短的時(shí)間內(nèi)完成。輸入格式第一行一個(gè)整數(shù)n。下面每行，一個(gè)數(shù)x。如果x=0,表示這個(gè)節(jié)點(diǎn)非葉子節(jié)點(diǎn)，遞歸地向下讀入其左孩子和右孩

18、子的信息，如果xm0,表示這個(gè)節(jié)點(diǎn)是葉子節(jié)點(diǎn)，權(quán)值為x。輸出格式輸出一個(gè)整數(shù)，表示最少有多少逆序?qū)?。樣例輸?00312 樣例輸出1數(shù)據(jù)規(guī)模與約定對(duì)于20%的數(shù)據(jù)，n<=5000。對(duì)于100%勺數(shù)據(jù)，1<=n<=200000,0<=ai<2A31。該題暫時(shí)沒有人完全正確，暫時(shí)沒有該語言的參考程序。編號(hào)：ALGO-8題目：操作格子關(guān)鍵字：線段樹類型：普通試題問題描述有n個(gè)格子，從左到右放成一排，編號(hào)為1-n。共有m次操作，有3種操作類型：1. 修改一個(gè)格子勺權(quán)值，2. 求連續(xù)一段格子權(quán)值和，3. 求連續(xù)一段格子勺最大值。對(duì)于每個(gè)2、3操作輸出你所求出勺結(jié)果。輸入格式

19、第一行2個(gè)整數(shù)n，m。接下來一行n個(gè)整數(shù)表示n個(gè)格子勺初始權(quán)值。接下來m行，每行3個(gè)整數(shù)p,x,y，p表示操作類型，p=1時(shí)表示修改格子x的權(quán)值為y,p=2時(shí)表示求區(qū)間x,y內(nèi)格子權(quán)值和，p=3時(shí)表示求區(qū)間x,y內(nèi)格子最大的權(quán)值。輸出格式有若干行，行數(shù)等于p=2或3的操作總數(shù)。每行1個(gè)整數(shù)，對(duì)應(yīng)了每個(gè)p=2或3操作的結(jié)果。樣例輸入4 31 2342 131433 14樣例輸出63數(shù)據(jù)規(guī)模與約定對(duì)于20%的數(shù)據(jù)n<=100，m<=200。對(duì)于50%的數(shù)據(jù)n<=5000，m<=5000。對(duì)于100%的數(shù)據(jù)1<=n<=100000，m<=100000，0&l

20、t;=格子權(quán)值<=10000。本題的Java參考代碼如下：import.*;import.*;publicclassMainfinalstaticintMAX_N=100007;classNodeintl,r;intsum,max;Node()Node(int_l,int_r,int_s,int_m)l=_l;r=_r;sum=_s;max=_m;intn,m;Nodetree=newNodeMAX_N<<2;inta=newintMAX_N;voidup(intid)treeid.sum=treeid<<1.sum+treeid<<1|1.sum;t

21、reeid.max=(treeid<<1.max,treeid<<1|1.max);voidbuild(intid,intl,intr)treeid=newNode(l,r,0,0);if(l=r)treeid.sum=treeid.max=al;return;intmid=(l+r)>>1;build(id<<1,l,mid);build(id<<1|1,mid+1,r);up(id);voidupdate(intid,intpos,intval)if(treeid.l=treeid.r)treeid.sum=treeid.max=

22、val;return;intmid=(treeid.l+treeid.r)>>1;if(pos<=mid)update(id<<1,pos,val);elseupdate(id<<1|1,pos,val);up(id);intsum(intid,intl,intr)if(l<=treeid.l&&treeid.r<=r)returntreeid.sum;intmid=(treeid.l+treeid.r)>>1;if(r<=mid)returnsum(id<<1,l,r);elseif(l>

23、;mid)returnsum(id<<1|1,l,r);elsereturnsum(id<<1,l,mid)+sum(id<<1|1,mid+1,r);intmax(intid,intl,intr)if(l<=treeid.l&&treeid.r<=r)returntreeid.max;intmid=(treeid.l+treeid.r)>>1;if(r<=mid)returnmax(id<<1,l,r);elseif(l>mid)returnmax(id<<1|1,l,r);els

24、ereturn(max(id<<1,l,mid),max(id<<1|1,mid+1,r);voidrun()throwsIOExceptionn=();m=();for(inti=1;i<=n;+i)ai=();build(1,1,n);for(inti=0;i<m;+i)inttype=();intl=();intr=();if(type=1)update(1,l,r);elseif(type=2)(sum(1,l,r);else(max(1,l,r);();publicstaticvoidmain(Stringargs)throwsIOExceptio

25、nnewMain().run();Main()cin=newInputReader;序列中的所有數(shù)都是不大于k的正整數(shù)；2.序列中至少有兩個(gè)數(shù)。3.序列中的數(shù)兩兩不相等；4. 如果第i-1個(gè)數(shù)比第i-2個(gè)數(shù)大，則第i個(gè)數(shù)比第i-2個(gè)數(shù)小；如果第i-1個(gè)數(shù)比第i-2個(gè)數(shù)小，則第i個(gè)數(shù)比第i-2個(gè)數(shù)大。比如，當(dāng)k=3時(shí)，有下面幾個(gè)這樣的序列：121321213232313 13 2一共有8種，給定k，請(qǐng)求出滿足上面要求的序列的個(gè)數(shù)。輸入格式輸入包含了一個(gè)整數(shù)k。(k<=20)輸出格式輸出一個(gè)整數(shù)，表示滿足要求的序列個(gè)數(shù)。樣例輸入3樣例輸出8本題的Java參考代碼如下：import.*;pub

26、licclassMainpublicstaticvoidmain(Stringargs)throwsIOExceptionBufferedReaderbf=newBufferedReader(newInputStreamReader);intn=();編號(hào)：ALGO-10題目：集合運(yùn)算關(guān)鍵字：數(shù)組排序類型：vip問題描述B在A中的余集。給出兩個(gè)整數(shù)集合A、B,求出他們的交集、并集以及輸入格式第一行為一個(gè)整數(shù)n,表示集合A中的元素個(gè)數(shù)。第二行有n個(gè)互不相同的用空格隔開的整數(shù)，表示集合A中的元素。第三行為一個(gè)整數(shù)m表示集合B中的元素個(gè)數(shù)。第四行有m個(gè)互不相同的用空格隔開的整數(shù)，表示集合B中的元素。

27、集合中的所有元素均為int范圍內(nèi)的整數(shù)，n、m<=1000。輸出格式第一行按從小到大的順序輸出第二行按從小到大的順序輸出第三行按從小到大的順序輸出樣例輸入512345AB交集中的所有元素。AB并集中的所有元素。B在A中的余集中的所有元素。5246810樣例輸出24123456810135樣例輸入4123435 67樣例輸出12345671234本題的Java參考代碼如下：import.*;importclassMainpublicstaticvoidmain(Stringargs)throwsIOExceptionBufferedReaderbr=newBufferedReader(ne

28、wInputStreamReader);intn=();intarr=newintn;Stringst=().split("");for(inta=0;a<a+)arra=(sta);(arr);intm=();inttag=newintm;Stringstr=().split("");for(inta=0;a<a+)taga=(stra);(tag);func(arr,tag);publicstaticvoidfunc(intarr,inttag)intx;for(inta=0;a<a+)x=(tag,arra);if(x>=0

29、)II");Set<Integer>set=newHashSet<Integer>();for(inta=0;a<a+)(arra);for(inta=0;a<a+)(taga);intsor=newint();Iterator<Integer>it=();while()for(inta=0;a<a+)sora=();(sor);for(inta=0;a<a+)+II");inty;for(inta=0;a<a+)y=(tag,arra);if(y<0)II");編號(hào)：ALGO-11題目：瓷磚

30、鋪放關(guān)鍵字：遞歸類型：vip試題問題描述：有一長度為N(1<=N<=10)的地板，給定兩種不同瓷磚：一種長度為1,另一種長度為2,數(shù)目不限。要將這個(gè)長度為N的地板鋪滿，一共有多少種不同的鋪法？例如,長度為4的地面一共有如下5種鋪法：4=1+1+1+14=2+1+14=1+2+14=1+1+24=2+2編程用遞歸的方法求解上述問題。輸入格式只有一個(gè)數(shù)N,代表地板的長度輸出格式輸出一個(gè)數(shù),代表所有不同的瓷磚鋪放方法的總數(shù)樣例輸入4樣例輸出5參考代碼：importclassMainpublicstaticvoidmain(Stringargs)Scannerinput=newScanne

31、r;intn=();if(1<=n&&n<=10)if(n=1)elseinttag=newintn;tag0=1;tag1=2;if(n=1)for（inta=2;a<n;a+）taga=taga-1+taga-2;編號(hào)：ALGO-12題目：冪方分解關(guān)鍵字：遞歸類型：vip試題問題描述：任何一個(gè)正整數(shù)都可以用2的冪次方表示。例如：137=27+23+20同時(shí)約定方次用括號(hào)來表示，即ab可表示為a（b）。由此可知，137可表示為：2（7）+2（3）+2（0）進(jìn)一步：7=22+2+20（21用2表示）3=2+20所以最后137可表示為：2（2（2）+2+2（0）

32、+2（2+2（0）+2（0）又如：1315=210+28+25+2+1所以1315最后可表示為：2（2（2+2（0）+2）+2（2（2+2（0）+2（2（2）+2（0）+2+2（0）輸入格式輸入包含一個(gè)正整數(shù)N（N<=20000）,為要求分解的整數(shù)。輸出格式程序輸出包含一行字符串，為符合約定的n的0,2表示（在表示中不能有空格）參考代碼：importclassMainpublicstaticvoidmain(Stringargs)throwsExceptionBufferedReaderbr=newBufferedReader(newInputStreamReader);intnumbe

33、r=();toString(number);privatestaticvoidtoString(Stringbinary)chartemp=();booleancontrol=false;for(inti=0;i<i+)if(tempi='1')if(control)"+");elsecontrol=true;"2");intmi=-i-1;if(mi=0)"(0)");elseif(mi>1)toString(mi);")");編號(hào)：ALGO-13題目：攔截導(dǎo)彈關(guān)鍵字：貪心動(dòng)態(tài)規(guī)劃類型

34、：vip試題問題描述：某國為了防御敵國的導(dǎo)彈襲擊，發(fā)展出一種導(dǎo)彈攔截系統(tǒng)。但是這種導(dǎo)彈攔截系統(tǒng)有一個(gè)缺陷：雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達(dá)捕捉到敵國的導(dǎo)彈來襲。由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導(dǎo)彈。輸入導(dǎo)彈依次飛來的高度(雷達(dá)給出的高度數(shù)據(jù)是不大于30000的正整數(shù))，計(jì)算這套系統(tǒng)最多能攔截多少導(dǎo)彈，如果要攔截所有導(dǎo)彈最少要配備多少套這種導(dǎo)彈攔截系統(tǒng)。輸入格式一行，為導(dǎo)彈依次飛來的高度輸出格式兩行，分別是最多能攔截的導(dǎo)彈數(shù)與要攔截所有導(dǎo)彈最少要配備的系統(tǒng)數(shù)樣例輸入38920715530029917015

35、865樣例輸出62參考代碼：import.*;import.*;publicclassMainpublicstaticvoidmain(Stringargs)throwsIOExceptionBufferedReaderbf=newBufferedReader(newInputStreamReader);Strings=();Stringss=("");intnuma=newint;intnumb=newint;intnumc=newint;for(inti=0;i<i+)numai=(ssi);numbi=1;numci=1;inta1=;inta2=;for(in

36、ti=0;i<i+)for(intj=0;j<i;j+)if(numai<numaj&&numbi<numbj+1)numbi=numbj+1;a1=(a1,numbi);for(inti=0;i<i+)for(intj=0;j<i;j+)if(numai>numaj&&numci<numcj+1)numci=numcj+1;a2=(a2,numci);編號(hào)：ALGO-14題目：回文數(shù)關(guān)鍵字：模擬高精度計(jì)算類型：vip試題問題描述：若一個(gè)數(shù)（首位不為零）從左向右讀與從右向左讀都一樣，我們就將其稱之為回文數(shù)。例如：給

37、定一個(gè)10進(jìn)制數(shù)56，將56加65（即把56從右向左讀），得到121是一個(gè)回文數(shù)。又如：對(duì)于10進(jìn)制數(shù)87：STEP1：87+78=165STEP2：165+561=726STEP3：726+627=1353STEP4：1353+3531=4884在這里的一步是指進(jìn)行了一次N進(jìn)制的加法，上例最少用了4步得到回文數(shù)4884。寫一個(gè)程序，給定一個(gè)（2<=N<=10或N=16）進(jìn)制數(shù)（其中16進(jìn)制數(shù)字為0-9與A-F），求最少經(jīng)過幾步可以得到回文數(shù)。如果在30步以內(nèi)（包含30步）不可能得到回文數(shù)，則輸出“Impossible!”輸入格式兩行，N與M輸出格式如果能在30步以內(nèi)得到回文數(shù)，輸

38、出“STEP=xX'（不含引號(hào)），其中xx是步數(shù)；否則輸出一行”Impossible!”（不含引號(hào)）樣例輸入987樣例輸出STEP=6參考代碼：importclassMainprivatestaticintn,count;publicstaticvoidmain(Stringargs)throwsIOExceptionBufferedReaderbr=newBufferedReader(newInputStreamReader);n=();Stringm=();longa=(m,n);longb=(newStringBuilder(m).reverse().toString(),n);

39、if(a=b)"STEP="+0);elsefunc(a,b);privatestaticvoidfunc(longa,longb)count+;if(count>30)"Impossible!");return;longsum=a+b;Stringstr=""while(sum>=n)longtmp=sum%n;sum/=n;if(tmp>=10)str=(char)(55+tmp)+str;elsestr=tmp+str;if(sum>=10)str=(char)(55+sum)+str;elsestr=s

40、um+str;Stringreverse=newStringBuilder(str).reverse().toString();if(!(reverse)a=(str,n);b=(reverse,n);func(a,b);else"STEP="+count);return;編號(hào)：ALGO-15題目：旅行家的預(yù)算關(guān)鍵字：貪心類型：vip試題問題描述：一個(gè)旅行家想駕駛汽車以最少的費(fèi)用從一個(gè)城市到另一個(gè)城市（假設(shè)出發(fā)時(shí)油箱是空的）。給定兩個(gè)城市之間的距離D1、汽車油箱的容量C（以升為單位）、每升汽油能行駛的距離D2、出發(fā)點(diǎn)每升汽油價(jià)格P和沿途油站數(shù)N（N可以為零），油站i離出發(fā)點(diǎn)

41、的距離Di、每升汽油價(jià)格Pi（i=1,2,N）。計(jì)算結(jié)果四舍五入至小數(shù)點(diǎn)后兩位。如果無法到達(dá)目的地，則輸出“NoSolution”。輸入格式第一行為4個(gè)實(shí)數(shù)D1、CD2、P與一個(gè)非負(fù)整數(shù)N;接下來N行，每行兩個(gè)實(shí)數(shù)Di、Pi。輸出格式如果可以到達(dá)目的地，輸出一個(gè)實(shí)數(shù)（四舍五入至小數(shù)點(diǎn)后兩位），表示最小費(fèi)用;否則輸出“NoSolution”（不含引號(hào)）。樣例輸入2樣例輸出參考代碼：importclassMainpublicstaticvoidmain(Stringargs)doublep=newdouble10241024;Scannersc=newScanner;inti,j,k=0;doub

42、led1=();doublec=();doubled2=();p01=();intn=();n+;for(i=1;i<n;i+)pi0=();pi1=();pn+0=d1;doublef=c*d2;for(i=0;i<n;i+)if(pi+10-pi0>f)"NoSolution");return;doublemin=0,max,d;for(i=0;i<n-1;i+)d=pi+10-pi0;while(d>0)while(pi+10-pk0-d>=f)k+;for(j=k;j<=i;j+)if(pj1<pk1)k=j;max=

43、f-(pi+10-pk0-d);if(max>d)max=d;d-=max;min+=max/d2*pk1;"%.2f",min);編號(hào)：ALGO-16題目：進(jìn)制轉(zhuǎn)化關(guān)鍵字：進(jìn)制轉(zhuǎn)化類型：vip試題問題描述：我們可以用這樣的方式來表示一個(gè)十進(jìn)制數(shù)：將每個(gè)阿拉伯?dāng)?shù)字乘以一個(gè)以該數(shù)字所處位置的(值減1)為指數(shù)，以10為底數(shù)的幕之和的形式。例如：123可表示為1*102+2*101+3*100這樣的形式。與之相似的，對(duì)二進(jìn)制數(shù)來說，也可表示成每個(gè)二進(jìn)制數(shù)碼乘以一個(gè)以該數(shù)字所處位置的(值1)為指數(shù)，以2為底數(shù)的幕之和的形式。一般說來，任何一個(gè)正整數(shù)R或一個(gè)負(fù)整數(shù)-R都可以被選

44、來作為一個(gè)數(shù)制系統(tǒng)的基數(shù)。如果是以R或-R為基數(shù)，則需要用到的數(shù)碼為0,1,.R1。例如，當(dāng)R=7時(shí)，所需用到的數(shù)碼是0,1,2,3,4,5和6,這與其是R或R無關(guān)。如果作為基數(shù)的數(shù)絕對(duì)值超過10,則為了表示這些數(shù)碼，通常使用英文字母來表示那些大于9的數(shù)碼。例如對(duì)16進(jìn)制數(shù)來說，用A表示10,用E表示11,用C表示12，用D表示13，用E表示14,用F表示15。在負(fù)進(jìn)制數(shù)中是用一R作為基數(shù)，例如一15(十進(jìn)制)相當(dāng)于110001(2進(jìn)制),并且它可以被表示為2的冪級(jí)數(shù)的和數(shù)：110001=1*(2)5+1*(2)4+0*(2)3+0*(2)20(2)11(2)0設(shè)計(jì)一個(gè)程序,讀入一個(gè)十進(jìn)制數(shù)和

45、一個(gè)負(fù)進(jìn)制數(shù)的基數(shù),并將此十進(jìn)制數(shù)轉(zhuǎn)換為此負(fù)進(jìn)制下的數(shù)：一R2,3,4,.,20輸入格式一行兩個(gè)數(shù)，第一個(gè)是十進(jìn)制數(shù)N(32768<=N<=32767),第二個(gè)是負(fù)進(jìn)制數(shù)的基數(shù)一R。格式輸出格式輸出所求負(fù)進(jìn)制數(shù)及其基數(shù),若此基數(shù)超過10,則參照16進(jìn)制的方式處理。參照樣例)樣例輸入130000-2樣例輸出30000=0000(base-2)樣例輸入-20000-2樣例輸出-20000=000(base-2)樣例輸入28800-16樣例輸出28800=19180(base-16)樣例輸入-25000-16樣例輸出-25000=7FB8(base-16)參考代碼：importclass

46、Mainpublicstaticvoidmain(Stringargs)Scannerscanner=newScanner;intN=();intR=();charc="09ABCDEFG".toCharArray();Strings1=N+"="Strings=""while(N!=0)intt=N%R;if(t<0)t=t-R;N=N/R+1;elseN=N/R;s=ct+s;+s+"(base"+R+")");編號(hào)：ALGO-17題目：乘積最大關(guān)鍵字：動(dòng)態(tài)規(guī)劃類型：vip試題問題描述

47、：今年是國際數(shù)學(xué)聯(lián)盟確定的“2000世界數(shù)學(xué)年”，又恰逢我國著名數(shù)學(xué)家華羅庚先生誕辰90周年。在華羅庚先生的家鄉(xiāng)江蘇金壇，組織了一場別開生面的數(shù)學(xué)智力競賽的活動(dòng)，你的一個(gè)好朋友XZ也有幸得以參加。活動(dòng)中，主持人給所有參加活動(dòng)的選手出了這樣一道題目：設(shè)有一個(gè)長度為N的數(shù)字串，要求選手使用K個(gè)乘號(hào)將它分成K+1個(gè)部分，找出一種分法，使得這K+1個(gè)部分的乘積能夠?yàn)樽畲?。同時(shí)，為了幫助選手能夠正確理解題意，主持人還舉了如下的一個(gè)例子：有一個(gè)數(shù)字串：312,當(dāng)N=3,K=1時(shí)會(huì)有以下兩種分法：3*12=3631*2=62這時(shí),符合題目要求的結(jié)果是：31*2=62現(xiàn)在，請(qǐng)你幫助你的好朋友XZ設(shè)計(jì)一個(gè)程序，

48、求得正確的答案。輸入格式程序的輸入共有兩行：第一行共有2個(gè)自然數(shù)N,K(6WNK40,KKW6)第二行是一個(gè)長度為N的數(shù)字串。輸出格式輸出所求得的最大乘積（一個(gè)自然數(shù)）樣例輸入4 21231樣例輸出62參考代碼：importclassMainpublicstaticvoidmain(Stringargs)throwsIOExceptionBufferedReader(newStreamTokenizerst=newStreamTokenizer(newInputStreamReader);();intN=(int);();intK=(int);();longM=(long);Stringstr

49、=(M);longdp=newlongK+1N+1;for(inti=1;i<=N;i+)dp0i=(0,i);for(inti=1;i<=K;i+)for(intj=1+i;j<=N;j+)for(intk=i;k<=N;k+)intfont=0;for(intl=k;l<j;l+)font=(l)-'0'+font*10;if(dpij<dpi-1k*font)dpij=dpi-1k*font;編號(hào)：ALGO-18題目：單詞接龍關(guān)鍵字：搜索類型：vip試題問題描述：單詞接龍是一個(gè)與我們經(jīng)常玩的成語接龍相類似的游戲，現(xiàn)在我們已知一組單詞，且

50、給定一個(gè)開頭的字母，要求出以這個(gè)字母開頭的最長的“龍”(每個(gè)單詞都最多在“龍”中出現(xiàn)兩次)，在兩個(gè)單詞相連時(shí)，其重合部分合為一部分，例如beast和astonish，如果接成一條龍則變?yōu)閎eastonish，另外相鄰的兩部分不能存在包含關(guān)系，例如at和atide間不能相連。輸入格式輸入的第一行為一個(gè)單獨(dú)的整數(shù)n(n<=20)表示單詞數(shù)，以下n行每行有一個(gè)單詞，輸入的最后一行為一個(gè)單個(gè)字符，表示“龍”開頭的字母。你可以假定以此字母開頭的“龍”一定存在.輸出格式只需輸出以此字母開頭的最長的“龍”的長度樣例輸入5 attouchcheatchoosetacta樣例輸出23樣例說明連成的“龍”為

51、atoucheatactactouchoose參考代碼：importclassMainprivatestaticStringa=newString20;privatestaticintb=newint20;privatestaticintmax;privatestaticintn;publicstaticvoidmain(Stringargs)Scannerscanner=newScanner;n=();for(inti=0;i<n;i+)ai=();Stringstring=();f(string,();privatestaticvoidf(Strings,intlength)for(

52、inti=0;i<n;i+)if(ai.indexOf(s)=0&&bi<2)intlength1=();intlength2=ai.length();bi+;intp=1;length=length+length2-length1;while(p<length2)f(ai.substring(length2-p,length2),length);p+=1;length=length-length2+length1;bi-;max=length>max?length:max;編號(hào)：ALGO-19題目：方格取數(shù)關(guān)鍵字：動(dòng)態(tài)規(guī)劃類型：vip試題問題描述：設(shè)有

53、N*N的方格圖(N<=10),我們將其中的某些方格中填入正整數(shù)，而其他的方格中則放入數(shù)字0。某人從圖的左上角的A點(diǎn)(1,1)出發(fā)，可以向下行走，也可以向右走，直到到達(dá)右下角的B點(diǎn)(N,N)。在走過的路上，他可以取走方格中的數(shù)(取走后的方格中將變?yōu)閿?shù)字0)。此人從A點(diǎn)到B點(diǎn)共走兩次，試找出2條這樣的路徑，使得取得的數(shù)之和為最大。輸入格式輸入的第一行為一個(gè)整數(shù)N(表示N*N的方格圖)，接下來的每行有三個(gè)整數(shù)，前兩個(gè)表示位置，第三個(gè)數(shù)為該位置上所放的數(shù)。一行單獨(dú)的0表示輸入結(jié)束。輸出格式只需輸出一個(gè)整數(shù)，表示2條路徑上取得的最大的和。樣例輸入82 3132663 574 4145 221564

54、6 3157 214000樣例輸出67參考代碼：importclassMainstaticintx;staticinty;staticintn;publicstaticvoidmain(Stringargs)throwsIOExceptionBufferedReaderbr=newBufferedReader(newInputStreamReader);n=();inttag=newint2*n+12*n+1;intarr=newintn*n2;out:for(inti=1;i+)Stringstr=().split("");for(intj=0;j<1;j+)x=arri0=(str0);y=