组合数学
组合数学容斥原理原理设 $U$ 中的集合有 $n$ 种不同的属性,而第 $i$ 种属性称为 $P_i$ ,拥有属性 $P_i$ 的元素构成集合 $S_i$,那么 $|\bigcup_{i = 1}^{n}S_i| = \sum_{m=1}^{n} (-1)^{m-1} \sum_{a_i < a_{i + 1}} |\bigcap_{i = 1}^{m}S_{a_i}|$ $|\bigcap_{i = 1}^{n}S_i| = \sum_{m=1}^{n} (-1)^{m-1} \sum_{a_i < a_{i + 1}} |\bigcup_{i = 1}^{m}S_{a_i}|$
咕咕咕
数据结构
数据结构线段树线段树合并原理线段树合并是将多颗线段树合并成一颗线段树。合并的时候,将重合的节点值相加,不重合的节点保持原样。
123456789101112131415int merge(int p1, int p2, int l, int r) { if(p1 == 0 || p2 == 0) { return p1 + p2; } if(l == r) { nod[p1].mx = nod[p1].mx + nod[p2].mx; nod[p1].ans = l; return p1; } int mid = (l + r) / 2; ls[p1] = merge(ls[p1], ls[p2], l, mid); rs[p1] = merge(rs[p1], rs[p2], mid + 1, r); pushup(p1); return p1;}
时间复杂度线段树 $T_1, T_2,…, T_n$ 将它们以任意顺序合并的时间复杂度为 $O(\sum_{i = 1}^n |T_i| - ...
题目选做
2024.2CF1096DCF1096D Easy Problem首先我们可以很自然的想到状态 $dp_{i,j}$ 表示前 $i$ 个字符只包含 “$hard$” 前 $k$ 的字串最少需要多少代价。然后就是分类讨论:首先是删除第 $i$ 个字符,直接用 $dp_{i,j} = min(dp_{i-1,j} + cost_i, dp_{i,j})$ 转移就行了;不删除第 $i$ 个数字,如果 $s_i$ 是 “$hard$” 的第 $k$ 个数字那么 $dp_{i,k} = min(dp_{i - 1,k - 1}, dp_{i,j})$,对于其他的位置只需要 $dp_{i,j} = min(dp_{i - 1,j}, dp_{i,j})$。最后答案就是 $max(dp_{n, 0},dp_{n, 1},dp_{n, 2},dp_{n, 3})$ ,其中 $n$ 是字符串 $s$ 的长度。时间复杂度为$O(n)$。当然也可以用滚动数组优化空间复杂度。
12345678910111213141516171819202122232425262728 ...
图论
图论拓扑排序拓扑排序的定义拓扑排序:在一个 $DAG$(有向无环图) 中,我们将图中的顶点以线性方式进行排序,使得对于任何的顶点 $u$ 到 $v$ 的有向边 $(u,v)$, $u$ 都在 $v$ 的前面。
形式化地,设 $q_i$ 表示结点 $i$ 在 $p$ 中的位置,那么对于图上每条有向边 $u \rightarrow v$ ,均有 $q_u < q_v$ 。
拓扑排序的实现由于原图无环,所以在拓扑排序没有结束的时候必然存在入度为 $0$ 的节点,将这个点加入 $p$ 并删去其出边。
可以通过 $BFS$ 或者 $DFS$ 实现,时间复杂度为 $O(N + M)$
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849#include <iostream>#include <queue>#include <vector>using namespace std;int main() { int n; ci ...