zanejins

王道考研+夏令营

题解(19)

/ 注册

全部文章 / 王道考研+夏令营（共30篇）

21 拓扑排序来自专栏

理论说明本次我们主要苏里一下图论中的另一个经典问题--拓扑排序，并以该问题作为图论最后一个专题。设有一个有向无环图DAG，对其进行拓扑排序即求其中结点的一个拓扑序列，对于所有的有向边（U,A），在该序列中结点U都排序在结点V之前。满足该要求的结点序列，我们称为满足拓扑次序的序列。求这个序列的过程...

C++ 拓扑排序

2022-04-28

0 404

20 最短路径

理论说明之前已经总结梳理完最小生成树之后，我们再来梳理一下图论中的另一个经典问题：最短路径问题。即寻找图中某两个特定结点之间的最短路径长度。所谓图上的路径，即从图中一个起始结点到一个终止结点途中经过的所有结点序列，路径的长度即所经过的边权和。朴素Dijkstra算法朴素堆优化的D...

最短路径 C++

2022-04-28

0 377

19 最小生成树（MST）来自专栏

理论说明本节我们了解图论中的一类经典问题---最小生成树。在一个无向连通图中，如果存在一个连通子图包含原图中所有的结点和部分边，且这个子图中不存在回路，那么我们称这个子图为原图的一棵生成树。在带权图中，所有的生成树中边权的和最小的数（可能不唯一），被称为最小生成树。最小生成树问题是图论的经典问...

C++ 最小生成树

2022-04-27

0 637

18 并查集来自专栏

理论说明并查集的作用：判断两个元素是否再同一集合中求集合中元素的数量等这里用树结构来表示集合。那么如何判断两个元素是否再同一集合中？我们可以利用一个数组，数组单元i保存结点i的父节点编号，若该结点已经是根结点，则其双亲结点信息保存为-1.有了这样的存储结构，我们就能通过不断地...

C++ 并查集

2022-04-27

0 362

16 二分求幂来自专栏

理论说明该问题解决的是如何快速的求得a的b次方。一般做***是使用了一个循环次数为b的for循环，并在每次循环时都累乘a,这样在b次循环结束时就能获得a的b次方。但是显然这种方法并不是最优的。按照这个策略，当我们循环到第i次时，此时的累乘的结果即为2的i次。那么当我们完成了前16次循环时，我们就得...

C++ 二分求幂

2022-04-13

0 408

15 素数筛法来自专栏

题目来源和说明题目来源于2009年哈尔滨工业大学计算机研究生机考真题题目描述给定一个数字n,要求判断是否是素数（0,1,负数字都是非素数）样例输入 13 1 输出 yes no 简要分析素数判断，从2-sqrt(n)找是否能够整除的因子即可。 C++ 代码 #include&l...

素数筛选 c++

2022-04-06

0 316

14 最小公倍数来自专栏

题目来源和说明 2011年哈尔滨工业大学计算机研究生机试真题题目描述输入两个正整数，求其最小公倍数样例输入 10 14 输出 70 简要分析最小公倍数：两个数字的乘积再除以最大公约数。最大公约数的方法已经再第13记录了。具体的代码如下： C++ 代码 #include<ios...

C++ LCM

2022-04-06

0 327

13 最大公约数来自专栏

题目来源和说明 2011年哈尔滨工业大学计算机研究生机试真题题目描述输入两个正整数，求其最大公约数样例输入 49 14 输出 7 简要分析要求a和b的最大公约数：（1）如果a和b全为0，则他们的最大公约数不存在（2）如果a和b其中之一为0，则他们的最大公约数为a、b中非零的那...

gcd C++

2022-04-06

0 265

12 进制转换来自专栏

题目来源和说明题目来源于2008年浙江大学计算机及软件工程研究生机试真题。题目描述输入两个不超过整型定义的非负10进制整数A和B(<=2^31-1)，输出A+B的m (1 < m <10)进制数。样例输入 8 1300 48 2 1 7 0 输出 2504 1000 ...

进制转换 C++

2022-04-06

0 510

11 %运算符来自专栏

题目来源和说明题目来源于王道考研，题目链接如下： https://www.nowcoder.com/questionTerminal/8c3c5dae2c4a4266ba04f993a18e286b 题目描述读入两个小于10000的正整数A和B，计算A+B。需要注意的是：如果A和B的末尾K（不超...

取模 C++

2022-04-05

0 421