当前位置： 首页 > news >正文

基本算法

news 2025/9/16 2:48:09

1. 二分与三分

二分

lower_bound 和 upper_bound

在从小到大的排好序的数组中，在数组的 [begin, end) 区间中二分查找第一个大于等于（大于）大于 value 的数，找到返回该数字的地址，没找到则返回 end

lower_bound(begin, end, value);		//>=
upper_bound(begin, end, value);		//>

拓展：
用 greater<type>() 重载
在从大到小的排好序的数组中，在数组的 [begin, end) 区间中二分查找第一个小于等于（小于）value 的数，找到返回该数字的地址，没找到则返回 end

lower_bound (begin, end, value, greater<int>())		//<=
upper_bound (begin, end, value, greater<int>())		//<

整数二分

左闭右开 (也适用于二分答案)

bool check (int x) { } // 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int lowerBound (int l, int r)
{while (l < r){int mid = l + (r - l >> 1);if (check (mid))		//if (a[mid]>=x)r = mid;elsel = mid + 1;}return l;
}// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int upperBound (int l, int r)
{while (l < r){int mid = l + (r - l + 1 >> 1);if (check (mid))l = mid;elser = mid - 1;}return l;
}

左闭右闭 (仅适用于二分查找)

int binaySearch(vector<int> &a, int k)
{int l = 0, r = a.size() - 1;while (l <= r ){int mid = l + (r - l >> 1);if (a[mid] == k)return mid;	elsea[mid] > k ? r = mid - 1 : l = mid + 1;		}
}

实数二分

bool check (double x) {}double bsearch_3 (double l, double r)
{const double eps = 1 e-6;while (r - l > eps){double mid = l + (r - l) / 2;if (check (mid))r = mid;elsel = mid;}return l;
}

三分

整数三分

int l, r;
while (r - l > 2) 
{  int midl = l + (r - l) / 3, midr = r - (r - l) / 3;if (check (midl) <= check (midr)) l = midl; // 这里是求凸形函数；如果求凹形，那么改为 r = midrelse r = midr;
}
int res = 1e9;
for (int i = l; i <= r; i++) res = min (res, check (i)); // 找到[l, r]区间的范围

实数三分

double l, r;
while (r - l > eps) 
{double midl = l + (r - l) / 3, midr = r - (r - l) / 3;if (check (midl) <= check (midr)) l = midl; // 这里是求凸形函数；如果求凹形，那么改为 r = midrelse r = midr;
}

2. 前缀和与差分

一维

a[i] = b[1] + b[2] + ... + b[i]
b[l] + ... + b[r] = a[r] - a[l - 1]//给区间[l, r]中的每个数加上d：
b[l] += d, b[r + 1] -= d

二维

a[i, j] // 第i行j列格子左上部分所有元素的和a[i][j] 
= (a[i - 1][j] + a[i][j - 1]) 
- a[i - 1][j - 1] 
+ b[i][j]//以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
a[x2, y2] - a[x1 - 1, y2] - a[x2, y1 - 1] + a[x1 - 1, y1 - 1]//给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上d：
a[x1, y1] += d, a[x2 + 1, y1] -= d, a[x1, y2 + 1] -= d, a[x2 + 1, y2 + 1] += d

三维

a[i, j ,k]	// 第i行j列k高度格子左上部分所有元素的和a[i][j][k] 
= (a[i - 1][j][k] + a[i][j - 1][k] + a[i][j][k - 1]) 
- (a[i - 1][j - 1][k] + a[i - 1][j][k - 1] + a[i][j - 1][k - 1]) 
+ a[i - 1][j - 1][k - 1] 
+ b[i][j][k];//以(x1, y1, z1)为左上角，(x2, y2, z2)为右下角的子矩阵的和为：
a[x2][y2][z2]
- a[x1 - 1][y2][z2] - a[x2][y1 - 1][z2] - a[x2][y2][z1 - 1]
+ a[x1 - 1][y1 - 1][z2] + a[x1 - 1][y2][z1 - 1] + a[x2][y1 - 1][z1 - 1]
- a[x1 - 1][y1 - 1][z1 - 1]//给以(x1, y1, z1)为左上角，(x2, y2, z2)为右下角的子矩阵中的所有元素加上d：
a[x1][y1][z1] += d;
a[x1][y2 + 1][z1] -= d;
a[x2 + 1][y1][z1] -= d;
a[x2 + 1][y2 + 1][z1] += d;
a[x1][y1][z2 + 1] -= d;
a[x1][y2 + 1][z2 + 1] += d;
a[x2 + 1][y1][z2 + 1] += d;
a[x2 + 1][y2 + 1][z2 + 1] -= d;

const int N = 110;
ll n, a[N][N][N], q;void solve ()
{ll i, j, k;scanf ("%lld", &n);for (i = 1; i <= n; i++){for (j = 1; j <= n; j++){for (k = 1; k <= n; k++){scanf ("%lld", &a[i][j][k]);a[i][j][k] += a[i][j][k - 1];}}}for (i = 1; i <= n; i++){for (j = 1; j <= n; j++){for (k = 1; k <= n; k++){a[i][j][k] += a[i][j - 1][k];}}}for (i = 1; i <= n; i++){for (j = 1; j <= n; j++){for (k = 1; k <= n; k++){a[i][j][k] += a[i - 1][j][k];}}}scanf ("%lld", &q);while (q--){ll x1, x2, y1, y2, z1, z2;scanf ("%lld%lld%lld%lld%lld%lld", &x1, &x2, &y1, &y2, &z1, &z2);ll ans = a[x2][y2][z2];ans -= a[x1 - 1][y2][z2];ans -= a[x2][y1 - 1][z2];ans -= a[x2][y2][z1 - 1];ans += a[x1 - 1][y1 - 1][z2];ans += a[x1 - 1][y2][z1 - 1];ans += a[x2][y1 - 1][z1 - 1];ans -= a[x1 - 1][y1 - 1][z1 - 1];printf ("%lld\n", ans);}
}

前缀 GCD 与后缀 GCD

problem - 6025 (hdu.edu.cn)

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n + 1), L(n + 1), R(n + 1);	// 定义数组 a 和前缀 L、后缀 R    for (int i = 1; i <= n; i++)	cin >> a[i];// 构造前缀 GCD 数组 L
    L[1] = a[1];
    for (int i = 2; i <= n; i++)	
    	L[i] = __gcd(L[i - 1], a[i]);// 构造后缀 GCD 数组 R
    R[n] = a[n];
    for (int i = n - 1; i >= 1; i--)
        R[i] = __gcd(R[i + 1], a[i]);// 初始化答案为移除第一个元素或移除最后一个元素时的 GCD
    int ans = max(L[n - 1], R[2]);// 遍历中间的元素，计算移除该元素时的 GCD
    for (int i = 2; i <= n - 1; i++)
        ans = max(ans, __gcd(L[i - 1], R[i + 1]));    cout << ans << endl;	// 输出最大 GCD
}

3. 高精度

加法

// C = A + B, A >= 0, B >= 0
vector<int> add(vector<int> &A, vector<int> &B)
{if (A.size() < B.size()) return add(B, A);vector<int> C;int t = 0;for (int i = 0; i < A.size(); i ++ ){t += A[i];if (i < B.size()) t += B[i];C.push_back(t % 10);t /= 10;}if (t) C.push_back(t);return C;
}

减法

// C = A - B, 满足A >= B, A >= 0, B >= 0
vector<int> sub(vector<int> &A, vector<int> &B)
{vector<int> C;for (int i = 0, t = 0; i < A.size(); i ++ ){t = A[i] - t;if (i < B.size()) t -= B[i];C.push_back((t + 10) % 10);if (t < 0) t = 1;else t = 0;}while (C.size() > 1 && C.back() == 0) C.pop_back();return C;
}

乘法

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

除法

  • 高精度除以低精度
// A / b = C ... r, A >= 0, b > 0
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;
}

4. 双指针

int i = 0, j = n - 1;
while (i < j)
{... i++;j--;
}for (int i = 0, j = n - 1; i < j; i++, j--)
{}

5. 离散化

模板 1

vector<int> arr; 					// 存储所有待离散化的值
sort (arr.begin (), arr.end ()); 	// 将所有值排序
arr.erase (unique (arr.begin (), arr.end ()), arr.end ());   // 去掉重复元素// 二分求出 x 对应的离散化的值
int find (int x) // 找到第一个大于等于 x 的位置
{int l = 0, r = arr.size () - 1;while (l < r){int mid = l + r >> 1;if (arr[mid] >= x) r = mid;else l = mid + 1;}return r + 1; // 映射到 1, 2, ... N
}

模板 2

vector<int> tmp (arr); sort (tmp.begin (), tmp.end ());tmp.erase (unique (tmp.begin (), tmp.end ()), tmp.end ());for (int i = 0; i < n; i++)arr[i] = lower_bound (tmp.begin (), tmp.end (), arr[i]) - tmp.begin ();

模板 3

struct Data 
{int idx, val;bool operator<(const Data& o) const {if (val == o.val)return idx < o.idx;  // 当值相同时，先出现的元素离散化后的值更小return val < o.val;}
} tmp[maxn];  // 也可以使用 pairfor (int i = 1; i <= n; i++) tmp[i] = (Data){i, arr[i]};sort (tmp + 1, tmp + n + 1);for (int i = 1; i <= n; ++i) arr[tmp[i].idx] = i;

6. 排序与排列

排序

sort

sort (a.begin (), a.end ());//less<int>()		//1 2 3 4 5
sort (a.begin (), a.end (), greater<int>());	//5 4 3 2 1bool cmp (...)
{...
}
sort (a.begin (), a.end (), cmp);//lambda表达式
sort(a.begin(), a.end(), [](int x,int y){return x>y;} );
原本应该是这样的:
sort(a.begin(), a.end(), [](int x,int y) -> bool {return x>y;} );
C++可以自动识别函数返回值得数据类型，所以可以简写

struct cri
{int a, b, v;bool operator<(const cri &x) const{return v < x.v;}
} a[N];sort (a + 1, a + n + 1);struct cri
{int a, b, v;bool operator>(const cri &x) const{return v > x.v;}
} a[N];sort (a + 1, a + n + 1, greater<cri>());

冒泡排序

// 假设数组的大小是 n + 1，冒泡排序从数组下标 1 开始 
void bubble_sort(int *a, int n)
{bool flag = true;while (flag){flag = false;for (int i = 1; i < n; ++i){if (a[i] > a[i + 1]){flag = true;int t = a[i];a[i] = a[i + 1];a[i + 1] = t;}}}
}

插入排序

  • 直接插入排序
void insertion_sort(int arr[], int len)
{for (int i = 1; i < len; ++i){ int key = arr[i]; int j = i - 1; while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j--;}arr[j + 1] = key;}
}
  • 折半插入排序
void insertion_sort(int arr[], int len)
{if (len < 2) return;for (int i = 1; i != len; ++i){int key = arr[i];auto index = upper_bound(arr, arr + i, key) - arr; // 使用 memmove 移动元素，比使用 for 循环速度更快，时间复杂度仍为 O(n) memmove(arr + index + 1, arr + index, (i - index) * sizeof(int));arr[index] = key;}
}

选择排序

#include <utility> void selection_sort(int* a, int n) 
{for (int i = 1; i < n; ++i) { int ith = i; for (int j = i + 1; j <= n; ++j) if (a[j] < a[ith])	ith = j;swap(a[i], a[ith]); }
}

快速排序

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);
}

归并排序

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];
}

桶排序

constexpr int N = 100010;
int n, w, a[N];
vector<int> bucket[N];void insertion_sort(vector<int> &A)
{
    for (int i = 1; i < A.size(); ++i)
    {
        int key = A[i];
        int j = i - 1;
        while (j >= 0 && A[j] > key)
        {
            A[j + 1] = A[j];
            --j;
        }
        A[j + 1] = key;
    }
}void bucket_sort()
{
    int bucket_size = w / n + 1;
    for (int i = 0; i < n; ++i)		
    	bucket[i].clear();
    for (int i = 1; i <= n; ++i)	 
    	bucket[a[i] / bucket_size].push_back(a[i]);    int p = 0;
    for (int i = 0; i < n; ++i)
    {
        insertion_sort(bucket[i]);
        for (int j = 0; j < bucket[i].size(); ++j)
            a[++p] = bucket[i][j];
    }
}

int a[maxn], bucket[N];
void solve()
{
    int n;
    cin >> n;
    
    for (int i = 1; i <= n; ++i)
    {
        a[i] = read();
        bucket[a[i]]++;
    }
    
    for (int i = 0; i <= 1000000; ++i)
    {
        for (int j = 1; j <= bucket[i]; ++j)
            write(i), puts("");
    }
}

希尔排序

template <typename T>
void shell_sort(T array[], int length)
{
    int h = 1;
    while (h < length / 3)
        h = 3 * h + 1;
        
    while (h >= 1)
    {
        for (int i = h; i < length; i++)
        {
            for (int j = i; j >= h && array[j] < array[j - h]; j -= h)
                swap(array[j], array[j - h]);
        }
        h = h / 3;
    }
}

排列

next_permutation 与 prev_permutation

do
{...
}while (next_permutation (v.begin (), v.end ()));
//while (next_permutation (v.begin (), v.end (), cmp));
//获取下一个排列 do
{...
}while (prev_permutation (v.begin (), v.end ()));
//while (prev_permutation (v.begin (), v.end (), cmp));
//获取上一个排列

7. 区间合并

// 将所有存在交集的区间合并
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;
}

8. 倍增

利用二进制本身的特性，把一个数 \(N\) 用二进制展开，即

\[N=a_02^0+a_12^1+a_22^2+a_32^3+a_42^4+\cdots \]

二进制划分反映了一种快速增长的特性，第 \(i\) 位的权值 \(2^i\) 等于前面所有权值的和加 \(1\) ，即

\[2^i=2^{i-1}+2^{i-2}+\cdots+2^1+2^0+1 \]

一个整数 \(n\) ，它的二进制只有 \(log_{2}n\) 位。如果要从 \(0\) 增长到 \(n\) ，可以以 \(1,\;2,\;4,\;\cdots,\;2^k\) 为“跳板”，快速跳到 \(n\)，这些跳板只有 \(k=log_2n\) 个。

倍增法的局限性是需要提前计算出第 \(1,\;2,\;4,\;\cdots,\;2^k\) 个跳板，这要求数据是静态不变的，不是动态变化的。如果数据发生了变化，那么所有跳板需要重新计算，跳板就失去了意义。

P 4155 [SCOI 2015] 国旗计划 - 洛谷 | 计算机科学教育新生态 (luogu. com. cn)

int n, m;
int n2;
int go[N][20];
int res[N];
struct peo
{
    int id, l, r;
    bool operator<(const peo a) { return l < a.l; }
} p[N * 2];void init()
{
    int nxt = 1;
    for (int i = 1; i <= n2; i++)
    {
        while (nxt <= n2 && p[nxt].l <= p[i].r)
            nxt++;
        go[i][0] = nxt - 1;
    }
    for (int i = 1; (1 << i) <= n; i++)
        for (int s = 1; s <= n2; s++)
            go[s][i] = go[go[s][i - 1]][i - 1];
}void getans(int x)
{
    int len = p[x].l + m, cur = x, ans = 1;
    for (int i = log2(N); i >= 0; i--)
    {
        int pos = go[cur][i];
        if(pos && p[pos].r < len)
        {
            ans += 1 << i;
            cur = pos;
        }
    }
    res[p[x].id] = ans + 1;
}void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        p[i].id = i;
        cin >> p[i].l >> p[i].r;
        if (p[i].r < p[i].l)
            p[i].r += m;
    }
    sort(p + 1, p + n + 1);
    n2 = n;
    for (int i = 1; i <= n; i++)
    {
        n2++;
        p[n2] = p[i];
        p[n2].l = p[i].l + m;
        p[n2].r = p[i].r + m;
    }
    init();
    for (int i = 1; i <= n;i++)
        getans(i);
    for (int i = 1; i <= n;i++)
        cout << res[i] << ' ';
}

9. 分治

普通分治

将整个问题分解成若干小问题后再分而治之。如果分解得到的子问题相对来说还是太大，则可反复使用分治策略将这些子问题分成更小的同类型子问题，直至产生方便求解的子问题，必要时逐步合并这些子问题的解，从而得到问题的解。

分治算法可以由递归过程来表示，因为分治法就是一种找大规模问题与小规模问题关系的方法，是递归设计的一种具体策略

汉诺塔

void move(char from , char to) 
{cout << "Move" << from << "to" << to <<endl;
}
void Hanoi(int n, char A, char B, char C)
{if(n==1)move(A, C);else{Hanoi(n - 1, A, C, B);move(A, C);Hanoi(n - 1, B, A, C);}
}
int main()
{int n;cin >> n;Hanoi(n,'A','B','C');return 0;
}

根号分治

询问根据一个阈值设为 S 分为两部分。两个部分用不同的算法处理，一部分可以用 暴力直接处理，另一部分可以通过 预处理和动态维护。

P 8572 [JRKSJ R 6] Eltaw - 洛谷 | 计算机科学教育新生态 (luogu. com. cn)

#include<bits/stdc++.h>
using namespace std;
#define int long long
int c[705][705];
signed main()
{
    int n, k, q;
    cin >> n >> k >> q;
    vector<vector<int> > a(k + 1, vector<int>(n + 1));	//int a[n + 1][k + 1];
    for (int i = 1; i <= k;i++)
        for (int j = 1; j <= n;j++)
        {
            int x;
            cin >> x;
            a[i][j] = a[i][j - 1] + x;
        }    if(n<=700)
    {
        for (int i = 1; i <= k;i++)
            for (int j = 1; j <= n;j++)
                for (int p = 1; p <= n;p++)
                    c[j][p] = max(c[j][p], a[i][p] - a[i][j - 1]);
                    
        while(q--)
        {
            int l, r;
            cin >> l >> r;
            cout << c[l][r] << endl;
        }        return 0;
    }        while(q--)
    {
        int l, r, mx = 0;
        cin>>l>>r;
        for (int i = 1; i <= k;i++)
            mx = max(mx, a[i][r] - a[i][l - 1]);        cout << mx << endl;
    }
}

10. 贪心法与拟阵

贪心算法及其理论依据——拟阵 - MwingFly - 博客园
贪心算法与拟阵理论-CSDN博客
贪心与拟阵_拟阵与贪心算法-CSDN博客

11.模拟

例题 1

题目描述 ： 7-2 奥运排行榜(编程题)-CSDN博客

struct node
{
    int id;
    double a[4];
} s[N];int t;
int rank_[N][N];void solve()
{
    int n, m, k;
    cin >> n >> m;    for (int i = 0; i < n; i++)
    {
        cin >> s[i].a[0] >> s[i].a[1] >> k;
        s[i].id = i;
        s[i].a[2] = s[i].a[0] / k;
        s[i].a[3] = s[i].a[1] / k;
    }    for (t = 0; t < 4; t++)
    {
        sort(s, s + n, [](node a, node b){ return a.a[t] > b.a[t]; });
        
        rank_[s[0].id][t] = 1;
        
        for (int i = 1; i < n; i++)
        {
            if (s[i].a[t] == s[i - 1].a[t])
                rank_[s[i].id][t] = rank_[s[i - 1].id][t];
            else
                rank_[s[i].id][t] = i + 1;
        }
    }    int ask;
    
    for (int i = 0; i < m; i++)
    {
        cin >> ask;
        
        int k = 0;
        
        for (int j = 1; j < 4; j++)
            if (rank_[ask][j] < rank_[ask][k])
                k = j;        if (i != 0)
            cout << ' ';
        cout << rank_[ask][k] << ":" << k + 1;
    }
}
http://www.vanclimg.com/news/159.html

相关文章：

  • JimuReport 积木报表 v2.1.1 版本发布，免费开源的报表和大屏设计
  • 一期6.文本摘要（md版）
  • 虚拟机之间实现免密登录，SSH密钥认证
  • 新认识了一个既简单又好用的AI修图工具丨PhotoDirector Ultra 2025 v16.6 相片大师
  • LGP4171 [JSTS 2010] 满汉全席 学习笔记
  • 2025年7款效率翻倍项目管理软件工具清单，项目经理生存手册！
  • Java初步了解
  • 微服务学习-01-微服务技术栈导学
  • CVE-2021-25646 Apache Druid 远程代码执行漏洞 (复现)
  • 9N90-ASEMI工业驱动专用9N90
  • 读后感
  • 我的 10 级 Claude Code 速查表让你几分钟内变专家（你现在是第几级？）
  • Docker容器服务端口探测 - Leonardo
  • Docker搭建Hadoop集群
  • 总结与计划 7.28
  • Inventory System Plugin
  • 联邦学习中的持续学习技术
  • CHO细胞抗体表达｜重组抗体纯化｜高效抗体生产
  • new
  • （阶段二：落地） CMS 模板系统核心数据结构与流程梳理（SceneStack）
  • CAXA3D 实体设计2025最新版本下载安装图文教程，一键快速安装激活
  • 前端开发者的利器：6款最强类EXCEL表格插件对比，轻松实现Excel级交互
  • 软考系统分析师每日学习卡 | [日期：2025-07-28] | [今日主题：操作系统概述]
  • xshell的正则表达式
  • Linux查看PCIe版本及速率
  • 盈鹏飞嵌入式带你玩转T113系列tina5 SDK(7)-使用ADB来传输文件
  • CLion与Beta版：使用Unicode UTF-8提供全球语言支持
  • PowerShell脚本执行打包命令
  • 盈鹏飞嵌入式带你玩转T113系列tina5 SDK(6)-添加心跳灯
  • “轻”是态度，“强”是底气：折叠屏的“成人礼”