JZTXT

算法总结

发布时间 2023-09-30 07:51:52作者: Gmor_cerr

排序

Quick_Sort

void Quick_Sort(int q[], int l, int r) {
    if (l >= r) return;

    int i = l - 1, j = r + 1, x = q[(l + r) >> 1];
    while (i < j) {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}

Merge_Sort

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 = 1, 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 (int i = l, j = 1; i <= r; i++, j++) q[i] = tmp[j];
}

二分查找

int search(int a[], int l, int r, int x) { // 查找大于等于x的第一个数字
	int ret = 0;
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (a[mid] >= x) ret = mid, r = mid - ;
		else l = mid + 1;
	}
	return ret;
}

二分答案

// 记录答案写法
while (l <= r) {
	int mid = (l + r) >> 1;
	if (check(mid)) ans = mid, l = mid + 1;
	else r = mid - 1;
}

// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用
while (l < r) {
	int mid = (l + r + 1) >> 1;
	if (check(mid)) l = mid;
	else r = mid - 1;
}

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用
while (l < r) {
	int mid = (l + r) >> 1;
	if (check(mid)) l = mid;
	else r = mid - 1;
}

浮点数二分

double search(double l, double r)
{
    const double eps = 1e-6; // eps 表示精度，取决于题目对精度的要求
    while (r - l > eps)
    {
        double mid = (l + r) >> 1;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

三分

while (r - l > eps) {
  	mid = (lmid + rmid) / 2;
  	lmid = mid - eps;
  	rmid = mid + eps;
  	if (f(lmid) < f(rmid))
  	  r = mid;
 	else
  	  l = mid;
}

前缀和

一维前缀和

s[i] = a[1] + ... + a[i] = s[i-1] + a[i];
a[l] + ... + a[r] = s[r] - s[l-1];

二维前缀和

s[i][j] += s[i-1][j] + s[i][j-1] - s[i-1][j-1];
(x1, y1) + ... + (x2, y2) = s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1];

差分

一维差分

(l - r) + x -> a[l] += x; a[r+1] -= x;

二维差分

(x1, y1 - x2, y2) + x -> s[x1][y1] += x; s[x2+1][y1] -= x; s[x1][y2+1] -= x; s[x2+1][y2+1] += x;

双指针

for (int i = 0, j = 0; i < n; i ++ )
{
    while (j < i && check(i, j)) j ++ ;
    // 具体问题的逻辑
}
//常见问题分类：
//   (1) 对于一个序列，用两个指针维护一段区间
//   (2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作

位运算

n >> k & 1 // 求n的第k位数字
lowbit(n) = n & -n = n & (~n + 1)// 返回n的最后一位1

离散化

特点 : 值域跨度大, 但稀疏

vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end()); // 去掉重复元素

// 二分求出x对应的离散化的值
int find(int x) { // 找到第一个大于等于x的位置
    int l = 0, r = alls.size() - 1;
    while (l < r)
    {
        int mid = (l + r) >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1; // 映射到[1, 2, ...n]
}

快速幂

int ksm(int x, int r) {
	int ret = 1;
	while (r) {
		if (r & 1) ret *= x;
		x *= x;
		r >> 1;
	}
	return ret;
}

矩阵快速幂

void add(LL &a, const &b) { // 取模
	a += b;
	a >= mid ? a -= mid : false;
}

void mul(LL A[N][N], LL B[N][N], LL C[N][N], int n, int s, int m) { // C = A * B;
	for (int i = 0; i < n; i++) 
		for (int j = 0; j <= m; j++) {
			C[i][j] = 0;
			for (int k = 0; k < s; k++)
				add(C[i][j], 1LL * A[i][k] * B[k][j] % mod);
		}
}

while (k) { // ans = a ^ k;
	if (k & 1LL) {
		mul(ans, a, tmp, n, n, n);
		memcpy(ans, tmp, sizeof(ans));
	}
	mul(a, a, tmp, n, n, n);
	memcpy(a, tmp, sizeof(a));
	k >> 1;
}

区间合并

// 将所有存在交集的区间合并
void merge(vector<PII> &segs) {
    vector<PII> res;
    sort(segs.begin(), segs.end());
    int st = -2e9, ed = -2e9;
    for (auto seg : segs)
        if (ed < seg.first) {
            if (st != -2e9) res.push_back({st, ed});
            st = seg.first, ed = seg.second;
        }
        else ed = max(ed, seg.second);
    if (st != -2e9) res.push_back({st, ed});
    segs = res;
}

快读

inline int read() {
	int 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 << 3) + (s << 1) + ch - '0'; ch = getchar();}
	return s * w;
}