Post

基础算法

Posted Updated
By skye-ye

views 25 min read
基础算法

排序

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

#include <iostream>
using namespace std;
const int N = 1e6 + 10;

int n;
int q[N];

void quick_sort(int q[], int l, int r) {
  if (l >= r) return;
  int x = q[(l + r + 1) / 2], i = l - 1, j = 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, i - 1); // 注意边界情况，防止死循环
  quick_sort(q, i, r);
}

int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) scanf("%d", &q[i]);

  quick_sort(q, 0, n - 1);

  for (int i = 0; i < n; i++) printf("%d ", q[i]);

  return 0;
}

归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

#include <iostream>
using namespace std;
const int N = 1000010;

int n;
int q[N], tmp[N];

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

int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) scanf("%d", &q[i]);

  merge_sort(q, 0, n - 1);

  for (int i = 0; i < n; i++) printf("%d ", q[i]);

  return 0;
}

二分

整数二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

#include <iostream>
using namespace std;
const int N = 100010;

int n, m;
int q[N];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%d", &q[i]);
    
    while (m--) {
        int x;
        scanf("%d", &x);
        
        int l = 0, r = n - 1;
        while (l < r) {
          /* 这三行是固定搭配，先写后两行的边界处理，再判断是否加一 */
            int mid = l + r >> 1;
            if (q[mid] >= x) r = mid;
            else l = mid + 1;
        }
        
        if( q[l] != x) cout << "-1 -1" << endl;
        else {
            cout << l << ' ';
            
            int l = 0; r = n - 1;
            while (l < r) {
              /* 这三行是固定搭配，先写后两行的边界处理，再判断是否加一，两种情况一般各出现一次 */
                int mid = l + r + 1 >> 1;
                if (q[mid] <= x) l = mid;
                else r = mid - 1;
            }
            
            cout << l << endl;
        }
    }
    return 0;
}

大整数

0. 大整数存储方式

大整数用数组的形式倒序存储

1. 大整数加法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

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

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];
    if (i < B.size()) t += B[i];
    C.push_back(t % 10);
    t /= 10;
  }
  
  if (t) C.push_back(1);
  return C;
}

int main() {
  string a, b;
  vector<int> A, B;
  
  cin >> a >> b;
  /* 倒着表示大整数，最高位可能有进位 */
  for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
  for (int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');
  
  auto C = add(A, B);
  
  for (int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
  return 0;
}

2. 大整数减法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

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

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];
  }
  /* 两数相等的情况应该返回true */
  return true;
}

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;
    /* 判断一下B是否溢出 */
    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;
}
int main() {
  string a, b;
  vector<int> A, B;
  
  cin >> a >> b;
  for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
  for (int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');
  
  /* 判断大减小还是小减大 */
  if (cmp(A, B)) {
    auto C = sub(A, B);
    for (int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
  } else {
    auto C = sub(B, A);
    printf("-");
    for (int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
  }
  return 0;
}

3. 大整数乘法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

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

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

int main() {
  string a;
  int b;
  
  cin >> a >> b;
  
  vector<int> A;
  for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
  
  auto C = mul(A, b);
  
  for (int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
  
  return 0;
}

4. 大整数除法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

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

/* A / b， 商是C，余数是r */
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;
}

int main() {
  string a;
  int b;
  
  cin >> a >> b;
  
  vector<int> A;
  for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
  
  int r; // 余数
  auto C = div(A, b, r);
  
  for (int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
  cout << endl << r << endl;
  
  return 0;
}

前缀和

1. 一维前缀和

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

#include <iostream>
using namespace std;
const int N = 100010;

int n, m;
int a[N], s[N];

int main() {
  // ios::sync_with_stdio(false); 
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  
  for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];
  
  while (m--) {
    int l, r;
    scanf("%d%d", &l, &r);
    printf("%d\n", s[r] - s[l - 1]);
  }
  
  return 0;
}

2. 二维前缀和

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

#include <iostream>
using namespace std;
const int N = 1010;

int n, m, q;
int a[N][N], s[N][N];

int main() {
  scanf("%d%d%d", &n, &m, &q);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
      scanf("%d", &a[i][j]);
  
  /* 求前缀和 */
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
      s[i][j] = s[i - 1][j] +s[i][j - 1] -s[i - 1][j - 1] + a[i][j];
  
  while (q--) {
    int x1, y1, x2, y2;
    scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
    printf("%d\n", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
  }
  return 0;
}

差分

前缀和逆运算

1. 一维差分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#include <iostream>
using namespace std;
const int N = 100010;

int n, m;
int a[N], b[N]; // a为前缀和，b为差分数组

void insert(int l, int r, int c) {
  b[l] += c;
  b[r + 1] -= c;
}

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  
  for (int i = 1; i <= n; i++) insert(i, i, a[i]);
  
  while (m--) {
    int l, r, c;
    scanf("%d%d%d", &l, &r, &c);
    insert(l, r, c);
  }
  
  for (int i = 1; i <= n; i++) b[i] += b[i - 1];
  
  for (int i = 1; i <= n; i++) printf("%d ", b[i]);
  
  return 0;
}

2. 二维差分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

#include <iostream>
using namespace std;
const int N = 1010;

int n, m, q;
int a[N][N], b[N][N];

void insert(int x1, int y1, int x2, int y2, int c) {
  b[x1][y1] += c;
  b[x2 + 1][y1] -= c;
  b[x1][y2 + 1] -= c;
  b[x2 + 1][y2 + 1] += c;
}

int main() {
  scanf("%d%d%d", &n, &m, &q);
  
  for (int i = 1; i <= n; i++) 
    for (int j = 1; j <= m; j++) 
      scanf("%d", &a[i][j]);
  
  for (int i = 1; i<= n; i++)
    for (int j = 1; j <= m; j++)
      insert(i, j, i, j, a[i][j]);
  
  while (q--) {
    int x1, y1, x2, y2, c;
    cin >> x1 >> y1 >> x2 >> y2 >> c;
    insert(x1, y1, x2, y2, 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];
  
  for (int i = 1; i <= n; i++){
    for (int j = 1; j <= m; j++) printf("%d ", b[i][j]);
    puts("");
  }
  return 0;
}

双指针

0. 用途

可以将O(n2)的算法优化到O(n)。

1. 例

输入几个由空格分开的单词，将其分别输出。

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

#include <iostream>
#include <cstring>
using namespace std;

int main() {
  char str[1000];
  /* C++中gets函数已被弃用 */
  fgets(str, sizeof(str), stdin);
  int n = strlen(str);
    
  for (int i = 0; str[i]; i++) {
    int j = i;
    while (j < n && str[j] != ' ') j++;
        
    for (int k = i; k < j; k++) cout << str[k];
    cout << endl;
        
    i = j;
  }
  return 0;
}

2. 最长连续不重复子序列

给定一个长度为 n 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。

输入格式

第一行包含整数 n。

第二行包含 n 个整数（均在 0∼105 范围内），表示整数序列。

输出格式

共一行，包含一个整数，表示最长的不包含重复的数的连续区间的长度。

数据范围

1≤n≤105

输入样例：

1
2

5
1 2 2 3 5

输出样例：

1

3

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

#include <iostream>
using namespace std;
const int N = 100010;

int n;
int a[N], s[N]; // a数组来记录数据，s数组来记录每个数字出现的次数

int main() {
  cin >> n;
  for (int i = 0; i < n; i++) cin >> a[i];
  
  int res = 0;
  for (int i = 0, j = 0; i < n; i++) {
    s[a[i]]++;
    while (s[a[i]] > 1) { // 若大于一，则有重复数据
      s[a[j]]--; // 此时j需要右移
      j++;
    }
    
    res = max(res, i - j + 1);
  }
  
  cout << res << endl;
  return 0;
}

位运算

给定一个长度为 n 的数列，请你求出数列中每个数的二进制表示中 1 的个数。

输入格式

第一行包含整数 n。

第二行包含 n 个整数，表示整个数列。

输出格式

共一行，包含 n 个整数，其中的第 i 个数表示数列中的第 i 个数的二进制表示中 1 的个数。

数据范围

1≤n≤100000, 0≤数列中元素的值≤109

输入样例：

1
2

5
1 2 3 4 5

输出样例：

1

1 1 2 1 2

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

#include <iostream>
using namespace std;

int lowbit(int x) {
  return x & -x;
}

int main() {
  int n;
  cin >> n;
  while (n--) {
    int x;
    cin >> x;
    int res = 0;
    while (x) x -= lowbit(x), res++; // 每次提取最后一位1
    
    cout << res << ' ';
  }
  return 0;
}

离散化

0. 适用范围

数据跨度大，但数据稀疏。

1. 技巧

将跨度大的数据在保序的情况下映射到小区间中。

2. 例子

假定有一个无限长的数轴，数轴上每个坐标上的数都是 0。

现在，我们首先进行 n 次操作，每次操作将某一位置 x 上的数加 c。

接下来，进行 m 次询问，每个询问包含两个整数 l 和 r，你需要求出在区间 [l,r] 之间的所有数的和。

输入格式

第一行包含两个整数 n 和 m。

接下来 n 行，每行包含两个整数 x 和 c。

再接下来 m 行，每行包含两个整数 l 和 r。

输出格式

共 m 行，每行输出一个询问中所求的区间内数字和。

数据范围

−109≤x≤109, 1≤n,m≤105, −109≤l≤r≤109, −10000≤c≤10000

输入样例：

1
2
3
4
5
6
7

3 3
1 2
3 6
7 5
1 3
4 6
7 8

输出样例：

1
2
3

8
0
5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 300010;

typedef pair<int, int> PII;

int n, m;
int a[N], s[N];

vector<int> alls;
vector<PII> add, query;

/* unique函数的实现 */
vector<int>::iterator unique(vector<int> &a) {
  int j = 0;
  for (int i = 0; i < a.size(); i++)
    if (!i || a[i] != a[i - 1])
      a[j++] = a[i];
  
  return a.begin() + j;
}

/* 二分查找映射后的数据位置 */
int find(int 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;
}

int main() {
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    int x, c;
    cin >> x >> c;
    add.push_back({x, c});
    
    alls.push_back(x);
  }
  
  for (int i = 0; i < m ;i++) {
    int l, r;
    cin >> l >> r;
    query.push_back({l, r});
    
    alls.push_back(l);
    alls.push_back(r);
  }
  
  /* 去重 */
  sort(alls.begin(), alls.end());
  alls.erase(unique(alls.begin(), alls.end()), alls.end());
  
  /* 处理输入 */
  for (auto item : add) {
    int x = find(item.first);
    a[x] += item.second;
  }
  
  /* 预处理前缀和 */
  for (int i = 1; i <= alls.size(); i++) s[i] = s[i - 1] + a[i];
  
  /* 处理查询 */
  for (auto item : query) {
    int l = find(item.first), r = find(item.second);
    cout << s[r] - s[l - 1] << endl;
  }
  return 0;
}

区间合并

给定 n 个区间 [li,ri]，要求合并所有有交集的区间。

注意如果在端点处相交，也算有交集。

输出合并完成后的区间个数。

例如：[1,3] 和 [2,6] 可以合并为一个区间 [1,6]。

输入格式

第一行包含整数 n。

接下来 n 行，每行包含两个整数 l 和 r。

输出格式

共一行，包含一个整数，表示合并区间完成后的区间个数。

数据范围

1≤n≤100000, −109≤li≤ri≤109

输入样例：

1
2
3
4
5
6

5
1 2
2 4
5 6
7 8
7 9

输出样例：

1

3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 100010;

typedef pair<int, int> PII;

int n;
vector<PII> segs;

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

int main() {
  cin >> n;
  for (int i = 0; i < n; i++) {
    int l, r;
    cin >> l >> r;
    segs.push_back({l, r});
  }
  
  merge(segs);
  
  cout << segs.size() << endl;
  return 0;
}

快速选择

给定一个长度为 n 的整数数列，以及一个整数 k，请用快速选择算法求出数列从小到大排序后的第 k 个数。

输入格式

第一行包含两个整数 n 和 k。

第二行包含 n 个整数（所有整数均在 1∼109 范围内），表示整数数列。

输出格式

输出一个整数，表示数列的第 k 小数。

数据范围

1≤n≤100000, 1≤k≤n

输入样例：

1
2

5 3
2 4 1 5 3

输出样例：

1

3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#include <iostream>
using namespace std;
const int N = 100010;

int n, k;
int q[N];

int quick_sort(int l, int r, int k) {
  if (l == r) return q[l];
  
  /* 快排部分 partition sort */
  int x = q[l], i = l - 1, j = r + 1;
  while (i < j) {
    while (q[++i] < x);
    while (q[--j] > x);
    if (i < j) swap(q[i], q[j]);
  }
  
  int sl = j - l + 1; // 比x小的数的数量
  if (k <= sl) return quick_sort(l, j, k); // 如果k比sl小，则递归左边
  
  return quick_sort(j + 1, r, k - sl); // 反之递归右边
}

int main() {
  cin >> n >> k;
  for (int i = 0; i < n; i++) cin >> q[i];
  
  cout << quick_sort(0, n - 1, k) << endl;
  
  return 0;
}

逆序对的数量（归并）

给定一个长度为 n 的整数数列，请你计算数列中的逆序对的数量。

逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满足 i<j 且 a[i]>a[j]，则其为一个逆序对；否则不是。

输入格式

第一行包含整数 n，表示数列的长度。

第二行包含 n 个整数，表示整个数列。

输出格式

输出一个整数，表示逆序对的个数。

数据范围

1≤n≤100000， 数列中的元素的取值范围 [1,109]。

输入样例：

1
2

6
2 3 4 5 6 1

输出样例：

1

5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

#include <iostream>
using namespace std;
typedef long long LL;
const int N = 100010;

int n;
int q[N], tmp[N];

LL merge_sort(int l, int r) {
  if (l >= r) return 0;
  
  int mid = l + r >> 1;
  LL res = merge_sort(l, mid) + merge_sort(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++];
      res += mid - i + 1; // 更新逆序对数量
    }
  while (i <= mid) tmp[k++] = q[i++];
  while (j <= r) tmp[k++] = q[j++];
  
  for (int i = l, j = 0;i <= r; i++, j++) q[i] = tmp[j];
  
  return res;
}

int main() {
  cin >> n;
  for (int i = 0; i < n; i++) cin >> q[i];
  
  cout << merge_sort(0, n - 1) << endl;
  return 0;
}

数的三次方根（浮点数二分）

给定一个浮点数 n，求它的三次方根。

输入格式

共一行，包含一个浮点数 n。

输出格式

共一行，包含一个浮点数，表示问题的解。

注意，结果保留 6 位小数。

数据范围

−10000≤n≤10000

输入样例：

1

1000.00

输出样例：

1

10.000000

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

#include <iostream>
using namespace std;

int main() {
  double x;
  cin >> x;
  
  double l = -10000, r = 10000;
  
  while (r - l > 1e-8) {
      double mid = (l + r) / 2;
      if (mid * mid * mid >= x) r = mid;
      else l = mid;
  }
  
  printf("%lf", l);
  return 0;
}
Blogging, Algorithm
排序 二分 高精度 前缀和 差分 双指针 离散化
This post is licensed under CC BY 4.0 by the author.