发布时间 : 星期日 文章蓝桥杯题库中的算法训练试题更新完毕开始阅读8091ff71dd88d0d232d46a5a
如果x=0，表示这个节点非叶子节点，递归地向下读入其左孩子和右孩子的信息，如果x≠0，表示这个节点是叶子节点，权值为x。 输出格式
输出一个整数，表示最少有多少逆序对。 样例输入 3 0 0 3 1 2 样例输出 1
数据规模与约定
对于20%的数据，n <= 5000。
对于100%的数据，1 <= n <= 200000，0 <= a[i]<2^31。
28. 算法训练安慰奶牛
时间限制：1.0s 内存限制：256.0MB
问题描述
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。
21
输出格式
输出一个整数, 所需要的总时间(包含和在你所在的牧场的奶牛的两次谈话时间)。 样例输入 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。
29. 算法训练 最短路
时间限制：1.0s 内存限制：256.0MB
问题描述
给定一个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
22
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，保证从任意顶点都能到达其他所有顶点。
30. 算法训练结点选择
时间限制：1.0s 内存限制：256.0MB
问题描述
有一棵 n 个节点的树，树上每个节点都有一个正整数权值。如果一个点被选择了，那么在树上和它相邻的点都不能被选择。求选出的点的权值和最大是多少？ 输入格式
第一行包含一个整数 n 。
接下来的一行包含 n 个正整数，第 i 个正整数代表点 i 的权值。 接下来一共 n-1 行，每行描述树上的一条边。 输出格式
输出一个整数，代表选出的点的权值和的最大值。 样例输入 5
1 2 3 4 5 1 2 1 3 2 4 2 5 样例输出 12 样例说明
23
选择3、4、5号点，权值和为 3+4+5 = 12 。 数据规模与约定
对于20%的数据， n <= 20。 对于50%的数据， n <= 1000。 对于100%的数据， n <= 100000。 权值均为不超过1000的正整数。
31. 算法训练 K好数
时间限制：1.0s 内存限制：256.0MB
问题描述
如果一个自然数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。
32. 算法训练最大最小公倍数
时间限制：1.0s 内存限制：256.0MB
问题描述
已知一个正整数N，问从1~N中任选出三个数，他们的最小公倍数最大可以为多少。
24