ACM基础算法模板

快速排序

时间复杂度: $O(nlog(n))$,模板题

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


void quick_sort(int q[],int l,int r){
    if(l >= r) return;
    
    // 1. 寻找分界点
    int x = q[(l + r)/2],i = l - 1, j = r + 1;
    // 2. 调整区间
    while(i < j){
        do i++; while(q[i] < x);
        do j--; while(q[j] > x);
        if(i < j) swap(q[i],q[j]);
    }
    
    // 3. 分布递归
    quick_sort(q,l,j);
    quick_sort(q,j+1,r);
}

归并排序

时间复杂度: $O(nlog(n))$,模板题

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


void merge_sort(int q[],int l,int r){
    if(l >= r) return;
    
    // 1. 确定分界点
    int mid = (l + r) >> 1;
    // 2. 进行递归
    merge_sort(q,l,mid);
    merge_sort(q,mid+1,r);
    // 3. 合并区间
    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];
}

二分查找

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


bool check(int x); // 检查x是否满足某种性质

// 最小满足点:  若mid满足搜索[l,mid],否则搜索[mid+1,r]
// 一段区间，开始不满足后来满足
int bsearch_low(int l,int r){
  while(l < r){
    int mid = l + r >> 1;
    if( check(mid) ) r = mid;
    else l = mid + 1;
  }
}

// 最大满足点:  若mid满足搜索[mid,r],否则搜索[l,mid-1]
// 一段区间，开始满足后来不满足
int bsearch_high(int l,int r){
  while(l < r){
    int mid = l + r + 1 >> 1;
    if( check(mid) ) l = mid;
    else r = mid - 1;
  }
}

高精度加法模板

需要注意的是： A是一个从低位到高位的数组，比如A是[1,2,3],代表的值是321

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


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

高精度减法模板

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


vector<int> sub(v & A, v & B){
    for(int i = 0; i < A.size() ; i++){
        A[i] -= B[i];
        if(A[i] < 0){
            A[i] += 10;
            A[i+1] -= 1;
        }
    }
    // 去掉前导0
    while(A.size() > 1 && A.back() == 0) A.pop_back();
    return A;
}

字符串杂知识

1
2
3
4
5
6
7
8
9


// C++ string 转 C string
s1.c_str();

// 字符串取字串
// 在字符串s1上从start位置开始截取，截取length长度
s1.substr(start,length);

// 查找字符串某个字符的位置
s1.find('x')

C++ 切割字符串

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


#include <iostream>
#include <vector>
#include <sstream>
using namespace std;

vector<string> v1;

int main(){
  string tmp_s = "123&1234&90";
  stringstream ss(tmp_s);

  while (getline(ss, tmp_s, '&')) {
      v1.push_back(tmp_s);
  }
  return 0;
}

清空queue

void clear(queue<string> & q){
    queue<string> empty;
    swap(empty,q);
}

ACM基础算法模板

相关文章：