余弦の博客

参考博客：链式前向星 -- 最通俗易懂的讲解、算法讲解：二分图匹配【图论】、趣写算法系列之 -- 匈牙利算法、匈牙利算法与增广路径 暑假整的忘了发 2333 <hr style=" border:solid; width:100px; height:1px;" color=#000000 size=1"> 一、链式前向星 1.是什么 2.如何存图 定义及初始化 加边 遍历 二、二分图匹配 1.二分图 2.匹配 3.匈牙利算法 核心代码 几道例题 A - Fire Net 题目大意及思路 代码 B...

加入了 ReverseList 函数，逆转单链表操作 改了个 bug，逆转链表时特判一个结点的情况 又改了 N 个 bug，特判空链表的情况 <hr style="border:solid; width:100px; height:1px;" color=#000000 size=1"> 试试模板类加上数据结构 肯定还是会有遗漏的地方的，欢迎指正 不多说，上代码 ps:nullptr 是 c++11 特性，使用时需注意 # 结点定义 template <class T> class LNode...

在这个由于疫情导致格外漫长的暑假里，我们没有办法线下集训，所以只能在网上刷学长拉的专题，更多的靠自己自学，并且由于在家诸多因素，实际上懈怠了很多，在此我总结一下在这个暑假里学的东西。 暑假之前，我所掌握的算法极少，只有寒假蓝桥杯集训时的枚举、贪心、二分、并查集、基础的动态规划等，刷题也不多，而在这个暑假里，跟着学长拉的专题和推荐的博客自学，本次暑期集训共拉了 8 个专题：线段树、最短路、最小生成树、KMP、博弈论、强连通、二分图匹配、网络流，越往后难度越高，从一天能刷 4-5 道变成 2-3...

状压讲解部分参考博客状压 DP 详解（位运算） # 一、什么是状压 dp？ 这里是引用 状压 dp，即将状态压缩成 2 进制来保存，如矩阵中将一行的状态压缩成一个二进制串，如 dp [S][v] 中，S 可以代表已经访问过的顶点的集合，v 可以代表当前所在的顶点为 v。S 代表的就是一种状态（二进制表示）， (11001)2 代表在二进制中 {0，3，4} 三个顶点已经访问过了，(11001)2 代表的十进制数就是 25 ，所以当 S 为 25 的时候其实就是代表已经访问过了 {0，3，4} 三个顶点，那假如一共有 5 个顶点（标号为 01234）的话，所有的顶点都访问完毕，Sj...

题目集总目录 学习指路博客 二叉树、队列 # 03 - 树 1 树的同构 (25 分) 本题链接 小白专场会做详细讲解，基本要求，一定要做 题目大意：给定两棵树，请你判断它们是否是同构的。 # 思路 1. 二叉树的表示 数组存储结构体，结构体含数据、左右孩子的下标（Null 代表 - 1） 2. 建二叉树 返回根节点下标 3. 同构判断 利用递归。若 R1、R2 同时为空，返回 true。若其中一个为空，返回 false。若根节点元素就不相同，则返回...

题目集总目录 学习指路博客 数据结构学习笔记＜9＞ 散列查找 # 11 - 散列 1 电话聊天狂人 (25 分) 本题链接 一定要做。如果不知道怎么下手，可以看 “小白专场”，将详细给出 C 语言实现的方法 # 思路 散列查找，插入的时候若键值已存在改改操作就好，直接用之前的模板 # 代码 #include <iostream>#include <cmath>#include <utility>using namespace std;const int MaxSize = 100000;typedef int Index;//...

# 一、散列表（哈希表） # 1. 概念引出 编译处理中对变量的管理：动态查找问题 利用查找树进行？—— 两个变量名（字符串）比较效率不高 将字符串转换为数字，再处理？—— 即为散列查找的思想 已知的几种查找方法： 顺序查找 O (N) 二分查找（静态查找） O (log2N) 二叉搜索树 O (h) h 为二叉查找树的高度 平衡二叉树 O (log2N) # 问题：如何快速搜索到需要的关键词？若关键词不方便比较怎么办？ 查找的本质：<font color=#FF0000> 已知对象找位置 有序的安排对象：全序（完全有序，eg:...

题目集总目录 学习指路博客 数据结构学习笔记＜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...