并查集
将两个集合合并
询问两个元素是否在一个集合当中
每个集合用一棵树来表示。树根的编号就是整个集合的编号。每个节点存储它的父节点
p[x]表示x的父节点
- 如何判断树根：
if(p[x] == x)当父节点等于自身时，代表找到根节点 - 如何求
x的集合编号：while(p[x] != x) x = p[x]; - 如何合并两个集合：
px是x的集合编号，py是y的集合编号。p[x] = y - 优化：路径压缩
朴素并查集：
int p[N]; //存储每个点的祖宗节点
// 返回x的祖宗节点+路径压缩
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ ) p[i] = i;
// 合并a和b所在的两个集合：
p[find(a)] = find(b);
维护size的并查集：
应用：连通块中点的数量
int p[N], size[N];
//p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量
// 返回x的祖宗节点
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ )
{
p[i] = i;
size[i] = 1;
}
// 合并a和b所在的两个集合：
size[find(b)] += size[find(a)];
p[find(a)] = find(b);
维护到祖宗节点距离的并查集：
int p[N], d[N];
//p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离
// 返回x的祖宗节点
int find(int x)
{
if (p[x] != x)
{
int u = find(p[x]);
d[x] += d[p[x]];
p[x] = u;
}
return p[x];
}
// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ )
{
p[i] = i;
d[i] = 0;
}
// 合并a和b所在的两个集合：
p[find(a)] = find(b);
d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量
应用：食物链
$x$ 吃 $y$ 表示 $y$ 到 $x$ 的距离为 $1$
$y$ 是第 $0$ 代，吃 $y$ 的 $x$ 是第 $1$ 代，吃 $x$ 的是第 $2$ 代,根节点是第 $0$ 代
三种关系：用点到根节点之间的距离表示其余根节点之间的关系
mod 3 = 1:可以吃根节点
mod 3 = 2:可以被根节点吃
mod 3 = 0:和根节点同类
#include <iostream>
using namespace std;
const int N = 50010;
int n, m;
int p[N], d[N];
int find(int x)
{
if (p[x] != x)
{
int t = find(p[x]);
d[x] +=d[p[x]];
/*
d[x]存储的永远是x到p[x]的距离，其目的是为了求x到根节点的距离
d[i]是第i个节点到其父节点距离,再加上父节点到根节点的距离
find()函数进行了路径压缩，当查询某个节点 i 时，如果 i 的父节点不为根节点的话，就会进行递归调用
将 i 节点沿途路径上所有节点均指向父节点，此时的 d[i] 存放的是 i 到父节点，也就是根节点的距离。
*/
p[x] = t;//先算距离，最后再把结点挂到根上
}
return p[x];
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) p[i] = i;
int res = 0;
while (m -- )
{
int t, x, y;
scanf("%d%d%d", &t, &x, &y);
if (x > n || y > n) res ++ ;
else
{
int px = find(x), py = find(y);
if (t == 1)
{
if (px == py && (d[x] - d[y]) % 3 != 0) res ++ ;
//x和y在一棵树上但不同类。(d[x] - d[y]) % 3 != 0则表示二者不同类
//如果x、y不在一棵树里，那必然没矛盾
//同一棵树的所有结点都有关系（同类关系或吃与被吃的关系）
//为什么要建多棵树：出现与前面都没关系的结点
else if (px != py)
{
p[px] = py;//x归到y
d[px] = d[y] - d[x];//让x到py的距离等于y到py的距离，x和y变成同一类
}
}
else
{
if (px == py && (d[x] - d[y] - 1) % 3) res ++ ;//等于 0 则不是谎话
else if (px != py)
{
p[px] = py;
d[px] = d[y] + 1 - d[x];//dx在模3的情况下应该比dy多1
}
}
}
}
printf("%d\n", res);
return 0;
}
堆
应用：
如何手写一个堆(小根堆)?
- 插入一个数
heap[ ++ size] = x; up(size); - 求集合当中的最小值
heap[1] - 删除最小值
heap[1] = heap[size]; size --;down(1); - 删除任意一个元素
heap[k] = heap[size]; size --;down(k);up(k); - 修改任意一个元素
heap[k] = x;down(k);up(k);
堆是一棵完全二叉树
// h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1
// ph[k]存储第k个插入的点在堆中的位置（p是下标，h是堆，ph从下标映射到堆）
// hp[k]存储堆中下标是k的点是第几个插入的
int h[N], ph[N], hp[N], size;
// 交换两个点，及其映射关系
void heap_swap(int a, int b)
{
swap(ph[hp[a]],ph[hp[b]]);//hp[i] = j是在堆中下标为i的点第j个插入的数
swap(hp[a], hp[b]);
swap(h[a], h[b]);
}
void down(int u)//往下调整，把结点往下移
{
int t = u;//t存储三个结点中存在的最小的结点的下标，初始化为当前结点u
if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;// 左子节点存在并且小于当前结点，更新t的下标
if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
if (u != t)//如果t==u意味着不用变动，u就是三个结点中拥有最小值的结点下标，否则交换数值
{
heap_swap(h[t], h[u]);
down(t);
}
}
void up(int u)//往上调整
{
while (u / 2 && h[u] < h[u / 2])
{
heap_swap(u, u / 2);
u >>= 1;
}
}
// O(n)建堆
for (int i = n / 2; i; i -- ) down(i);
哈希表
模拟散列表
(1) 拉链法
int h[N], e[N], ne[N], idx;
// 向哈希表中插入一个数
void insert(int x)
{
int k = (x % N + N) % N;
e[idx] = x;
ne[idx] = h[k];
h[k] = idx ++ ;
}
// 在哈希表中查询某个数是否存在
bool find(int x)
{
int k = (x % N + N) % N;
for (int i = h[k]; i != -1; i = ne[i])
if (e[i] == x)
return true;
return false;
}
(2) 开放寻址法
int h[N];
// 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置
int find(int x)
{
int t = (x % N + N) % N;
while (h[t] != null && h[t] != x)
{
t ++ ;
if (t == N) t = 0;
}
return t;
}
//memset(h, 0x3f, sizeof h); 0x3f大于1e
9，不会爆int
字符串哈希（字符串前缀哈希）
核心思想：将字符串看成
P进制数，P的经验值是131或13331，取这两个值的冲突概率低
小技巧：取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果
- 任意字符不可以映射成0，否则会出现不同的字符串都映射成0的情况，比如A,AA,AAA皆为0
- 冲突问题：通过巧妙设置P (131 或 13331) , Q (264)(264)的值，一般可以理解为不产生冲突。
前缀和公式 $h[i+1]=h[i]×P+s[i]$
区间和公式 $h[l,r]=h[r]−h[l−1]×P^{r−l+1}$
$ABCDE$ 与 $ABC$ 的前三个字符值是一样，只差两位，
乘上 $P^2$ 把 $ABC$ 变为 $ABC00$，再用 $ABCDE$ - $ABC00$ 得到 $DE$ 的哈希值。
typedef unsigned long long ULL;
ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64
// 初始化
p[0] = 1;//从1开始映射
for (int i = 1; i <= n; i ++ )
{
h[i] = h[i - 1] * P + str[i];
p[i] = p[i - 1] * P;
}
// 计算子串 str[l ~ r] 的哈希值
ULL get(int l, int r)
{
return h[r] - h[l - 1] * p[r - l + 1];
}
stl简介
C++ STL简介
vector, 变长数组，倍增的思想
size() 返回元素个数
empty() 返回是否为空
clear() 清空
front()/back()
push_back()/pop_back()
begin()/end()
[]
支持比较运算，按字典序
三种遍历方式
for(int i = 0; i < a.size(); i ++) cout << a[i];
for(atuo i = a.begin(); i != a.end; i ++) cout << *i;
for(auto x : a) cout << x << ' ';
pair<int, int>
first, 第一个元素
second, 第二个元素
支持比较运算，以first为第一关键字，以second为第二关键字（字典序）
string，字符串
size()/length() 返回字符串长度
empty()
clear()
substr(起始下标，(子串长度)) 返回子串
c_str() 返回字符串所在字符数组的起始地址
queue, 队列
size()
empty()
push() 向队尾插入一个元素
front() 返回队头元素
back() 返回队尾元素
pop() 弹出队头元素
priority_queue, 优先队列，默认是大根堆
size()
empty()
push() 插入一个元素
top() 返回堆顶元素
pop() 弹出堆顶元素
定义成小根堆的方式：priority_queue<int, vector<int>, greater<int>> q;
stack, 栈
size()
empty()
push() 向栈顶插入一个元素
top() 返回栈顶元素
pop() 弹出栈顶元素
deque, 双端队列
size()
empty()
clear()
front()/back()
push_back()/pop_back()
push_front()/pop_front()
begin()/end()
[]
set, map, multiset, multimap, 基于平衡二叉树（红黑树），动态维护有序序列
size()
empty()
clear()
begin()/end()
++, -- 返回前驱和后继，时间复杂度 O(logn)
set/multiset
insert() 插入一个数
find() 查找一个数
count() 返回某一个数的个数
erase()
(1) 输入是一个数x，删除所有x O(k + logn)
(2) 输入一个迭代器，删除这个迭代器
lower_bound()/upper_bound()
lower_bound(x) 返回大于等于x的最小的数的迭代器
upper_bound(x) 返回大于x的最小的数的迭代器
map/multimap
insert() 插入的数是一个pair
erase() 输入的参数是pair或者迭代器
find()
[] 注意multimap不支持此操作。 时间复杂度是 O(logn)
lower_bound()/upper_bound()
unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表
和上面类似，增删改查的时间复杂度是 O(1)
不支持 lower_bound()/upper_bound()， 迭代器的++，--
bitset, 圧位
bitset<10000> s;
~, &, |, ^
>>, <<
==, !=
[]
count() 返回有多少个1
any() 判断是否至少有一个1
none() 判断是否全为0
set() 把所有位置成1
set(k, v) 将第k位变成v
reset() 把所有位变成0
flip() 等价于~
flip(k) 把第k位取反
