/目录1问题描述2解决方案2.1蛮力法2.2分治法（归并排序）给定一个随机数数组，求取这个数组中的逆序对总个数。要求时间效率尽可能高。 那么，何为逆序对？引用自百度百科：设A为一个有n个数字的有序集 (n>1)，其中所有数字各不相同。如果存在正整数i,j使得1≤i<j≤n而且...

/目录1问题描述2解决方案2.1构造最小生成树示例2.2伪码及时间效率分析2.3具体编码（最佳时间效率）  何为Kruskal算法？该算法功能：求取加权连通图的最小生成树。假设加权连通图有n个顶点，那么其最小生成树有且仅有n-1条边。该算法核心思想：从给定加权连通图中，选择当前未被选择的，不能形成回...

/目录1问题描述2解决方案  问题描述FarmerJohn变得非常懒，他不想再继续维护供奶牛之间供通行的道路。道路被用来连接N个牧场，牧场被连续地编号为1到N。每一个牧场都是一个奶牛的家。FJ计划除去P条道路中尽可能多的道路，但是还要保持牧场之间的连通性。你首先要决定那些道路是需要保留的N-1条道路...

/目录1问题描述2解决方案2.1使用Dijkstra算法得到最短距离示例2.2具体编码何为Dijkstra算法？Dijkstra算法功能：给出加权连通图中一个顶点，称之为起点，找出起点到其它所有顶点之间的最短距离。Dijkstra算法思想：采用贪心法思想，进行n-1次查找（PS:n为加权连通图的顶点总个数，除去起点，则...

/目录1问题描述2解决方案2.1使用Floyd算法得到最短距离示例2.2具体编码 何为Floyd算法？Floyd算法功能：给定一个加权连通图，求取从每一个顶点到其它所有顶点之间的最短距离。（PS：其实现功能也称完全最短路径问题）Floyd算法思想：将顶点i到j的直接距离依次与顶点i到顶点j之间加入k个中间节点...

/目录1问题描述2解决方案2.1具体编码何为BellmanFord算法？BellmanFord算法功能：给定一个加权连通图，选取一个顶点，称为起点，求取起点到其它所有顶点之间的最短距离，其显著特点是可以求取含负权图的单源最短路径。BellmanFord算法思想：第一，初始化所有点。每一个点保存一个值，表示从原点到达这个...

/目录1问题描述2解决方案2.1具体编码  何为spfa（ShortestPathFasterAlgorithm）算法？spfa算法功能：给定一个加权连通图，选取一个顶点，称为起点，求取起点到其它所有顶点之间的最短距离，其显著特点是可以求含负权图的单源最短路径，且效率较高。（PS：引用自百度百科：s...

/目录1问题描述2解决方案把n个皇后放在一个n*n的棋盘上，使得任何两个皇后都不能相互攻击，即它们不能同行，不能同列，也不能位于同一条对角线上。本文采用全排列的方法，从n个皇后的全排列中寻找符合规则的皇后排列。 为什么这里是说全排列呢？因为在N皇后问题中，棋盘每一行只准放一个皇后，且每一行的皇后必定要选一列。...

/目录1问题描述2解决方案什么是哈密顿回路？引用自百度百科：哈密顿图（哈密尔顿图）（英语：Hamiltonianpath，或Traceablepath）是一个无向图，由天文学家哈密顿提出，由指定的起点前往指定的终点，途中经过所有其他节点且只经过一次。在图论中是指含有哈密顿回路的图，闭合的哈密顿路径称作哈密顿回路（Ham...

/目录1问题描述2解决方案2.1全排列思想求解2.2状态空间树思想求解求n个正整数构成的一个给定集合A={a1,a2,a3,...,an}的子集，子集的和要等于一个给定的正整数d。请输出所有符合条件的子集。   本文下面编码思想参考自文末参考资料1，下面的思想讲解直接引用文末参考资料1。方...

/目录1问题描述2解决方案2.1floyd算法解决2.2spfa算法解决 问题描述给定一个n个顶点，m条边的有向图（其中某些边权可能为负，但保证没有负环）。请你计算从1号点到其他点的最短路（顶点从1到n编号）。输入格式第一行两个整数n,m。接下来的m行，每行有三个整数u,v,l，表示u到v有一条长度为l的边。...

/目录1问题描述2解决方案问题描述有一棵n个节点的树，树上每个节点都有一个正整数权值。如果一个点被选择了，那么在树上和它相邻的点都不能被选择。求选出的点的权值和最大是多少？输入格式第一行包含一个整数n。接下来的一行包含n个正整数，第i个正整数代表点i的权值。接下来一共n-1行，每行描述树上的一条边。输出格式输出一个整数...

/目录1问题描述2解决方案问题描述如果一个自然数N的K进制表示中任意的相邻的两位都不是相邻的数字，那么我们就说这个数是K好数。求L位K进制数中K好数的数目。例如K=4，L=2的时候，所有K好数为11、13、20、22、30、31、33共7个。由于这个数目很大，请你输出它对1000000007取模后的值。输入格式输入包含...

/目录1问题描述2解决方案问题描述已知一个正整数N，问从1~N中任选出三个数，他们的最小公倍数最大可以为多少。输入格式输入一个正整数N。输出格式输出一个整数，表示你找到的最小公倍数。样例输入9样例输出504数据规模与约定1<=N<=106。本题主要考查贪心法思想的运用，以及对于求取最小公倍数的数学基本知识。...

/目录1问题描述2解决方案问题描述给定一个序列，每次询问序列中第l个数到第r个数中第K大的数是哪个。输入格式第一行包含一个数n，表示序列长度。第二行包含n个正整数，表示给定的序列。第三个包含一个正整数m，表示询问个数。接下来m行，每行三个数l,r,K，表示询问序列从左往右第l个数到第r个数中，从大往小第K大的数是哪个。...