以下内容不定时更新，想到啥写啥。。
读写优化
快读
code
template <class T> inline void read(T &res)
{
char ch = getchar(); bool f = 0; res = 0;
for(; !isdigit(ch); ch = getchar()) f |= ch == '-';
for(; isdigit(ch); ch = getchar()) res = (res << 1) + (res << 3) + (ch ^ 48);
res = f ? ~res + 1 : res;
}
快写
code
template <class T> inline void waw(T x)
{
if(x > 9) waw(x / 10);
putchar(x % 10 ^ 48);
}
template <class T> inline void ww(T x)
{
if(x < 0) x = ~x + 1, putchar('-');
waw(x);
}
基础算法
排序
快排
直接用自带的函数实现即可，sort(起点，终点，排列规则（这个可以没有）)。
归并
通常会用来求逆序对。
code
void merge_sort(int q[], int l, int r)
{
if (l >= r) return;
int mid = l + r >> 1;
merge_sort(q, l, mid);
merge_sort(q, mid + 1, r);
int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r)
if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
else tmp[k ++ ] = q[j ++ ];
while (i <= mid) tmp[k ++ ] = q[i ++ ];
while (j <= r) tmp[k ++ ] = q[j ++ ];
for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}
\(O(n)\) 的基数排序（位运算版本）
最快的排序方法。
code
``` inline void Sort() { static ll p = 65535; for (rl i = 1; i <= n; ++i) c[a[i] & p]++; for (rl i = 1; i <= p; ++i) c[i] += c[i - 1]; for (rl i = n; i >= 1; --i) b[c[a[i] & p]--] = i; memset(c, 0, sizeof c); for (rl i = 1; i <= n; ++i) c[(a[b[i]] >> 16) & p]++; for (rl i = 1; i <= p; ++i) c[i] += c[i - 1]; for (rl i = n; i >= 1; --i) d[c[(a[b[i]] >> 16) & p]--] = b[i]; for (rl i = 1; i <= n; ++i) b[i] = d[i]; } ```排完序后 b 中是排好的序列。
图论
最短路
Floyd
code
for(rl k=1; k <= n; ++ k)
for(rl i=1; i <= n; ++ i)
for(rl j=1; j <= n; ++ j)
g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
// 传递闭包
#define for(i, a, b) for(rl i=a; i <= b; ++ i)
for(k, 1, n)
for(i, 1, n)
for(j, 1, n)
g[i][j] |= g[i][k] & g[k][j];
spfa
code
inline bool spfa()
{
queue<ll> q;
memset(dis, 0x3f, sizeof dis);
dis[s] = 0, q.push(s);
while(!q.empty())
{
ll u = q.front();
q.pop(); st[u] = false;
for(rl i=h[u]; ~i; i = ne[i])
{
ll v = e[i];
if(dis[v] > dis[u] + w[i])
{
dis[v] = dis[u] + w[i];
sla[v] = sla[u] + 1;
if(sla[v] >= n + 2) return true; // 判断是否存在负环
if(!st[v]) st[v] = true, q.push(v);
}
}
}
return true;
}
dijkstra( + heap)
code
struct node
{
ll id, dis;
bool operator <(const node &x) const
{
return dis > x.dis;
}
};
inline void dijkstra()
{
priority_queue<node> q;
memset(dis, 0x3f, sizeof dis);
dis[s] = 0, q.push({s, 0});
while(q.size())
{
auto t = q.top();
q.pop();
ll u = t.id;
if(st[u]) continue;
st[u] = true;
for(rl i=h[u]; ~i; i = ne[i])
{
ll v = e[i];
if(dis[v] > dis[u] + w[i])
{
dis[v] = dis[u] + w[i];
q.push({v, dis[v]});
}
}
}
}
最小生成树
kruskal
code
struct node
{
ll u, v, w;
bool used;
}e[M];
bool cmp(node a, node b) { return a.w < b.w; }
ll find(ll x) { return p[x] == x ? x : p[x] = find(p[x]); }
int main()
{
scanf("%lld %lld", &n, &m);
for(i ,1, n) p[i] = i;
for(i, 1, m) scanf("%lld %lld %lld ", &e[i].u, &e[i].v, &e[i].w);
sort(e + 1, e + m + 1, cmp);
for(i, 1, m)
{
ll a = find(e[i].u), b = find(e[i].v), w = e[i].w;
if(a != b)
{
ans += w;
p[a] = b;
e[i].used = true;
if( ++ cnt = n - 1) break;
}
}
return 0;
}
强连通分量相关
单连通分量
ll dfn[N], low[N], timestamp, dep[N], scc_cnt, scc_size[N];
ll top, stk[N], id[N];
bool in_stk[N];
vector<ll> scc[N];
inline void tarjan(ll u)
{
in_stk[u] = true;
dfn[u] = low[u] = ++ timestamp, stk[ ++ top] = u;
for(rl i=h[u]; ~i; i = ne[i])
{
ll v = e[i];
if(!dfn[v]) { tarjan(v); low[u] = min(low[u], low[v]); }
else if(in_stk[v]) low[u] = min(low[u], low[v]);
}
if(low[u] == dfn[u])
{
ll ele; scc_cnt ++ ;
do {
ele = stk[top -- ], in_stk[ele] = false;
scc_size[scc_cnt] ++, scc[scc_cnt].push_back(ele);
id[ele] = scc_cnt;
} while(ele != u);
}
}
点双连通分量
ll dfn[N], low[N], dcc_cnt, dcc_size[N];
ll stk[N], top, id[N];
bool cut[N];
vector<ll> dcc[N];
inline void tarjan(ll u)
{
dfn[u] = low[u] = ++ timestamp, stk[ ++ top] = u;
if(u == root && h[u] == -1)
{
dcc_cnt ++, dcc[dcc_cnt].push_back(u);
return ;
}
ll cnt = 0;
for(rl i=h[u]; ~i; i = ne[i])
{
ll v = e[i];
if(!dfn[v])
{
tarjan(v), low[u] = min(low[u], low[v]);
if(dfn[u] <= low[v])
{
++ cnt;
if(u != root || cnt > 1) cut[u] = true;
++ dcc_cnt;
ll ele;
do {
ele = stk[ top -- ], dcc[dcc_cnt].push_back(ele);
} while(u != v);
dcc[dcc_cnt].push_back(u);
}
}
else low[u] = min(low[u], dfn[v]);
}
}
边双连通分量
ll dfn[N], low[N], timestamp, id[N], dcc_cnt, dcc_size[N];
ll stk[N], top;
inline void tarjan(ll u, ll from)
{
dfn[u] = low[u] = ++ timestamp;
stk[ ++ top] = u; in_stk[u] = true;
for(rl i=h[u]; ~i; i = ne[i])
{
ll v = e[i];
if(!dfn[v])
{
tarjan(v), low[u] = min(low[u], low[v]);
if(dfn[u] < low[v]) is_bridge[i] = is_bridge[i ^ 1] = true;
}
else if(i != (from ^ 1)) low[u] = min(low[u], dfn[v]);
}
if(dfn[u] == low[u])
{
ll ele;
dcc_cnt ++ ;
do {
ele = stk[top -- ]; dcc_size[dcc_cnt] ++ ;
dcc[dcc_cnt].push_back(ele); id[ele] = dcc_cnt;
} whie(ele != u);
}
匈牙利算法
\(最小点覆盖 \leftrightarrow 最大匹配数 \leftrightarrow 顶点数 - 最小边覆盖 \leftrightarrow 顶点数 - 最大独立集\)
一维
inline bool find(ll u)
{
for(rl i=h[u]; ~i; i = ne[i])
{
ll v = e[i], t = match[v];
if(st[v]) continue;
st[v] = true;
if(!t || find(r)) {match[v] = u; return true; }
}
return false;
}
int main()
{
ll res = 0;
for(i, 1, n)
{
memset(st, 0, sizeof st);
if(find(i)) res ++ ;
}
return 0;
}
二维
typedef pair<ll, ll> pll;
pll match[N][N];
ll dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // 不同的方向数组可能不同
inline bool find(ll x, ll y)
{
for(i, 0, 3)
{
ll a = x + dx[i], b = y + dy[i];
if(a < 1 || a > n || b < 1 || b > m) continue;
if(st[a][b] || g[a][b]) continue; // st 为是否查询过，g 为是否能够放置棋子
st[a][b] = true;
auto = match[a][b];
if(!t.x || find(t.x, t.y)) { match[a][b] = {x, y}; return true; }
}
return false;
}
差分约束
将式子转化为
\[x_a - x'_a \le k
\]
连接从 \(x'_a\) 到 \(x_a\) 一条长度为 \(k\) 的边
倍增法求LCA
code
#define ll long long
#define rl register ll
ll fa[N][M], dep[N];
inline void bfs()
{
memset(dep, 0x3f, sizeof dep);
dep[0] = 0, dep[1] = 1;
ll hh = 0, tt = -1;
q[ ++ tt] = 1;
while(hh <= tt)
{
ll u = q[hh ++ ];
for(rl i=h[u]; ~i; i = ne[i]) // 我的邻接表初始化为-1
{
ll v = e[i];
if(dep[v] > dep[u] + 1)
{
dep[v] = dep[u] + 1;
q[ ++ tt] = v;
fa[v][0] = u;
for(rl k=1; k < 21; ++ k)
fa[v][k] = fa[fa[v][k-1]][k-1];
}
}
}
}
inline ll lca(ll a, ll b)
{
if(dep[a] < dep[b]) swap(a, b);
for(rl i = 21; i >= 0; -- i)
if(dep[fa[a][i]] >= dep[b])
a = fa[a][i];
if(a == b) return a;
for(rl i=21; i >= 0; -- i)
if(fa[a][i] != fa[b][i])
a = fa[a][i], b = fa[b][i];
return fa[a][0];
}
O(1) 复杂度访问LCA
code
ll dep[N], st[M][N], dfn[N], idx;
inline ll get(ll a, ll b) { return dep[a] > dep[b] ? b : a; }
inline void dfs(ll u, ll fa)
{
dep[u] = dep[fa] + 1, dfn[u] = ++ idx, st[0][idx] = fa;
for(rl i=h[u]; ~i; i = ne[i]) { ll v = e[i]; if(v == fa) continue; dfs(v, u); } // 原因同上
}
inline void init()
{
dfs(root, -1);
for(rl j=0; j <= M; ++ j)
for(rl i=1; i + (1 << j) - 1 <= n; ++ i)
st[j][i] = get(st[j - 1][i], st[j - 1][i + (1 << j - 1)]);
}
inline ll lca(ll a, ll b)
{
if(a == b) return a;
if((a = dfn[a]) > (b = dfn[b])) swap(a, b);
ll l = __lg(b - a);
return get(st[l][a + 1], st[l][b - (1 << l) + 1]);
}
数据结构
树状数组（一维，单点修改，区间查询)
如若想要区间修改，单点查询，则只需要对存储的序列进行差分。然后存入树状数组
code
#define lowbit(x) (x & -x)
inline void add(ll x, ll c)
{
for(; x <= n; x += lowbit(x)) tr[x] += c;
}
inline ll sum(ll x)
{
ll res = 0;
for(; x; x -= lowbit(x)) res += tr[x];
return res;
}
树状数组（二维，区间修改，区间查询）
树状数组在存储的时候同样也是存储差分序列。2023-10-12 16:20:18 星期四
code
#define lowbit(x) (x & -x)
ll tr1[N], tr2[N];
inline void add(ll x, ll c)
{
ll i = x - 1;
for(; x <= n; x += lowbit(x)) tr1[x] += c, tr2[x] += i * c;
}
inline void sum(ll x)
{
ll res = 0, resu = 0, i = x;
for(; x; x -= lowbit(x)) res += tr1[x], resu += tr2[x];
return i * res - resu
}
树链剖分
注意下面有打注释的地方不同题目可能不同，只是放了一些常见的操作。
code
inline void add(ll a, ll b) { e[ ++ tot] = {b, h[a]}, h[a] = tot; }
inline void dfs1(ll u, ll p, ll d)
{
fa[u] = p, dep[u] = d, sz[u] = 1;
for(rl i=h[u]; ~i; i = e[i].ne)
{
ll v = e[i].v;
if(v == p) continue;
dfs1(v, u, d + 1);
sz[u] += sz[v];
if(sz[son[u]] < sz[v]) son[u] = v;
}
}
inline void dfs2(ll u, ll t)
{
top[u] = t, id[u] = ++ cnt, nw[cnt] = w[u];
if(!son[u]) return ;
dfs2(son[u], t);
for(rl i=h[u]; ~i; i = e[i].ne)
{
ll v = e[i].v;
if(v == son[u] || v == fa[u]) continue;
dfs2(v, v);
}
}
inline void update(ll u, ll l, ll r, ll k)
{
if(l <= tr[u].l && r >= tr[u].r)
{
tr[u].tag += k, tr[u].minn += k; // 依据题目而不同
return ;
}
pushdown(u); // 如果是区间修改且有懒标记的话，递归前要pushdown
ll mid = tr[u].l + tr[u].r >> 1; // 注意别写成 l + r >> 1
if(l <= mid) update(u << 1, l, r, k);
if(r > mid) update(u << 1 | 1, l, r, k);
pushup(u);
}
inline ll query(ll u, ll l, ll r)
{
ll res = 1e17; // 依据题目求最大值最小值区间和而不同
if(l <= tr[u].l && r >= tr[u].r) return tr[u].minn; // 同上
pushdown(u);
ll mid = tr[u].l + tr[u].r >> 1; // 注意同上
if(l <= mid) res = min(res, query(u << 1, l, r));
if(r > mid) res = min(res, query(u << 1 | 1, l, r)); // 同上
return res;
}
inline void upd_path(ll u, ll v, ll k)
{
while(top[u] != top[v])
{
if(dep[top[u]] < dep[top[v]]) swap(u, v);
update(1, id[top[u]], id[u], k);
u = fa[top[u]];
}
if(dep[u] < dep[v]) swap(u, v);
update(1, id[v], id[u], k);
}
inline ll query_path(ll u, ll v) // 注释的查询路径的东西因题目而不同
{
ll res = 1e17; //
while(top[u] != top[v])
{
if(dep[top[u]] < dep[top[v]]) swap(u, v);
res = min(res, query(1, id[top[u]], id[u])); // query函数一样，但是求和还是最大值还是最小值不同
u = fa[top[u]];
}
if(dep[u] < dep[v]) swap(u, v);
res = min(res, query(1, id[v], id[u])); // 同上
return res;
}
inline void upd_tree(ll u, ll k) // 修改子树
{
update(1, id[u], id[u] + sz[u] - 1, k);
}
inline ll que_tree(ll u) // 查询子树
{
return query(1, id[u], id[u] + sz[u] - 1);
}