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

算法训练 编号：ALGO-1 题目：区间k大数查问列 重点字：排序查找 种类：普通试题 问题描绘 给定一个序列，每次询问序列中第l个数到第r个数中第K大的数是哪个。 输入格式 第一行包含一个数n，表示序列长度。 第二行包含n个正整数，表示给定的序列。 第三个包含一个正整数m，表示询问个数。 接下来m行，每行三个数l,r,K，表示询问序列从左往右第l个数到第r个数中，从大往小 第K大的数是哪个。序列元素从1开始标号。 输出格式 总合输出m行，每行一个数，表示询问的答案。 样例输入 5 12345 2 152 232 样例输出 4 2 数据规模与约定 对于30%的数据，n,m<=100； 对于100%的数据，n,m<=1000； 保证k<=(r-l+1)，序列中的数<=1000000。 此题的Java参照代码如下： importclassMain { privatestaticBufferedInputStreamin=newBufferedInputStream; publicstaticvoidmain(String[]args)throwsIOException { int[]nums=newint[readInt( )]; for(inti=0;i<;i++) { nums[i]=readInt( ); } for(inti=readInt( );i>0;i--) { inta=readInt( ); intb=readInt( ); intc=readInt( ); int[]tn=newint[b-a+1]; for(intj=0;j<;j++) { tn[j]=nums[a-1+j]; } (tn); } } privatestaticintreadInt( )throwsIOException { inti,sum=0; while(((i=( ))&48)!=48||i>57); for(;(i&56)==48||(i&62)==56;i=( )) sum=sum*10+(i&15); returnsum; } } 编号：ALGO-2 题目：最大最小公倍数 重点字：贪心 种类：普通试题 问题描绘 已知一个正整数N，问从1~N中任选出三个数，他们的最小公倍数最大能够为多少。 输入格式 输入一个正整数N。 输出格式 输出一个整数，表示你找到的最小公倍数。 样例输入 9 样例输出 504 数据规模与约定 1<=N<=1000000。 此题的Java参照代码如下： importclassMain{ publicstaticvoidmain(String[]args){ Scannersc=newScanner; intn=( ); longanser=1; switch(n){ case95152:; publicclassMain{ publicstaticvoidmain(String[]args)throwsIOException{ BufferedReaderbfr=newBufferedReader(newInputStreamReader); Strings[]=( ).split("+"); intK=(s[0]); intL=(s[1]); intf[][]=newint[L][K]; inti,j,k,sum=0; for(j=0;j<K;j++)f[0][j]=1; f[0][0]=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) { f[i][j]+=f[i-1][k]; f[i][j]%=07; } } } } for(j=0;j<K;j++){sum+=f[L-1][j];sum%=07;} } } 编号：ALGO-4 题目：节点选择 重点字：树形动向规划 种类：普通试题 问题描绘 有一棵n个节点的树，树上每个节点都有一个正整数权值。如果一个点被选择了，那么在树上和它相邻的点都不能被选择。求选出的点的权值和最大是多少？ 输入格式 第一行包含一个整数n。 接下来的一行包含n个正整数，第i个正整数代表点i的权值。 接下来一共n-1行，每行描绘树上的一条边。 输出格式 输出一个整数，代表选出的点的权值和的最大值。 样例输入 5 12345 2 3 4 5 样例输出 12 样例说明 选择3、4、5号点，权值和为3+4+5=12。 数据规模与约定 对于20%的数据，n<=20。 对于50%的数据，n<=1000。 对于100%的数据，n<=100000。 权值均为不超过1000的正整数。 此题的Java参照代码如下： import.*; import.*; publicclassM