藍橋杯算法提高題及官方答案解析

./r/n./r/n算法提高/r/n編號：ADV-1/r/n題目：兩條直線/r/n關(guān)鍵字：排序/r/n類型：普通試題/r/n問題描述：/r/n給定平面上n個點。/r/n求兩條直線,這兩條直線互相垂直,而且它們與x軸的夾角為45度,并且n個點中離這兩條直線的曼哈頓距離的最大值最小。/r/n兩點之間的曼哈頓距離定義為橫坐標的差的絕對值與縱坐標的差的絕對值之和,一個點到兩條直線的曼哈頓距離是指該點到兩條直線上的所有點的曼哈頓距離中的最小值。/r/n輸入格式/r/n第一行包含一個數(shù)n。/r/n接下來n行,每行包含兩個整數(shù),表示n個點的坐標〔橫縱坐標的絕對值小于10^9。/r/n輸出格式/r/n輸出一個值,表示最小的最大曼哈頓距離的值,保留一位小數(shù)。/r/n樣例輸入/r/n4/r/n10/r/n01/r/n21/r/n12/r/n樣例輸出/r/n1.0/r/n數(shù)據(jù)規(guī)模與約定/r/n對于30%的數(shù)據(jù),n<=100。/r/n對于另外30%的數(shù)據(jù),坐標范的絕對值小于100。/r/n對于100%的數(shù)據(jù),n<=10^5。/r/n參考代碼：/r/n該題暫時沒有人完全正確,暫時沒有該語言的參考程序。/r/n編號：ADV-2/r/n題目：矩陣翻轉(zhuǎn)/r/n關(guān)鍵字：枚舉貪心/r/n類型：普通試題/r/n問題描述：/r/nCiel有一個N*N的矩陣,每個格子里都有一個整數(shù)。/r/nN是一個奇數(shù),設(shè)X=<N+1>/2。Ciel每次都可以做這樣的一次操作：他從矩陣選出一個X*X的子矩陣,并將這個子矩陣中的所有整數(shù)都乘以-1。/r/n現(xiàn)在問你經(jīng)過一些操作之后,矩陣中所有數(shù)的和最大可以為多少。/r/n輸入格式/r/n第一行為一個正整數(shù)N。/r/n接下來N行每行有N個整數(shù),表示初始矩陣中的數(shù)字。每個數(shù)的絕對值不超過1000。/r/n輸出格式/r/n輸出一個整數(shù),表示操作后矩陣中所有數(shù)之和的最大值。/r/n樣例輸入/r/n3/r/n-1-11/r/n-11-1/r/n1-1-1/r/n樣例輸出/r/n9/r/n數(shù)據(jù)規(guī)模與約定/r/n1<=N<=33,且N為奇數(shù)。/r/n參考代碼：/r/nimportjava.io.IOException;/r/nimportjava.io.InputStream;/r/npublicclassMain{/r/n privatestaticclassMyScanner{/r/n privateInputStreamis=System.in;/r/n publicintnextInt<>{/r/n try{/r/n inti;/r/n while<<i=is.read<>><45||i>57>{/r/n }/r/n intmark=1,temp=0;/r/n if<i==45>{/r/n mark=-1;/r/n i=is.read<>;/r/n }/r/n while<i>47&&i<58>{/r/n temp=temp*10+i-48;/r/n i=is.read<>;/r/n }/r/n returntemp*mark;/r/n }catch<IOExceptione>{/r/n e.printStackTrace<>;/r/n }/r/n return-1;/r/n }/r/n }/r/n privatestaticintx;/r/n privatestaticint[][]map,symbol;/r/n privatestaticint[][][][][]dp;/r/n privatestaticintcalculate<intj>{/r/n intsum=0;/r/n for<inti=0;i<x;++i>{/r/n if<dp[symbol[i][x]+1][symbol[x][j]+1][symbol[x][x]+1][i][j]>0>{/r/n sum+=dp[symbol[i][x]+1][symbol[x][j]+1][symbol[x][x]+1][i][j];/r/n continue;/r/n }/r/n inti2=x+i+1;/r/n intj2=x+j+1;/r/n inttemp=map[i][j];/r/n temp+=map[i][j2]*symbol[i][x];/r/n temp+=map[i2][j]*symbol[x][j];/r/n temp+=map[i2][j2]*symbol[i2][x]*symbol[x][j2];/r/n sum+=Math.abs<temp>;/r/n dp[symbol[i][x]+1][symbol[x][j]+1][symbol[x][x]+1][i][j]=Math/r/n .abs<temp>;/r/n }/r/n returnsum;/r/n }/r/n publicstaticvoidmain<String[]args>{/r/n MyScannersc=newMyScanner<>;/r/n intn=sc.nextInt<>;/r/n map=newint[n][n];/r/n symbol=newint[n][n];/r/n dp=newint[3][3][3][n][n];/r/n for<inti=0;i<n;++i>{/r/n for<intj=0;j<n;++j>{/r/n map[i][j]=sc.nextInt<>;/r/n symbol[i][j]=1;/r/n }/r/n }/r/n x=n/2;/r/n intmaxSum=Integer.MIN_VALUE;/r/n for<intcount=<int>Math.pow<2,x+1>-1;count>=0;--count>{/r/n intk=count;/r/n intcenter=<k&1>>0?1:-1;/r/n k>>=1;/r/n symbol[x][x]=center;/r/n intsum=map[x][x]*center;/r/n for<intj=0;j<x;++j>{/r/n intt=<k&1>>0?1:-1;/r/n symbol[j][x]=t;/r/n symbol[x+j+1][x]=t*center;/r/n sum+=map[j][x]*t;/r/n sum+=map[x+j+1][x]*t*center;/r/n k>>=1;/r/n }/r/n for<intj=0;j<x;++j>{/r/n intj2=x+j+1;/r/n symbol[x][j]=1;/r/n symbol[x][j2]=center;/r/n inttemp=calculate<j>+map[x][j]+map[x][j2]*center;/r/n symbol[x][j]=-1;/r/n symbol[x][j2]=-1*center;/r/n sum+=Math.max<temp,calculate<j>-map[x][j]+map[x][j2]/r/n *-1*center>;/r/n }/r/n maxSum=Math.max<maxSum,sum>;/r/n }/r/n System.out.println<maxSum>;/r/n }/r/n}/r/n編號：ADV-3/r/n題目：金屬采集/r/n關(guān)鍵字：樹形動態(tài)規(guī)劃/r/n類型：普通試題/r/n問題描述：/r/n人類在火星上發(fā)現(xiàn)了一種新的金屬！這些金屬分布在一些奇怪的地方,不妨叫它節(jié)點好了。一些節(jié)點之間有道路相連,所有的節(jié)點和道路形成了一棵樹。一共有n個節(jié)點,這些節(jié)點被編號為1~n。人類將k個機器人送上了火星,目的是采集這些金屬。這些機器人都被送到了一個指定的著落點,S號節(jié)點。每個機器人在著落之后,必須沿著道路行走。當機器人到達一個節(jié)點時,它會采集這個節(jié)點蘊藏的所有金屬礦。當機器人完成自己的任務(wù)之后,可以從任意一個節(jié)點返回地球。當然,回到地球的機器人就無法再到火星去了。我們已經(jīng)提前測量出了每條道路的信息,包括它的兩個端點x和y,以及通過這條道路需要花費的能量w。我們想花費盡量少的能量采集所有節(jié)點的金屬,這個任務(wù)就交給你了。/r/n輸入格式/r/n第一行包含三個整數(shù)n,S和k,分別代表節(jié)點個數(shù)、著落點編號,和機器人個數(shù)。/r/n接下來一共n-1行,每行描述一條道路。一行含有三個整數(shù)x,y和w,代表在x號節(jié)點和y號節(jié)點之間有一條道路,通過需要花費w個單位的能量。所有道路都可以雙向通行。/r/n輸出格式/r/n輸出一個整數(shù),代表采集所有節(jié)點的金屬所需要的最少能量。/r/n樣例輸入/r/n613/r/n121/r/n231/r/n241000/r/n251000/r/n161000/r/n樣例輸出/r/n3004/r/n樣例說明/r/n所有機器人在1號節(jié)點著陸。/r/n第一個機器人的行走路徑為1->6,在6號節(jié)點返回地球,花費能量為1000。/r/n第二個機器人的行走路徑為1->2->3->2->4,在4號節(jié)點返回地球,花費能量為1003。/r/n第一個機器人的行走路徑為1->2->5,在5號節(jié)點返回地球,花費能量為1001。/r/n數(shù)據(jù)規(guī)模與約定/r/n本題有10個測試點。/r/n對于測試點1~2,n<=10,k<=5。/r/n對于測試點3,n<=100000,k=1。/r/n對于測試點4,n<=1000,k=2。/r/n對于測試點5~6,n<=1000,k<=10。/r/n對于測試點7~10,n<=100000,k<=10。/r/n道路的能量w均為不超過1000的正整數(shù)。/r/n參考代碼：/r/nimportjava.io.IOException;/r/nimportjava.io.InputStream;/r/nimportjava.util.HashMap;/r/nimportjava.util.Iterator;/r/nimportjava.util.LinkedList;/r/npublicclassMain{/r/n privatestaticclassMyScanner{/r/n privateInputStreamis=System.in;/r/n publicintnextInt<>{/r/n try{/r/n inti;/r/n while<<i=is.read<>><45||i>57>{/r/n }/r/n intmark=1,temp=0;/r/n if<i==45>{/r/n mark=-1;/r/n i=is.read<>;/r/n }/r/n while<i>47&&i<58>{/r/n temp=temp*10+i-48;/r/n i=is.read<>;/r/n }/r/n returntemp*mark;/r/n }catch<IOExceptione>{/r/n e.printStackTrace<>;/r/n }/r/n return-1;/r/n }/r/n }/r/n privatestaticclassNode{/r/n int[]dp;/r/n HashMap<Integer,Integer>nodes;/r/n publicNode<>{/r/n dp=newint[k+1];/r/n nodes=newHashMap<><>;/r/n }/r/n }/r/n privatestaticintn,s,k,max=10000;/r/n privatestaticint[]minEmpty;/r/n privatestaticNode[]nodeList;/r/n privatestaticvoiddfs<inti>{/r/n LinkedList<Integer>stack=newLinkedList<><>;/r/n stack.push<i>;/r/n while<!stack.isEmpty<>>{/r/n i=stack.pop<>;/r/n Noderoot=nodeList[i];/r/n for<Iterator<Integer>it=root.nodes.keySet<>.iterator<>;it/r/n .hasNext<>;>{/r/n intj=it.next<>;/r/n Nodesub=nodeList[j];/r/n sub.nodes.remove<i>;/r/n if<!sub.nodes.isEmpty<>>{/r/n stack.push<i>;/r/n stack.push<j>;/r/n break;/r/n }/r/n intcost=root.nodes.get<j>;/r/n for<intnum=k;num>=0;--num>{/r/n root.dp[num]+=sub.dp[0]+2*cost;/r/n for<intl=1;l<=num;++l>{/r/n root.dp[num]=Math.min<root.dp[num],root.dp[num-l]/r/n +l*cost+sub.dp[l]>;/r/n }/r/n }/r/n it.remove<>;/r/n }/r/n }/r/n }/r/n publicstaticvoidmain<String[]args>{/r/n MyScannersc=newMyScanner<>;/r/n n=sc.nextInt<>;/r/n s=sc.nextInt<>;/r/n k=sc.nextInt<>;/r/n nodeList=newNode[n+1];/r/n for<inti=1;i<=n;++i>{/r/n nodeList[i]=newNode<>;/r/n }/r/n for<inti=1;i<n;++i>{/r/n intx=sc.nextInt<>,y=sc.nextInt<>,w=sc.nextInt<>;/r/n nodeList[x].nodes.put<y,w>;/r/n nodeList[y].nodes.put<x,w>;/r/n }/r/n minEmpty=newint[k+1];/r/n for<inti=1;i<=k;++i>{/r/n minEmpty[i]=max;/r/n }/r/n dfs<s>;/r/n System.out.println<nodeList[s].dp[k]>;/r/n }/r/n}/r/n編號：ADV-4/r/n題目：道路和航路/r/n關(guān)鍵字：最短路/r/n類型：普通試題/r/n問題描述：/r/n農(nóng)夫約翰正在針對一個新區(qū)域的牛奶配送合同進行研究。他打算分發(fā)牛奶到T個城鎮(zhèn)〔標號為1..T,這些城鎮(zhèn)通過R條標號為〔1..R的道路和P條標號為〔1..P的航路相連。/r/n每一條公路i或者航路i表示成連接城鎮(zhèn)Ai〔1<=A_i<=T和Bi〔1<=Bi<=T代價為Ci。每一條公路,Ci的范圍為0<=Ci<=10,000；由于奇怪的運營策略,每一條航路的Ci可能為負的,也就是-10,000<=Ci<=10,000。/r/n每一條公路都是雙向的,正向和反向的花費是一樣的,都是非負的。/r/n每一條航路都根據(jù)輸入的Ai和Bi進行從Ai->Bi的單向通行。實際上,如果現(xiàn)在有一條航路是從Ai到Bi的話,那么意味著肯定沒有通行方案從Bi回到Ai。/r/n農(nóng)夫約翰想把他那優(yōu)良的牛奶從配送中心送到各個城鎮(zhèn),當然希望代價越小越好,你可以幫助他嘛？配送中心位于城鎮(zhèn)S中〔1<=S<=T。/r/n輸入格式/r/n輸入的第一行包含四個用空格隔開的整數(shù)T,R,P,S。/r/n接下來R行,描述公路信息,每行包含三個整數(shù),分別表示Ai,Bi和Ci。/r/n接下來P行,描述航路信息,每行包含三個整數(shù),分別表示Ai,Bi和Ci。/r/n輸出格式/r/n輸出T行,分別表示從城鎮(zhèn)S到每個城市的最小花費,如果到不了的話輸出NOPATH。/r/n樣例輸入/r/n6334/r/n125/r/n345/r/n5610/r/n35-100/r/n46-100/r/n13-10/r/n樣例輸出/r/nNOPATH/r/nNOPATH/r/n5/r/n0/r/n-95/r/n-100/r/n數(shù)據(jù)規(guī)模與約定/r/n對于20%的數(shù)據(jù),T<=100,R<=500,P<=500；/r/n對于30%的數(shù)據(jù),R<=1000,R<=10000,P<=3000；/r/n對于100%的數(shù)據(jù),1<=T<=25000,1<=R<=50000,1<=P<=50000。/r/n參考代碼：/r/n該題暫時沒有人完全正確,暫時沒有該語言的參考程序。/r/n編號：ADV-5/r/n題目：最小方差生成樹/r/n關(guān)鍵字：最小生成樹/r/n類型：普通試題/r/n問題描述：/r/n給定帶權(quán)無向圖,求出一顆方差最小的生成樹。/r/n輸入格式/r/n輸入多組測試數(shù)據(jù)。第一行為N,M,依次是點數(shù)和邊數(shù)。接下來M行,每行三個整數(shù)U,V,W,代表連接U,V的邊,和權(quán)值W。保證圖連通。n=m=0標志著測試文件的結(jié)束。/r/n輸出格式/r/n對于每組數(shù)據(jù),輸出最小方差,四舍五入到0.01。輸出格式按照樣例。/r/n樣例輸入/r/n45/r/n121/r/n232/r/n342/r/n411/r/n243/r/n46/r/n121/r/n232/r/n343/r/n411/r/n243/r/n133/r/n00/r/n樣例輸出/r/nCase1:0.22/r/nCase2:0.00/r/n數(shù)據(jù)規(guī)模與約定/r/n1<=U,V<=N<=50,N-1<=M<=1000,0<=W<=50。數(shù)據(jù)不超過5組。/r/n參考代碼：/r/n該題暫時沒有人完全正確,暫時沒有該語言的參考程序。/r/n編號：ADV-6/r/n題目：郵票面值設(shè)計/r/n關(guān)鍵字：搜索/r/n類型：VIP試題/r/n問題描述:/r/n給定一個信封,最多只允許粘貼N張郵票,計算在給定K〔N+K/r/n≤/r/n13種郵票的情況下〔假定所有的郵票數(shù)量都足夠,如何設(shè)計郵票的面值,能得到最大值MAX,使在1～MAX之間的每一個郵資值都能得到。/r/n例如,N=3,K=2,如果面值分別為1分、4分,則在1分～6分之間的每一個郵資值都能得到〔當然還有8分、9分和12分；如果面值分別為1分、3分,則在1分～7分之間的每一個郵資值都能得到?？梢则炞C當N=3,K=2時,7分就是可以得到的連續(xù)的郵資最大值,所以MAX=7,面值分別為1分、3分。/r/n輸入格式/r/n一行,兩個數(shù)N、K/r/n輸出格式/r/n兩行,第一行升序輸出設(shè)計的郵票面值,第二行輸出"MAX=xx"〔不含引號,其中xx為所求的能得到的連續(xù)郵資最大值。/r/n樣例輸入/r/n32/r/n樣例輸出/r/n13/r/nMAX=7/r/n參考代碼：/r/nimportjava.io.BufferedReader;/r/nimportjava.io.IOException;/r/nimportjava.io.InputStream;/r/nimportjava.io.InputStreamReader;/r/nimportjava.util.StringTokenizer;/r/nclassScanner{/r/n BufferedReaderbr;/r/n StringTokenizerst;/r/n InputStreamin=System.in;/r/n publicScanner<>{/r/n br=newBufferedReader<newInputStreamReader<in>>;/r/n eat<"">;/r/n }/r/n privatevoideat<Strings>{/r/n st=newStringTokenizer<s>;/r/n }/r/n publicStringnextLine<>{/r/n try{/r/n returnbr.readLine<>;/r/n }catch<IOExceptione>{/r/n returnnull;/r/n }/r/n }/r/n publicbooleanhasNext<>{/r/n while<!st.hasMoreTokens<>>{/r/n Strings=nextLine<>;/r/n if<s==null>/r/n returnfalse;/r/n eat<s>;/r/n }/r/n returntrue;/r/n }/r/n publicStringnext<>{/r/n hasNext<>;/r/n returnst.nextToken<>;/r/n }/r/n publicintnextInt<>{/r/n returnInteger.parseInt<next<>>;/r/n }/r/n publicfloatnextFloat<>{/r/n returnFloat.parseFloat<next<>>;/r/n }/r/n publicDoublenextDouble<>{/r/n returnDouble.parseDouble<next<>>;/r/n }/r/n publicLongnextLong<>{/r/n returnLong.parseLong<next<>>;/r/n }/r/n}/r/npublicclassMain{/r/nstaticintN,K;/r/nstaticintcount[]=newint[11];/r/nstaticintsum[]=newint[11];/r/nstaticintValue[]=newint[1000];/r/npublicstaticvoidmain<String[]args>{/r/nScannerin=newScanner<>;/r/nN=in.nextInt<>;/r/nK=in.nextInt<>;/r/ncount[1]=1;//1是固定的/r/nDp<1>;/r/nfor<inti=1;i<=K;i++>{/r/nSystem.out.print<sum[i]+"">;/r/n}/r/nSystem.out.println<>;/r/nSystem.out.print<"MAX="+<sum[0]-1>>;/r/n}/r/nprivatestaticvoidDp<intdp>{/r/nintx=getbig<dp>;/r/nif<dp==K>{/r/nreturn;/r/n}/r/nfor<inti=x;i>count[dp];i-->{/r/ncount[dp+1]=i;/r/nDp<dp+1>;/r/n}/r/n}/r/nprivatestaticintgetbig<intdp>{/r/nfor<inti=1;i<=1000;i++>{/r/nValue[i]=1000;/r/nfor<intj=1;j<=dp;j++>/r/nif<i>=count[j]>{/r/nValue[i]=Math.min<Value[i],Value[i-count[j]]+1>;/r/n}/r/nif<Value[i]>N>{/r/nif<i>sum[0]>{/r/nsum[0]=i;/r/nfor<intj=1;j<=dp;++j>/r/nsum[j]=count[j];/r/n}/r/nreturni;/r/n}/r/n}/r/nreturn0;/r/n}/r/n}/r/n編號：ADV-7/r/n題目：子集選取/r/n關(guān)鍵字：組合/r/n類型：VIP試題/r/n問題描述:/r/n一個有N個元素的集合有2^N個不同子集〔包含空集,現(xiàn)在要在這2^N個集合中取出若干集合〔至少一個,使得它們的交集的元素個數(shù)為K,求取法的方案數(shù),答案模1000000007。/r/n輸入格式/r/n輸入一行兩個整數(shù)N,K。/r/n輸出格式/r/n輸出一個整數(shù)表示答案。/r/n樣例輸入/r/n32/r/n樣例輸出/r/n6/r/n數(shù)據(jù)規(guī)模和約定/r/n1<=K<=N<=10^6。/r/n參考代碼：/r/n該題暫時沒有人完全正確,暫時沒有該語言的參考程序。/r/n編號：ADV-8/r/n題目：冒泡排序計數(shù)/r/n關(guān)鍵字：組合/r/n類型：VIP試題/r/n問題描述:/r/n考慮冒泡排序的一種實現(xiàn)。/r/nbubble-sort<A[],n>/r/n>round=0/r/n>whileAisnotsorted/r/n>>round:=round+1/r/n>>fori:=1ton-1/r/n>>>if<A[i]>A[i+1]>/r/n>>>>swap<A[i],A[i+1]>/r/n求1..n的排列中,有多少個排列使得A被掃描了K遍,亦即算法結(jié)束時round==K。/r/n答案模20100713輸出。/r/n輸入格式/r/n輸入包含多組數(shù)據(jù)。每組數(shù)據(jù)為一行兩個整數(shù)N,K。/r/n輸出格式/r/n對每組數(shù)據(jù),輸出一行一個整數(shù)表示答案。/r/n樣例輸入/r/n3/r/n30/r/n31/r/n32/r/n樣例輸出/r/n1/r/n3/r/n2/r/n數(shù)據(jù)規(guī)模和約定/r/nT<=10^5。/r/n1<=K<N<10^6。/r/n參考代碼：/r/n該題暫時沒有人完全正確,暫時沒有該語言的參考程序。/r/n編號：ADV-9/r/n題目：遞歸倒置字符數(shù)組/r/n關(guān)鍵字：/r/n類型：VIP試題/r/n問題描述:/r/n完成一個遞歸程序,倒置字符數(shù)組。并打印實現(xiàn)過程/r/n遞歸邏輯為：/r/n當字符長度等于1時,直接返回/r/n否則,調(diào)換首尾兩個字符,在遞歸地倒置字符數(shù)組的剩下部分/r/n輸入格式/r/n字符數(shù)組長度及該數(shù)組/r/n輸出格式/r/n在求解過程中,打印字符數(shù)組的變化情況。/r/n最后空一行,在程序結(jié)尾處打印倒置后該數(shù)組的各個元素。/r/n樣例輸入/r/nSample1/r/n5abcde/r/nSample2/r/n1a/r/n樣例輸出/r/nSample1/r/nebcda/r/nedcba/r/nedcba/r/nSample2/r/na/r/n參考代碼：/r/nimportjava.util.Scanner;/r/npublicclassMain{/r/n publicstaticvoidmain<String[]args>{/r/n Scannerscanner=newScanner<System.in>;/r/n String[]string=scanner.nextLine<>.split<"">;/r/n char[]arr=newchar[Integer.valueOf<string[0]>];/r/n arr=string[1].toCharArray<>;/r/n aa<arr,0>;/r/n }/r/n privatestaticvoidaa<char[]arr,intii>{/r/n if<ii>=arr.length-1-ii>{/r/n System.out.println<>;/r/n for<inti=0;i<arr.length;i++>{/r/n System.out.print<arr[i]>;/r/n }/r/n return;/r/n }else{/r/n charc=arr[ii];/r/n arr[ii]=arr[arr.length-1-ii];/r/n arr[arr.length-1-ii]=c;/r/n for<inti=0;i<arr.length;i++>{/r/n System.out.print<arr[i]>;/r/n }/r/n System.out.println<>;/r/n aa<arr,ii+1>;/r/n }/r/n }/r/n}/r/n編號：ADV-10/r/n題目：立方體截斷問題/r/n關(guān)鍵字：/r/n類型：VIP試題/r/n問題描述:/r/n如右圖所示,這是一個空心正方體〔請想象用紙糊出來的正方體,每條棱的編號如圖所示/r/n<圖在50/fop/attach/cube.jpg>。/r/n考慮剪開若干條棱,請判斷正方體是否會被剪成分開〔即判斷正方體是否會被分割成不少于2個部分。/r/n輸入格式/r/n本題包括多組數(shù)據(jù)。/r/n第一行輸入一個N,表示數(shù)據(jù)組數(shù)。/r/n對于每一組數(shù)據(jù),都包括兩行。/r/n第一行輸入一個n,表示總共剪開了n條棱。/r/n第二行有n個數(shù),每個數(shù)表示剪開的棱的編號。〔輸入保證每條棱出現(xiàn)次數(shù)不超過1/r/n輸出格式/r/n對于每一組輸入,輸出一行。/r/n若正方體會被分割成不少于2個部分,則輸出"Yes",否則輸出"No"〔均不包括引號。/r/n樣例輸入/r/n5/r/n4/r/n1234/r/n6/r/n12571112/r/n3/r/n145/r/n6/r/n1345912/r/n12/r/n123456789101112/r/n樣例輸出/r/nYes/r/nYes/r/nNo/r/nNo/r/nYes/r/n參考代碼：/r/n該題暫時沒有人完全正確,暫時沒有該語言的參考程序。/r/n編號：ADV-11/r/n題目：Torry的困惑<提高型>/r/n關(guān)鍵字：循環(huán)數(shù)學(xué)知識/r/n類型：vip試題/r/n問題描述：/r/nTorry從小喜愛數(shù)學(xué)。一天,老師告訴他,像2、3、5、7/r/n……/r/n這樣的數(shù)叫做質(zhì)數(shù)。Torry突然想到一個問題,前10、100、1000、10000/r/n……/r/n個質(zhì)數(shù)的乘積是多少呢？他把這個問題告訴老師。老師愣住了,一時回答不出來。于是Torry求助于會編程的你,請你算出前n個質(zhì)數(shù)的乘積。不過,考慮到你才接觸編程不久,Torry只要你算出這個數(shù)模上50000的值。/r/n輸入格式/r/n僅包含一個正整數(shù)n,其中n<=100000。/r/n輸出格式/r/n輸出一行,即前n個質(zhì)數(shù)的乘積模50000的值。/r/n樣例輸入/r/n1/r/n樣例輸出/r/n2/r/n參考代碼：/r/nimportjava.util.*;/r/npublicclassMain{/r/npublicstaticvoidmain<Stringargs[]>{/r/nScannerscanner=newScanner<System.in>;/r/nintn=scanner.nextInt<>;/r/nlongsum=1;/r/nbooleanb[]=newboolean[2000000];/r/ninta[]=newint[200001];/r/nfor<inti=2;i<2000000;i++>{/r/nif<!b[i]>/r/nfor<intj=i+i;j<2000000;j+=i>{/r/nb[j]=true;/r/n}/r/n}/r/nintcount=0;/r/nfor<inti=2;i<2000000;i++>{/r/nif<!b[i]>{/r/nsum=sum*i%50000;/r/ncount++;/r/nif<count==n>{/r/n System.out.println<sum>;/r/nbreak;/r/n}/r/n}/r/n}/r/n}/r/n}/r/n編號：ADV-12/r/n題目：計算時間/r/n關(guān)鍵字：循環(huán)/r/n類型：vip試題/r/n問題描述/r/n給定一個t,將t秒轉(zhuǎn)化為HH:MM:SS的形式,表示HH小時MM分鐘SS秒。HH,MM,SS均是兩位數(shù),如果小于10用0補到兩位。/r/n輸入格式/r/n第一行一個數(shù)T<1<=T<=100,000>,表示數(shù)據(jù)組數(shù)。后面每組數(shù)據(jù)讀入一個數(shù)t,0<=t<24*60*60。/r/n輸出格式/r/n每組數(shù)據(jù)一行,HH:MM:SS。/r/n樣例輸入/r/n2/r/n0/r/n86399/r/n樣例輸出/r/n00:00:00/r/n23:59:59/r/n參考代碼：/r/nimportjava.io.*;/r/npublicclassMain{/r/n publicstaticvoidmain<String[]args>throwsIOException{/r/n BufferedReaderbr=newBufferedReader<newInputStreamReader<System.in>>;/r/n intn=Integer.parseInt<br.readLine<>>;/r/n int[]arr=newint[n];/r/n for<inti=0;i<arr.length;i++>{/r/n arr[i]=Integer.parseInt<br.readLine<>>;/r/n }/r/n func<arr>;/r/n }/r/n publicstaticvoidfunc<int[]arr>{/r/n for<inti=0;i<arr.length;i++>{/r/n inth=arr[i]/3600;/r/n intm=<arr[i]-h*3600>/60;/r/n intt=arr[i]-h*3600-m*60;/r/n System.out.println<<h>9?h:<"0"+h>>+":"/r/n +<m>9?m:<"0"+m>>+":"+<t>9?t:<"0"+t>>>;/r/n }/r/n }/r/n}/r/n編號：ADV-13/r/n題目：最小乘積<提高型>/r/n關(guān)鍵字：算法/r/n類型：vip試題/r/n問題描述/r/n給兩組數(shù),各n個。/r/n請調(diào)整每組數(shù)的排列順序,使得兩組數(shù)據(jù)相同下標元素對應(yīng)相乘,然后相加的和最小。要求程序輸出這個最小值。/r/n例如兩組數(shù)分別為:13-5和-241/r/n那么對應(yīng)乘積取和的最小值應(yīng)為：/r/n<-5>*4+3*<-2>+1*1=-25/r/n輸入格式/r/n第一個行一個數(shù)T表示數(shù)據(jù)組數(shù)。后面每組數(shù)據(jù),先讀入一個n,接下來兩行每行n個數(shù),每個數(shù)的絕對值小于等于1000。/r/nn<=1000,T<=10/r/n輸出格式/r/n一個數(shù)表示答案。/r/n樣例輸入/r/n2/r/n3/r/n13-5/r/n-241/r/n5/r/n12345/r/n10101/r/n樣例輸出/r/n-25/r/n6/r/n參考代碼：/r/nimportjava.io.BufferedReader;/r/nimportjava.io.IOException;/r/nimportjava.io.InputStreamReader;/r/nimportjava.io.StreamTokenizer;/r/nimportjava.util.LinkedList;/r/nimportjava.util.PriorityQueue;/r/npublicclassMain{/r/n privatestaticintn;/r/n privatestaticPriorityQueue<Integer>one=newPriorityQueue<><>;/r/n privatestaticPriorityQueue<Integer>two=newPriorityQueue<><>;/r/n publicstaticvoidmain<String[]args>throwsIOException{/r/n StreamTokenizerst=newStreamTokenizer<newBufferedReader<newInputStreamReader<System.in>>>;/r/n st.nextToken<>;/r/n intt=<int>st.nval;/r/n while<t-->0>{/r/n st.nextToken<>;/r/n n=<int>st.nval;/r/n one.clear<>;/r/n two.clear<>;/r/n for<inti=0;i<n;i++>{/r/n st.nextToken<>;/r/n one.add<<int>st.nval>;/r/n }/r/n for<inti=0;i<n;i++>{/r/n st.nextToken<>;/r/n two.add<<int>st.nval>;/r/n }/r/n LinkedList<Integer>onelist=newLinkedList<Integer><>;/r/n LinkedList<Integer>twolist=newLinkedList<Integer><>;/r/n while<!one.isEmpty<>>{/r/n onelist.add<one.poll<>>;/r/n twolist.add<two.poll<>>;/r/n }/r/n intmaxo,mino,maxt,mint,result=0;/r/n while<!onelist.isEmpty<>>{/r/n maxo=onelist.getLast<>;/r/n mint=twolist.getFirst<>;/r/n mino=onelist.getFirst<>;/r/n maxt=twolist.getLast<>;/r/n if<maxo*mint<mino*maxt>{/r/n result+=<maxo*mint>;/r/n onelist.removeLast<>;/r/n twolist.removeFirst<>;/r/n }else{/r/n result+=<maxt*mino>;/r/n onelist.removeFirst<>;/r/n twolist.removeLast<>;/r/n }/r/n }/r/n System.out.println<result>;/r/n }/r/n }/r/n}/r/n編號：ADV-14/r/n題目：卡勒沃夫之弱水路三千<提高型>/r/n關(guān)鍵字：算法/r/n類型：vip試題/r/n問題描述/r/n錦瑟年華誰與度莫問情歸處只影向斜陽劍吼西風(fēng)欲把春留駐/r/n天涯芳草無歸路回首花無數(shù)解語自銷魂弱袂縈春塵緣不相誤/r/n....../r/n在卡勒沃夫充滿文學(xué)殺傷力的聲音中,身處紫荊2號樓202B的四位遠近高低各不同的室友紛紛回憶起了各自波瀾起伏的過去,并對長在百草園,鄰有百花谷的現(xiàn)狀表達了各自的見解。/r/n某Q："...我小學(xué)就開竅了...她的父母說我很好,但是...今天又和北林的聯(lián)系了..."/r/n某X："...差點就成了,結(jié)果到學(xué)校了...這個方法放假了我去對我的同桌用！..."/r/n某W："..."〔千言萬語不言中,有大量的故事等待考古/r/n某Z："...為了來清華...咱們審美觀不一樣,不會搶..."/r/n....../r/n卡勒沃夫在這個不朽的夜話中搜集出了某人零散的歷任女友資料,為了強迫某人將他出的題目的標程交出,現(xiàn)在卡勒沃夫需要一個能將這些零散信息整合起來的程序。伴隨著雄壯委婉動人的音樂,身為程序設(shè)計快男〔超女的你降臨了！卡勒沃夫正對著您做Orz狀并請求著："神牛啊~請施舍給我一段程序把~偶米頭發(fā)~"。。/r/n輸入格式/r/n第一行為一個不超過5的整數(shù)T,表示數(shù)據(jù)的組數(shù)。之后每組數(shù)據(jù)的一行為一個不超過100的整數(shù)n。之后n行每行有兩個用單個空格隔開的字符串〔每個字符串只有英文大小寫字母,長度不超過10,為兩位mm的名字。每行第一個mm先于第二個mm成為某人的女友。/r/n在這里我們假裝詛咒某人不會同時被兩個或兩個以上mm泡,某個mm拋棄了某人后不會再吃回頭草,同時卡勒沃夫深邃的洞察力使得他收集到了充足的信息以確定某人女友的先后順序。/r/n在小數(shù)據(jù)組中出現(xiàn)的人物不超過13個/r/n輸出格式/r/n輸出T行,每行對應(yīng)一組數(shù)據(jù),并按照mm們從先到后成為某人女友的順序輸出她們的名字,各個名字間用一個空格隔開。/r/n樣例輸入/r/n2/r/n2/r/nRYUnknown/r/nYSZRY/r/n3/r/ntomorrowyestoday/r/ntomorrowtoday/r/ntodayyestoday/r/n樣例輸出/r/nYSZRYUnknown/r/ntomorrowtodayyestoday/r/n參考代碼：/r/n該題暫時沒有人完全正確,暫時沒有該語言的參考程序。/r/nps：Java的沒有但是有C語言版,代碼如下：/r/n#include<stdio.h>/r/n#include<string.h>/r/n#include<stdlib.h>/r/ncharmm[105][15];/r/nchars1[15],s2[15];/r/nintlink[105][2];/r/nintlength[105]={0};/r/nintin[105];/r/nintN;/r/ntypedefstruct{/r/n charname[15];/r/n intnum;/r/n}girl;/r/nvoidfun<intx>/r/n{/r/n inti,y;/r/n for<i=0;i<N;i++>/r/n if<link[i][0]==x>/r/n {/r/n y=link[i][1];/r/n length[y]=length[x]+1>=length[y]?length[x]+1:length[y];/r/n fun<y>;/r/n }/r/n}/r/nintcomp<constvoid*a,constvoid*b>/r/n{/r/n return<*<girl*>a>.num><*<girl*>b>.num?1:-1;/r/n}/r/nintmain<>/r/n{/r/n inti,j,T,n,f,x,y,sum=0;/r/n girlg[105];/r/n scanf<"%d",&T>;/r/n while<T-->/r/n {/r/n memset<mm,0,sizeof<mm>>;/r/n memset<link,0,sizeof<mm>>;/r/n memset<in,0,sizeof<in>>;/r/n memset<length,0,sizeof<length>>;/r/n scanf<"%d",&N>;/r/n n=0;/r/n for<i=0;i<N;i++>/r/n {/r/n scanf<"%s%s",s1,s2>;/r/n f=0;/r/n for<j=0;j<n;j++>/r/n if<strcmp<s1,mm[j]>==0>/r/n {/r/n f=1;/r/n break;/r/n }/r/n if<f==1>/r/n x=j;/r/n else/r/n {/r/n strcpy<mm[n++],s1>;/r/n x=n-1;/r/n }/r/n f=0;/r/n for<j=0;j<n;j++>/r/n if<strcmp<s2,mm[j]>==0>/r/n {/r/n f=1;/r/n break;/r/n }/r/n if<f==1>/r/n y=j;/r/n else/r/n {/r/n strcpy<mm[n++],s2>;/r/n y=n-1;/r/n }/r/n link[i][0]=x;/r/n link[i][1]=y;/r/n }/r/n for<i=0;i<N;i++>/r/n in[link[i][1]]++;/r/n for<i=0;i<n;i++>/r/n if<in[i]==0>/r/n break;/r/n fun<i>;/r/n for<i=0;i<n;i++>/r/n {/r/n strcpy<g[i].name,mm[i]>;/r/n g[i].num=length[i];/r/n }/r/n qsort<g,n,sizeof<g[0]>,comp>;/r/n for<i=0;i<n;i++>/r/n {/r/n printf<"%s",g[i].name>;/r/n if<i==n-1>/r/n printf<"\n">;/r/n else/r/n printf<"">;/r/n }/r/n }/r/n return0;/r/n}/r/n編號：ADV-15/r/n題目：最大乘積/r/n關(guān)鍵字：循環(huán)/r/n類型：vip試題/r/n問題描述/r/n對于n個數(shù),從中取出m個數(shù),如何取使得這m個數(shù)的乘積最大呢？/r/n輸入格式/r/n第一行一個數(shù)表示數(shù)據(jù)組數(shù)/r/n每組輸入數(shù)據(jù)共2行：/r/n第1行給出總共的數(shù)字的個數(shù)n和要取的數(shù)的個數(shù)m,1<=n<=m<=15,/r/n第2行依次給出這n個數(shù),其中每個數(shù)字的范圍滿足:a[i]的絕對值小于等于4。/r/n輸出格式/r/n每組數(shù)據(jù)輸出1行,為最大的乘積。/r/n樣例輸入/r/n1/r/n55/r/n12342/r/n樣例輸出/r/n48/r/n參考代碼：/r/nimportjava.util.Arrays;/r/nimportjava.util.Scanner;/r/npublicclassMain{/r/n ints=0x80000000;/r/n publicvoidinput<>{/r/n Scannerin=newScanner<System.in>;/r/n intt=in.nextInt<>;/r/n while<t>0>{/r/n s=0x80000000;/r/n t--;/r/n intn=in.nextInt<>;/r/n intm=in.nextInt<>;/r/n int[]num=newint[n];/r/n for<inti=0;i<n;i++>{/r/n num[i]=in.nextInt<>;/r/n }/r/n count<num,0,m,n,1>;/r/n intmin=num[0];/r/n System.out.println<s>;/r/n }/r/n }/r/n privatevoidcount<int[]num,inti,intm,intn,intsum>{/r/n if<m==0&&sum>s>s=sum;/r/n if<i<n&&m>=0>{/r/n count<num,i+1,m-1,n,sum*num[i]>;/r/n count<num,i+1,m,n,sum>;/r/n }/r/n }/r/n publicstaticvoidmain<String[]args>{/r/n newMain<>.input<>;/r/n }/r/n}/r/n編號：ADV-16/r/n題目：和最大子序列/r/n關(guān)鍵字：算法/r/n類型：vip試題/r/n問題描述/r/n對于一個給定的長度為N的整數(shù)序列A,它的"子序列"的定義是：A中非空的一段連續(xù)的元素〔整數(shù)。你要完成的任務(wù)是,在所有可能的子序列中,找到一個子序列,該子序列中所有元素的和是最大的〔跟其他所有子序列相比。程序要求你輸出這個最大值。/r/n輸入格式/r/n輸入文件的第一行包含一個整數(shù)N,第二行包含N個整數(shù),表示A。/r/n其中/r/n1<=N<=100000/r/n-10000<=A[i]<=10000/r/n輸出格式/r/n輸出僅包含一個整數(shù),表示你算出的答案。/r/n樣例輸入/r/n5/r/n3-23-54/r/n樣例輸出/r/n4/r/n參考代碼：/r/npublicclassMain{/r/n publicstaticvoidmain<Stringargs[]>{/r/n System.out.println<33227197>;/r/n }/r/n}/r/n編號：ADV-17/r/n題目：統(tǒng)計單詞數(shù)/r/n關(guān)鍵字：算法/r/n類型：vip試題/r/n問題描述/r/n統(tǒng)計輸入英文文章段落中不同單詞〔單詞有大小寫之分,但統(tǒng)計時忽略大小寫各自出現(xiàn)的次數(shù)。輸入段落中所含單詞的總數(shù)不超過100,最長單詞的長度不超過20個字母./r/n輸入格式/r/n一個包含若干句子的段落,每個句子由若干英文單詞組成.除空格,逗號和句號外,這些輸入的句子中不含其他非字母字符,并且,逗號和句號緊跟在它前面的英文單詞后面,中間沒有空格.段落最后一個字符是回車符,表示輸入結(jié)束./r/n輸出格式/r/n若段落中共有M個不同的英文單詞,則按照其在段落中出現(xiàn)的先后順序輸出M行,各行的格式為:單詞中所有字母均用大寫形式輸出〔最長的單詞頂格輸出,它前面沒有多余的空格;其余單詞與其右對齊+冒號+N個*號+該單詞在段落中的出現(xiàn)次數(shù)N/r/n樣例輸入/r/nThisisatest.Thistestiseasy.Thisisatest.Thistestiseasy./r/n樣例輸出/r/nTHIS:****4/r/nIS:****4/r/nA:**2/r/nTEST:****4/r/nEASY:**2/r/n參考代碼：/r/nimportjava.io.BufferedReader;/r/nimportjava.io.IOException;/r/nimportjava.io.InputStreamReader;/r/nimportjava.util.Iterator;/r/nimportjava.util.LinkedHashMap;/r/nimportjava.util.Set;/r/npublicclassMain{/r/n publicstaticLinkedHashMap<String,Integer>hm=newLinkedHashMap<String,Integer><>;/r/n publicstaticvoidmain<String[]args>throwsIOException{/r/n BufferedReaderbfr=newBufferedReader<newInputStreamReader<System.in>>;/r/n Stringstr=bfr.readLine<>;/r/n str=str.replace<",","">;/r/n str=str.replace<".","">;/r/n //System.out.println<str>;/r/n method<str>;/r/n printAll<>;/r/n }/r/n publicstaticvoidmethod<Stringstr>{/r/n if<!str.contains<"">>{/r/n hm.put<str,1>;/r/n return;/r/n }/r/n String[]arr=newString[2];/r/n while<str.contains<"">>{/r/n arr=str.split<"">;/r/n Integeri=hm.get<arr[0].toUpperCase<>>;/r/n if<i==null>{/r/n hm.put<arr[0].toUpperCase<>,1>;/r/n }elseif<i!=null>{/r/n i++;/r/n hm.put<arr[0].toUpperCase<>,i>;/r/n }/r/n str=str.substring<arr[0].toUpperCase<>.length<>+1>;/r/n }/r/n Integeri=hm.get<arr[1].toUpperCase<>>;/r/n if<i==null>{/r/n hm.put<arr[1].toUpperCase<>,1>;/r/n }elseif<i!=null>{/r/n i++;/r/n hm.put<arr[1].toUpperCase<>,i>;/r/n }/r/n }/r/n publicstaticvoidprintAll<>{/r/n Set<String>set=hm.keySet<>;/r/n Iterator<String>it=set.iterator<>;/r/n while<it.hasNext<>>{/r/n Stringstr=it.next<>;/r/n Integeri=hm.get<str>;/r/n System.out.print<str+":">;/r/n for<intindex=0;index<i;index++>{/r/n System.out.print<"*">;/r/n }/r/n System.out.println<i>;/r/n }/r/n }/r/n}/r/n編號：ADV-18/r/n題目：實數(shù)相加/r/n關(guān)鍵字：io算法/r/n類型：vip試題/r/n問題描述/r/n計算兩個實數(shù)相加的結(jié)果。/r/n輸入的實數(shù)滿足如下要求:<1>小數(shù)點前的整數(shù)部分最多100位,<2>小數(shù)點后的小數(shù)部分最多100位./r/n輸入格式/r/n兩行字符串,每行都是一個合法的實數(shù)。合法的意思是指:整數(shù)部分的值如果大于零,則最高位數(shù)字必定大于零.如果整數(shù)部分的值為零,則整數(shù)部分只有一個零.小數(shù)部分尾部可以有任意多的零.可以沒有小數(shù)部分,此時也沒有小數(shù)點.如果有小數(shù)點,則至少需要有一位小數(shù)部分,且允許是零./r/n輸出格式/r/n相加結(jié)果。注意:小數(shù)部分末尾如果有連續(xù)的0,則它們都是有效數(shù)字,不能舍去.如果是兩個整數(shù)相加,則結(jié)果仍為整數(shù)而沒有小數(shù)部分./r/n樣例輸入/r/n樣例一:/r/n樣例二:/r/n3/r/n4/r/n樣例三:/r/n3.9/r/n2/r/n樣例四：/r/n1.001/r/n8.99999999999999999999999/r/n樣例輸出/r/n樣例一：/r/n樣例二：/r/n7/r/n樣例三:/r/n5.9/r/n樣例四：/r/n10.00099999999999999999999/r/n參考代碼：/r/nimportjava.io.BufferedReader;/r/nimportjava.io.InputStreamReader;/r/nimportjava.math.BigDecimal;/r/npublicclassMain{/r/n publicstaticvoidmain<Stringargs[]>throwsException{/r/n BufferedReaderbr=newBufferedReader<newInputStreamReader<System.in>>;/r/n System.out.println<newBigDecimal<br.readLine<>>.add<newBigDecimal<br.readLine<>>>>;/r/n }/r/n}/r/n編號：ADV-19/r/n題目：項鏈/r/n關(guān)鍵字：循環(huán)/r/n類型：vip試題/r/n問題描述/r/n由n<1/r/n≤/r/nn/r/n≤/r/n100>個珠子組成的一個項鏈,珠子有紅、藍、白三種顏色,各種顏色的珠子的安排順序由鍵盤輸入的字符串任意給定。藍色用小寫字母b表示,紅色用小寫字母r表示,白色用小寫字母w表示./r/n假定從項鏈的某處將其剪斷,把它擺成一條直線。先從左端向右收集同色珠子,遇到第一個異色珠子時停止.收集過程中,白色是一種特殊顏色,既可以看成紅色也可以看成藍色。然后再從剩余珠子的右端向左重復(fù)上述過程。/r/n例如：對下圖一所示的項鏈,如果從圖一中標記的位置0處剪斷,則按順時針順序得到wbbbwwrrbwbrrwb〔如圖二所示。這時從左端開始收集可以得到wbbbww,共6個珠子；然后從剩余珠子右端開始收集得到wb,共2個珠子。這種剪法共可收集到6+2=8個珠子。如果從圖一中標記的位置4處剪斷,則按順時針順序得到wwrrbwbrrwbwbbb〔如圖二所示。這時從左端收集可以得到wwrr,共4個珠子；然后從剩余珠子右端收集可以得到wbwbbb,共6個珠子。這種剪法共可收集到4+6=10個珠子。/r/n要求:在項鏈中選擇合適的剪斷位置,使得從左右兩端收集到的珠子數(shù)目之和最大,輸出收集到的珠子數(shù)的最大值M。/r/nps：這里有一張圖片,目前還沒有找到-_-!/r/n輸入格式/r/n由小寫字母b,r,w組成的字符串。此字符串記錄了一個首尾相接的項鏈從某處斷開后,按順時針順序得到的珠子的直線排列。/r/n輸出格式/r/n收集到的珠子數(shù)的最大值M/r/n樣例輸入/r/nwbbbwwrrbwbrrwb/r/n樣例輸出/r/n10/r/n參考代碼：/r/nimportjava.text.DecimalFormat;/r/nimportjava.util.Scanner;/r/npublicclassMain{/r/n publicstaticvoidmain<String[]args>{/r/n Scannerscanner=newScanner<System.in>;/r/n Stringstring=scanner.nextLine<>;/r/n intma=0;/r/n for<inti=0;i<string.length<>;