zanejins

分类

王道考研+夏令营(30) 题解(19)

/ 注册

TA的专栏 32篇文章 6人订阅

高校夏令营机试训练

32篇文章 947人学习

0篇文章 0人学习

0篇文章 0人学习

0篇文章 0人学习

全部文章（共45篇）

21 拓扑排序来自专栏

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

C++ 拓扑排序

2022-04-28

0 404

20 最短路径

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

最短路径 C++

2022-04-28

0 377

题解 | #Jungle Roads#

英语太难啦，大致意思是这样的：一个部落有n个村子，若干条道路，每个道路有它的花费，要修一条可以连接所有村子的路，保证花费最小，典型的最小生成树。用例第一行是n个村子，之后的n-1行是道路信息 A 2 B 12 I 25 这代表有两条路通往村子A，AB之间的花费是12，AI之间的花费是25。这个...

C++ 最小生成树

2022-04-27

0 476

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

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

C++ 最小生成树

2022-04-27

0 637

18 并查集来自专栏

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

C++ 并查集

2022-04-27

0 362

17 高精度整数来自专栏

理论说明我们常用如下结构体保存一个高精度整数： struct bigInteger { int digit[1000]; int size; }; 其中digit数组用来保存大整数中每若干位的数字，这里我们暂且使用每4位为一个单位保存，size为digit数组中第一个我们没使用过的数组...

C++ 高精度整数

2022-04-25

0 482

16 二分求幂来自专栏

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

C++ 二分求幂

2022-04-13

0 408

16 分解素因数来自专栏

题目来源和说明本题来源于2007年清华大学计算机研究生机考真题。题目描述求正整数N(N>1)的质因数的个数。相同的质因数需要重复计算。如120=22235，共有5个质因数。输入描述可能有多组测试数据，每组测试数据的输入是一个正整数N，(1<N<10^9)。输出描述对...

C++ 素因数

2022-04-07

0 505

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