目录
*由于被外星人入侵,英文目录无法快速跳转
通用
快读
仅适用于整数的快读:
inline long long read(){
long long s = 0, w = 1;
char ch = getchar();
while (ch < '0' || ch > '9'){
if (ch == '-') w = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9'){
s = s * 10 + ch - '0';
ch = getchar();
}
return s * w;
}
卡常
dfs必备
#pragma GCC target("sse,sse2,sse3,sse4.1,sse4.2,popcnt,abm,mmx,avx")
#pragma comment(linker,"/STACK:102400000,102400000")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
数论
快速幂
计算:\(a ^ b \% p\)
int power(int a, int b, int p){
int ans = 1 % p;
for (; b; b >>= 1){
if (b & 1) ans = (long long)ans * a % p;
a = (long long)a * a % p;
}
return ans;
}
线性筛素数
int n, cnt, p[100000010];
bool v[100000010];
void prime(){
v[1] = 1;
for (int i = 2; i <= n; i++){
if (!v[i]) p[++cnt] = i;
for (int j = 1; p[j] * i <= n; j++){
v[p[j] * i] = 1;
if (i % p[j] == 0) break;
}
}
}
最大公约数
方法:辗转相除
int gcd (int a, int b){
if (b == 0) return a;
return gcd (b, a % b);
//return b ? gcd(b, a % b) : a;
}
int lcm(int a, int b){
return a * b / gcd(a, b);
}
拓展欧几里得
int exgcd(int a, int b, int &x, int &y) {
if (b == 0){
x = 1, y = 0;
return a;
}
int d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
void work1(){
int a, b, x, y, d;
scanf("%d%d", &a, &b);
d = exgcd(a, b, x, y);
printf("gcd(a, b) = %d\n", d);
printf("x = %d, y = %d\n", x, y);
}
void work2(){ //乘法逆元
int n = read(), p = read();
for (int i = 1; i <= n; i++){
int x, y;
exgcd(i, p, x, y);
x = (x % p + p) % p;
printf("%d\n", x); //x是a在mod p下的逆元
}
}
费马小定理
公式: \(a^{p-1} \equiv 1 \pmod{p} (a \nmid p)\) 其中 \(p\) 是素数
应用: 乘法逆元 \(a \times a^{p-2} \equiv 1 \pmod{p} (a \nmid p)\) 其中 \(p\) 是素数
时间复杂度: \(\Theta(\log n)\)
欧拉函数
int n, cnt;
int phi[1000010], p[1000010];
bool vis[1000010];
void getphi(){
phi[1] = 1;
for (int i = 2; i <= n; i++){
if (!vis[i]) p[++cnt] = i, phi[i] = i-1;
for (int j = 1; j <= cnt; j++){
if (i * p[j] > n) break;
vis[i * p[j]] = 1;
if (i % p[j] == 0){
phi[i*p[j]] = phi[i] * p[j];
break;
}
phi[i*p[j]] = phi[i] * (p[j]-1);
}
}
}
数据结构
并查集
const int MAXN = 100010;
int fa[MAXN], n; //有n个点
//int size[MAXN]
int find(int x){
if (x == fa[x]) return x;
return fa[x] = find(fa[x]);
//return (x == fa[x]) ? x : fa[x] = find(fa[x]);
}
void merge(int x, int y){
x = find(x), y = find(y);
fa[x] = y;
//size[y] += size[x];
}
void init(){
for (int i = 1; i <= n; i++) fa[i] = i;
}
线段树1
实现一个数据结构支持区间加,区间求和,具体要求如下
-
1 l r k
把区间 \([l, r]\) 中的每一项增加 \(k\) -
2 l r
求区间 \([l, r]\) 中的每一个数的和
const int MAXN = 100010;
int a[MAXN], n, m;
struct SegmentTree{
int l, r;
long long sum, add;
#define l(x) t[x].l
#define r(x) t[x].r
#define sum(x) t[x].sum
#define add(x) t[x].add
}t[MAXN*4];
void build(int p, int l, int r){
l(p) = l, r(p) = r;
if (l == r){
sum(p) = a[l];
return;
}
int mid = (l + r) >> 1;
build(p*2, l, mid);
build(p*2+1, mid+1, r);
sum(p) = sum(p*2) + sum(p*2+1);
}
void spread(int p){
if (add(p)){
sum(p*2) += add(p) * (r(p*2) - l(p*2) + 1);
sum(p*2+1) += add(p) * (r(p*2+1) - l(p*2+1) + 1);
add(p*2) += add(p);
add(p*2+1) += add(p);
add(p) = 0;
}
}
void change(int p, int l, int r, int d){
if(l <= l(p) && r >= r(p)){
sum(p) += (long long)d * (r(p) - l(p) + 1);
add(p) += d;
return;
}
spread(p);
int mid = (l(p) + r(p)) / 2;
if (l <= mid) change(p*2, l, r, d);
if (r > mid) change(p*2+1, l, r, d);
sum(p) = sum(p*2) + sum(p*2+1);
}
long long ask(int p, int l, int r){
if (l <= l(p) && r >= r(p)) return sum(p);
spread(p);
int mid = (l(p)+r(p)) >> 1;
long long ans = 0;
if (l <= mid) ans += ask(p*2, l, r);
if (r > mid) ans += ask(p*2+1, l ,r);
return ans;
}
void work(){
n = read(), m = read();
for (int i = 1; i <= n; i++)
a[i] = read();
build(1, 1, n);
while (m--){
int flag = read();
if (flag == 1){
int x = read(), y = read(), k = read();
change(1, x, y, k);
}
else{
int x = read(), y = read();
printf("%lld\n", ask(1, x, y));
}
}
}
线段树2
实现一个数据结构支持区间加,区间求和,具体要求如下
-
1 l r k
把区间 \([l, r]\) 中的每一项增乘 \(k\) -
2 l r k
把区间 \([l, r]\) 中的每一项增加 \(k\) -
3 l r
求区间 \([l, r]\) 中的每一个数的和
const int MAXN = 100010;
int a[MAXN], n, m, mo;
struct SegmentTree{
int l, r;
long long sum, add = 0, mul = 1;
#define l(x) t[x].l
#define r(x) t[x].r
#define sum(x) t[x].sum
#define add(x) t[x].add
#define mul(x) t[x].mul
}t[MAXN*4];
void build(int p, int l, int r){
l(p) = l, r(p) = r;
if (l == r){
sum(p) = a[l];
return;
}
int mid = (l + r) >> 1;
build(p*2, l, mid);
build(p*2+1, mid+1, r);
sum(p) = sum(p*2) + sum(p*2+1);
}
void spread(int p){
//更新每段的和
sum(p*2) = (sum(p*2) * mul(p) + add(p) * (r(p*2) - l(p*2) + 1)) % mo;
sum(p*2+1) = (sum(p*2+1) * mul(p) + add(p) * (r(p*2+1) - l(p*2+1) + 1)) % mo;
//先更新乘法懒标记,后更新加法懒标记
mul(p*2) = (mul(p*2) * mul(p)) % mo;
mul(p*2+1) = (mul(p*2+1) * mul(p)) % mo;
add(p*2) = (add(p*2) * mul(p) + add(p)) % mo;
add(p*2+1) = (add(p*2+1) * mul(p) + add(p)) % mo;
//懒标记归位
mul(p) = 1;
add(p) = 0;
}
void change_add(int p, int l, int r, int d){
if(l <= l(p) && r >= r(p)){
sum(p) += d * (r(p) - l(p) + 1), sum(p) %= mo;
add(p) += d, add(p) %= mo;
return;
}
spread(p);
int mid = (l(p) + r(p)) / 2;
if (l <= mid) change_add(p*2, l, r, d);
if (r > mid) change_add(p*2+1, l, r, d);
sum(p) = sum(p*2) + sum(p*2+1), sum(p) %= mo;
}
void change_mul(int p, int l, int r, int d){
if(l <= l(p) && r >= r(p)){
sum(p) *= d, sum(p) %= mo;
mul(p) *= d, mul(p) %= mo;
add(p) *= d, add(p) %= mo;
return;
}
spread(p);
int mid = (l(p) + r(p)) / 2;
if (l <= mid) change_mul(p*2, l, r, d);
if (r > mid) change_mul(p*2+1, l, r, d);
sum(p) = sum(p*2) + sum(p*2+1), sum(p) %= mo;
}
long long ask(int p, int l, int r){
if (l <= l(p) && r >= r(p)) return sum(p) % mo;
spread(p);
int mid = (l(p)+r(p)) >> 1;
long long ans = 0;
if (l <= mid) ans += ask(p*2, l, r), ans %= mo;
if (r > mid) ans += ask(p*2+1, l ,r), ans %= mo;
return ans % mo;
}
void work(){
n = read(), m = read(), mo = read();
for (int i = 1; i <= n; i++)
a[i] = read() % mo;
build(1, 1, n);
while (m--){
int flag = read();
if (flag == 1){
int x = read(), y = read(), k = read() % mo;
change_mul(1, x, y, k);
}
else if (flag == 2){
int x = read(), y = read(), k = read() % mo;
change_add(1, x, y, k);
}
else{
int x = read(), y = read();
printf("%lld\n", ask(1, x, y) % mo);
}
}
}
线段树3
实现一个数据结构支持单点修改,区间求最大子段和,具体要求如下
-
1 l r
求区间 \([l, r]\) 中的最大子段和 \(k\) -
2 x k
把第 \(x\) 项改为 \(k\)
const int MAXN = 500010, inf = 0x7fffffff;
int a[MAXN], n, m;
struct SegmentTree{
int l, r, sum;
int lmax, rmax, mmax;
#define l(x) t[x].l
#define r(x) t[x].r
#define sum(x) t[x].sum
#define m(x) t[x].mmax
#define lm(x) t[x].lmax
#define rm(x) t[x].rmax
}t[MAXN*4];
void update(int p){
sum(p) = sum(p<<1) + sum(p<<1|1);
lm(p) = max(sum(p<<1)+lm(p<<1|1), lm(p<<1));
rm(p) = max(sum(p<<1|1)+rm(p<<1), rm(p<<1|1));
m(p) = max(max(m(p<<1), m(p<<1|1)), rm(p<<1)+lm(p<<1|1));
}
void build(int p, int l, int r){
l(p) = l, r(p) = r;
if (l == r){
sum(p) = m(p) = lm(p) = rm(p) = a[l];
return;
}
int mid = (l + r) >> 1;
build(p<<1, l, mid);
build(p<<1|1, mid+1, r);
update(p);
}
void change(int p, int x, int d){
if(l(p)== r(p)){
sum(p) = m(p) = lm(p) = rm(p) = d;
return;
}
int mid = (l(p) + r(p)) >> 1;
if (x <= mid) change(p<<1, x, d);
if (x > mid) change(p<<1|1, x, d);
update(p);
}
SegmentTree ask(int p, int l, int r){
if (l <= l(p) && r(p) <= r) return t[p];
int mid = (l(p) + r(p)) >> 1;
if(r <= mid) return ask(p<<1, l, r);
if(l > mid) return ask(p<<1|1, l, r);
SegmentTree x = ask(p<<1, l, r), y = ask(p<<1|1, l, r), re;
re.sum = x.sum + y.sum;
re.lmax = max(x.sum+y.lmax, x.lmax);
re.rmax = max(y.sum+x.rmax, y.rmax);
re.mmax = max(max(x.mmax, y.mmax), x.rmax+y.lmax);
return re;
}
void work(){
n = read(), m = read();
for (int i = 1; i <= n; i++)
a[i] = read();
build(1, 1, n);
while (m--){
int flag = read();
if (flag == 1){
int x = read(), y = read();
if (x > y) swap(x, y);
printf("%d\n", ask(1, x, y).mmax);
}
else{
int x = read(), y = read();
change(1, x, y);
}
}
}
树状数组1
实现一个数据结构支持单点加,区间求和,具体要求如下
-
1 i k
把第 \(i\) 项增加 \(k\) -
2 l r
求区间 \([l, r]\) 中的每一个数的和
const int MAXN = 600060;
int n, m, a[MAXN], c[MAXN];
void add(int x, int y){
for (; x <= n; x += x & -x) c[x] += y;
}
int ask(int x){
int ans = 0;
for (; x; x -= x & -x)
ans += c[x];
return ans;
}
void work(){
n = read(), m = read();
for (int i = 1; i <= n; i++)
a[i] = read();
for (int i = 1; i <= n; i++)
add(i, a[i]);
while (m--){
int flag = read();
if (flag == 1){
int x = read(), k = read();
add(x, k);
}
else{
int x = read(), y = read();
printf("%d\n", ask(y) - ask(x-1));
}
}
}
树状数组2
实现一个数据结构支持区间加,区间求和,具体要求如下
-
1 l r k
把区间 \([l, r]\) 中的每一项增加 \(k\) -
2 l r
求区间 \([l, r]\) 中的每一个数的和
const int MAXN = 600010;
int a[MAXN], n, m;
long long c[2][MAXN], sum[MAXN];
long long ask(int k, int x){
long long ans = 0;
for (; x; x -= x & -x) ans += c[k][x];
return ans;
}
void add(int k, int x, int y){
for (; x <= n; x += x & -x) c[k][x] += y;
}
void work(){
n = read(), m = read();
for (int i = 1; i <= n; i++)
a[i] = read(), sum[i] = sum[i-1] + a[i];
while (m--){
int falg = read();
if (falg == 1){
int x = read(), y = read(), k = read();
add(0, x, k);
add(0, y+1, -k);
add(1, x, x * k);
add(1, y+1, -(y+1) * k);
}
else{
int x = read(), y = read();
long long ans = sum[y] + (y+1) * ask(0, y) - ask(1, y);
ans -= sum[x-1] + x * ask(0, x-1) - ask(1, x-1);
printf("%lld\n", ans);
}
}
}
图论
Floyd
基本思想: 动态规划
时间复杂度: \(\Theta(n^3)\)
存图方式: 邻接矩阵
Code
int n, m, d[3333][3333];
void Floyd(){
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (i != j && i != k && j != k)
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
void work(){
n = read(), m = read();
memset(d, 0x3f, sizeof(d));
for (int i = 1; i <= n; i++)
d[i][i] = 0;
for (int i = 1; i <= m; i++){
int x = read(), y = read(), z = read();
d[x][y] = min(d[x][y], z);
}
Floyd();
}
传递闭包
基本思想: Floyd
时间复杂度: \(\Theta(n^3)\)
存图方式: 邻接矩阵
Code
int n, m, d[3333][3333];
void Floyd(){
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (i != j && i != k && j != k)
d[i][j] |= d[i][k] & d[k][j];
}
void work(){
n = read(), m = read();
for (int i = 1; i <= n; i++)
d[i][i] = 1;
for (int i = 1; i <= m; i++){
int x = read(), y = read();
d[x][y] = d[y][x] = 1;
}
Floyd();
}
Dijkstra1
基本思想: 贪心
时间复杂度: \(\Theta(n^2)\)
存图方式: 邻接矩阵
Code
const int MAXN = 3030;
int a[MAXN][MAXN], d[MAXN], n, m, s;
bool v[MAXN];
void Dijkstra(){
memset(d, 0x3f, sizeof(d));
memset(v, false, sizeof(v));
d[s] = 0;
for (int i = 1; i < n; i++){
int x = 0;
for (int j = 1; j <= n; j++)
if (!v[j] && (x == 0 || d[j] < d[x]))
x = j;
v[x] = true;
for (int y = 1; y <= n; y++)
d[y] = min(d[y], d[x] + a[x][y]);
}
}
void work(){
memset(a, 0x3f, sizeof(a));
n = read(), m = read(), s = read();
for (int i = 1; i <= n; i++)
a[i][i] = 0;
for (int i = 1; i <= m; i++){
int x = read(), y = read(), z = read();
a[x][y] = min(a[x][y], z);
}
Dijkstra();
}
Dijkstra2
基本思想: 贪心
时间复杂度: \(\Theta(m \log n)\)
存图方式: 链表
Code
const int MAXN = 1e5 + 10, MAXM = 1e6 +10;
int head[MAXN], ver[MAXM], edge[MAXM], Next[MAXM], d[MAXN];
bool v[MAXN];
int n, m, s, tot;
priority_queue <pair<int, int> > q;
void add(int u, int v, int w){
tot++;
ver[tot] = v, edge[tot] = w;
Next[tot] = head[u], head[u] = tot;
}
void Dijkstra(int st){
memset(d, 0x3f, sizeof(d));
memset(v, 0, sizeof(v));
d[st] = 0;
q.push(make_pair(0, st));
while (!q.empty()){
int x = q.top().second;
q.pop();
if (v[x]) continue;
v[x] = 1;
for (int i = head[x]; i; i = Next[i]){
int y = ver[i], z = edge[i];
if (d[y] > d[x] + z){
d[y] = d[x] + z;
q.push (make_pair(-d[y], y));
}
}
}
}
void work(){
n = read(), m = read(), s = read();
for (int i = 1; i <= m; i++){
int u = read(), v = read(), w = read();
add(u, v, w);
}
Dijkstra(s);
}
Bellman-Ford
即是没有队列优化的SPFA, 中文名: 福特算法, 不常用
基本思想: 迭代
时间复杂度: \(\Theta(n m)\)
存图方式: 数组
Code
const int MAXN = 100010;
int n, m;
int d[MAXN], w[MAXN], ax[MAXN], ay[MAXN];
bool v[MAXN];
void Ford(int s){
d[s] = 0;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
d[ax[j]] = min(d[ax[j]], d[ay[j]] + w[j]);
d[ay[j]] = min(d[ay[j]], d[ax[j]] + w[j]);
}
}
}
void work(){
memset(d, 0x3f, sizeof(d));
memset(w, 0x3f, sizeof(w));
n = read(), m = read();
int s = read();
for (int i = 1; i <= m; i++){
ax[i] = read(), ay[i] = read();
w[i] = read();
}
Ford(s);
}
SPFA
关于SPFA, 它死了……
基本思想: Ford(即队列优化的Ford算法)
时间复杂度: \(\Theta(k m)\), 通常情况下 \(k = 2\), 最坏情况下 \(k = n\)
Code
const int MAXN = 150000;
int head[MAXN], ver[MAXN], edge[MAXN], Next[MAXN], d[MAXN];
int n, m, tot, s;
bool v[MAXN];
queue <int> q;
void add(int x, int y, int z){
tot++;
ver[tot] = y, edge[tot] = z, Next[tot] = head[x], head[x] = tot;
}
void spfa(int i){
memset(d, 0x3f, sizeof(d));
//memset(v, 0, sizeof(v));
d[i] = 0;
v[i] = 1;
q.push(i);
while(!q.empty()){
int x = q.front();
q.pop();
v[x] = 0;
for (int i = head[x]; i; i = Next[i]){
int y = ver[i];
long long z = edge[i];
if (d[y] > d[x]+z){
d[y] = d[x]+z;
if (!v[y]) q.push(y), v[y] = 1;
}
}
}
}
void work(){
n = read(), m = read(), s = read();
for (int i = 1; i <= m; i++){
int x = read(), y = read(), z = read();
add(x, y, z), add(y, x, z);
}
spfa(s);
}
倍增求LCA
const int SIZE = 500010;
int n, m, s, tot, t;
int f[SIZE][41], d[SIZE];
int ver[2*SIZE], Next[2*SIZE], head[SIZE];
queue <int> q;
void add(int x, int y){
tot++;
ver[tot] = y;
Next[tot] = head[x];
head[x] = tot;
}
void bfs(){
q.push(s);
d[s] = 1;
while (q.size()){
int x = q.front();
q.pop();
for (int i = head[x]; i; i = Next[i]){
int y = ver[i];
if (d[y]) continue;
d[y] = d[x] + 1;
f[y][0] = x;
for (int j = 1; j <= t; j++)
f[y][j] = f[f[y][j-1]][j-1];
q.push(y);
}
}
}
int lca(int x, int y){
if (d[x] > d[y]) swap(x, y);
for (int i = t; i >= 0; i--)
if (d[f[y][i]] >= d[x])
y = f[y][i];
if (x == y) return x;
for (int i = t; i >= 0; i--)
if (f[x][i] != f[y][i])
x = f[x][i], y = f[y][i];
return f[x][0];
}
void work(){
n = read(), m = read(), s = read();
t = (int)(log(n) / log(2)) + 1;
for (int i = 1; i <= n-1; i++){
int x = read(), y = read();
add(x, y), add(y, x);
}
bfs();
for (int i = 1; i <= m; i++){
int x = read(), y = read();
printf("%d\n", lca(x, y));
}
}