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

1、算法訓(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ù)，表示詢問的答案。樣例輸入51 2 3 4 521 5 22 3 2樣例輸出42數(shù)據(jù)規(guī)模與約定對于30%的數(shù)據(jù)，n,m=100；對于100%的數(shù)據(jù)，n,m=1000；保

2、證k=(r-l+1)，序列中的數(shù)=1000000。本題的Java參考代碼如下：import java.io.BufferedInputStream;import java.io.IOException;import java.util.Arrays;public class Mainprivate static BufferedInputStream in = new BufferedInputStream(System.in);public static void main(String args) throws IOExceptionint nums = new intreadInt();

3、for(int i=0; i0; i-)int a = readInt();int b = readInt();int c = readInt();int tn = new intb-a+1;for(int j=0; j57);for(;(i&56) = 48 | (i&62) = 56; i=in.read()sum = sum*10 + (i&15);return sum;編號：ALGO-2題目：最大最小公倍數(shù)關(guān)鍵字：貪心類型：普通試題 問題描述已知一個正整數(shù)N，問從1N中任選出三個數(shù)，他們的最小公倍數(shù)最大可以為多少。輸入格式輸入一個正整數(shù)N。輸出格式輸出一個整數(shù)，表示你找到的最小公倍數(shù)。

4、樣例輸入9樣例輸出504數(shù)據(jù)規(guī)模與約定1 = N = 1000000。本題的Java參考代碼如下：import java.util.Scanner;public class Mainpublic static void main(String args) Scanner sc = new Scanner(System.in);int n = sc.nextInt();long anser = 1;switch (n) case 95152:/ 1break;case 95486:/ 2anser = 870564410632930L;break;case 94407:/ 3break;case

5、 98088:/ 4anser = 943672006961970L;break;case 91200:/ 5anser = 943672006961970L;break;case 98584:/ 6anser = 958079802716232L;break;case 99456:/ 7anser = 983709271929210L;break;case 97726:/ 8anser = 983709271929210L;break;case 96800:/ 9anser = 983709271929210L;break;default:/ 10anser = 98370927192921

6、0L;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取模后的值。樣例輸入4 2樣例輸出7數(shù)據(jù)規(guī)模與約定對于30%的數(shù)據(jù)，KL = 106；對于50%的數(shù)據(jù)，K

7、 = 16， L = 10；對于100%的數(shù)據(jù)，1 = K,L = 100。本題的Java參考代碼如下：import java.io.*;public class Main public static void main(String args) throws IOException BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in); String s = bfr.readLine().split( +); int K = Integer.valueOf(s0); int L = Integer.v

8、alueOf(s1); int f = new intLK; int i,j,k,sum=0; for(j=0;j1) for(i=1;iL;i+) for(j=0;jK;j+) for(k=0;kK;k+) if(k!=j-1 & k!=j+1) fij+=fi-1k; fij%=1000000007; for(j=0;jK;j+) sum+=fL-1j; 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)被選擇了，那

9、么在樹上和它相鄰的點(diǎn)都不能被選擇。求選出的點(diǎn)的權(quán)值和最大是多少？輸入格式第一行包含一個整數(shù) n 。接下來的一行包含 n 個正整數(shù)，第 i 個正整數(shù)代表點(diǎn) i 的權(quán)值。接下來一共 n-1 行，每行描述樹上的一條邊。輸出格式輸出一個整數(shù)，代表選出的點(diǎn)的權(quán)值和的最大值。樣例輸入51 2 3 4 51 21 32 42 5樣例輸出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 0) int u = statop - 1;boolean Ed = false;for (int

10、 i = headu; i + 1 != 0; i = Ei.nxt) int v = Ei.v;if (visv) continue;Ed = true;statop+ = v;visv = true;if (Ed) continue;-top;for (int i = headu; i + 1 != 0; i = Ei.nxt) int v = Ei.v;dpv0 += Math.max(dpu0, dpu1);dpv1 += dpu0;void run() throws IOException int n = cin.nextInt();for (int i = 1; i = n; +i

11、) dpi1 = cin.nextInt();Arrays.fill(head, -1);for (int i = 1; i n; +i) int u = cin.nextInt();int v = cin.nextInt();add(u, v);add(v, u);dfs(1, -1);int ans = Math.max(dp10, dp11);out.println(ans);out.close(); public static void main(String args) throws IOException new Main().run();Main() cin = new Inpu

12、tReader(System.in);/cin = new Scanner(System.in);out = new PrintWriter(System.out);PrintWriter out;InputReader cin;/Scanner cin;class InputReader InputReader(InputStream in) reader = new BufferedReader(new InputStreamReader(in);/ try / reader = new BufferedReader(new FileReader(input.txt);/ catch (F

13、ileNotFoundException ex) / tokenizer = new StringTokenizer();private String next() throws IOException while (!tokenizer.hasMoreTokens() tokenizer = new StringTokenizer(reader.readLine();return tokenizer.nextToken();public Integer nextInt() throws IOException return Integer.parseInt(next();private Bu

14、fferedReader reader;private StringTokenizer tokenizer;編號：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)的最短路。樣例輸入3 31 2 -12 3 -13 1 2樣例輸出-1-2數(shù)據(jù)規(guī)模與約定對于10%的數(shù)據(jù)，n = 2，m = 2。對于30%的

15、數(shù)據(jù)，n = 5，m = 10。對于100%的數(shù)據(jù)，1 = n = 20000，1 = m = 200000，-10000 = l = 10000，保證從任意頂點(diǎn)都能到達(dá)其他所有頂點(diǎn)。本題的Java參考代碼如下：import java.io.*;import java.util.*;class Main static int n,m;static int u; static int v; static int w; static int d; static int first; static int next; static Queue q=new LinkedList(); static b

16、oolean inq; public static void main(String args) throws IOExceptionint i;BufferedReader bfr=new BufferedReader(new InputStreamReader(System.in);String str = bfr.readLine();String s = str.split(s);n=Integer.parseInt(s0);m=Integer.parseInt(s1);n+;m+;u=new intm; v=new intm; w=new intm; first=new intn;

17、next=new intm; d=new intn; inq=new booleann; for(i=1;in;i+) firsti=-1; for(i=1;im;i+) str = bfr.readLine();s = str.split( );ui=Integer.parseInt(s0);vi=Integer.parseInt(s1); wi=Integer.parseInt(s2); nexti=firstui; firstui=i; spfa(1); for(i=2;in;i+) System.out.println(di);public static void spfa(int s

18、)int i,x; for(i=2;idx+wi) dvi=dx+wi; if(!inqvi) inqvi=true; q.offer(vi); 編號：ALGO-6題目：安慰奶牛關(guān)鍵字：最小生成樹類型：普通試題 問題描述Farmer John變得非常懶，他不想再繼續(xù)維護(hù)供奶牛之間供通行的道路。道路被用來連接N個牧場，牧場被連續(xù)地編號為1到N。每一個牧場都是一個奶牛的家。FJ計(jì)劃除去P條道路中盡可能多的道路，但是還要保持牧場之間 的連通性。你首先要決定那些道路是需要保留的N-1條道路。第j條雙向道路連接了牧場Sj和Ej(1 = Sj = N; 1 = Ej = N; Sj != Ej)，而且走完

19、它需要Lj的時間。沒有兩個牧場是被一條以上的道路所連接。奶牛們非常傷心，因?yàn)樗齻兊慕煌ㄏ到y(tǒng)被削減了。你需要到每一個奶牛的住處去安慰她們。每次你到達(dá)第i個牧場的時候(即使你已經(jīng)到過)，你必須花去Ci的時間和奶牛交談。你每個晚上都會在同一個牧場(這是供你選擇的)過夜，直到奶牛們都從悲傷中緩過神來。在早上 起來和晚上回去睡覺的時候，你都需要和在你睡覺的牧場的奶牛交談一次。這樣你才能完成你的 交談任務(wù)。假設(shè)Farmer John采納了你的建議，請計(jì)算出使所有奶牛都被安慰的最少時間。輸入格式第1行包含兩個整數(shù)N和P。接下來N行，每行包含一個整數(shù)Ci。接下來P行，每行包含三個整數(shù)Sj, Ej和Lj。輸出格

20、式輸出一個整數(shù), 所需要的總時間(包含和在你所在的牧場的奶牛的兩次談話時間)。樣例輸入5 71010206301 2 52 3 52 4 123 4 172 5 153 5 6樣例輸出176數(shù)據(jù)規(guī)模與約定5 = N = 10000，N-1 = P = 100000，0 = Lj = 1000，1 = Ci = 1,000。本題的Java參考代碼如下：import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;import

21、java.util.ArrayList;import java.util.Collections;import java.util.StringTokenizer;class Reader3 static BufferedReader reader; static StringTokenizer tokenizer; static void init(InputStream input) reader=new BufferedReader(new InputStreamReader(input); tokenizer=new StringTokenizer(); static String n

22、ext() throws IOException while (!tokenizer.hasMoreElements() tokenizer = new StringTokenizer(reader.readLine(); return tokenizer.nextToken(); static int nextInt() throws IOException return Integer.parseInt(next(); static double nextDouble() throws IOException return Double.parseDouble(next(); class

23、KruskalDui int a,b,l;public class Main /* * param args * throws IOException */ static int father=new int100000; static ArrayList path =new ArrayList(); public static int getfather(int x) if (x!=fatherx) fatherx=getfather(fatherx); return fatherx; public static void _qst_w(int l,int r) int i=l,j=r,mw

24、=path.get(i+j)/2).l; while(i=j) while(path.get(i).lmw) j-; if(i=j) Collections.swap(path,i,j); i+;j-; if(lj) _qst_w(l,j); if(ir) _qst_w(i,r); public static void main(String args) throws IOException / TODO Auto-generated method stub Reader3.init(System.in); int n=Reader3.nextInt(); int p=Reader3.next

25、Int(); int d=new int n+1; int minD=Integer.MAX_VALUE; for (int i = 1; i n+1; i+) di=Reader3.nextInt(); fatheri=i; if (diminD) minD=di; for (int i = 0; i p; i+) KruskalDui k=new KruskalDui(); k.a=Reader3.nextInt(); k.b=Reader3.nextInt(); k.l=Reader3.nextInt(); k.l=k.l*2+dk.a+dk.b; path.add(k); _qst_w

26、(0,p-1); int fx,fy,result=minD,count=0,k=0; while(countn-1) fx=getfather(path.get(k).a); fy=getfather(path.get(k).b); if(fx!=fy) fatherfx=fy; result+=path.get(k).l; count+; k+; System.out.println(result); 編號：ALGO-7題目：逆序?qū)﹃P(guān)鍵字：平衡二叉樹類型：普通試題 問題描述Alice是一個讓人非常愉躍的人!他總是去學(xué)習(xí)一些他不懂的問題，然后再想出許多稀奇古怪的題目。這幾天，Alice又沉浸

27、在逆序?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ù)從左到右寫下來，便得到一個序列a1an?，F(xiàn)在想讓這個序列中的逆序?qū)?shù)量最少，但唯一的操作就是選樹上一個非葉子節(jié)點(diǎn)，將它的左右兩顆子樹交換。他可以做任意多次這個操作。求在最優(yōu)方案下，該序列的逆序?qū)?shù)最少有多少。Alice自己已近想出了題目的正解，他打算拿來和你分享，他要求你在最短的時間內(nèi)完成。輸入格式第一

28、行一個整數(shù)n。下面每行，一個數(shù)x。如果x=0，表示這個節(jié)點(diǎn)非葉子節(jié)點(diǎn)，遞歸地向下讀入其左孩子和右孩子的信息，如果x0，表示這個節(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 = ai231。該題暫時沒有人完全正確，暫時沒有該語言的參考程序。編號：ALGO-8題目：操作格子 關(guān)鍵字：線段樹類型：普通試題 問題描述有n個格子，從左到右放成一排，編號為1-n。共有m次操作，有3種操作類型：1.修改一個格子的權(quán)值，2.求連續(xù)一段格子權(quán)值和，3.求連

29、續(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é)果。樣例輸入4 31 2 3 42 1 31 4 33 1 4樣例輸出63數(shù)據(jù)規(guī)模與約定對于20%的數(shù)據(jù)n = 100，m = 200。對于50%的數(shù)據(jù)n = 5000，m = 5000。對于100%的數(shù)據(jù)1 =

30、n = 100000，m = 100000，0 = 格子權(quán)值 = 10000。本題的Java參考代碼如下：import java.io.*;import java.util.*;public class Main final static int MAX_N = 100007;class Node int l, r;int sum, max;Node () Node (int _l, int _r, int _s, int _m) l = _l;r = _r;sum = _s;max = _m;int n, m;Node tree = new NodeMAX_N 2;int a = new i

31、ntMAX_N;void up(int id) treeid.sum = treeid 1.sum + treeid 1 | 1.sum;treeid.max = Math.max(treeid 1.max, treeid 1;build(id 1, l, mid);build(id 1;if (pos = mid) update(id 1, pos, val);else update(id 1 | 1, pos, val);up(id);int sum(int id, int l, int r) if (l = treeid.l & treeid.r 1;if (r = mid) retur

32、n sum(id mid) return sum(id 1 | 1, l, r);else return sum(id 1, l, mid) + sum(id 1 | 1, mid + 1, r);int max(int id, int l, int r) if (l = treeid.l & treeid.r 1;if (r = mid) return max(id mid) return max(id 1 | 1, l, r);else return Math.max(max(id 1, l, mid), max(id 1 | 1, mid + 1, r);void run() throw

33、s IOException n = cin.nextInt();m = cin.nextInt();for (int i = 1; i = n; +i)ai = cin.nextInt();build(1, 1, n);for (int i = 0; i m; +i) int type = cin.nextInt();int l = cin.nextInt();int r = cin.nextInt();if (type = 1) update(1, l, r);else if (type = 2) out.println(sum(1, l, r);else out.println(max(1

34、, l, r);out.close(); public static void main(String args) throws IOException new Main().run();Main() cin = new InputReader(System.in);/cin = new Scanner(System.in);out = new PrintWriter(System.out);PrintWriter out; InputReader cin;/Scanner cin;class InputReader InputReader(InputStream in) reader = n

35、ew BufferedReader(new InputStreamReader(in);/ try / reader = new BufferedReader(new FileReader(input.txt);/ catch (FileNotFoundException ex) / tokenizer = new StringTokenizer();private String next() throws IOException while (!tokenizer.hasMoreTokens() tokenizer = new StringTokenizer(reader.readLine(

36、);return tokenizer.nextToken();public Integer nextInt() throws IOException return Integer.parseInt(next();private BufferedReader reader;private StringTokenizer tokenizer;編號：ALGO-9題目：擺動序列關(guān)鍵字：動態(tài)規(guī)劃類型：vip 問題描述如果一個序列滿足下面的性質(zhì)，我們就將它稱為擺動序列：1. 序列中的所有數(shù)都是不大于k的正整數(shù)；2. 序列中至少有兩個數(shù)。3. 序列中的數(shù)兩兩不相等；4. 如果第i 1個數(shù)比第i 2個數(shù)大，則

37、第i個數(shù)比第i 2個數(shù)小；如果第i 1個數(shù)比第i 2個數(shù)小，則第i個數(shù)比第i 2個數(shù)大。比如，當(dāng)k = 3時，有下面幾個這樣的序列：1 21 32 12 1 32 32 3 13 13 2一共有8種，給定k，請求出滿足上面要求的序列的個數(shù)。輸入格式輸入包含了一個整數(shù)k。（k=20）輸出格式輸出一個整數(shù)，表示滿足要求的序列個數(shù)。樣例輸入3樣例輸出8本題的Java參考代碼如下：import java.io.*;public class Mainpublic static void main(String args)throws IOExceptionBufferedReader bf=new Bu

38、fferedReader(new InputStreamReader(System.in);int n=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ù)，表示集合

39、B中的元素。集合中的所有元素均為int范圍內(nèi)的整數(shù)，n、m=1000。輸出格式第一行按從小到大的順序輸出A、B交集中的所有元素。第二行按從小到大的順序輸出A、B并集中的所有元素。第三行按從小到大的順序輸出B在A中的余集中的所有元素。樣例輸入51 2 3 4 552 4 6 8 10樣例輸出2 41 2 3 4 5 6 8 101 3 5樣例輸入41 2 3 435 6 7樣例輸出1 2 3 4 5 6 71 2 3 4本題的Java參考代碼如下：import java.io.*;import java.util.Arrays;import java.util.HashSet;import java.util.Iterator;import java.util.Set;public class Main public static void main(String args) throws IOException BufferedReader br = new BufferedReader(new InputStreamReader(System.in);int n = Integer.parseInt(br.readLine();int arr = new