

c++算法竞赛常用板子集合(持续更新) - shiranui
source link: https://www.cnblogs.com/shiranui/p/16817296.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

c++算法竞赛常用板子集合(持续更新)
本文主要包含算法竞赛一些常用的板子,码风可能不是太好,还请见谅。
后续会继续补充没有的板子。当然我太菜了有些可能写不出来T^T
稍微有些分类但不多,原谅我QwQ
建议 Ctrl
+ F
以快速查找板子。
此处为查询区间和的树状数组。
int bit[500010];
void add(int k, int x) {
while (k <= n) {
bit[k] += x;
k += lowbit(k);
}
}
int ask(int k) {
int res = 0;
while (k) {
res += bit[k];
k -= lowbit(k);
}
return res;
}
此处为区间修改区间查询区间和的线段树。
struct SegmentTree {
ll sum[N << 2], lazy[N << 2];
int l[N << 2], r[N << 2];
void update(int rt) {
sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}
void pushdown(int rt) {
if (!lazy[rt]) return ;
sum[rt << 1] += (r[rt << 1] - l[rt << 1] + 1) * lazy[rt], lazy[rt << 1] += lazy[rt];
sum[rt << 1 | 1] += (r[rt << 1 | 1] - l[rt << 1 | 1] + 1) * lazy[rt], lazy[rt << 1 | 1] += lazy[rt];
lazy[rt] = 0;
update(rt);
}
void build(int rt, int L, int R) {
l[rt] = L, r[rt] = R;
if (L == R) {
sum[rt] = a[L];
return ;
}
int mid = L + R >> 1;
build(rt << 1, L, mid), build(rt << 1 | 1, mid + 1, R);
update(rt);
}
void change(int rt, int L, int R, int x) {
if (L <= l[rt] && r[rt] <= R) {
sum[rt] += (r[rt] - l[rt] + 1) * x;
lazy[rt] += x;
return ;
}
pushdown(rt);
if (L <= r[rt << 1]) change(rt << 1, L, R, x);
if (l[rt << 1 | 1] <= R) change(rt << 1 | 1, L, R, x);
update(rt);
}
ll query(int rt, int L, int R) {
if (L <= l[rt] && r[rt] <= R) return sum[rt];
pushdown(rt);
ll res = 0;
if (L <= r[rt << 1]) res += query(rt << 1, L, R);
if (l[rt << 1 | 1] <= R) res += query(rt << 1 | 1, L, R);
return res;
}
} tree;
不是吧真有人手写堆吗
ll q[N], cnt;
void pushup(int id) {
while (id > 1) {
if (q[id] >= q[id >> 1]) break;
swap(q[id], q[id >> 1]);
id >>= 1;
}
}
void movedown() {
int id = 1;
while (id << 1 <= cnt) {
if ((id << 1 | 1) <= cnt) {
if (q[id] < min(q[id << 1], q[id << 1 | 1])) break;;
if (q[id << 1] < q[id << 1 | 1]) swap(q[id], q[id << 1]), id <<= 1;
else swap(q[id], q[id << 1 | 1]), id = id << 1 | 1;
}
else {
if (q[id] > q[id << 1]) swap(q[id], q[id << 1]);
break;
}
}
}
void add(ll x) {
q[++cnt] = x;
pushup(cnt);
}
void pop() {
swap(q[1], q[cnt]);
cnt--;
movedown();
}
struct Disjoint_Set {
int p[N], size[N];
void build() {
for (int i = 1; i <= n; i++) p[i] = i, size[i] = 1;
}
int root(int x) {
if (p[x] != x) return p[x] = root(p[x]);
return x;
}
void merge(int x, int y) {
x = root(x), y = root(y);
if (size[x] > size[y]) swap(x, y);
p[x] = y;
size[y] += size[x];
}
bool check(int x, int y) {
x = root(x), y = root(y);
return x == y;
}
} a;
代码实现查询区间 [l,r] 的区间最大值
for (int i = 1; i <= n; i++) st[0][i] = a[i];
for (int j = 1; j <= lg; j++) {
for (int i = 1; i <= n - (1 << j) + 1; i++) {
st[j][i] = max(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
}
}
int l, r, lg2, len;
for (int i = 1; i <= m; i++) {
l = read(), r = read();
lg2 = log2(r - l + 1);
len = 1 << lg2;
printf("%d\n", max(st[lg2][l], st[lg2][r - len + 1]));
}
const int N = 100010;
int last[N], cnt;
struct edge {
int to, next, w;
} e[N << 1];
void addedge(int x, int y, int w) {
e[++cnt].to = y;
e[cnt].next = last[x];
e[cnt].w = w;
last[x] = cnt;
}
此处贴的是 Tarjan法 求LCA。更多方法
struct Disjoint_Set {
int p[N], size[N];
void build() {
for (int i = 1; i <= n; i++) p[i] = i, size[i] = 1;
}
int root(int x) {
if (p[x] != x) return p[x] = root(p[x]);
return x;
}
void merge(int x, int y) {
x = root(x), y = root(y);
if (size[x] > size[y]) swap(x, y);
p[x] = y;
size[y] += size[x];
}
bool check(int x, int y) {
x = root(x), y = root(y);
return x == y;
}
} a;
int last[N], cnt;
struct edge {
int to, next;
} e[N << 1];
void addedge(int x, int y) {
e[++cnt].to = y;
e[cnt].next = last[x];
last[x] = cnt;
}
struct node {
int x, y, ans;
} ask[N];
vector <int> g[N];
int p[N];
bool vis[N];
int r[N];
void dfs(int x, int f) {
p[x] = f;
for (int i = last[x]; i; i = e[i].next) {
int v = e[i].to;
if (v == f) continue;
vis[v] = 1;
for (int j : g[v]) {
int o = ask[j].x;
if (o == v) o = ask[j].y;
if (!vis[o]) continue;
ask[j].ans = r[a.root(o)];
}
dfs(v, x);
a.merge(x, v);
r[a.root(x)] = x;
}
}
单源最短路(Dijkstra)
这里是堆优化版呢。笑了有些时候堆优化还没不优化好
void dij(int s) {
priority_queue <pii, vector<pii>, greater<pii> > q;
memset(dis, 0x7f7f7f7f, sizeof(dis));
q.push({0, s});
dis[s] = 0;
while (!q.empty()) {
pii u = q.top(); q.pop();
int pos = u.second;
if (vis[pos]) continue;
vis[pos] = 1;
for (int j = last[pos]; j; j = e[j].next) {
int v = e[j].to;
if (vis[v]) continue;
if (dis[pos] + e[j].w < dis[v]) dis[v] = dis[pos] + e[j].w, q.push({dis[v], v});
}
}
其中 p 为缩点后的新点。
int dfn[N], low[N], dcnt;
bool instack[N];
stack <int> s;
int p[N], h[N];
void dfs(int x, int f) {
instack[x] = 1;
s.push(x);
dfn[x] = low[x] = ++dcnt;
for (int i = last[0][x]; i; i = e[0][i].next) {
int v = e[0][i].to;
if (dfn[v]) {
if (instack[v]) low[x] = min(low[x], dfn[v]);
continue;
}
dfs(v, x);
low[x] = min(low[x], low[v]);
}
if (low[x] >= dfn[x]) {
p[x] = x, h[x] = a[x], instack[x] = 0;
while (s.top() != x) {
p[s.top()] = x;
h[x] += a[s.top()];
instack[s.top()] = 0;
s.pop();
}
s.pop();
}
}
int st[N], ed[N];
struct edge {
int u, v;
} e[N << 1];
int rd[N], cd[N];
bool cmp(edge x, edge y) {
if (x.u != y.u) return x.u < y.u;
return x.v < y.v;
}
int ans[N << 1], cnt;
void dfs(int x) {
while (st[x] <= ed[x]) {
st[x]++;
dfs(e[st[x] - 1].v);
}
ans[++cnt] = x;
}
fac[0] = fac[1] = 1;
for (int i = 2; i <= n; i++) fac[i] = fac[i - 1] * i % mod;
inv[1] = 1;
for (int i = 2; i <= n; i++) inv[i] = (mod - mod / i) * inv[mod % i] % mod;
ll qpow(ll a, ll b) {
ll res = 1;
while (b) {
if (b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
矩阵快速幂
不是我说这写的是真的丑,凑活着看吧QAQ
struct sq {
ll x[110][110];
void build() {
for (int i = 1; i <= n; i++) x[i][i] = 1;
}
void dd() {
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
x[i][j] = 0;
}
} a, ans;
sq operator *(const sq &x, const sq &y) {
sq res;
res.dd();
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
res.x[i][j] = (res.x[i][j] + x.x[i][k] * y.x[k][j] % mod) % mod;
return res;
}
void qpow(ll x) {
while (x) {
if (x & 1) ans = ans * a;
a = a * a;
x >>= 1;
}
}
p 数组表示基底,x 为添加进的数字。
int p[N];
void add(ll x) {
for (int i = N; i >= 0; i--) {
if (!(x & (1ll << i))) continue;
if (p[i]) x ^= p[i];
else {p[i] = x; return ;}
}
}
int prime[6000010], cnt;
bool isprime[N + 10];
void prim() {
isprime[0] = isprime[1] = 1;
for (int i = 2; i <= n; i++) {
if (!isprime[i]) prime[++cnt] = i;
for (int j = 1; j <= cnt && i * prime[j] <= n; j++) {
isprime[i * prime[j]] = 1;
if (i % prime[j] == 0) break;
}
}
}
字符串哈希
int Char(char c) {
if (c >= '0' && c <= '9') return c - '0' + 1; //0~9: 1~10
if (c >= 'a' && c <= 'z') return c - 'a' + 11; //a~z: 11~37
if (c >= 'A' && c <= 'Z') return c - 'A' + 38; //A~Z: 38~65
return 0;
}
map <ll, int> mp;
cin >> s;
ll x = 0;
for (int i = 0; i < s.size(); i++) x = (x * 100) + Char(s[i]);
mp[x] = 1;
s 和 t 为需要匹配的两个 char
类型数组。
borderi 表示 t 长度为 i 的前缀最长的 border 长度。
完了border是啥来着?
ls = strlen(s + 1), lt = strlen(t + 1);
int j = 0;
for (int i = 2; i <= lt; i++) {
while (j >= 1 && t[j + 1] != t[i]) j = border[j];
if (t[j + 1] == t[i]) j++;
border[i] = j;
}
int sx = 1, tx = 0;
while (sx <= ls) {
while (tx >= 1 && s[sx] != t[tx + 1]) tx = border[tx];
if (t[tx + 1] == s[sx]) tx++;
if (tx == lt) printf("%d\n", sx - lt + 1);
sx++;
}
AC自动机
struct Trie {
int id[27], cnt, fail;
} t[N];
void Build(string &s) {
int now = 0;
for (int i = 0; i < s.size(); i++) {
if (!t[now].id[s[i] - 'a']) t[now].id[s[i] - 'a'] = ++cnt;
now = t[now].id[s[i] - 'a'];
}
t[now].cnt++;
}
void Fail() {
queue <int> q;
for (int i = 0; i < 26; i++) {
int v = t[0].id[i];
if (v != 0) {
t[v].fail = 0;
q.push(v);
}
}
while (!q.empty()) {
int u = q.front(); q.pop();
for (int i = 0; i < 26; i++) {
int v = t[u].id[i];
if (v != 0) {
t[v].fail = t[t[u].fail].id[i];
q.push(v);
}
else t[u].id[i] = t[t[u].fail].id[i];
}
}
}
string s;
int ans;
void Query() {
int now = 0;
for (int i = 0; i < s.size(); i++) {
now = t[now].id[s[i] - 'a'];
for (int to = now; to; to = t[to].fail) {
if (t[to].cnt == -1) break;
ans += t[to].cnt;
t[to].cnt = -1;
}
}
}
Recommend
-
63
前几天在AINLP公众号上分享了国内一个新兴AI算法竞赛平台 FlyAI :
-
19
点击 我爱计算机视觉 标星,更快获取CVML新技术 CVPR 2020 已经公布了大多数workshop的细...
-
8
git常用命令整理(已包括branch、tag等持续更新~) 「 开发工具 」 —— 2018年11月01日 [本文结构] 之前写过一篇文章
-
24
↑ 点击 蓝字 关注极市平台 团队介绍...
-
4
优爱腾古装竞赛迈入“短兵相接”,芒果TV持续旁观文娱商业观察 · 21小时前如果说“选秀”是视频网站2021网综赛道首个火力最为集中的战场,那么剧集赛道无疑在“古装”。
-
3
写ts也有不短的时间了,先凌乱的整理一下日常容易让人困惑的点吧,后续可能按条理整理一下。我要说话 type和interface在主要使用场景下,type和interface的功能是比较重合的,这也是容易造成人困惑的地方。我要说话
-
2
Go 常用的包推荐 (持续更新) 2020年11月17日 | 字数 651 |
-
4
研究了LCA,写篇笔记记录一下。 讲解使用例题 P3379 【模板】最近公共祖先(LCA)。 什么是LCA ...
-
13
V2EX › 推广 我来送自家种的秋月梨啦,分子集合
-
1
Docker常用命令笔记(持续补充更新) 发布:3小时前 更新:3小时前...
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK