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

..算法訓(xùn)練編號：ALGO-1題目：區(qū)間k大數(shù)查詢列關(guān)鍵字：排序查找類型：普通試題問題描述給定一個序列,每次詢問序列中第l個數(shù)到第r個數(shù)中第K大的數(shù)是哪個。輸入格式第一行包含一個數(shù)n,表示序列長度。第二行包含n個正整數(shù),表示給定的序列。第三個包含一個正整數(shù)m,表示詢問個數(shù)。接下來m行,每行三個數(shù)l,r,K,表示詢問序列從左往右第l個數(shù)到第r個數(shù)中,從大往小第K大的數(shù)是哪個。序列元素從1開始標(biāo)號。輸出格式總共輸出m行,每行一個數(shù),表示詢問的答案。樣例輸入5123452152232樣例輸出42數(shù)據(jù)規(guī)模與約定對于30%的數(shù)據(jù),n,m<=100；對于100%的數(shù)據(jù),n,m<=1000；保證k<=<r-l+1>,序列中的數(shù)<=1000000。本題的Java參考代碼如下：importjava.io.BufferedInputStream;importjava.io.IOException;importjava.util.Arrays;publicclassMain{ privatestaticBufferedInputStreamin=newBufferedInputStream<System.in>; publicstaticvoidmain<String[]args>throwsIOException { int[]nums=newint[readInt<>]; for<inti=0;i<nums.length;i++> { nums[i]=readInt<>; } for<inti=readInt<>;i>0;i--> { inta=readInt<>; intb=readInt<>; intc=readInt<>; int[]tn=newint[b-a+1]; for<intj=0;j<tn.length;j++> { tn[j]=nums[a-1+j]; } Arrays.sort<tn>; System.out.println<tn[tn.length-c]>; } } privatestaticintreadInt<>throwsIOException { inti,sum=0; while<<<i=in.read<>>&48>!=48||i>57>; for<;<i&56>==48||<i&62>==56;i=in.read<>> sum=sum*10+<i&15>; returnsum; }}編號：ALGO-2題目：最大最小公倍數(shù)關(guān)鍵字：貪心類型：普通試題問題描述已知一個正整數(shù)N,問從1~N中任選出三個數(shù),他們的最小公倍數(shù)最大可以為多少。輸入格式輸入一個正整數(shù)N。輸出格式輸出一個整數(shù),表示你找到的最小公倍數(shù)。樣例輸入9樣例輸出504數(shù)據(jù)規(guī)模與約定1<=N<=1000000。本題的Java參考代碼如下：importjava.util.Scanner;publicclassMain{ publicstaticvoidmain<String[]args>{ Scannersc=newScanner<System.in>; intn=sc.nextInt<>; longanser=1; switch<n>{ case95152://1 break; case95486://2 anser=870564410632930L; break; case94407://3 break; case98088://4 anser=943672006961970L; break; case91200://5 anser=943672006961970L; break; case98584://6 anser=958079802716232L; break; case99456://7 anser=983709271929210L; break; case97726://8 anser=983709271929210L; break; case96800://9 anser=983709271929210L; break; default://10 anser=983709271929210L; } System.out.println<anser>; } }編號：ALGO-3題目：k好數(shù)關(guān)鍵字：動態(tài)規(guī)劃類型：普通試題問題描述如果一個自然數(shù)N的K進(jìn)制表示中任意的相鄰的兩位都不是相鄰的數(shù)字,那么我們就說這個數(shù)是K好數(shù)。求L位K進(jìn)制數(shù)中K好數(shù)的數(shù)目。例如K=4,L=2的時候,所有K好數(shù)為11、13、20、22、30、31、33共7個。由于這個數(shù)目很大,請你輸出它對1000000007取模后的值。輸入格式輸入包含兩個正整數(shù),K和L。輸出格式輸出一個整數(shù),表示答案對1000000007取模后的值。樣例輸入42樣例輸出7數(shù)據(jù)規(guī)模與約定對于30%的數(shù)據(jù),KL<=106；對于50%的數(shù)據(jù),K<=16,L<=10；對于100%的數(shù)據(jù),1<=K,L<=100。本題的Java參考代碼如下：importjava.io.*;publicclassMain{publicstaticvoidmain<String[]args>throwsIOException{BufferedReaderbfr=newBufferedReader<newInputStreamReader<System.in>>;Strings[]=bfr.readLine<>.split<"+">;intK=Integer.valueOf<s[0]>;intL=Integer.valueOf<s[1]>;intf[][]=newint[L][K];inti,j,k,sum=0;for<j=0;j<K;j++>f[0][j]=1;f[0][0]=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>{f[i][j]+=f[i-1][k];f[i][j]%=1000000007;}}}}for<j=0;j<K;j++>{sum+=f[L-1][j];sum%=1000000007;}System.out.println<sum>;}}編號：ALGO-4題目：節(jié)點(diǎn)選擇關(guān)鍵字：樹形動態(tài)規(guī)劃類型：普通試題問題描述有一棵n個節(jié)點(diǎn)的樹,樹上每個節(jié)點(diǎn)都有一個正整數(shù)權(quán)值。如果一個點(diǎn)被選擇了,那么在樹上和它相鄰的點(diǎn)都不能被選擇。求選出的點(diǎn)的權(quán)值和最大是多少？輸入格式第一行包含一個整數(shù)n。接下來的一行包含n個正整數(shù),第i個正整數(shù)代表點(diǎn)i的權(quán)值。接下來一共n-1行,每行描述樹上的一條邊。輸出格式輸出一個整數(shù),代表選出的點(diǎn)的權(quán)值和的最大值。樣例輸入51234512132425樣例輸出12樣例說明選擇3、4、5號點(diǎn),權(quán)值和為3+4+5=12。數(shù)據(jù)規(guī)模與約定對于20%的數(shù)據(jù),n<=20。對于50%的數(shù)據(jù),n<=1000。對于100%的數(shù)據(jù),n<=100000。權(quán)值均為不超過1000的正整數(shù)。本題的Java參考代碼如下：importjava.io.*;importjava.util.*;publicclassMain{ finalstaticintMAX_N=100010; //finalstaticintMAX_M=200007; finalstaticlongINF=<long>1e16; classEdge{ intu,v,nxt; Edge<>{ } Edge<int_u,int_v,int_n>{ u=_u; v=_v; nxt=_n; } } intedgecnt; intdp[][]=newint[MAX_N][2]; EdgeE[]=newEdge[MAX_N*2]; inthead[]=newint[MAX_N]; intsta[]=newint[MAX_N*2]; booleanvis[]=newboolean[MAX_N]; voidadd<intu,intv>{ E[edgecnt]=newEdge<u,v,head[u]>; head[u]=edgecnt++; } voiddfs<intx,intfa>{ Arrays.fill<vis,false>; inttop=0; vis[x]=true; sta[top++]=x; while<top>0>{ intu=sta[top-1]; booleanEd=false; for<inti=head[u];i+1!=0;i=E[i].nxt>{ intv=E[i].v; if<vis[v]>continue; Ed=true; sta[top++]=v; vis[v]=true; } if<Ed>continue; --top; for<inti=head[u];i+1!=0;i=E[i].nxt>{ intv=E[i].v; dp[v][0]+=Math.max<dp[u][0],dp[u][1]>; dp[v][1]+=dp[u][0]; } } } voidrun<>throwsIOException{ intn=cin.nextInt<>; for<inti=1;i<=n;++i> dp[i][1]=cin.nextInt<>; Arrays.fill<head,-1>; for<inti=1;i<n;++i>{ intu=cin.nextInt<>; intv=cin.nextInt<>; add<u,v>; add<v,u>; } dfs<1,-1>; intans=Math.max<dp[1][0],dp[1][1]>; out.println<ans>; out.close<>; } publicstaticvoidmain<String[]args>throwsIOException{ newMain<>.run<>; } Main<>{ cin=newInputReader<System.in>; // cin=newScanner<System.in>; out=newPrintWriter<System.out>; } PrintWriterout; InputReadercin; //Scannercin; classInputReader{ InputReader<InputStreamin>{ reader=newBufferedReader<newInputStreamReader<in>>; //try{ //reader=newBufferedReader<newFileReader<"input.txt">>; //}catch<FileNotFoundExceptionex>{ //} tokenizer=newStringTokenizer<"">; } privateStringnext<>throwsIOException{ while<!tokenizer.hasMoreTokens<>>{ tokenizer=newStringTokenizer<reader.readLine<>>; } returntokenizer.nextToken<>; } publicIntegernextInt<>throwsIOException{ returnInteger.parseInt<next<>>; } privateBufferedReaderreader; privateStringTokenizertokenizer; }}編號：ALGO-5題目：最短路關(guān)鍵字：最短路類型：普通試題問題描述給定一個n個頂點(diǎn),m條邊的有向圖〔其中某些邊權(quán)可能為負(fù),但保證沒有負(fù)環(huán)。請你計(jì)算從1號點(diǎn)到其他點(diǎn)的最短路〔頂點(diǎn)從1到n編號。輸入格式第一行兩個整數(shù)n,m。接下來的m行,每行有三個整數(shù)u,v,l,表示u到v有一條長度為l的邊。輸出格式共n-1行,第i行表示1號點(diǎn)到i+1號點(diǎn)的最短路。樣例輸入3312-123-1312樣例輸出-1-2數(shù)據(jù)規(guī)模與約定對于10%的數(shù)據(jù),n=2,m=2。對于30%的數(shù)據(jù),n<=5,m<=10。對于100%的數(shù)據(jù),1<=n<=20000,1<=m<=200000,-10000<=l<=10000,保證從任意頂點(diǎn)都能到達(dá)其他所有頂點(diǎn)。本題的Java參考代碼如下：importjava.io.*;importjava.util.*;classMain{staticintn,m; staticint[]u;staticint[]v;staticint[]w;staticint[]d;staticint[]first;staticint[]next;staticQueue<Integer>q=newLinkedList<Integer><>;staticboolean[]inq; publicstaticvoidmain<String[]args>throwsIOException { inti; BufferedReaderbfr=newBufferedReader<newInputStreamReader<System.in>>; Stringstr=bfr.readLine<>; String[]s=str.split<"\\s">; n=Integer.parseInt<s[0]>; m=Integer.parseInt<s[1]>; n++; m++; u=newint[m];v=newint[m];w=newint[m];first=newint[n];next=newint[m];d=newint[n];inq=newboolean[n]; for<i=1;i<n;i++> first[i]=-1; for<i=1;i<m;i++> { str=bfr.readLine<>; s=str.split<"">; u[i]=Integer.parseInt<s[0]>; v[i]=Integer.parseInt<s[1]>; w[i]=Integer.parseInt<s[2]>; next[i]=first[u[i]];first[u[i]]=i; } spfa<1>; for<i=2;i<n;i++> System.out.println<d[i]>; } publicstaticvoidspfa<ints> { inti,x; for<i=2;i<n;i++> d[i]=Integer.MAX_VALUE; q.offer<s>; while<!q.isEmpty<>> { x=q.poll<>; inq[x]=false; for<i=first[x];i!=-1;i=next[i]>if<d[v[i]]>d[x]+w[i]>{d[v[i]]=d[x]+w[i];if<!inq[v[i]]>{inq[v[i]]=true;q.offer<v[i]>;}} } }}編號：ALGO-6題目：安慰奶牛關(guān)鍵字：最小生成樹類型：普通試題問題描述FarmerJohn變得非常懶,他不想再繼續(xù)維護(hù)供奶牛之間供通行的道路。道路被用來連接N個牧場,牧場被連續(xù)地編號為1到N。每一個牧場都是一個奶牛的家。FJ計(jì)劃除去P條道路中盡可能多的道路,但是還要保持牧場之間的連通性。你首先要決定那些道路是需要保留的N-1條道路。第j條雙向道路連接了牧場Sj和Ej<1<=Sj<=N;1<=Ej<=N;Sj!=Ej>,而且走完它需要Lj的時間。沒有兩個牧場是被一條以上的道路所連接。奶牛們非常傷心,因?yàn)樗齻兊慕煌ㄏ到y(tǒng)被削減了。你需要到每一個奶牛的住處去安慰她們。每次你到達(dá)第i個牧場的時候<即使你已經(jīng)到過>,你必須花去Ci的時間和奶牛交談。你每個晚上都會在同一個牧場<這是供你選擇的>過夜,直到奶牛們都從悲傷中緩過神來。在早上起來和晚上回去睡覺的時候,你都需要和在你睡覺的牧場的奶牛交談一次。這樣你才能完成你的交談任務(wù)。假設(shè)FarmerJohn采納了你的建議,請計(jì)算出使所有奶牛都被安慰的最少時間。輸入格式第1行包含兩個整數(shù)N和P。接下來N行,每行包含一個整數(shù)Ci。接下來P行,每行包含三個整數(shù)Sj,Ej和Lj。輸出格式輸出一個整數(shù),所需要的總時間<包含和在你所在的牧場的奶牛的兩次談話時間>。樣例輸入57101020630125235241234172515356樣例輸出176數(shù)據(jù)規(guī)模與約定5<=N<=10000,N-1<=P<=100000,0<=Lj<=1000,1<=Ci<=1,000。本題的Java參考代碼如下：importjava.io.BufferedReader;importjava.io.IOException;importjava.io.InputStream;importjava.io.InputStreamReader;importjava.util.ArrayList;importjava.util.Collections;importjava.util.StringTokenizer;classReader3{staticBufferedReaderreader;staticStringTokenizertokenizer;staticvoidinit<InputStreaminput>{reader=newBufferedReader<newInputStreamReader<input>>;tokenizer=newStringTokenizer<"">;}staticStringnext<>throwsIOException{while<!tokenizer.hasMoreElements<>>{tokenizer=newStringTokenizer<reader.readLine<>>;}returntokenizer.nextToken<>;}staticintnextInt<>throwsIOException{returnInteger.parseInt<next<>>;}staticdoublenextDouble<>throwsIOException{returnDouble.parseDouble<next<>>;}}classKruskalDui{inta,b,l;}publicclassMain{/***@paramargs*@throwsIOException*/staticintfather[]=newint[100000];staticArrayList<KruskalDui>path=newArrayList<KruskalDui><>;publicstaticintgetfather<intx>{if<x!=father[x]>{father[x]=getfather<father[x]>;}returnfather[x];}publicstaticvoid_qst_w<intl,intr>{inti=l,j=r,mw=path.get<<i+j>/2>.l;while<i<=j>{while<path.get<i>.l<mw>i++;while<path.get<j>.l>mw>j--;if<i<=j>{Collections.swap<path,i,j>;i++;j--;}}if<l<j>_qst_w<l,j>;if<i<r>_qst_w<i,r>;}publicstaticvoidmain<String[]args>throwsIOException{//TODOAuto-generatedmethodstubReader3.init<System.in>;intn=Reader3.nextInt<>;intp=Reader3.nextInt<>;intd[]=newint[n+1];intminD=Integer.MAX_VALUE;for<inti=1;i<n+1;i++>{d[i]=Reader3.nextInt<>;father[i]=i;if<d[i]<minD>{minD=d[i];}}for<inti=0;i<p;i++>{KruskalDuik=newKruskalDui<>;k.a=Reader3.nextInt<>;k.b=Reader3.nextInt<>;k.l=Reader3.nextInt<>;k.l=k.l*2+d[k.a]+d[k.b];path.add<k>;}_qst_w<0,p-1>;intfx,fy,result=minD,count=0,k=0;while<count<n-1>{fx=getfather<path.get<k>.a>;fy=getfather<path.get<k>.b>;if<fx!=fy>{father[fx]=fy;result+=path.get<k>.l;count++;}k++;}System.out.println<result>;}}編號：ALGO-7題目：逆序?qū)﹃P(guān)鍵字：平衡二叉樹類型：普通試題問題描述Alice是一個讓人非常愉躍的人!他總是去學(xué)習(xí)一些他不懂的問題,然后再想出許多稀奇古怪的題目。這幾天,Alice又沉浸在逆序?qū)Φ目鞓樊?dāng)中,他已近學(xué)會了如何求逆序?qū)?shù),動態(tài)維護(hù)逆序?qū)?shù)等等題目,他認(rèn)為把這些題讓你做簡直是太沒追求了,于是,經(jīng)過一天的思考和完善,Alice終于拿出了一道他認(rèn)為差不多的題目：有一顆2n-1個節(jié)點(diǎn)的二叉樹,它有恰好n個葉子節(jié)點(diǎn),每個節(jié)點(diǎn)上寫了一個整數(shù)。如果將這棵樹的所有葉子節(jié)點(diǎn)上的數(shù)從左到右寫下來,便得到一個序列a[1]…a[n]?，F(xiàn)在想讓這個序列中的逆序?qū)?shù)量最少,但唯一的操作就是選樹上一個非葉子節(jié)點(diǎn),將它的左右兩顆子樹交換。他可以做任意多次這個操作。求在最優(yōu)方案下,該序列的逆序?qū)?shù)最少有多少。Alice自己已近想出了題目的正解,他打算拿來和你分享,他要求你在最短的時間內(nèi)完成。輸入格式第一行一個整數(shù)n。下面每行,一個數(shù)x。如果x=0,表示這個節(jié)點(diǎn)非葉子節(jié)點(diǎn),遞歸地向下讀入其左孩子和右孩子的信息,如果x≠0,表示這個節(jié)點(diǎn)是葉子節(jié)點(diǎn),權(quán)值為x。輸出格式輸出一個整數(shù),表示最少有多少逆序?qū)?。樣例輸?00312樣例輸出1數(shù)據(jù)規(guī)模與約定對于20%的數(shù)據(jù),n<=5000。對于100%的數(shù)據(jù),1<=n<=200000,0<=a[i]<2^31。該題暫時沒有人完全正確,暫時沒有該語言的參考程序。編號：ALGO-8題目：操作格子關(guān)鍵字：線段樹類型：普通試題問題描述有n個格子,從左到右放成一排,編號為1-n。共有m次操作,有3種操作類型：1.修改一個格子的權(quán)值,2.求連續(xù)一段格子權(quán)值和,3.求連續(xù)一段格子的最大值。對于每個2、3操作輸出你所求出的結(jié)果。輸入格式第一行2個整數(shù)n,m。接下來一行n個整數(shù)表示n個格子的初始權(quán)值。接下來m行,每行3個整數(shù)p,x,y,p表示操作類型,p=1時表示修改格子x的權(quán)值為y,p=2時表示求區(qū)間[x,y]內(nèi)格子權(quán)值和,p=3時表示求區(qū)間[x,y]內(nèi)格子最大的權(quán)值。輸出格式有若干行,行數(shù)等于p=2或3的操作總數(shù)。每行1個整數(shù),對應(yīng)了每個p=2或3操作的結(jié)果。樣例輸入431234213143314樣例輸出63數(shù)據(jù)規(guī)模與約定對于20%的數(shù)據(jù)n<=100,m<=200。對于50%的數(shù)據(jù)n<=5000,m<=5000。對于100%的數(shù)據(jù)1<=n<=100000,m<=100000,0<=格子權(quán)值<=10000。本題的Java參考代碼如下：importjava.io.*;importjava.util.*;publicclassMain{ finalstaticintMAX_N=100007; classNode{ intl,r; intsum,max; Node<>{ } Node<int_l,int_r,int_s,int_m>{ l=_l; r=_r; sum=_s; max=_m; } } intn,m; Nodetree[]=newNode[MAX_N<<2]; inta[]=newint[MAX_N]; voidup<intid>{ tree[id].sum=tree[id<<1].sum+tree[id<<1|1].sum; tree[id].max=Math.max<tree[id<<1].max,tree[id<<1|1].max>; } voidbuild<intid,intl,intr>{ tree[id]=newNode<l,r,0,0>; if<l==r>{ tree[id].sum=tree[id].max=a[l]; return; } intmid=<l+r>>>1; build<id<<1,l,mid>; build<id<<1|1,mid+1,r>; up<id>; } voidupdate<intid,intpos,intval>{ if<tree[id].l==tree[id].r>{ tree[id].sum=tree[id].max=val; return; } intmid=<tree[id].l+tree[id].r>>>1; if<pos<=mid>update<id<<1,pos,val>; elseupdate<id<<1|1,pos,val>; up<id>; } intsum<intid,intl,intr>{ if<l<=tree[id].l&&tree[id].r<=r>{ returntree[id].sum; } intmid=<tree[id].l+tree[id].r>>>1; if<r<=mid>returnsum<id<<1,l,r>; elseif<l>mid>returnsum<id<<1|1,l,r>; else{ returnsum<id<<1,l,mid>+sum<id<<1|1,mid+1,r>; } } intmax<intid,intl,intr>{ if<l<=tree[id].l&&tree[id].r<=r>{ returntree[id].max; } intmid=<tree[id].l+tree[id].r>>>1; if<r<=mid>returnmax<id<<1,l,r>; elseif<l>mid>returnmax<id<<1|1,l,r>; else{ returnMath.max<max<id<<1,l,mid>,max<id<<1|1,mid+1,r>>; } } voidrun<>throwsIOException{ n=cin.nextInt<>; m=cin.nextInt<>; for<inti=1;i<=n;++i> a[i]=cin.nextInt<>; build<1,1,n>; for<inti=0;i<m;++i>{ inttype=cin.nextInt<>; intl=cin.nextInt<>; intr=cin.nextInt<>; if<type==1>update<1,l,r>; elseif<type==2>out.println<sum<1,l,r>>; elseout.println<max<1,l,r>>; } out.close<>; } publicstaticvoidmain<String[]args>throwsIOException{ newMain<>.run<>; } Main<>{ cin=newInputReader<System.in>; //cin=newScanner<System.in>; out=newPrintWriter<System.out>; } PrintWriterout; InputReadercin; //Scannercin; classInputReader{ InputReader<InputStreamin>{ reader=newBufferedReader<newInputStreamReader<in>>; //try{ //reader=newBufferedReader<newFileReader<"input.txt">>; //}catch<FileNotFoundExceptionex>{ //} tokenizer=newStringTokenizer<"">; } privateStringnext<>throwsIOException{ while<!tokenizer.hasMoreTokens<>>{ tokenizer=newStringTokenizer<reader.readLine<>>; } returntokenizer.nextToken<>; } publicIntegernextInt<>throwsIOException{ returnInteger.parseInt<next<>>; } privateBufferedReaderreader; privateStringTokenizertokenizer; }}編號：ALGO-9題目：擺動序列關(guān)鍵字：動態(tài)規(guī)劃類型：vip問題描述如果一個序列滿足下面的性質(zhì),我們就將它稱為擺動序列：1.序列中的所有數(shù)都是不大于k的正整數(shù)；2.序列中至少有兩個數(shù)。3.序列中的數(shù)兩兩不相等；4.如果第i–1個數(shù)比第i–2個數(shù)大,則第i個數(shù)比第i–2個數(shù)?。蝗绻趇–1個數(shù)比第i–2個數(shù)小,則第i個數(shù)比第i–2個數(shù)大。比如,當(dāng)k=3時,有下面幾個這樣的序列：121321213232313132一共有8種,給定k,請求出滿足上面要求的序列的個數(shù)。輸入格式輸入包含了一個整數(shù)k?！瞜<=20輸出格式輸出一個整數(shù),表示滿足要求的序列個數(shù)。樣例輸入3樣例輸出8本題的Java參考代碼如下：importjava.io.*;publicclassMain{publicstaticvoidmain<Stringargs[]>throwsIOException{BufferedReaderbf=newBufferedReader<newInputStreamReader<System.in>>;intn=Integer.parseInt<bf.readLine<>>;System.out.println<<int><Math.pow<2,n>-n-1>*2>;}}編號：ALGO-10題目：集合運(yùn)算關(guān)鍵字：數(shù)組排序類型：vip問題描述給出兩個整數(shù)集合A、B,求出他們的交集、并集以及B在A中的余集。輸入格式第一行為一個整數(shù)n,表示集合A中的元素個數(shù)。第二行有n個互不相同的用空格隔開的整數(shù),表示集合A中的元素。第三行為一個整數(shù)m,表示集合B中的元素個數(shù)。第四行有m個互不相同的用空格隔開的整數(shù),表示集合B中的元素。集合中的所有元素均為int范圍內(nèi)的整數(shù),n、m<=1000。輸出格式第一行按從小到大的順序輸出A、B交集中的所有元素。第二行按從小到大的順序輸出A、B并集中的所有元素。第三行按從小到大的順序輸出B在A中的余集中的所有元素。樣例輸入5123455246810樣例輸出24123456810135樣例輸入412343567樣例輸出12345671234本題的Java參考代碼如下：importjava.io.*;importjava.util.Arrays;importjava.util.HashSet;importjava.util.Iterator;importjava.util.Set;publicclassMain{ publicstaticvoidmain<String[]args>throwsIOException{ BufferedReaderbr=newBufferedReader<newInputStreamReader<System.in>>; intn=Integer.parseInt<br.readLine<>>; int[]arr=newint[n]; Stringst[]=br.readLine<>.split<"">; for<inta=0;a<arr.length;a++>{ arr[a]=Integer.parseInt<st[a]>; } Arrays.sort<arr>; intm=Integer.parseInt<br.readLine<>>; int[]tag=newint[m]; Stringstr[]=br.readLine<>.split<"">; for<inta=0;a<tag.length;a++>{ tag[a]=Integer.parseInt<str[a]>; } Arrays.sort<tag>; func<arr,tag>; } publicstaticvoidfunc<int[]arr,int[]tag>{ intx; for<inta=0;a<arr.length;a++>{ x=Arrays.binarySearch<tag,arr[a]>; if<x>=0>{ System.out.print<arr[a]+"">; } } System.out.println<>; Set<Integer>set=newHashSet<Integer><>; for<inta=0;a<arr.length;a++>{ set.add<arr[a]>; } for<inta=0;a<tag.length;a++>{ set.add<tag[a]>; } int[]sor=newint[set.size<>]; Iterator<Integer>it=set.iterator<>; while<it.hasNext<>>{ for<inta=0;a<sor.length;a++>{ sor[a]=it.next<>; } } Arrays.sort<sor>; for<inta=0;a<sor.length;a++>{ System.out.print<sor[a]+"">; } System.out.println<>; inty; for<inta=0;a<arr.length;a++>{ y=Arrays.binarySearch<tag,arr[a]>; if<y<0>{ System.out.print<arr[a]+"">; } } System.out.println<>; }}編號：ALGO-11題目：瓷磚鋪放關(guān)鍵字：遞歸類型：vip試題問題描述：有一長度為N<1<=Ｎ<=10>的地板,給定兩種不同瓷磚：一種長度為1,另一種長度為2,數(shù)目不限。要將這個長度為N的地板鋪滿,一共有多少種不同的鋪法？例如,長度為4的地面一共有如下5種鋪法：4=1+1+1+14=2+1+14=1+2+14=1+1+24=2+2編程用遞歸的方法求解上述問題。輸入格式只有一個數(shù)N,代表地板的長度輸出格式輸出一個數(shù),代表所有不同的瓷磚鋪放方法的總數(shù)樣例輸入4樣例輸出5參考代碼：importjava.util.Scanner;publicclassMain{ publicstaticvoidmain<String[]args> { Scannerinput=newScanner<System.in>; intn=input.nextInt<>; if<1<=n&&n<=10> { if<n==1> { System.out.println<"1">; } else { int[]tag=newint[n]; tag[0]=1; tag[1]=2; if<n==1> { System.out.println<tag[0]>; } for<inta=2;a<n;a++> { tag[a]=tag[a-1]+tag[a-2]; } System.out.println<tag[n-1]>; } } } }編號：ALGO-12題目：冪方分解關(guān)鍵字：遞歸類型：vip試題問題描述：任何一個正整數(shù)都可以用2的冪次方表示。例如：137=27+23+20同時約定方次用括號來表示,即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+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輸入格式輸入包含一個正整數(shù)N〔N<=20000,為要求分解的整數(shù)。輸出格式程序輸出包含一行字符串,為符合約定的n的0,2表示〔在表示中不能有空格參考代碼：importjava.io.BufferedReader;importjava.io.InputStreamReader;publicclassMain{ publicstaticvoidmain<String[]args>throwsException{ BufferedReaderbr=newBufferedReader<newInputStreamReader<System.in>>; intnumber=Integer.valueOf<br.readLine<>>; toString<Integer.toBinaryString<number>>; } privatestaticvoidtoString<Stringbinary>{ char[]temp=binary.toCharArray<>; booleancontrol=false; for<inti=0;i<temp.length;i++>{ if<temp[i]=='1'>{ if<control> System.out.print<"+">; else control=true; System.out.print<"2">; intmi=temp.length-i-1; if<mi==0> System.out.print<"<0>">; elseif<mi>1>{ System.out.print<"<">; toString<Integer.toBinaryString<mi>>; System.out.print<">">; } } } }}編號：ALGO-13題目：攔截導(dǎo)彈關(guān)鍵字：貪心動態(tài)規(guī)劃類型：vip試題問題描述：某國為了防御敵國的導(dǎo)彈襲擊,發(fā)展出一種導(dǎo)彈攔截系統(tǒng)。但是這種導(dǎo)彈攔截系統(tǒng)有一個缺陷：雖然它的第一發(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ù)樣例輸入38920715530029917015865樣例輸出62參考代碼：importjava.io.*;importjava.util.*;publicclassMain{ publicstaticvoidmain<Stringargs[]>throwsIOException{ BufferedReaderbf=newBufferedReader<newInputStreamReader<System.in>>; Strings=bf.readLine<>; String[]ss=s.split<"">; int[]numa=newint[ss.length]; int[]numb=newint[ss.length]; int[]numc=newint[ss.length]; for<inti=0;i<ss.length;i++>{ numa[i]=Integer.parseInt<ss[i]>; numb[i]=1; numc[i]=1; } inta1=Integer.MIN_VALUE; inta2=Integer.MIN_VALUE; for<inti=0;i<numa.length;i++>{ for<intj=0;j<i;j++>{ if<numa[i]<numa[j]&&numb[i]<numb[j]+1>{ numb[i]=numb[j]+1; } a1=Math.max<a1,numb[i]>; } } for<inti=0;i<numa.length;i++>{ for<intj=0;j<i;j++>{ if<numa[i]>numa[j]&&numc[i]<numc[j]+1>{ numc[i]=numc[j]+1; } } a2=Math.max<a2,numc[i]>; } System.out.println<a1>; System.out.println<a2>; }}編號：ALGO-14題目：回文數(shù)關(guān)鍵字：模擬高精度計(jì)算類型：vip試題問題描述：若一個數(shù)〔首位不為零從左向右讀與從右向左讀都一樣,我們就將其稱之為回文數(shù)。例如：給定一個10進(jìn)制數(shù)56,將56加65〔即把56從右向左讀,得到121是一個回文數(shù)。又如：對于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。寫一個程序,給定一個N〔2<=N<=10或N=16進(jìn)制數(shù)M〔其中16進(jìn)制數(shù)字為0-9與A-F,求最少經(jīng)過幾步可以得到回文數(shù)。如果在30步以內(nèi)〔包含30步不可能得到回文數(shù),則輸出"Impossible!"輸入格式兩行,N與M輸出格式如果能在30步以內(nèi)得到回文數(shù),輸出"STEP=xx"〔不含引號,其中xx是步數(shù)；否則輸出一行"Impossible!"〔不含引號樣例輸入987樣例輸出STEP=6參考代碼：importjava.io.BufferedReader;importjava.io.IOException;importjava.io.InputStreamReader;publicclassMain{ privatestaticintn,count; publicstaticvoidmain<String[]args>throwsIOException{ BufferedReaderbr=newBufferedReader<newInputStreamReader<System.in>>; n=Integer.parseInt<br.readLine<>>; Stringm=br.readLine<>; longa=Long.parseLong<m,n>; longb=Long.parseLong<newStringBuilder<m>.reverse<>.toString<>,n>; if<a==b> System.out.println<"STEP="+0>; else func<a,b>; } privatestaticvoidfunc<longa,longb>{ count++; if<count>30>{ System.out.println<"Impossible!">; return; } longsum=a+b; Stringstr=""; while<sum>=n>{ longtmp=sum%n; sum/=n; if<tmp>=10> str=<char><55+tmp>+str; else str=tmp+str; } if<sum>=10> str=<char><55+sum>+str; else str=sum+str; Stringreverse=newStringBuilder<str>.reverse<>.toString<>; if<!str.equals<reverse>>{ a=Long.parseLong<str,n>; b=Long.parseLong<reverse,n>; func<a,b>; }else{ System.out.println<"STEP="+count>; return; } }}編號：ALGO-15題目：旅行家的預(yù)算關(guān)鍵字：貪心類型：vip試題問題描述：一個旅行家想駕駛汽車以最少的費(fèi)用從一個城市到另一個城市〔假設(shè)出發(fā)時油箱是空的。給定兩個城市之間的距離D1、汽車油箱的容量C〔以升為單位、每升汽油能行駛的距離D2、出發(fā)點(diǎn)每升汽油價格P和沿途油站數(shù)N〔N可以為零,油站i離出發(fā)點(diǎn)的距離Di、每升汽油價格Pi〔i=1,2,……N。計(jì)算結(jié)果四舍五入至小數(shù)點(diǎn)后兩位。如果無法到達(dá)目的地,則輸出"NoSolution"。輸入格式第一行為4個實(shí)數(shù)D1、C、D2、P與一個非負(fù)整數(shù)N；接下來N行,每行兩個實(shí)數(shù)Di、Pi。輸出格式如果可以到達(dá)目的地,輸出一個實(shí)數(shù)〔四舍五入至小數(shù)點(diǎn)后兩位,表示最小費(fèi)用；否則輸出"NoSolution"〔不含引號。樣例輸入275.611.927.42.82102.02.9220.02.2樣例輸出26.95參考代碼：importjava.util.Scanner;publicclassMain{ publicstaticvoidmain<String[]args>{ double[][]p=newdouble[1024][1024]; Scannersc=newScanner<System.in>; inti,j,k=0; doubled1=sc.nextDouble<>; doublec=sc.nextDouble<>; doubled2=sc.nextDouble<>; p[0][1]=sc.nextDouble<>; intn=sc.nextInt<>; n++; for<i=1;i<n;i++>{ p[i][0]=sc.nextDouble<>; p[i][1]=sc.nextDouble<>; } p[n++][0]=d1; doublef=c*d2; for<i=0;i<n;i++>{ if<p[i+1][0]-p[i][0]>f>{ System.out.println<"NoSolution">; return; } } doublemin=0,max,d; for<i=0;i<n-1;i++>{ d=p[i+1][0]-p[i][0]; while<d>0>{ while<p[i+1][0]-p[k][0]-d>=f> k++; for<j=k;j<=i;j++> if<p[j][1]<p[k][1]> k=j; max=f-<p[i+1][0]-p[k][0]-d>; if<max>d> max=d; d-=max; min+=max/d2*p[k][1]; } } System.out.println<String.format<"%.2f",min>>; }}編號：ALGO-16題目：進(jìn)制轉(zhuǎn)化關(guān)鍵字：進(jìn)制轉(zhuǎn)化類型：vip試題問題描述：我們可以用這樣的方式來表示一個十進(jìn)制數(shù)：將每個阿拉伯?dāng)?shù)字乘以一個以該數(shù)字所處位置的〔值減１為指數(shù),以１０為底數(shù)的冪之和的形式。例如：１２３可表示為１＊１０２＋２＊１０１＋３＊１００這樣的形式。與之相似的,對二進(jìn)制數(shù)來說,也可表示成每個二進(jìn)制數(shù)碼乘以一個以該數(shù)字所處位置的〔值－１為指數(shù),以２為底數(shù)的冪之和的形式。一般說來,任何一個正整數(shù)Ｒ或一個負(fù)整數(shù)－Ｒ都可以被選來作為一個數(shù)制系統(tǒng)的基數(shù)。如果是以Ｒ或－Ｒ為基數(shù),則需要用到的數(shù)碼為０,１,．．．．Ｒ－１。例如,當(dāng)Ｒ＝７時,所需用到的數(shù)碼是０,１,２,３,４,５和６,這與其是Ｒ或－Ｒ無關(guān)。如果作為基數(shù)的數(shù)絕對值超過１０,則為了表示這些數(shù)碼,通常使用英文字母來表示那些大于９的數(shù)碼。例如對１６進(jìn)制數(shù)來說,用Ａ表示１０,用Ｂ表示１１,用Ｃ表示１２,用Ｄ表示１３,用Ｅ表示１４,用Ｆ表示１５。在負(fù)進(jìn)制數(shù)中是用－Ｒ作為基數(shù),例如－１５〔十進(jìn)制相當(dāng)于１１０００１〔－２進(jìn)制,并且它可以被表示為２的冪級數(shù)的和數(shù)：１１０００１＝１＊〔－２５＋１＊〔－２４＋０＊〔－２３＋０＊〔－２２＋０＊〔－２１＋１＊〔－２０設(shè)計(jì)一個程序,讀入一個十進(jìn)制數(shù)和一個負(fù)進(jìn)制數(shù)的基數(shù),并將此十進(jìn)制數(shù)轉(zhuǎn)換為此負(fù)進(jìn)制下的數(shù)：－Ｒ∈｛－２,－３,－４,．．．,－２０｝輸入格式一行兩個數(shù),第一個是十進(jìn)制數(shù)Ｎ〔－32768＜＝Ｎ＜＝32767,第二個是負(fù)進(jìn)制數(shù)的基數(shù)－Ｒ。輸出格式輸出所求負(fù)進(jìn)制數(shù)及其基數(shù),若此基數(shù)超過１０,則參照１６進(jìn)制的方式處理?！哺袷絽⒄諛永龢永斎?30000-2樣例輸出樣例輸入-20000-2樣例輸出樣例輸入28800-16樣例輸出28800=19180<base-16>樣例輸入-25000-16樣例輸出-25000=7FB8<base-16>參考代碼：importjava.util.Scanner;publicclassMain{ publicstaticvoidmain<String[]args>{ Scannerscanner=newScanner<System.in>; intN=scanner.nextInt<>; intR=scanner.nextInt<>; char[]c="0123456789ABCDEFG".toCharArray<>; Strings1=N+"="; Strings=""; while<N!=0>{ intt=N%R; if<t<0>{ t=t-R; N=N/R+1; }else N=N/R; s=c[t]+s; } System.out.println<s1+s+"<base"+R+">">; }}編號：ALGO-17題目：乘積最大關(guān)鍵字：動態(tài)規(guī)劃類型：vip試題問題描述：今年是國際數(shù)學(xué)聯(lián)盟確定的"2000——世界數(shù)學(xué)年",又恰逢我國著名數(shù)學(xué)家華羅庚先生誕辰90周年。在華羅庚先生的家鄉(xiāng)XX金壇,組織了一場別開生面的數(shù)學(xué)智力競賽的活動,你的一個好朋友XZ也有幸得以參加?；顒又?主持人給所有參加活動的選手出了這樣一道題目：設(shè)有一個長度為N的數(shù)字串,要求選手使用K個乘號將它分成K+1個部分,找出一種分法,使得這K+1個部分的乘積能夠?yàn)樽畲?。同時,為了幫助選手能夠正確理解題意,主持人還舉了如下的一個例子：有一個數(shù)字串：312,當(dāng)N=3,K=1時會有以下兩種分法：3*12=3631*2=62這時,符合題目要求的結(jié)果是：31*2=62現(xiàn)在,請你幫助你的好朋友XZ設(shè)計(jì)一個程序,求得正確的答案。輸入格式程序的輸入共有兩行：第一行共有2個自然數(shù)N,K〔6≤N≤40,1≤K≤6第二行是一個長度為N的數(shù)字串。輸出格式輸出所求得的最大乘積〔一個自然數(shù)。樣例輸入421231樣例輸出62參考代碼：importjava.io.BufferedReader;importjava.io.IOException;importjava.io.InputStreamReader;importjava.io.StreamTokenizer;publicclassMain{ publicstaticvoidmain<String[]args>throwsIOException{ StreamTokenizerst=newStreamTokenizer<newBufferedReader<newInputStreamReader<System.in>>>; st.nextToken<>; intN=<int>st.nval; st.nextToken<>; intK=<int>st.nval; st.nextToken<>; longM=<long>st.nval; Stringstr=String.valueOf<M>; longdp[][]=newlong[K+1][N+1]; for<inti=1;i<=N;i++>{ dp[0][i]=Long.parseLong<str.substring<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=str.charAt<l>-'0'+font*10; } if<dp[i][j]<dp[i-1][k]*font> dp[i][j]=dp[i-1][k]*font; } } } System.out.println<dp[K][N]>; }}編號：ALGO-18題目：單詞接龍關(guān)鍵字：搜索類型：vip試題問題描述：單詞接龍是一個與我們經(jīng)常玩的成語接龍相類似的游戲,現(xiàn)在我們已知一組單詞,且給定一個開頭的字母,要求出以這個字母開頭的最長的"龍"〔每個單詞都最多在"龍"中出現(xiàn)兩次,在兩個單詞相連時,其重合部分合為一部分,例如beast和astonish,如果接成一條龍則變?yōu)閎eastonish,另外相鄰的兩部分不能存在包含關(guān)系,例如at和atide間不能相連。輸入格式輸入的第一行為一個單獨(dú)的整數(shù)n<n<=20>表示單詞數(shù),以下n行每行有一個單詞,輸入的最后一行為一個單個字符,表示"龍"開頭的字母。你可以假定以此字母開頭的"龍"一定存在.輸出格式只需輸出以此字母開頭的最長的"龍"的長度樣例輸入5attouchcheatchoosetacta樣例輸出23樣例說明連成的"龍"為atoucheatactactouchoose參考代碼：importjava.util.Scanner;publicclassMain{ privatestaticString[]a=newString[20]; privatestaticint[]b=newint[20]; privatestaticintmax; privatestaticintn; publicstaticvoidmain<String[]args>{ Scannerscanner=newScanner<System.in>; n=scanner.nextInt<>; for<inti=0;i<n;i++> a[i]=scanner.next<>; Stringstring=scanner.next<>; f<string,string.length<>>; rintln<max>; } privat