算法模版

算法

发布日期: 2023-08-11

文章字数: 5.8k

阅读时长: 34 分

阅读次数:

以下为程序设计竞赛学习经历的积累
其中若有错误恳请斧正,看到会及时修正

一基础算法

1.前缀和

一维

for (int i = 1; i <= n; i++) {
	pre[i] = pre[i - 1] + a[i];
}
// 原始数组a[N],前缀和数组pre[N]
// 预处理后做到O(1)求区间[l,r]的和

$$
\sum_{i=l}^{r}a[i] = pre[r] - pre[l - 1]
$$

二维

for (int i = 1; i <= n; i++) {
	for (int j = 1; j <= m; j++) {
		pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + a[i][j];
	}
}
// 原始数组a[N],前缀和数组pre[N]
// 预处理后做到O(1)求矩形左上角坐标(x1,y1),右下角坐标(x2,y2)的和

$$
\sum_{i=x1}^{x2}\sum_{j=y1}^{y2}a[i][j]=a[i][j] = pre[x2][y2] - pre[x2][y1 - 1] - pre[x1 - 1][y2] + pre[x1 - 1][y1 - 1]
$$

2.差分

一维

for (int i = 1; i <= n; i++) {
	int l, r, c;
	cin >> l >> r >> c;
	b[l] += c;
	b[r + 1] += -c;
}
for (int i = 1; i <= n; i++) {
	b[i] += b[i - 1];
}
//多次对区间运算,可以归为一次

二维

for (int i = 1; i <= n; i++) {
	int x1, y1, x2, y2, c;
	cin >> x1 >> y1 >> x2 >> y2 >> c;
	b[x1][y1] += c;
	b[x1][y2 + 1] -= c;
	b[x2 + 1][y1] -= c;
	b[x2 + 1][y2 + 1] += c;	
}
for (int i = 1; i <= n; i++) {
	for (int j = 1; j <= m; j++) {
		b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
	}
}
//多次对矩形区域运算,可以归为一次

3.二分

//取右区间
int l = 1, r = n;
while (l < r) {
	int mid = l + r + 1 >> 1;
	if (check(mid)) {
		l = mid;
	} else {
		r = mid - 1;
	}
}


//取左区间
int l = 1, r = n;
while (l < r) {
	int mid = l + r >> 1;
	if (check(mid)) {
		r = mid;
	} else {
		l = mid + 1;
	}
}


//实数二分
double eps = 1e-6;
double l = 1, r = n;
while (r - l > eps) {
	double mid = (l + r) / 2;
	if (check(mid)) {
		l = mid;
	} else {
		r = mid;
	}
}

4.高精度

高精度加法

vector<int> add(vector<int>&a, vector<int>&b) {
	vector<int>c(max(a.size(), b.size()) + 9);
	for (int i = 0; i < a.size(); i++) c[i] += a[i];
	for (int i = 0; i < b.size(); i++) c[i] += b[i];
	for (int i = 0; i < c.size(); i++) {
		c[i + 1] += c[i] / 10;
		c[i] %= 10;
	}
	while (c.size() > 1 && c.back() == 0) c.pop_back();
	return c;
}

高精度减法

bool cmp(vector<int>&a, vector<int>&b) {
	if (a.size() != b.size()) return a.size() > b.size();
	for (int i = a.size() - 1; i >= 0; i--) {
		if (a[i] != b[i]) return a[i] > b[i];
	}
	return 1;
}
vector<int> sub(vector<int>&a, vector<int>&b) {
	vector<int>c;
	int t = 0;
	for (int i = 0; i < a.size(); i++) {
		t = a[i] - t;
		if (i < b.size()) t -= b[i];
		c.push_back((t + 10) % 10);
		t = t < 0 ? 1 : 0;
	}
	while (c.size() > 1 && c.back() == 0) c.pop_back();
	return c;
}

高精度乘法

//高精度 X 低精度
vector<int> mul(vector<int>&a, int b) {
	vector<int>c;
	int t = 0;
	for (int i = 0; i < a.size(); i++) {
		t += a[i] * b;
		c.push_back(t % 10);
		t /= 10;
	}
	while (t) {
		c.push_back(t % 10);
		t /= 10;
	}
	while (c.size() > 1 && c.back() == 0) c.pop_back();
	return c;
}


//高精度 X 高精度
vector<int> mul(vector<int>&a, vector<int>&b) {
	vector<int>c(a.size() + b.size() + 9);
	for (int i = 0; i < a.size(); i++) {
		for (int j = 0; j < b.size(); j++) {
			c[i + j] += a[i] * b[j];
		}
	}
	for (int i = 0; i + 1 < c.size(); i++) {
		c[i + 1] += c[i] / 10;
		c[i] %= 10;
	}
	while (c.size() > 1 && c.back() == 0) c.pop_back();
	return c;
}

高精度除法

vector<int> div(vector<int>&a, int &b, int &r) {
	vector<int>c;
	r = 0;
	for (int i = a.size() - 1; i >= 0; i--) {
		r = r * 10 + a[i];
		c.push_back(r / b);
		r %= b;
	}
	reverse(c.begin(), c.end());
	while (c.size() > 1 && c.back() == 0) c.pop_back();
	return c;
}

二数论

1.质数筛

朴素

bool check(int n) {
	if (n < 2) {
		return false;
	}
	for (int i = 2; i * i <= n; i++) {
		if (n % i == 0) {
			return false;
		}
	}
	return true;
}

埃氏筛

bool st[N];
void init(int n) {
	se[0] = st[1] = true;
	for (int i = 2; i <= n; i++) {
		if (!st[i]) {
			for (int j = i * 2; j <= n; j += i) {
				st[j] = true;
			}
		}
	}
}

欧式筛

bool st[N];
int pr[N];
int id;
void init(int n) {
	st[0] = st[1] = true;
	for (int i = 2; i <= n; i++) {
		if (!st[i]) {
			pr[++id] = i;
		}
		for (int j = 1; j <= id && i * pr[j] <= n; j++) {
			st[i * pr[j]] = true;
			if (i % pr[j] == 0) {
				break;
			}
		}
	}
}

2.欧拉函数

朴素

int get(int n) {
	int ans = n;
	for (int i = 2; i * i <= n; i++) {
		if (n % i == 0) {
			ans = ans / i * (i - 1);
			while (n % i == 0) n /= i;
		}
	}
	if (n > 1) {
		ans = ans / n * (n - 1);
	}
	return ans;
}

欧拉函数埃氏筛

int e[N];
void init(int n) {
	for (int i = 1; i <= n; i++) {
		e[i] = i;
	}
	for (int i = 2; i <= n; i++) {
		if (e[i] == i) {
			for (int j = i; j <= n; j += i) {
				e[j] = e[j] / i * (i - 1);
			}
		}
	}
}

欧拉函数欧式筛

bool st[N];
int pr[N], e[N];
int id;
void init(int n) {
	e[1] = 1;
	st[0] = st[1] = true;
	for (int i = 2; i <= n; i++) {
		if (!st[i]) {
			pr[++id] = i;
			e[i] = i - 1;
		}
		for (int j = 1; j <= id && i * pr[j] <= n; j++) {
			st[i * pr[j]] = true;
			if (i % pr[j] == 0) {
				e[i * pr[j]] = e[i] * pr[j];
				break;
			}
			e[i * pr[j]] = e[i] * (pr[j] - 1);
		}
	}
}

3.快速幂&龟速乘

constexpr int mod = 1e9 + 7;
//快速幂
int qpow(int a, int b) {
	int ans = 1 % mod;
	while (b) {
		if (b & 1) {
			ans = ans * a % mod;
		}
		a = a * a % mod;
		b >>= 1;
	}
	return ans;
}


//龟速乘
int mul(int a, int b) {
	int ans = 0;
	while (b) {
		if (b & 1) {
			ans = (ans + a) % mod;
		}
		a = a * 2 % mod;
		b >>= 1;
	}
	return ans;
}

4.扩展欧几里得

//gcd
int gcd(int a, int b) {
	return b ? gcd(b, a % b) : a;
}


//exgcd
//已知a,b,ax+by=gcd(a,b)
//求x,y
int x, y;
int exgcd(int a, int b) {
	if (!b) {
		x = 1, y = 0;
		return a;
	}
	int gcd = exgcd(b, a % b);
	int t = x;
	x = y;
	y = t - a / b * y;
	return gcd;
}

5.组合数

template<typename T>
T qmi(T n, long long k) {
    T res = 1;
    while (k) {
        if (k & 1) res = res * n;
        n *= n;
        k >>= 1;
    }
    return res;
}
template <const int M>
struct ModInt {
    int x;
    int norm(int x) {
        if (x < 0) {
            x += M;
        }
        if (x >= M) {
            x -= M;
        }
        return x;
    }
    ModInt(int x = 0) : x(norm(x % M)) {}
    int val() const {
        return x;
    }
    ModInt operator -() const {
        return ModInt(norm(M - x));
    }
    ModInt inv() const {
        assert(x != 0);
        return qmi(*this, M - 2);
    }
    ModInt &operator *=(const ModInt &rhs) {
        x = (long long)(x) * rhs.x % M;
        return *this;
    }
    ModInt &operator +=(const ModInt &rhs) {
        x = norm(x + rhs.x);
        return *this;
    }
    ModInt &operator -=(const ModInt &rhs) {
        x = norm(x - rhs.x);
        return *this;
    }
    ModInt &operator /=(const ModInt &rhs) {
        return *this *= rhs.inv();
    }
    bool operator < (const ModInt &rhs) {
        return x < rhs.x;
    }
    bool operator == (const ModInt &rhs) {
        return x == rhs.x;
    }
    bool operator != (const ModInt &rhs) {
        return x != rhs.x;
    }
    friend ModInt operator *(const ModInt &lhs, const ModInt &rhs) {
        ModInt res = lhs;
        res *= rhs;
        return res;
    }
    friend ModInt operator +(const ModInt &lhs, const ModInt &rhs) {
        ModInt res = lhs;
        res += rhs;
        return res;
    }
    friend ModInt operator -(const ModInt &lhs, const ModInt &rhs) {
        ModInt res = lhs;
        res -= rhs;
        return res;
    }
    friend ModInt operator /(const ModInt &lhs, const ModInt &rhs) {
        ModInt res = lhs;
        res /= rhs;
        return res;
    }
    friend std::istream &operator >>(std::istream &is, ModInt &a) {
        long long v;
        is >> v;
        a = ModInt(v);
        return is;
    }
    friend std::ostream &operator <<(std::ostream &os, const ModInt &a) {
        return os << a.val();
    }
};
using Z=ModInt<(int)(1e9+7)>;
namespace Combinatorics {
    std::vector<Z> fac, inv;
    void C_init(int n) {
        fac.resize(n + 1);
        inv.resize(n + 1);
        fac[0] = 1;
        for (int i = 1; i <= n; i++) {
            fac[i] = fac[i - 1] * i;
        }
        inv[n] = fac[n].inv();
        for (int i = n; i >= 1; i--) {
            inv[i - 1] = inv[i] * i;
        }
    }
    Z C(int a, int b) {
        if (a < b) return Z(0);
        return fac[a] * inv[b] * inv[a - b];
    }
    Z A(int a, int b) {
        if (a < b) return Z(0);
        return fac[a] * inv[a - b];
    }
    Z H(int a, int b) {
    //  If you want to use it, please open the array length to 2 * n
        return C(a + b - 1, b);
    }
}
using namespace Combinatorics;
//使用时注意模数
//初始化 C_init(n)

6.连续区间位运算

//区间&
int SumAnd(int l, int r) {
	int x = 0;
	while (l < r) {
		l >>= 1;
		r >>= 1;
		x += 1;
	}
	return l << x;
}


//区间|
int SumOr(int l, int r) {
	int x = 0;
	while (l < r) {
		l >>= 1;
		r >>= 1;
		x += 1;
	}
	while (x--) l = l << 1 | 1;
	return l;
}

三图论

1.建图&搜图

//数组存图
int g[N][N];
g[x][y] = z; //添加x->y  权值为z
g[y][x] = z; //添加y->x  权值为z


//链式前向星
struct node {
	int x, y, z;
} g[N]; //双向边数组要加倍
int h[N], idx;
void add(int x, int y, int z) {
	g[idx] = {h[x], y, z};
	h[x] = idx++;
}
//需初始化数组h[N]为-1
for (int i = 0; i < N; i++) {
	h[i] = -1;
}
//遍历   ~i等同于i!=-1
for (int i = h[x]; ~i; i = g[i].x) {

}


//vector存图
vector<pair<int, int>>g[N];
g[x].push_back({y, z}); //添加x->y  权值为z
g[y].push_back({x, z}); //添加y->x  权值为z
//遍历
for (auto [y, z] : g[x]) {

}


//树的深度遍历
vector<vector<pair<int, int>>>g(n + 1);
vector<bool>st(n + 1, 0);
function<void(int, int)>dfs = [&](int x, int fa)->void{
	st[x] = 1;
	for (auto [y, z] : g[x]) {
		if (y == fa || st[y]) {
			continue;
		}
		dfs(y, x);
	}
};


//树的广度遍历
vector<vector<pair<int, int>>>g(n + 1);
vector<bool>st(n + 1);
function<void(int)>bfs = [&](int root)->void{
	queue<int>q;
	st[root] = 1;
	q.push(root);
	while (q.size()) {
		auto x = q.front();
		q.pop();
		for (auto [y, z] : g[x]) {
			if (st[y]) {
				continue;
			}
			q.push(y);
		}
	}
};

2.最短路

Floyd

vector<vector<int>>g(n + 1, vector<int>(n + 1, INF));
auto Floyd = [&]()->void {
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
			}
		}
	}
};
//注意初始化数组 g[i][j] = INF

Dijkstra

//朴素
vector<vector<int>>g(n + 1, vector<int>(n + 1, INF));
auto Dijkstar = [&]()->void {
	vector<int>dis(n + 1, INF);
	vector<bool>st(n + 1, 0);
	dis[1] = 0;
	for (int i = 1; i <= n; i++) {
		int t = -1;
		for (int j = 1; j <= n; j++) {
			if (!st[j] && (t == -1 || dis[t] > dis[j])) {
				t = j;
			}
		}
		st[t] = 1;
		for (int j = 1; j <= n; j++) {
			dis[j] = min(dis[j], dis[t] + g[t][j]);
		}
	}
};
//注意初始化数组 g[i][j] = INF


//堆优化
vector<vector<pair<int, int>>>g(n + 1);
auto Dijkstar = [&]()->void {
	vector<int>dis(n + 1, INF);
	vector<bool>st(n + 1, 0);
	dis[1] = 0;
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>q;
	q.push({0, 1});
	while (q.size()) {
		auto [zz, x] = q.top();
		q.pop();
		if (st[x]) continue;
		st[x] = 1;
		for (auto [y, z] : g[x]) {
			if (dis[y] > dis[x] + z) {
				dis[y] = dis[x] + z;
				q.push({dis[y], y});
			}
		}
	}
};

Bellman-Ford

//朴素
struct node {
	int x, y, z;
};
node g[N];
int dis[N];
auto BellmanFord = [&]()->void {
	vector<int>dis(n + 1, INF);
	dis[1] = 0;
	for (int j = 1; j < n; j++) {
		for (int i = 1; i <= m; i++) {
			auto [x, y, z] = g[i];
			dis[y] = min(dis[y], dis[x] + z); // x->y
			dis[x] = min(dis[x], dis[y] + z); // y->x
		}
	}
};


//队列优化
vector<vector<pair<int, int>>>g(n + 1);
auto SPFA = [&]()->void {
	vector<int>dis(n + 1, INF);
	vector<bool>st(n + 1, 0);
	dis[1] = 0;
	queue<int>q;
	q.push(1);
	while (q.size()) {
		auto x = q.front();
		q.pop();
		st[x] = 0;
		for (auto [y, z] : g[x]) {
			if (dis[y] > dis[x] + z) {
				dis[y] = dis[x] + z;
				if (!st[y]) {
					q.push(y);
					st[y] = 1;
				}
			}
		}
	}
};

3.拓扑排序

vector<int>g[N];
int d[N], top[N];
int id;
void topsort() {
	queue<int>q;
	for (int i = 1; i <= n; i++) {
		if (!d[i]) {
			q.push(i);
		}
	}
	while (q.size()) {
		auto x = q.front();
		q.pop();
		top[++id] = x;
		for (auto y : g[x]) {
			d[y] -= 1;
			if (!d[y]) {
				q.push(y);
			}
		}
	}
}
//id==n 说明存在拓扑序列

4.最小生成树

prim

int g[N][N];
bool st[N];
int dis[N];
int prim() {
	for (int i = 1; i <= n; i++) {
		st[i] = false;
		dis[i] = INF;
	}
	dis[1] = 0;
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		int t = -1;
		for (int j = 1; j <= n; j++) {
			if (!st[j] && (t == -1 || dis[j] < dis[t])) {
				t = j;
			}
		}
		if (dis[t] > INF / 2) {
			return INF;
		}
		st[t] = true;
		ans += dis[t];
		for (int j = 1; j <= n; j++) {
			dis[j] = min(dis[j], g[t][j]);
		}
	}
	return ans;
}
//注意初始化数组
for (int i = 1; i <= n; i++) {
	for (int j = 1; j <= n; j++) {
		g[i][j] = INF;
	}
}

Kruskal

struct node {
	int x, y, z;
	bool friend operator<(node a, node b) {
		return a.z < b.z;
	}
};
node t[N];
struct DSU {
	vector<int>f, siz;
	DSU(int n): f(n + 1), siz(n + 1, 1) {
		for (int i = 1; i <= n; i++) f[i] = i;
	}
	int find(int x) {
		while (x != f[x]) x = f[x] = f[f[x]];
		return x;
	}
	bool same(int x, int y) {
		return find(x) == find(y);
	}
	bool merge(int x, int y) {
		x = find(x);
		y = find(y);
		if (x == y) return false;
		f[y] = x;
		siz[x] += siz[y];
		return true;
	}
	int size(int x) {
		return siz[find(x)];
	}
};
int Kruskal() {
	DSU dsu(n);
	sort(t + 1, t + m + 1);
	int ans = 0, cnt = 0;
	for (int i = 1; i <= m; i++) {
		auto [x, y, z] = t[i];
		if (dsu.same(x, y)) {
			continue;
		}
		cnt += 1;
		dsu.merge(x, y);
		ans += z;
	}
	return (cnt == n - 1 ? ans : INF);
}

5.LCA

vector<int>g[N];
int dep[N], f[N][22];
void dfs(int x, int fa) {
	f[x][0] = fa;
	dep[x] = dep[fa] + 1;
	for (int i = 1; i <= 20; i++) {
		f[x][i] = f[f[x][i - 1]][i - 1];
	}
	for (auto y : g[x]) {
		if (y == fa) {
			continue;
		}
		dfs(y, x);
	}
}
int lca(int x, int y) {
	if (dep[x] < dep[y]) {
		swap(x, y);
	}
	for (int i = 20; i >= 0; i--) {
		if (dep[f[x][i]] >= dep[y]) {
			x = f[x][i];
		}
		if (x == y) {
			return x;
		}
	}
	for (int i = 20; i >= 0; i--) {
		if (f[x][i] != f[y][i]) {
			x = f[x][i];
			y = f[y][i];
		}
	}
	return f[x][0];
}

6.树的直径

//dp形式
int mx = 0;
vector<int>f1(n + 1), f2(n + 1);
function<void(int, int)>dfs = [&](int x, int fa) {
	f1[x] = f2[x] = 0;
	for (auto [y, z] : g[x]) {
		if (y == fa) continue;
		dfs(y, x);
		int t = f1[y] + z;
		if (f1[x] < t) {
			f2[x] = f1[x];
			f1[x] = t;
		} else if (f2[x] < t) {
			f2[x] = t;
		}
	}
	mx = max(mx, f1[x] + f2[x]);
};
dfs(1, 0);

//搜索形式
int mx = 0, p;
function<void(int, int, int)>dfs = [&](int x, int fa, int d) {
	if (mx < d) {
		mx = d;
		p = x;
	}
	for (auto [y, z] : g[x]) {
		if (y == fa) continue;
		dfs(y, x, d + z);
	}
};
dfs(1, 0, 0);
dfs(p, 0, 0);

四数据结构

1.并查集/DSU

struct DSU {
	vector<int>f, siz;
	DSU(int n): f(n + 1), siz(n + 1, 1) {
		for (int i = 1; i <= n; i++) f[i] = i;
	}
	int find(int x) {
		while (x != f[x]) x = f[x] = f[f[x]];
		return x;
	}
	bool same(int x, int y) {
		return find(x) == find(y);
	}
	bool merge(int x, int y) {
		x = find(x);
		y = find(y);
		if (x == y) return false;
		f[y] = x;
		siz[x] += siz[y];
		return true;
	}
	int size(int x) {
		return siz[find(x)];
	}
};

2.单调队列

deque<int>q;
for (int i = 1; i <= n; i++) {
	if (q.size() && q.front() <= i - k) q.pop_front();
	while (q.size() && a[q.back()] >= a[i]) q.pop_back();
	q.push_back(i);
	if (i >= k) {
		cout << a[q.front()] << "\n";
	}
}
// 求k区间长度最小值  队列从小到大
// 求最大值需将第4行代码改为 <= 队列从大到小

3.ST表/RMQ

struct RMQ {
	vector<int>lg;
	vector<vector<int>>f;
	RMQ(int n): lg(n + 1), f(n + 1, vector<int>(33)) {
		lg[0] = -1;
		for (int i = 1; i <= n; i++) {
			f[i][0] = a[i];
			lg[i] = lg[i >> 1] + 1;
		}
		for (int j = 1; j <= lg[n]; j++) {
			for (int i = 1; i + (1 << j) - 1 <= n; i++) {
				f[i][j] = max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
			}
		}
	}
	int query(int l, int r) {
		int t = lg[r - l + 1];
		return max(f[l][t], f[r - (1 << t) + 1][t]);
	}
};

4.树状数组

struct Fenwick {
	int n;
	vector<int>tr;
	Fenwick(int _n): n(_n + 1), tr(_n + 2) {}
	int lowbit(int x) {
		return x & -x;
	}
	void insert(int x, int z) {
		for (int i = x + 1; i <= n; i += lowbit(i)) {
			tr[i] += z;
		}
	}
	int sum(int x) {
		int ans = 0;
		for (int i = x + 1; i >= 1; i -= lowbit(i)) {
			ans += tr[i];
		}
		return ans;
	}
	int query(int l, int r) {
		return sum(r) - sum(l - 1);
	}
};

5.线段树

int a[N];
#define kl k<<1
#define kr k<<1|1
template <typename T>
struct SegmentTree {
	struct node {
		int l, r;
		T sum, add;
		int mid() {
			return l + r >> 1;
		};
	};
	vector<node>t;
	SegmentTree(int n): t(n << 2) {}
	void pushup(int k) {
		t[k].sum = t[kl].sum + t[kr].sum;
	}
	void pushdown(int k) {
		if (!t[k].add) return ;
		t[kl].sum += t[k].add * (t[kl].r - t[kl].l + 1);
		t[kr].sum += t[k].add * (t[kr].r - t[kr].l + 1);
		t[kl].add += t[k].add;
		t[kr].add += t[k].add;
		t[k].add = 0;
	}
	void build(int k, int l, int r) {
		t[k] = {l, r, 0, 0};
		if (l == r) {
			t[k].sum = a[l];
			return ;
		}
		int mid = t[k].mid();
		build(kl, l, mid);
		build(kr, mid + 1, r);
		pushup(k);
	}
	void modify(int k, int l, int r, int x) {
		if (l <= t[k].l && t[k].r <= r) {
			t[k].sum += x * (t[k].r - t[k].l + 1);
			t[k].add += x;
			return ;
		}
		pushdown(k);
		int mid = t[k].mid();
		if (l <= mid) modify(kl, l, r, x);
		if (r > mid) modify(kr, l, r, x);
		pushup(k);
	}
	T query(int k, int l, int r) {
		if (l <= t[k].l && t[k].r <= r) return t[k].sum;
		pushdown(k);
		int ans = 0;
		int mid = t[k].mid();
		if (l <= mid) ans += query(kl, l, r);
		if (r > mid) ans += query(kr, l, r);
		return ans;
	}
};

五字符串

1.哈希

字符串哈希

template<typename T>
T qmi(T n, long long k) {
	T res = 1;
	while (k) {
		if (k & 1) res = res * n;
		n *= n;
		k /= 2;
	}
	return res;
}
template <const int M>
struct ModInt {
	int x;
	int norm(int x) {
		if (x < 0) {
			x += M;
		}
		if (x >= M) {
			x -= M;
		}
		return x;
	}
	ModInt(int x = 0) : x(norm(x % M)) {}
	int val() const {
		return x;
	}
	ModInt operator -() const {
		return ModInt(norm(M - x));
	}
	ModInt inv() const {
		assert(x != 0);
		return qmi(*this, M - 2);
	}
	ModInt &operator *=(const ModInt &rhs) {
		x = (long long)(x) * rhs.x % M;
		return *this;
	}
	ModInt &operator +=(const ModInt &rhs) {
		x = norm(x + rhs.x);
		return *this;
	}
	ModInt &operator -=(const ModInt &rhs) {
		x = norm(x - rhs.x);
		return *this;
	}
	ModInt &operator /=(const ModInt &rhs) {
		return *this *= rhs.inv();
	}
	bool operator < (const ModInt &rhs) {
		return x < rhs.x;
	}
	bool operator == (const ModInt &rhs) {
		return x == rhs.x;
	}
	bool operator != (const ModInt &rhs) {
		return x != rhs.x;
	}
	friend ModInt operator *(const ModInt &lhs, const ModInt &rhs) {
		ModInt res = lhs;
		res *= rhs;
		return res;
	}
	friend ModInt operator +(const ModInt &lhs, const ModInt &rhs) {
		ModInt res = lhs;
		res += rhs;
		return res;
	}
	friend ModInt operator -(const ModInt &lhs, const ModInt &rhs) {
		ModInt res = lhs;
		res -= rhs;
		return res;
	}
	friend ModInt operator /(const ModInt &lhs, const ModInt &rhs) {
		ModInt res = lhs;
		res /= rhs;
		return res;
	}
	friend std::istream &operator >>(std::istream &is, ModInt &a) {
		long long v;
		is >> v;
		a = ModInt(v);
		return is;
	}
	friend std::ostream &operator <<(std::ostream &os, const ModInt &a) {
		return os << a.val();
	}
};
template <typename T, const int P>
struct single_hash {
	int n;
	std::vector<T> h, hi, p;
	single_hash(string s) : n(s.size() - 1), h(n + 1), hi(n + 2), p(n + 1) {
		p[0] = 1;
		for (int i = 1; i <= n; i++) {
			p[i] = p[i - 1] * P;
			h[i] = h[i - 1] * P + s[i];
		}
		for (int i = n; i >= 1; i--) {
			hi[i] = hi[i + 1] * P + s[i];
		}
	}
	T get(int l, int r) {
		return h[r] - h[l - 1] * p[r - l + 1];
	}
	T geti(int l, int r) {
		return hi[l] - hi[r + 1] * p[r - l + 1];
	}
	bool ispalindrome(int l, int r) {
		return get(l, r) == geti(l, r);
	}
	bool same(int l1, int r1, int l2, int r2) {
		return get(l1, r1) == get(l2, r2);
	}
	T MergeFF(int l1, int r1, int l2, int r2) { // Forward and Forward
		return get(l1, r1) * p[r2 - l2 + 1] + get(l2, r2);
	}
	T MergeFR(int l1, int r1, int l2, int r2) { // Forward and reverse
		return get(l1, r1) * p[r2 - l2 + 1] + geti(l2, r2);
	}
	T MergeRF(int l1, int r1, int l2, int r2) { // reverse and Forward
		return geti(l1, r1) * p[r2 - l2 + 1] + get(l2, r2);
	}
	T MergeRR(int l1, int r1, int l2, int r2) { // reverse and reverse
		return geti(l1, r1) * p[r2 - l2 + 1] + geti(l2, r2);
	}
};
using SingleHash1 = single_hash < ModInt < (int)(1e9 + 7) >, 131 >;
using SingleHash2 = single_hash < ModInt < (int)(1e9 + 9) >, 13331 >;

struct DoubleHash : SingleHash1, SingleHash2 {
	using SingleHash1::single_hash;
	using SingleHash2::single_hash;

	DoubleHash(string s) : SingleHash1::single_hash(s), SingleHash2::single_hash(s) {}

	pair<int, int> get(int l, int r) {
		int h1 = SingleHash1::get(l, r).val();
		int h2 = SingleHash2::get(l, r).val();
		return pair<int, int> (h1, h2);
	}
	pair<int, int> geti(int l, int r) {
		int h1 = SingleHash1::geti(l, r).val();
		int h2 = SingleHash2::geti(l, r).val();
		return pair<int, int> (h1, h2);
	}
	bool ispalindrome(int l, int r) {
		return SingleHash1::get(l, r) == SingleHash1::geti(l, r);
		return SingleHash2::get(l, r) == SingleHash2::geti(l, r);
	}
	bool same(int l1, int r1, int l2, int r2) {
		return get(l1, r1) == get(l2, r2);
	}
	pair<int, int> MergeFF(int l1, int r1, int l2, int r2) { // Forward and Forward
		int h1 = SingleHash1::MergeFF(l1, r1, l2, r2).val();
		int h2 = SingleHash2::MergeFF(l1, r1, l2, r2).val();
		return pair<int, int> (h1, h2);
	}
	pair<int, int> MergeFR(int l1, int r1, int l2, int r2) { // Forward and reverse
		int h1 = SingleHash1::MergeFR(l1, r1, l2, r2).val();
		int h2 = SingleHash2::MergeFR(l1, r1, l2, r2).val();
		return pair<int, int> (h1, h2);
	}
	pair<int, int> MergeRF(int l1, int r1, int l2, int r2) { // reverse and Forward
		int h1 = SingleHash1::MergeRF(l1, r1, l2, r2).val();
		int h2 = SingleHash2::MergeRF(l1, r1, l2, r2).val();
		return pair<int, int> (h1, h2);
	}
	pair<int, int> MergeRR(int l1, int r1, int l2, int r2) { // reverse and reverse
		int h1 = SingleHash1::MergeRR(l1, r1, l2, r2).val();
		int h2 = SingleHash2::MergeRR(l1, r1, l2, r2).val();
		return pair<int, int> (h1, h2);
	}
};

散列表

//开放寻址法
int h[N];//一般开两倍以上
int find(int x) {
	int k = (x % N + N) % N;
	while (h[k] != INF && h[k] != x) {
		k += 1;
		if (k == N) k = 0;
	}
	return k;
}

//拉链法
int h[N], e[N], ne[N], idx;
void insert(int x) {
	int k = (x % N + N) % N;
	e[idx] = x;
	ne[idx] = h[k];
	h[k] = idx++;
}
int find(int x) {
	int k = (x % N + N) % N;
	for (int i = h[k]; i != INF; i = ne[i]) {
		if (e[i] == x) {
			return 1;
		}
	}
	return 0;
}

2.KMP

//s主串
//ne数组：当前位置最长相同前后缀的长度，即前缀最后一位下标
vector<int>ne(n + 1);
for (int i = 2, j = 0; i <= n; i++) {
	while (j && p[i] != p[j + 1]) j = ne[j];
	j += p[i] == p[j + 1];
	ne[i] = j;
}
for (int i = 1, j = 0; i <= m; i++) {
	while (j && s[i] != p[j + 1]) j = ne[j];
	j += s[i] == p[j + 1];
	if (j == n) {
		j = ne[j];
		cout << i - n + 1 - 1 << " ";
	}
}


//n-ne[n]表示：字符串的循环结

3.Manacher

struct Manacher {
	int n, mx = 0;
	string s = "<,";
	vector<int>f;
	Manacher(string _s): n(_s.size() - 1), f(n * 2 + 3) {
		for (int i = 1; i <= n; i++) {
			s += _s[i];
			s += ",";
		}
		s += ">";
		n = n * 2 + 2;
		int x = 0, mid = 0;
		for (int i = 1; i <= n; i++) {
			f[i] = i < x ? min(f[mid * 2 - i], x - i) : 1;
			while (s[i - f[i]] == s[i + f[i]]) f[i] += 1;
			if (x < i + f[i]) {
				x = i + f[i];
				mid = i;
			}
			mx = max(mx, f[i] - 1);
		}
	}
};

4.字典树/Trie

int idx, f[N << 5][2], cnt[N << 5];
void insert(int val) {
	int x = 0;
	for (int i = 31; i >= 0; i--) {
		int u = val >> i & 1;
		if (!f[x][u]) {
			f[x][u] = ++idx;
		}
		x = f[x][u];
	}
	cnt[x] += 1;
}
int query(int val) {
	int x = 0, ans = 0;
	for (int i = 31; i >= 0; i--) {
		int u = val >> i & 1;
		if (f[x][!u]) {
			ans += 1 << i;
			x = f[x][!u];
		} else {
			x = f[x][u];
		}
	}
	return ans;
}

六动态规划

七杂项

1.写题模版

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
constexpr int mod = 1e9 + 7;
constexpr int N = 2e5 + 9;

void solve() {

}

constexpr bool test = 0;
signed main() {
	cin.tie(0)->ios::sync_with_stdio(false);
	cout << fixed << setprecision(10);
	int T = 1;
	if (test) cin >> T;
	for (int i = 1; i <= T; i++) solve();
	return 0;
}

2.自动取模

template<typename T>
T qmi(T n, long long k) {
    T res = 1;
    while (k) {
        if (k & 1) res = res * n;
        n *= n;
        k >>= 1;
    }
    return res;
}
template <const int M>
struct ModInt {
    int x;
    int norm(int x) {
        if (x < 0) {
            x += M;
        }
        if (x >= M) {
            x -= M;
        }
        return x;
    }
    ModInt(int x = 0) : x(norm(x % M)) {}
    int val() const {
        return x;
    }
    ModInt operator -() const {
        return ModInt(norm(M - x));
    }
    ModInt inv() const {
        assert(x != 0);
        return qmi(*this, M - 2);
    }
    ModInt &operator *=(const ModInt &rhs) {
        x = (long long)(x) * rhs.x % M;
        return *this;
    }
    ModInt &operator +=(const ModInt &rhs) {
        x = norm(x + rhs.x);
        return *this;
    }
    ModInt &operator -=(const ModInt &rhs) {
        x = norm(x - rhs.x);
        return *this;
    }
    ModInt &operator /=(const ModInt &rhs) {
        return *this *= rhs.inv();
    }
    bool operator < (const ModInt &rhs) {
        return x < rhs.x;
    }
    bool operator == (const ModInt &rhs) {
        return x == rhs.x;
    }
    bool operator != (const ModInt &rhs) {
        return x != rhs.x;
    }
    friend ModInt operator *(const ModInt &lhs, const ModInt &rhs) {
        ModInt res = lhs;
        res *= rhs;
        return res;
    }
    friend ModInt operator +(const ModInt &lhs, const ModInt &rhs) {
        ModInt res = lhs;
        res += rhs;
        return res;
    }
    friend ModInt operator -(const ModInt &lhs, const ModInt &rhs) {
        ModInt res = lhs;
        res -= rhs;
        return res;
    }
    friend ModInt operator /(const ModInt &lhs, const ModInt &rhs) {
        ModInt res = lhs;
        res /= rhs;
        return res;
    }
    friend std::istream &operator >>(std::istream &is, ModInt &a) {
        long long v;
        is >> v;
        a = ModInt(v);
        return is;
    }
    friend std::ostream &operator <<(std::ostream &os, const ModInt &a) {
        return os << a.val();
    }
};
using Z=ModInt<(int)(1e9+7)>;

3.排序

归并排序

vector<int>b(N);
void merge_sort(vector<int>&a, int l, int r) {
	if (l >= r) return ;
	int mid = l + r >> 1;
	merge_sort(a, l, mid), merge_sort(a, mid + 1, r);
	int k = 1, i = l, j = mid + 1;
	while (i <= mid && j <= r) {
		if (a[i] > a[j]) {
			ans += mid - i + 1;
		}
		b[k++] = a[i] <= a[j] ? a[i++] : a[j++];
	}
	while (i <= mid) b[k++] = a[i++];
	while (j <= r) b[k++] = a[j++];
	for (int i = l, j = 1; i <= r;) a[i++] = b[j++];
}

https://blog.shaogy.top/2023/suan-fa-mo-ban/

本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 FW !

算法模版

JavaScript

2023-09-04 JavaScript

JavaScript

CSSflex布局与响应式布局

2023-07-26 CSS

flex布局响应式布局

算法模版

一 基础算法

1.前缀和

一维

二维

2.差分

一维

二维

3.二分

4.高精度

高精度加法

高精度减法

高精度乘法

高精度除法

二 数论

1.质数筛

朴素

埃氏筛

欧式筛

2.欧拉函数

朴素

欧拉函数埃氏筛

欧拉函数欧式筛

3.快速幂&龟速乘

4.扩展欧几里得

5.组合数

6.连续区间位运算

三 图论

1.建图&搜图

2.最短路

Floyd

Dijkstra

Bellman-Ford

3.拓扑排序

4.最小生成树

prim

Kruskal

5.LCA

6.树的直径

四 数据结构

1.并查集/DSU

2.单调队列

3.ST表/RMQ

4.树状数组

5.线段树

五 字符串

1.哈希

字符串哈希

散列表

2.KMP

3.Manacher

4.字典树/Trie

六 动态规划

七 杂项

1.写题模版

2.自动取模

3.排序

归并排序

客官行行好吧！

一基础算法

二数论

三图论

四数据结构

五字符串

六动态规划

七杂项