余弦の博客

题目集总目录 学习指路博客 数据结构学习笔记＜8＞ 排序 # 10 - 排序 4 统计工龄 (20 分) 本题链接 非常简单的练习，想一下用哪种排序效率最高？此题一定要做； ps: 灰常简单，都不想排序了【狗头保命】 # 代码 #include <iostream>#include <cstdio>using namespace std;typedef long long ll;#define div 1000000007const int maxn = 100005;const int inf = 0x3f3f3f;int N, x;int...

题目集总目录 学习指路博客 数据结构学习笔记＜8＞ 排序、归并排序循环实现（存用） # 09 - 排序 1 排序 (25 分) 本题链接 一个实验各种排序算法的平台，好好玩哈，然后去论坛晒结果 —— 实在不行可以看给出的参考代码。这是基本训练，一定要做 本题测试的各种排序算法的结果都在博客数据结构学习笔记＜8＞ 排序里边写了，这里仅给出插入排序的代码 # 代码 #include <iostream>#include <cstdio>using namespace std;typedef long long ll;const int maxn =...

递归的归并排序是很占空间和时间的，而非递归算法就不一样了，额外空间复杂度最少为 O (N)。 陈越姥姥的慕课里就讲得很清楚～ 戳这儿 这里就直接上代码 + 注释了 #include <iostream>#include <cstdio>#include <queue>using namespace std;typedef long long ll;const int maxn = 100005;const int inf = 0x3f3f3f;int N;ll a[maxn];void swap(ll &a, ll...

# 一、拓扑排序 # 1. 概念定义 # AOV 网络 例如，假定一个计算机专业的学生必须完成图 3-4 所列出的全部课程。从图中可以清楚地看出各课程之间的先修和后续的关系。如课程 C5 的先修课为 C2，后续课程为 C4 和 C6。通常，我们把这种顶点表示活动、边表示活动间先后关系的有向图称做顶点活动网 (Activity On Vertex network)，简称 AOV 网。 # 拓扑序、DAG 若图中从 V 到 W 有一条有向路径，则 V 一定排在 W 之前。满足该条件的顶点序列称为一个拓扑序 获得一个拓扑序的过程就是拓扑排序 AOV...

08-图7 公路村村通 (30分) 题目大意 代码 测试点 08-图8 How Long Does It Take (25分) 题目大意 思路 代码 测试点 08-图9 关键活动 (30分) 题目大意 代码 测试点 (目录) 题目集总目录 学习指路博客 解决最小生成树问题 (Kruskal 算法 & Prim 算法)、数据结构学习笔记＜8＞ 排序 # 08 - 图 7 公路村村通 (30 分) 本题链接 非常直白的最小生成树问题，但编程量略大，选做 —— 有时间就写写； #...

题目集总目录 学习指路博客 图论 # 07 - 图 4 哈利・波特的考试 (25 分) 本题链接 是很基本的算法应用，一定要做。如果不会，那么看看小白专场，会详细介绍 C 语言的实现方法 # 题目大意 给出每两个动物之间所需魔咒长度 哈利・波特最后应该带去考场的动物要使得最难变的动物所需总魔咒长度最小。 输出哈利・波特最后应该带去考场的动物的编号、以及最长的变形魔咒的长度 # 思路 用 Floyd 算法得出最短路矩阵 dist (dist [i][j] 表示 i 到 j 所需最短长度，在每行里找最难变 (即 dist [i][j] 最大) 的元素，在这些元素中找最小的，输出最小值的下标 i...

题目集总目录 学习指路博客 图 # 06 - 图 1 列出连通集 (25 分) 本题链接 非常基础的训练，一定要做 # 题目大意 输出图中所有连通集。先输出 DFS 的结果，再输出 BFS 的结果。 # 代码 #include <iostream>#include <cstdio>#include <queue>using namespace std;const int maxn = 11;int N,E,x,y;bool visited[maxn];int...

题目集总目录 学习指路博客 堆与哈夫曼树与并查集 # 05 - 树 7 堆中的路径 (25 分) 本题链接 将在 “小白专场” 中介绍 C 语言的实现方法，是建立最小堆的基本操作训练，一定要做 # 题目大意 给出最小堆的插入序列，和下标序列，每个下标 i 输出 Data [i] 到根结点路径上的值。 # 代码 #include <iostream>using namespace std;const int mindata = -10005;const int maxsize = 10000;typedef struct HeapStruct...

题目集总目录 学习指路博客 二叉搜索树与平衡二叉树 # 04 - 树 4 是否同一棵二叉搜索树 (25 分) 本题链接 小白专场将详细介绍 C 语言实现方法，属于基本训练，一定要做 # 题目大意 对于输入的各种插入序列，判断它们是否能生成一样的二叉搜索树。 # 思路 1. 分别建两棵树的判别方法 2. 不建树直接判断序列 3. 建一棵树再判别其他序列是否与该树一致 这里采用的是思路 3 # 代码 #include <iostream>using namespace std;#define maxsize 11typedef struct TNode*...

题目集总目录 学习笔记指路博客 线性表、堆栈 # 02 - 线性结构 1 两个有序链表序列的合并 (15 分) 本题链接 这是一道 C 语言函数填空题，训练最基本的链表操作。如果会用 C 编程的话，一定要做； # 代码 #include <stdio.h>#include <stdlib.h>typedef int ElementType;typedef struct Node *PtrToNode;struct Node { ElementType Data; PtrToNode Next;};typedef...