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

如有侵权，请联系网站删除，仅供学习与交流蓝桥杯练习系统算法训练习题加答案解析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 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(String args) throws IOExceptionint nums = new intreadInt();for(int i=0; i<nums.length; i+)numsi = readInt();for(int i=readInt(); i>0; i-)int a = readInt();int b = readInt();int c = readInt();int tn = new intb-a+1;for(int j=0; j<tn.length; j+)tnj = numsa-1+j;Arrays.sort(tn);System.out.println(tntn.length-c);private static int readInt() throws IOExceptionint i,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);return sum;编号：ALGO-2题目：最大最小公倍数关键字：贪心类型：普通试题问题描述已知一个正整数N，问从1N中任选出三个数，他们的最小公倍数最大可以为多少。输入格式输入一个正整数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 = 861460772824848L;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:/ 8anser = 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个。由于这个数目很大，请你输出它对1000000007取模后的值。输入格式输入包含两个正整数，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 InputStreamReader(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;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%=1000000007; for(j=0;j<K;j+) sum+=fL-1j; sum%=1000000007; 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 。数据规模与约定对于20%的数据， n <= 20。对于50%的数据， n <= 1000。对于100%的数据， n <= 100000。权值均为不超过1000的正整数。本题的Java参考代码如下：import java.io.*;import java.util.*;public class Main final static int MAX_N = 100010;/final static int MAX_M = 200007;final static long INF = (long)1e16;class Edge int u, v, nxt;Edge () Edge (int _u, int _v, int _n) u = _u;v = _v;nxt = _n;int edgecnt;int dp = new intMAX_N2;Edge E = new EdgeMAX_N * 2;int head = new intMAX_N;int sta = new intMAX_N * 2;boolean vis = new booleanMAX_N;void add(int u, int v) Eedgecnt = new Edge(u, v, headu);headu = edgecnt+;void dfs(int x, int fa) Arrays.fill(vis, false);int top = 0;visx = true;statop+ = x;while (top > 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.max(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);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 = new 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();return tokenizer.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有一条长度为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; static int w; static int d; static int first; static int next; static Queue<Integer> q=new LinkedList<Integer>(); 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=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;i<n;i+) firsti=-1; for(i=1;i<m;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;i<n;i+) System.out.println(di);public static void spfa(int s)int i,x; for(i=2;i<n;i+) di=Integer.MAX_VALUE; q.offer(s); while(!q.isEmpty() x=q.poll(); inqx=false; for(i=firstx;i!=-1;i=nexti) if(dvi>dx+wi) dvi=dx+wi; if(!inqvi) inqvi=true; q.offer(vi);编号：ALGO-6题目：安慰奶牛关键字：最小生成树类型：普通试题 问题描述Farmer John变得非常懒，他不想再继续维护供奶牛之间供通行的道路。道路被用来连接N个牧场，牧场被连续地编号为1到N。每一个牧场都是一个奶牛的家。FJ计划除去P条道路中尽可能多的道路，但是还要保持牧场之间 的连通性。你首先要决定那些道路是需要保留的N-1条道路。第j条双向道路连接了牧场Sj和Ej(1 <= Sj <= N; 1 <= Ej <= N; Sj != Ej)，而且走完它需要Lj的时间。没有两个牧场是被一条以上的道路所连接。奶牛们非常伤心，因为她们的交通系统被削减了。你需要到每一个奶牛的住处去安慰她们。每次你到达第i个牧场的时候(即使你已经到过)，你必须花去Ci的时间和奶牛交谈。你每个晚上都会在同一个牧场(这是供你选择的)过夜，直到奶牛们都从悲伤中缓过神来。在早上 起来和晚上回去睡觉的时候，你都需要和在你睡觉的牧场的奶牛交谈一次。这样你才能完成你的 交谈任务。假设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.BufferedReader;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) reader=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.parseInt(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<KruskalDui> path =new ArrayList<KruskalDui>(); 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=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); public static void main(String args) throws IOException / TODO Auto-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 (di<minD) 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(0,p-1); int fx,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) fatherfx=fy; result+=path.get(k).l; count+; k+; System.out.println(result);编号：ALGO-7题目：逆序对关键字：平衡二叉树类型：普通试题 问题描述Alice是一个让人非常愉跃的人!他总是去学习一些他不懂的问题，然后再想出许多稀奇古怪的题目。这几天，Alice又沉浸在逆序对的快乐当中，他已近学会了如何求逆序对对数，动态维护逆序对对数等等题目，他认为把这些题让你做简直是太没追求了，于是，经过一天的思考和完善，Alice终于拿出了一道他认为差不多的题目：有一颗2n-1个节点的二叉树，它有恰好n个叶子节点，每个节点上写了一个整数。如果将这棵树的所有叶子节点上的数从左到右写下来，便得到一个序列a1an。现在想让这个序列中的逆序对数量最少，但唯一的操作就是选树上一个非叶子节点，将它的左右两颗子树交换。他可以做任意多次这个操作。求在最优方案下，该序列的逆序对数最少有多少。Alice自己已近想出了题目的正解，他打算拿来和你分享，他要求你在最短的时间内完成。输入格式第一行一个整数n。下面每行，一个数x。如果x=0，表示这个节点非叶子节点，递归地向下读入其左孩子和右孩子的信息，如果x0，表示这个节点是叶子节点，权值为x。输出格式输出一个整数，表示最少有多少逆序对。样例输入300312样例输出1数据规模与约定对于20%的数据，n <= 5000。对于100%的数据，1 <= n <= 200000，0 <= ai<231。该题暂时没有人完全正确，暂时没有该语言的参考程序。编号：ALGO-8题目：操作格子 关键字：线段树类型：普通试题 问题描述有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 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, 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| 1.max);void build(int id, int l, int r) treeid = new Node(l, r, 0, 0);if (l = r) treeid.sum = treeid.max = al;return ;int mid = (l + r) >> 1;build(id << 1, l, mid);build(id << 1 | 1, mid + 1, r);up(id);void update(int id, int pos, int val) if (treeid.l = treeid.r) treeid.sum = treeid.max = val;return ;int mid = (treeid.l + treeid.r) >> 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 <= r) return treeid.sum;int mid = (treeid.l + treeid.r) >> 1;if (r <= mid) return sum(id << 1, l, r);else if (l > 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 <= r) return treeid.max;int mid = (treeid.l + treeid.r) >> 1;if (r <= mid) return max(id << 1, l, r);else if (l > 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() 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 (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;