笑枕晚风の小站

参考《算法竞赛进阶指南》、AcWing题库 12345678910// 自定义 PairHashstruct PairHash { template<typename T, typename U> size_t operator() (const pair<T, U> &v) const { size_t seed = 0; seed ^= hash<T>()(v.first) + 0x9e3779b9 + (seed << 6) + (seed >> 2); seed ^= hash<U>()(v.second) + 0x9e3779b9 + (seed << 6) + (seed >> 2); return seed; }}; 123456789101112// 自定义 VectorHashstruct VectorHash { template ...

参考《算法竞赛进阶指南》、AcWing题库 二叉搜索树与平衡树初步 在二叉树中, 有两组非常重要的条件, 分别是两类数据结构的基础性质。其一是 “堆性质”。二叉堆以及高级数据结构中的所有可合并堆, 都满足 “堆性质”。其二就是本节即将探讨的 “BST 性质”, 它是二叉搜索树 (Binary Search Tree）以及所有平衡树的基础。 BST 给定一棵二叉树, 树上的每个节点带有一个数值, 称为节点的 “关键码” 。所谓 “BST 性质” 是指, 对于树中的任意一个节点: 该节点的关键码不小于它的左子树中任意节点的关键码; 该节点的关键码不大于它的右子树中任意节点的关键码。 满足上述性质的二叉树就是一棵 “二叉搜索树” (BST)。显然, 二叉搜索树的中序遍历是一个关键码单调递增的节点序列。 BST 的建立 为了避免越界, 减少边界情况的特殊判断, 我们一般在 BST 中额外插入一个关键码为正无穷 (一个很大的正整数) 和一个关键码为负无穷的节点。仅由这两个节点构成的 BST 就是一棵初始的空 BST。如图所示。 简便起见, 在接下来的操作中, 我们假设 BST 不会含有 ...

参考《算法竞赛进阶指南》、AcWing题库 二叉堆 二叉堆是一种支持插入、删除、查询最值的数据结构。它其实是一棵满足“堆性质” 的完全二叉树, 树上的每个节点带有一个权值。 完全二叉树：叶子节点都在最后两层，且在最后一层集中于左侧的二叉树。 若树中的任意一个节点的权值都小于等于其父节点的权值, 则称该二叉树满足 “大根堆性质”。若树中任意一个节点的权值都大于等于其父节点的权值, 则称该二叉树满足 “小根堆性质” 。满足 “大根堆性质” 的完全二叉树就是 “大根堆”, 而满足 “小根堆性质” 的完全二叉树就是 “小根堆” , 二者都是二叉堆的形态之一。 根据完全二叉树的性质, 我们可以采用层次序列存储方式, 直接用一个数组来保存二叉堆。层次序列存储方式, 就是逐层从左到右为树中的节点依次编号, 把此编号作为节点在数组中存储的位置 (下标)。在这种存储方式中, 父节点编号等于子节点编号除以 2 , 左子节点编号等于父节点编号乘 2 , 右子节点编号等于父节点编号乘 2 加 1 , 如下图所示。 我们以大根堆为例探讨堆支持的几种常见操作的实现。 Insert Insert(val) ...

参考《算法竞赛进阶指南》、AcWing题库 可持久化数据结构 到目前为止, 我们学习的数据结构维护的都是 “数据集的最新状态”。若想知道数据集在任意时间的历史状态 (即 ∀i∈[1,M]\forall i \in[1, M]∀i∈[1,M], 执行完操作序列中第 iii 项操作后数据集的状态), 一种朴素的做法是 ∀i∈[1,M]\forall i \in[1, M]∀i∈[1,M], 在第 iii 项操作结束后, 把整个数据结构拷贝一遍, 存储在 history[i]history[i]history[i] 中, 多耗费 MMM 倍的空间。“可持久化” 提供了一种思想, 在每项操作结束后, 仅创建数据结构中发生改变的部分的副本, 不拷贝其他部分。这样一来, 维护数据结构的时间复杂度没有增加, 空间复杂度仅增长为与时间同级的规模。换言之, 可持久化数据结构能够高效地记录一个数据结构的所有历史状态。 可持久化 Trie 与 Trie 的节点一样, 可持久化 Trie 的每个节点也有若干字符指针指向子节点, 可以用 trie[x,c]trie[x, c]trie[x,c] 保存节点 x ...

参考《算法竞赛进阶指南》、AcWing题库 线段树 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566class SegTree {public: struct Node { int l = 0, r = 0; int sum = 0; }; vector<Node> tr; vector<int> a; int n; SegTree() {} SegTree(vector<int> &a) { n = a.size(); this->a = a; tr.resize(n * 4 + 1); build(1, 1, n); } voi ...

在 c++ 的标准库中，因为类继承关系比较复杂和模板使用比较多的原因，源代码中充斥着 typename、typedef 和 using 这三个关键字 typename 关键字 typename 的第一个作用是用作模板里面，来声明某种类型，比如这样的： 12template<typename _Tp, typename _Alloc> struct _Vector_base; 最开始的时候声明模板形参，也会使用 class，但我们都知道 class 总要是用来指定一个类名，据说是为了避免混淆，所以后来增加了 typename 这个关键字，它告诉编译器，跟在它后面的字符串是一个不确定的类型，而不是变量或者其他什么东西。 typename 在 stl 中还有另外一种作用，显示地告诉编译器一个名字表示的是类型。 123456789//test.cpp#include <ext/alloc_traits.h>using namespace std;template<typename _Tp, typename _Alloc>class AA{ ...

C++ 自定义比较器 重载操作符 < 实际上是对自定义的 struct，重写它的 operator < 方法 1234567891011121314151617struct Str{ string s; bool operator < (const Str &str) const { //注意有两个const return s.length() < str.s.length(); }};int main() { vector<Str> vec; for (int i = 0; i < 5; ++i) { Str s; cin >> s.s; vec.push_back(s); } sort(vec.begin(), vec.end()); return 0;} 函数比较器 可以通过写一个外部的比较器函数，实现 < 方法： 使用这种方式常常 ...

主要参考算法导论，修正原文错误、易混淆翻译，整合相关习题实战 字符串匹配 在编辑文本程序过程中, 我们经常需要在文本中找到某个模式的所有出现位置。典型情况 是, 一段正在被编辑的文本构成一个文件, 而所要搜寻的模式是用户正在输入的特定的关键字。 有效地解决这个问题的算法叫做字符串匹配算法, 该算法能够极大提高编辑文本程序时的响应 效率。在其他很多应用中, 字符串匹配算法用于在 DNA 序列中搜寻特定的序列。在网络搜索引 擎中也需要用这种方法来找到所要查询的网页地址。 字符串匹配问题的形式化定义如下: 假设文本是一个长度为 nnn 的数组 T[1,n]T[1, n]T[1,n], 而模式是一 个长度为 mmm 的数组 P[1..m]P[1 . . m]P[1..m], 其中 m⩽nm \leqslant nm⩽n, 进一步假设 PPP 和 TTT 的元素都是来自一个有限字母集 Σ\SigmaΣ 的字符。例如, Σ={0,1}\Sigma=\{0,1\}Σ={0,1} 或者 Σ={a,b,⋯ ,z}\Sigma=\{a, b, \cdots, z\}Σ={a,b,⋯,z} 。字符数组 ...

参考《算法竞赛进阶指南》、AcWing题库 计数类DP 我们通过几道例题来介绍动态规划中的计数问题和数位统计问题。这两类问题都特别强调 “不重不漏”, 统计对象的可能情况一般比较多, 通常需要精确的划分和整体性的计算。因此, 使用动态规划抽象出问题中的 “子结构” 和推导 的 “阶段”, 将有助于我们准确而高效地进行求解。 306. 杰拉尔德和巨型象棋 给定一个 H×WH \times WH×W 的棋盘，棋盘上只有 NNN 个格子是黑色的，其他格子都是白色的。 在棋盘左上角有一个卒，每一步可以向右或向下移动一格，并且不能移动到黑色格子中。 求这个卒从左上角移动到右下角，一共有多少种路线。 输入格式 第一行包含三个整数 H,W,NH,W,NH,W,N。 接下来 NNN 行，每行包含两个整数 x，yx，yx，y，描述一个黑色格子位于 xxx 行 yyy 列。 数据保证左上角和右下角的格子都是白色的。 输出格式 输出一个整数表示结果对 109+710^9+7109+7 取模后的值。 数据范围 1≤H,W≤1051 \le H,W \le 10^51≤H,W≤105, 1≤N≤20001 ...

二叉树 二叉树遍历 二叉树前序遍历 递归 123456789101112131415class Solution {public: vector<int> ans; vector<int> preorderTraversal(TreeNode* root) { dfs(root); return ans; } void dfs(TreeNode* root) { if (!root) return; ans.push_back(root->val); dfs(root->left); dfs(root->right); }}; 用栈模拟递归 12345678910111213141516class Solution {public: vector<int> preorderTraversal(TreeNode* root) { ...