AKSZ - 图论，字符串，数学笔记
2024-07-24 22:03:27
发布于：广东
9阅读
0回复
0点赞
链式前向星模板
一种图的表示方式，在无向图中编号为x和x^1的边是u->v和v->u
int head[maxn];
int nxt[maxn*2];
int to[maxn*2];
int tot;
void addedge(int u, int v, int w){
nxt[tot] = head[u];
to[tot] = v;
head[u] = tot++;
}
void init(){
memset(head, -1, sizeof head);
}
for (int i=head[u]; ~i; i=nxt[i]) v = to[i];
// 遍历点u的边
带权并查集：在维护并查集时维护其他信息
e.g. 点x到father[x]的长度
最小生成树kruscal
时间复杂度O(mlogm) 适用于稀疏图
将所有边递增排序后依次遍历
如果u, v已经联通那么continue
否则将边添加进图中使得u, v联通
最小生成树prim
时间复杂度O(n^2)或O(mlogm)
随便选一个点开始
用优先队列或枚举选出联通的权值最小的边
重复操作直到所有点都联通
01分数规划
求(a1+a2+a3+a4 ... an)/(b1+b2+b3+b4...bn)最大值的二分算法
(a1+a2+a3+a4)/(b1+b2+b3+b4) >= mid
a1+a2+a3+a4 >= mid(b1+b2+b3+b4)
check函数就变成了：a1-midb1+a2-midb2... >= 0
康托展开 -> 排序的映射
a[i] 代表i位后比s[i]小的个数
hash = a[1](n-1)! + a[2](n-2)! + a[3]*(n-3)! ... a[n]*0!
在菊花图下SPFA退化为Bellman Ford，最坏时间复杂度为O(n^2)
dijkstra 稀疏图 O(mlogm) 模板
struct node{
int u, w;
bool operator<(node other) const {
return w>other.w;
}
};
priority_queue<node> q;
vector<node> mp[maxn];
int vis[maxn];
int dist[maxn];
q.push({1, 0});
while (!q.empty()){
auto tp = q.top(); q.pop();
if (vis[tp.u]) continue;
vis[tp.u] = true;
for (auto it: mp[tp.u]){
if (dist[it.u] > tp.w+it.w){
dist[it.u] = tp.w+it.w;
q.push({it.u, dist[it.u]});
}
}
}
思路：反向建图，多层图
Tarjan算法：有向图的联通分量问题
dfn[x] 表示点x的DFS序成树编号
low[x] 表示x的子数的low[v]最小值
Tarjan求联通分量模板：
int dfn[maxn];
int low[maxn];
int vis[maxn];
int scc[maxn];
int timer=0, ans=0;
vector<int> cnt[maxn];
stack<int> s;
void tarjan(int u){
dfn[u] = low[u] = ++timer;
s.push(u); vis[u]=1;
for (int i=head[u]; ~i; i=nxt[i]){
int v=to[i];
if (!dfn[v]){
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (vis[v]){
low[u] = min(low[u], dfn[v]);
}
}
if (low[u] == dfn[u]){
int v; ans++;
do {
v = s.top(); s.pop();
vis[v] = 0;
scc[v] = ans;
cnt[ans].push_back(v);
} while (u!=v);
}
}
Tarjan求割桥问题模板：
int dfn[maxn];
int low[maxn];
int timer=0;
vector<pair<int, int>> bridge;
vector<int> mp[maxn];
void tarjan(int x, int father){
dfn[x] = low[x] = ++timer;
for (auto it: mp[x]){
if (!dfn[it]){
tarjan(it, x);
low[x] = min(low[x], low[it]);
if (low[it] > dfn[x]){
if (x<it) bridge.push_back({x, it});
else bridge.push_back({it, x});
}
} else {
if (it != father) low[x] = min(low[x], dfn[it]);
}
}
}
Tarjan求割点问题模板
int dfn[maxn];
int low[maxn];
int iscut[maxn];
int timer=0;
vector<int> mp[maxn];
void tarjan(int x, int root){
dfn[x] = low[x] = ++timer;
int son=0;
for (auto it: mp[x]){
if (!dfn[it]){
tarjan(it, root);
low[x] = min(low[x], low[it]);
son++;
if (low[it] >= dfn[x] && x != root){
iscut[x] = 1;
}
} else low[x] = min(low[x], dfn[it]);
}
if (x==root && son>1) iscut[x] = 1;
}
Tarjan缩点模板：
int dfn[maxn];
int low[maxn];
int vis[maxn];
int scc[maxn];
long long sum[maxn];
int timer=0, ans=0;
stack<int> s;
vector<int> mp[maxn];
void tarjan(int u){
dfn[u] = low[u] = ++timer;
s.push(u); vis[u]=1;
for (int i=head[u]; ~i; i=nxt[i]){
int v=to[i];
if (!dfn[v]){
tarjan(v);
low[u] = min(low[v], low[u]);
} else if (vis[v]){
low[u] = min(low[u], dfn[v]);
}
}
if (low[u] == dfn[u]){
int v; ans++;
do {
v = s.top(); s.pop();
vis[v] = 0;
scc[v] = ans;
sum[ans] += a[v];
} while (u != v);
}
}
差分约束系统
若存在点1到x的最短路，则对于任意点y，存在dist[1][x]<=dist[1][y]+dist[y][x]
超级原点，汇点：一个假的点连着所有其他的点，有时可以简化代码量
树形DP思路：换根法，二次扫描法
欧拉序求LCA
初始化O(mlogm)，查询O(1)
lca(a, b) 为a, b在欧拉序第一次出现的区间内最浅的点
重链剖分
将树分为轻链和重链，访问时先访问重链，再根据dfn序构造线段树
实现从a -> b节点之间的O(logn)区间修改
一棵树最多被分成logn个重链
AC 自动机
一种状态自动机，在字典树的基础上加上了类似于kmp的fail的逆边
可以在文本串中查询多个文字串出现的次数和位置
复杂度
模板:
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
const int maxn=2e6+5;
int idx(char c){
return c-'a';
}
struct Trie{
int ch[maxn][30];
int val[maxn];
int fail[maxn]; //最长的后缀相同的节点
int last[maxn]; //最长的后缀相同的单词节点
int vis[maxn];
int ind[maxn];
int sz;
void init() {
memset(ch[0], 0, sizeof ch[0]);
memset(val, 0, sizeof val);
sz=1;
}
int insert(string s){
int u=0;
for (int i=0; i<s.length(); i++){
int x=idx(s[i]);
if (ch[u][x]) u=ch[u][x];
else {
memset(ch[sz], 0, sizeof ch[sz]);
u = ch[u][x] = sz++;
}
} val[u]++; return u;
}
void getfail(){
memset(fail, 0, sizeof fail);
memset(last, 0, sizeof last);
queue<int> q;
fail[0] = 0;
for (int c=0; c<26; c++){
int u=ch[0][c];
if (u){
fail[u] = 0;
last[u] = 0;
q.push(u);
}
}
while (!q.empty()){
int tp=q.front(); q.pop();
for (int c=0; c<26; c++){
int u=ch[tp][c];
if (!u) continue;
q.push(u);
int j=fail[tp];
while (j && !ch[j][c]) j=fail[j];
fail[u] = ch[j][c];
if (val[fail[u]]) last[u] = fail[u];
else last[u] = last[fail[u]];
}
}
}
void find(string t){
memset(vis, 0, sizeof vis);
memset(ind, 0, sizeof ind);
int j=0;
for (int i=0; i<t.length(); i++){
int c=idx(t[i]);
while (j && !ch[j][c]) j=fail[j];
j = ch[j][c]; vis[j]++;
}
vector<int> topo;
queue<int> q;
for (int i=1; i<sz; i++) ind[last[i]]++;
for (int i=1; i<sz; i++) if (ind[i] == 0) q.push(i);
while (!q.empty()){
auto tp=q.front(); q.pop();
topo.push_back(tp);
ind[last[tp]]--;
if (ind[last[tp]] == 0) q.push(last[tp]);
}
for (int i=0; i<sz; i++){
auto tp=topo[i];
vis[last[tp]] += vis[tp];
}
}
};
O(n) 欧拉筛求质数
void init(){
for (int k=2; k<=n; k++){
if (!vis[k]) pri[++cnt]=k;
for (int j=1; j<=cnt && pri[k]*k<=n; j++){
vis[k*pri[j]] = 1;
if (k % pri[j] == 0) break;
}
}
}
O(n) 求欧拉函数 / 其他积性函数
const int maxn=1e5+5;
int p[maxn];
int vis[maxn];
int pri[maxn];
int cnt=0;
void euler(int n){
p[1] = 1;
for (int i=2; i<=n; i++){
if (!vis[i]) {
pri[++cnt] = i;
p[i] = i-1;
}
for (int j=1; j<=cnt && pri[j]*i<=n; j++){
vis[i*pri[j]] = 1;
if (i%pri[j] == 0) {
p[i*pri[j]] = p[i]*pri[j];
break;
} else {
p[i*pri[j]] = p[i]*p[pri[j]];
}
}
}
}
高斯消元
模拟用消元法解n元一次方程，复杂度O(n^3)
#include<iostream>
#include<cstdio>
#include<cmath>
const int maxn=105;
int n;
double f[maxn][maxn];
for (int i=1; i<=n; i++) {
for (int j=1; j<=n+1; j++) cin >> f[i][j];
}
for (int i=1; i<=n; i++){
int l=i; double tmp;
for (int j=i; j<=n; j++){
if (fabs(f[j][i]) > fabs(f[l][i])) l=j;
}
for (int j=1; j<=n+1; j++) swap(f[i][j], f[l][j]);
tmp = f[i][i];
if (fabs(tmp) <= 1e-6) {
cout << "No Solution" << endl;
return 0;
}
for (int j=1; j<=n+1; j++) f[i][j] /= tmp;
for (int j=1; j<=n; j++){
if (j==i) continue;
double r=f[j][i];
for (int k=1; k<=n+1; k++) f[j][k] -= r*f[i][k];
}
}
for (int i=1; i<=n; i++) printf("%.2lf\n", f[i][n+1]);
这里空空如也
有帮助，赞一个