蓝桥杯算法训练习题与官方答案.doc

算法训练 编号：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; 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中任选出三个数，他们的最小公倍数最大可以为多少。输入格式输入一个正整数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;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题目：节点选择关键字：树形动态规划类型：普通试题 问题描述有一棵 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 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 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=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); 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条道路中尽可能多的道路，但是还要保持牧场之间 的连通性。你首先要决定那些道路是需要保留的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 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=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.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.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(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题目：逆序对关键字：平衡二叉树类型：普通试题 问题描述Alice是一个让人非常愉跃的人!他总是去学习一些他不懂的问题，然后再想出许多稀奇古怪的题目。这几天，Alice又沉浸在逆序对的快乐当中，他已近学会了如何求逆序对对数，动态维护逆序对对数等等题目，他认为把这些题让你做简直是太没追求了，于是，经过一天的思考和完善，Alice终于拿出了一道他认为差不多的题目：有一颗2n-1个节点的二叉树，它有恰好n个叶子节点，每个节点上写了一个整数。如果将这棵树的所有叶子节点上的数从左到右写下来，便得到一个序列a1an。现在想让这个序列中的逆序对数量最少，但唯一的操作就是选树上一个非叶子节点，将它的左右两颗子树交换。他可以做任意多次这个操作。求在最优方案下，该序列的逆序对数最少有多少。Alice自己已近想出了题目的正解，他打算拿来和你分享，他要求你在最短的时间内完成。输入格式第一行一个整数n。下面每行，一个数x。如果x=0，表示这个节点非叶子节点，递归地向下读入其左孩子和右孩子的信息，如果x0，表示这个节点是叶子节点，权值为x。输出格式输出一个整数，表示最少有多少逆序对。样例输入300312样例输出1数据规模与约定对于20%的数据，n = 5000。对于100%的数据，1 = n = 200000，0 = ai231。该题暂时没有人完全正确，暂时没有该语言的参考程序。编号：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;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) 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 | 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; 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-9题目：摆动序列关键字：动态规划类型：vip 问题描述如果一个序列满足下面的性质，我们就将它称为摆动序列：1. 序列中的所有数都是不大于k的正整数；2. 序列中至少有两个数。3. 序列中的数两两不相等；4. 如果第i 1个数比第i 2个数大，则第i个数比第i 2个数小；如果第i 1个数比第i 2个数小，则第i个数比第i 2个数大。比如，当k = 3时，有下面几个这样的序列：1 21 32 12 1 32 32 3 13 13 2一共有8种，给定k，请求出满足上面要求的序列的个数。输入格式输入包含了一个整数k。（k=20）输出格式输出一个整数，表示满足要求的序列个数。样例输入3样例输出8本题的Java参考代码如下：import java.io.*;public class Mainpublic static void main(String args)throws IOExceptionBufferedReader bf=new BufferedReader(new InputStreamReader(System.in);int n=Integer.parseInt(bf.readLine();System.out.println(int)(Math.pow(2,n)-n-1)*2);编号：ALGO-10题目：集合运算关键字：数组 排序类型：vip 问题描述给出两个整数集合A、B，求出他们的交集、并集以及B在A中的余集。输入格式第一行为一个整数n，表示集合A中的元素个数。第二行有n个互不相同的用空格隔开的整数，表示集合A中的元素。第三行为一个整数m，表示集合B中的元素个数。第四行有m个互不相同的用空格隔开的整数，表示集合B中的元素。集合中的所有元素均为int范围内的整数，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 intn;String st = br.readLine().split( );for (int a = 0; a arr.length; a+) arra = Integer.parseInt(sta);Arrays.sort(arr);int m = Integer.parseInt(br.readLine();int tag = new intm;String str = br.readLine().split( );for (int a = 0; a tag.length; a+) taga = Integer.parseInt(stra);Arrays.sort(tag);func(arr, tag);public static void func(int arr, int tag) int x;for (int a = 0; a = 0) System.out.print(arra + );System.out.println();Set set = new HashSet();for (int a = 0; a arr.length; a+) set.add(arra);for (int a = 0; a tag.length; a+) set.add(taga);int sor = new intset.size();Iterator it = set.iterator();while (it.hasNext() for (int a = 0; a sor.length; a+) sora = it.next();Arrays.sort(sor);for (int a = 0; a sor.length; a+) System.out.print(sora + );System.out.println();int y;for (int a = 0; a arr.length; a+) y = Arrays.binarySearch(tag, arra);if (y 0) System.out.print(arra + );System.out.println();编号：ALGO-11题目：瓷砖铺放关键字：递归类型：vip试题问题描述：有一长度为N(1=10)的地板，给定两种不同瓷砖：一种长度为1，另一种长度为2，数目不限。要将这个长度为N的地板铺满，一共有多少种不同的铺法？例如，长度为4的地面一共有如下5种铺法：4=1+1+1+14=2+1+14=1+2+14=1+1+24=2+2编程用递归的方法求解上述问题。输入格式只有一个数N，代表地板的长度输出格式输出一个数，代表所有不同的瓷砖铺放方法的总数样例输入4样例输出5参考代码：import java.util.Scanner;public class Main public static void main(String args)Scanner input = new Scanner(System.in);int n = input.nextInt();if(1=n & n=10)