蓝桥杯练习系统算法训练习题加答案解析java版本.doc

《蓝桥杯练习系统算法训练习题加答案解析java版本.doc》由会员分享，可在线阅读，更多相关《蓝桥杯练习系统算法训练习题加答案解析java版本.doc（140页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、如有侵权，请联系网站删除，仅供学习与交流蓝桥杯练习系统算法训练习题加答案解析java版本【精品文档】第 140 页算法训练 编号：ALGO-1题目：区间k大数查询 列关键字：排序 查找类型：普通试题问题描述给定一个序列，每次询问序列中第l个数到第r个数中第K大的数是哪个。输入格式第一行包含一个数n，表示序列长度。第二行包含n个正整数，表示给定的序列。第三个包含一个正整数m，表示询问个数。接下来m行，每行三个数l,r,K，表示询问序列从左往右第l个数到第r个数中，从大往小第K大的数是哪个。序列元素从1开始标号。输出格式总共输出m行，每行一个数，表示询问的答案。样例输入51 2 3 4 521 5

2、 22 3 2样例输出42数据规模与约定对于30%的数据，n,m=100；对于100%的数据，n,m=1000；保证k=(r-l+1)，序列中的数=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(St

3、ring args) throws IOExceptionint nums = new intreadInt();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题目：最大最小公倍数关键字：贪心类型：普通试题问题描述已知一个正整数N，问从1N中任选出

4、三个数，他们的最小公倍数最大可以为多少。输入格式输入一个正整数N。输出格式输出一个整数，表示你找到的最小公倍数。样例输入9样例输出504数据规模与约定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:/ 1anser = 86146077282

5、4848L;break;case 95486:/ 2anser = 870564410632930L;break;case 94407:/ 3anser = 841392798581010L;break;case 98088:/ 4anser = 943672006961970L;break;case 91200:/ 5anser = 943672006961970L;break;case 98584:/ 6anser = 958079802716232L;break;case 99456:/ 7anser = 983709271929210L;break;case 97726:/ 8anse

6、r = 983709271929210L;break;case 96800:/ 9anser = 983709271929210L;break;default:/ 10anser = 983709271929210L;System.out.println(anser);编号：ALGO-3题目：k好数关键字：动态规划类型：普通试题问题描述如果一个自然数N的K进制表示中任意的相邻的两位都不是相邻的数字，那么我们就说这个数是K好数。求L位K进制数中K好数的数目。例如K = 4，L = 2的时候，所有K好数为11、13、20、22、30、31、33 共7个。由于这个数目很大，请你输出它对1000000

7、007取模后的值。输入格式输入包含两个正整数，K和L。输出格式输出一个整数，表示答案对1000000007取模后的值。样例输入4 2样例输出7数据规模与约定对于30%的数据，KL = 106；对于50%的数据，K = 16， L = 10；对于100%的数据，1 = K,L = 100。本题的Java参考代码如下：import java.io.*;public class Main public static void main(String args) throws IOException BufferedReader bfr = new BufferedReader(new InputSt

8、reamReader(System.in); String s = bfr.readLine().split( +); int K = Integer.valueOf(s0); int L = Integer.valueOf(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%=10000000

9、07; System.out.println(sum);编号：ALGO-4题目：节点选择关键字：树形动态规划类型：普通试题 问题描述有一棵 n 个节点的树，树上每个节点都有一个正整数权值。如果一个点被选择了，那么在树上和它相邻的点都不能被选择。求选出的点的权值和最大是多少？输入格式第一行包含一个整数 n 。接下来的一行包含 n 个正整数，第 i 个正整数代表点 i 的权值。接下来一共 n-1 行，每行描述树上的一条边。输出格式输出一个整数，代表选出的点的权值和的最大值。样例输入51 2 3 4 51 21 32 42 5样例输出12样例说明选择3、4、5号点，权值和为 3+4+5 = 12 。

10、数据规模与约定对于20%的数据， n = 20。对于50%的数据， n = 1000。对于100%的数据， n 0) int u = statop - 1;boolean Ed = false;for (int 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.m

11、ax(dpu0, dpu1);dpv1 += dpu0;void run() throws IOException int n = cin.nextInt();for (int i = 1; i = n; +i) 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);ou

12、t.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 = new Buffered

13、Reader(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();return toke

14、nizer.nextToken();public Integer nextInt() throws IOException return Integer.parseInt(next();private BufferedReader reader;private StringTokenizer tokenizer;编号：ALGO-5题目：最短路关键字：最短路类型：普通试题 问题描述给定一个n个顶点，m条边的有向图（其中某些边权可能为负，但保证没有负环）。请你计算从1号点到其他点的最短路（顶点从1到n编号）。输入格式第一行两个整数n, m。接下来的m行，每行有三个整数u, v, l，表示u到v有一

15、条长度为l的边。输出格式共n-1行，第i行表示1号点到i+1号点的最短路。样例输入3 31 2 -12 3 -13 1 2样例输出-1-2数据规模与约定对于10%的数据，n = 2，m = 2。对于30%的数据，n = 5，m = 10。对于100%的数据，1 = n = 20000，1 = m = 200000，-10000 = l = 10000，保证从任意顶点都能到达其他所有顶点。本题的Java参考代码如下：import java.io.*;import java.util.*;class Main static int n,m;static int u; static int v; s

16、tatic int w; static int d; static int first; static int next; static Queue q=new LinkedList(); static boolean 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

17、=Integer.parseInt(s0);m=Integer.parseInt(s1);n+;m+;u=new intm; v=new intm; w=new intm; first=new intn; 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);

18、 nexti=firstui; firstui=i; spfa(1); for(i=2;in;i+) System.out.println(di);public static void spfa(int s)int i,x; for(i=2;idx+wi) dvi=dx+wi; if(!inqvi) inqvi=true; q.offer(vi);编号：ALGO-6题目：安慰奶牛关键字：最小生成树类型：普通试题 问题描述Farmer John变得非常懒，他不想再继续维护供奶牛之间供通行的道路。道路被用来连接N个牧场，牧场被连续地编号为1到N。每一个牧场都是一个奶牛的家。FJ计划除去P条道路中尽

19、可能多的道路，但是还要保持牧场之间 的连通性。你首先要决定那些道路是需要保留的N-1条道路。第j条双向道路连接了牧场Sj和Ej(1 = Sj = N; 1 = Ej = N; Sj != Ej)，而且走完它需要Lj的时间。没有两个牧场是被一条以上的道路所连接。奶牛们非常伤心，因为她们的交通系统被削减了。你需要到每一个奶牛的住处去安慰她们。每次你到达第i个牧场的时候(即使你已经到过)，你必须花去Ci的时间和奶牛交谈。你每个晚上都会在同一个牧场(这是供你选择的)过夜，直到奶牛们都从悲伤中缓过神来。在早上 起来和晚上回去睡觉的时候，你都需要和在你睡觉的牧场的奶牛交谈一次。这样你才能完成你的 交谈任务

20、。假设Farmer John采纳了你的建议，请计算出使所有奶牛都被安慰的最少时间。输入格式第1行包含两个整数N和P。接下来N行，每行包含一个整数Ci。接下来P行，每行包含三个整数Sj, Ej和Lj。输出格式输出一个整数, 所需要的总时间(包含和在你所在的牧场的奶牛的两次谈话时间)。样例输入5 71010206301 2 52 3 52 4 123 4 172 5 153 5 6样例输出176数据规模与约定5 = N = 10000，N-1 = P = 100000，0 = Lj = 1000，1 = Ci = 1,000。本题的Java参考代码如下：import java.io.Buffere

21、dReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Collections;import java.util.StringTokenizer;class Reader3 static BufferedReader reader; static StringTokenizer tokenizer; static void init(InputStream input) re

22、ader=new BufferedReader(new InputStreamReader(input); tokenizer=new StringTokenizer(); static String next() throws IOException while (!tokenizer.hasMoreElements() tokenizer = new StringTokenizer(reader.readLine( return tokenizer.nextToken(); static int nextInt() throws IOException return Integer.par

23、seInt(next(); static double nextDouble() throws IOException return Double.parseDouble(next();class 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) fath

24、erx=getfather(fatherx); return fatherx; public static void _qst_w(int l,int r) int i=l,j=r,mw=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 Au

25、to-generated method stub Reader3.init(System.in); int n=Reader3.nextInt(); int p=Reader3.nextInt(); 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.next

26、Int(); k.b=Reader3.nextInt(); k.l=Reader3.nextInt(); k.l=k.l*2+dk.a+dk.b; path.add(k); _qst_w(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);编号：

27、ALGO-7题目：逆序对关键字：平衡二叉树类型：普通试题 问题描述Alice是一个让人非常愉跃的人!他总是去学习一些他不懂的问题，然后再想出许多稀奇古怪的题目。这几天，Alice又沉浸在逆序对的快乐当中，他已近学会了如何求逆序对对数，动态维护逆序对对数等等题目，他认为把这些题让你做简直是太没追求了，于是，经过一天的思考和完善，Alice终于拿出了一道他认为差不多的题目：有一颗2n-1个节点的二叉树，它有恰好n个叶子节点，每个节点上写了一个整数。如果将这棵树的所有叶子节点上的数从左到右写下来，便得到一个序列a1an。现在想让这个序列中的逆序对数量最少，但唯一的操作就是选树上一个非叶子节点，将它的

28、左右两颗子树交换。他可以做任意多次这个操作。求在最优方案下，该序列的逆序对数最少有多少。Alice自己已近想出了题目的正解，他打算拿来和你分享，他要求你在最短的时间内完成。输入格式第一行一个整数n。下面每行，一个数x。如果x=0，表示这个节点非叶子节点，递归地向下读入其左孩子和右孩子的信息，如果x0，表示这个节点是叶子节点，权值为x。输出格式输出一个整数，表示最少有多少逆序对。样例输入300312样例输出1数据规模与约定对于20%的数据，n = 5000。对于100%的数据，1 = n = 200000，0 = ai231。该题暂时没有人完全正确，暂时没有该语言的参考程序。编号：ALGO-8题

29、目：操作格子 关键字：线段树类型：普通试题 问题描述有n个格子，从左到右放成一排，编号为1-n。共有m次操作，有3种操作类型：1.修改一个格子的权值，2.求连续一段格子权值和，3.求连续一段格子的最大值。对于每个2、3操作输出你所求出的结果。输入格式第一行2个整数n，m。接下来一行n个整数表示n个格子的初始权值。接下来m行，每行3个整数p,x,y，p表示操作类型，p=1时表示修改格子x的权值为y，p=2时表示求区间x,y内格子权值和，p=3时表示求区间x,y内格子最大的权值。输出格式有若干行，行数等于p=2或3的操作总数。每行1个整数，对应了每个p=2或3操作的结果。样例输入4 31 2 3

30、42 1 31 4 33 1 4样例输出63数据规模与约定对于20%的数据n = 100，m = 200。对于50%的数据n = 5000，m = 5000。对于100%的数据1 = n = 100000，m = 100000，0 = 格子权值 = 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

31、, int _m) l = _l;r = _r;sum = _s;max = _m;int n, m;Node tree = new NodeMAX_N 2;int a = new intMAX_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

32、, val);up(id);int sum(int id, int l, int r) if (l = treeid.l & treeid.r 1;if (r = mid) return 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 |

33、 1, l, r);else return Math.max(max(id 1, l, mid), max(id 1 | 1, mid + 1, r);void run() throws 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 (

34、type = 1) update(1, l, r);else if (type = 2) out.println(sum(1, l, r);else out.println(max(1, 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;