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

算法训练

编号：ALGO-1

题目：区间k大数查询 列 关键字：排序 查找 类型：普通试题 问题描述

给定一个序列，每次询问序列中第l个数到第r个数中第K大的数是哪个。

输入格式

第一行包含一个数n，表示序列长度。

第二行包含n个正整数，表示给定的序列。

第三个包含一个正整数m，表示询问个数。

接下来m行，每行三个数l,r,K，表示询问序列从左往右第l个数到第r个数中，从大往小第K大的数是哪个。序列元素从1开始标号。

输出格式

总共输出m行，每行一个数，表示询问的答案。 样例输入 5

1 2 3 4 5 2 1 5 2 2 3 2

样例输出 4 2

数据规模与约定

对于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 Main { private static BufferedInputStream in = new BufferedInputStream(System.in); public static void main(String[] args) throws IOException { int[] nums = new int[readInt()]; for(int i=0; i0; i--) { int a = readInt(); int b = readInt(); int c = readInt(); int[] tn = new int[b-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，问从1~N中任选出三个数，他们的最小公倍数最大可以为多少。

输入格式

输入一个正整数N。

输出格式

输出一个整数，表示你找到的最小公倍数。 样例输入 9

样例输出 504

数据规模与约定 1 <= N <= 1000000。

本题的Java参考代码如下： import java.util.Scanner; public class Main{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); long anser = 1; switch (n) { case 95152:// 1 anser = 861460772824848L; break; case 95486:// 2 anser = 870564410632930L; break; case 94407:// 3 anser = 841392798581010L; break; case 98088:// 4 anser = 943672006961970L; break; case 91200:// 5 anser = 943672006961970L; break;

case 98584:// 6 anser = 958079802716232L; break; case 99456:// 7 anser = 983709271929210L; break; case 97726:// 8 anser = 983709271929210L; break; case 96800:// 9 anser = 983709271929210L; break; default:// 10 anser = 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(s[0]); int L = Integer.valueOf(s[1]); int f[][] = new int[L][K]; int i,j,k,sum=0;

for(j=0;j1) {

for(i=1;i

for(j=0;j

for(k=0;k

if(k!=j-1 && k!=j+1) {

f[i][j]+=f[i-1][k];

f[i][j]%=1000000007; } } } }

for(j=0;j

编号：ALGO-4 题目：节点选择

关键字：树形动态规划 类型：普通试题 问题描述

有一棵 n 个节点的树，树上每个节点都有一个正整数权值。如果一个点被选择了，那么在树上和它相邻的点都不能被选择。求选出的点的权值和最大是多少？

输入格式

第一行包含一个整数 n 。

接下来的一行包含 n 个正整数，第 i 个正整数代表点 i 的权值。

接下来一共 n-1 行，每行描述树上的一条边。

输出格式

输出一个整数，代表选出的点的权值和的最大值。 样例输入 5

1 2 3 4 5 1 2 1 3 2 4 2 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 int[MAX_N][2]; Edge E[] = new Edge[MAX_N * 2]; int head[] = new int[MAX_N]; int sta[] = new int[MAX_N * 2];

boolean vis[] = new boolean[MAX_N];

void add(int u, int v) { E[edgecnt] = new Edge(u, v, head[u]); head[u] = edgecnt++; }

void dfs(int x, int fa) { Arrays.fill(vis, false); int top = 0; vis[x] = true; sta[top++] = x; while (top > 0) { int u = sta[top - 1]; boolean Ed = false; for (int i = head[u]; i + 1 != 0; i = E[i].nxt) { int v = E[i].v; if (vis[v]) continue; Ed = true; sta[top++] = v; vis[v] = true; } if (Ed) continue; --top; for (int i = head[u]; i + 1 != 0; i = E[i].nxt) { int v = E[i].v; dp[v][0] += Math.max(dp[u][0], dp[u][1]); dp[v][1] += dp[u][0]; } } }

void run() throws IOException { int n = cin.nextInt(); for (int i = 1; i <= n; ++i) dp[i][1] = 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(dp[1][0], dp[1][1]); 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(\ // } 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 3 1 2 -1 2 3 -1 3 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 IOException { int i; BufferedReader bfr=new BufferedReader(new InputStreamReader(System.in)); String str = bfr.readLine(); String[] s = str.split(\ n=Integer.parseInt(s[0]); m=Integer.parseInt(s[1]); n++; m++; u=new int[m]; v=new int[m]; w=new int[m]; first=new int[n]; next=new int[m]; d=new int[n];

inq=new boolean[n]; for(i=1;i

{ x=q.poll(); inq[x]=false; for(i=first[x];i!=-1;i=next[i]) if(d[v[i]]>d[x]+w[i]) {

d[v[i]]=d[x]+w[i]; if(!inq[v[i]]) {

inq[v[i]]=true; q.offer(v[i]); } } } } }

编号：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 7 10

10 20 6 30 1 2 5 2 3 5 2 4 12 3 4 17 2 5 15 3 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 int[100000];

static ArrayList path =new ArrayList();

public static int getfather(int x) { if (x!=father[x]) {

father[x]=getfather(father[x]); }

return father[x]; }

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(l

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++) { d[i]=Reader3.nextInt(); father[i]=i;

if (d[i]

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+d[k.a]+d[k.b]; path.add(k); }

_qst_w(0,p-1);

int fx,fy,result=minD,count=0,k=0; while(count

fx=getfather(path.get(k).a); fy=getfather(path.get(k).b); if(fx!=fy){

father[fx]=fy;

result+=path.get(k).l; count++; } k++; }

System.out.println(result); } }

编号：ALGO-7 题目：逆序对

关键字：平衡二叉树 类型：普通试题

问题描述

Alice是一个让人非常愉跃的人!他总是去学习一些他不懂的问题，然后再想出许多稀奇古怪的题目。这几天，Alice又沉浸在逆序对的快乐当中，他已近学会了如何求逆序对对数，动态维护逆序对对数等等题目，他认为把这些题让你做简直是太没追求了，于是，经过一天的思考和完善，Alice终于拿出了一道他认为差不多的题目：

有一颗2n-1个节点的二叉树，它有恰好n个叶子节点，每个节点上写了一个整数。如果将这棵树的所有叶子节点上的数从左到右写下来，便得到一个序列a[1]?a[n]。现在想让这个序列中的逆序对数量最少，但唯一的操作就是选树上一个非叶子节点，将它的左右两颗子树交换。他可以做任意多次这个操作。求在最优方案下，该序列的逆序对数最少有多少。

Alice自己已近想出了题目的正解，他打算拿来和你分享，他要求你在最短的时间内完成。

输入格式

第一行一个整数n。

下面每行，一个数x。

如果x=0，表示这个节点非叶子节点，递归地向下读入其左孩子和右孩子的信息，如果x≠0，表示这个节点是叶子节点，权值为x。

输出格式

输出一个整数，表示最少有多少逆序对。 样例输入 3 0 0 3 1 2

样例输出 1

数据规模与约定

对于20%的数据，n <= 5000。

对于100%的数据，1 <= n <= 200000，0 <= a[i]<2^31。 该题暂时没有人完全正确，暂时没有该语言的参考程序。

编号：ALGO-8 题目：操作格子 关键字：线段树 类型：普通试题

问题描述

有n个格子，从左到右放成一排，编号为1-n。

共有m次操作，有3种操作类型：

1.修改一个格子的权值，

2.求连续一段格子权值和，

3.求连续一段格子的最大值。

对于每个2、3操作输出你所求出的结果。

本文来源：https://www.bwwdw.com/article/z2qd.html