基础算法（排序，二分，高精度，前缀和，差分，双指针，位运算，离散化，区间合并）

基础算法

- 基础算法
- - 排序
  - - 快速排序
    - - 步骤（分治）
    - 归并排序
    - - **步骤（分治）**：
  - 二分
  - - - 代码
  - 高精度
  - - A + B
    - A - B
    - A * b
    - A /b
  - 前缀和
  - - 一维数组
    - 二维数组
  - 差分（前缀和逆运算）
  - - 一维构造
    - 二维差分
  - 双指针
  - 位运算
  - - lowbit(x)
  - 离散化（整数）
  - - 核心代码
  - 区间合并(贪心)

排序

快速排序

步骤（分治）

确定分界点x（左右边界点或中间的点）
调整区间：使得第一个区间所有元素小于等于x，第二区间所有元素大于x

方法：双指针

左指针右移直到元素大于x，右指针相反，然后交换左右指针的值

递归处理左右两端

代码这样写(第一个元素为分界点)：

#include<iostream>
using namespace std;void print(int a[], int n)
{  for(int j= 0; j<n; j++){  cout<<a[j] <<"  ";  }  cout<<endl;  
}  void quickSort(int a[], int low ,int high)
{if(low<high)  {int i = low, j = high;  int x = a[low];                                      while(i<j)  {while(i<j && a[j] >= x) j--;  if(i<j) a[i++] = a[j];   while(i<j && a[i] <= x) i++;if(i<j) a[j--] = a[i];  } a[i] = x; quickSort(a, i+1 ,high);}
}int main()
{  int a[10] = {8,1,9,7,2,4,5,6,10,3};  cout<<"初始序列：";  print(a,10);  quickSort(a,0,9);  cout<<"排序结果：";  print(a,10);  return
}

一般我们更常用下面的代码(左边小于等于x, 右边大于等于x)

#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], i = l - 1, j = r + 1;while (i < j) {while (q[++i] < x);while (q[--j] > x);cout << q[i] << " " << q[j]<<endl;if (i < j)	swap(q[i], q[j]);for (int i = 0; i < n; ++i) {cout << q[i] << " " ;}cout << endl;}quick_sort(q, l, j);quick_sort(q, j + 1, r);
}int main() {cin >> n;for (int i = 0; i < n; ++i) {cin >> q[i];}quick_sort(q, 0, n - 1);for (int i = 0; i < n; ++i) {cout << q[i] << " ";}return 0;
}

归并排序

O(nlogn)

稳定：两个相同值排序后的相对位置不发生变化（快速排序不稳定）

步骤（分治）：

确定分界点，中间的点
递归排序left，right
归并，合二为一

代码

#include <iostream>
using namespace std;const int N = 1e6 + 10;
int n;
int q[N], tmp[N];void merge_sort(int arr[], int l, int r) {if (l >= r)     return;int mid = (l + r) / 2;merge_sort(arr, l, mid), merge_sort(arr, mid + 1, r);int i = l, j = mid + 1, k = 0;while (i <= mid && j <= r) {if (q[i] <= q[j])       tmp[k++] = q[i++];else    tmp[k++] = q[j++];    // cout << tmp[k-1] <<" "<<l<<" "<<r << endl;}while (i <= mid)    tmp[k++] = q[i++];while (j <= r)      tmp[k++] = q[j++];for (int m = 0; m < k; ++m) {q[l + m] = tmp[m];} // for (int i = 0; i < n; ++i) {//     cout << q[i] << " ";// } cout << endl;
}int main() {cin >> n;for (int i = 0; i < n; ++i) {cin >> q[i];}merge_sort(q, 0, n - 1);for (int i = 0; i < n; ++i) {cout << q[i] << " ";}
}

二分

(很容易死循环 TuT)

在一个区间：右半边满足某性质，左半边不满足，可以用二分来找到边界点

代码

class Solution {
public:int search(vector<int>& nums, int target) {int l = 0, r = nums.size() - 1;while (l <= r) {int mid = l + r >> 1;if (nums[mid] < target) l = mid + 1;else if (nums[mid] > target)   r = mid - 1;else    return mid; }return -1;}
};

样例

给定一个按照升序排列的长度为 nn 的整数数组，以及 qq 个查询。

对于每个查询，返回一个元素 kk 的起始位置和终止位置（位置从 00 开始计数）。

如果数组中不存在该元素，则返回 -1 -1。

输入格式

第一行包含整数 nn 和 qq，表示数组长度和询问个数。

第二行包含 nn 个整数（均在 1∼100001∼10000 范围内），表示完整数组。

接下来 qq 行，每行包含一个整数 kk，表示一个询问元素。

输出格式

共 qq 行，每行包含两个整数，表示所求元素的起始位置和终止位置。

如果数组中不存在该元素，则返回 -1 -1。

代码
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int ar[N];
int main() {int n, m;cin >> n >> m;for (int i = 0; i < n; ++i)     cin >> ar[i];while (m--) {int x;cin >> x;int l = 0, r = n - 1;while (l < r) {int mid = (l + r) >> 1;if (ar[mid] >= x)   r = mid;else    l = mid + 1;}// cout << l;if (ar[l] != x) {cout << "-1 -1" << endl;continue;}int ans1 = l;l = 0, r = n - 1;while (l < r){int mid = (l + r + 1) >> 1; // 防止死循环if (ar[mid] <= x)   l = mid;else    r = mid - 1; }int ans2 = l;cout << ans1 << " " << ans2 << endl; }return 0;
}

高精度

大整数存储：存在一个数组中，下标为零存个位

A + B

#include <iostream>
#include <vector>
using namespace std;
vector<int> a, b;
vector<int> add(vector<int> &a, vector<int> &b) {vector<int> ans;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];ans.push_back(t % 10);t /= 10;}if (t)  ans.push_back(t);//cout << ans.size() << endl;return ans;
}
int main() {string x, y;cin >> x >> y;for (int i = x.size() - 1; i  >= 0; --i)      a.push_back(x[i] - '0');for (int i = y.size() - 1; i  >= 0; --i)      b.push_back(y[i] - '0');vector<int> ans = add(a, b);for (int i = ans.size() - 1; i >= 0; --i)    cout <<ans[i];return 0; 
}

A - B

#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];}return true;
}
vector<int> minuss(vector<int> a, vector<int> b) {vector<int> ans;int t = 0;for (int i = 0; i < a.size(); ++i) {t += a[i];if (i < b.size())   t -= b[i];//if (t >= 0) {ans.push_back(t);t = 0;}     else {ans.push_back(10 + t);t = -1;}//cout << ans.size() << endl;}
//    for (int i = ans.size() - 1; i >= 0; --i) {
//        cout << ans[i];
//    }for (int i = ans.size() - 1; i >= 1; --i) {if (ans[i] == 0)    ans.pop_back();else    break;}return ans;
}
int main() {string a, b;cin >> a >> b;vector<int> aa, bb;for (int i = a.size() - 1; i >= 0; --i) {aa.push_back(a[i] - '0');}for (int i = b.size() - 1; i >= 0; --i) {bb.push_back(b[i] - '0');}vector<int> ans;if (!cmp(aa, bb)) {cout << "-";ans = minuss(bb, aa); }  else	 ans = minuss(aa, bb);//cout<<ans.size();for (int i = ans.size() - 1; i >= 0; --i) {cout << ans[i];}return 0;
}

A * b

高精度整数A乘低精度整数b

#include <iostream>
#include <vector>
using namespace std;
vector <int> mul(vector<int> a, int b) {vector<int> ans;int t = 0;for (int i = 0; i < a.size(); ++i) {t += a[i] * b;ans.push_back(t % 10);t /= 10; }if (t)  ans.push_back(t);while (ans.size() > 1 && ans.back() == 0) ans.pop_back();//cout << t << endl; return ans;
}
int main() {string a;int b;vector<int> A;cin >> a >> b;for (int i = a.size() - 1; i >= 0; --i)     A.push_back(a[i] - '0');auto ans = mul(A, b);for (int i = ans.size() - 1; i >= 0; --i) {cout << ans[i];}return 0;
}

A /b

高精度整数A除低精度整数b

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> div(vector<int> &a, int b, int &r) {r = 0;vector<int> c;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())   c.pop_back();return c;
}int main() {string a;int b, r;cin >> a >> b;vector <int> A;for (int i = a.size() - 1; i >= 0; --i) {A.push_back(a[i] - '0');}auto ans = div(A, b, r);for (int i = ans.size() - 1; i >= 0; --i) {cout << ans[i];}cout << endl;cout << r;return 0;
}

前缀和

一维数组

$S_i = a_1 + a_2 +...+ a_i$

$a_i = s_i -s_{i-1}$

定义 $s_0$ 为0
作用：一次运算求出一段区间的和([l, r] : $s_r$ - $s_{i-1}$ )

代码

#include <iostream>
#include <vector>
using namespace std;
int main() {int m, n;cin >> n >> m;vector<int> a(n + 1);vector<int> s(n + 1);for (int i = 1; i <=n; ++i) {cin >> a[i];s[i] = s[i-1] + a[i];}while (m--) {int l, r;cin >> l >> r;cout << s[r] - s[l - 1] << endl;}return 0;
}

二维数组

$S_{i,j} = S_{i-1,j}+S_{i,j-1}-S_{i-1,j-1}+a_{i,j}$

$a_{ij}到s_{ij}$
$S_{x_2y_2}-S_{x_2y_1}-S_{x_1y_2} + S{x_1y_1}$
代码

#include <iostream>
using namespace std;
const int N = 1010;
int m, n, q;
int a[N][N], s[N][N];
int main() {ios::sync_with_stdio(false);cin >> n >> m >> q;for (int i = 1; i <= n; ++i) {for (int j = 1; j <= m; ++j) {cin >> a[i][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;cin >> x1 >> y1 >> x2 >> y2;cout << s[x2][y2] - s[x2][y1-1] - s[x1-1][y2] + s[x1-1][y1-1] << endl;}return 0;
}

差分（前缀和逆运算）

一维构造

已知 $a_1,a_2,...,a_n$

构造 $b_1,b_2,...,b_n$

使得 $a_i=b_1+b_2+...+b_i$

我们可以通过b 数组得到a 数组

a数组[l, r] + c ： $b_l+c$ ， $b_{r+1}-c$

代码

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int s[N], d[N];
int main() {ios::sync_with_stdio(false);int n, m;cin >> n >> m;for (int i = 1; i <= n; ++i)  {cin >> s[i];d[i] = s[i] - s[i - 1];}while (m--) {int l, r, c;cin >> l >> r >> c;d[l] += c;d[r + 1] -= c;}for (int i = 1; i <= n; ++i) {s[i] = s[i - 1] + d[i];cout << s[i] << " ";}return 0;
}

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N], b[N];
void insert(int l, int r, int c) {b[l] += c;b[r + 1] -= c;
}
int main() {ios::sync_with_stdio(false);int n, m;cin >> n >> m;for (int i = 1; i <= n; ++i) {cin >> a[i];insert(i, i, a[i]);}while (m--) {int l, r, c;cin >> l >> r >> c;insert(l, r, c);}for (int i = 1; i <= n; ++i) {a[i] = a[i-1] + b[i];cout << a[i] << " ";}return 0;
}

二维差分

代码

注意insert函数

#include <iostream>
using namespace std;
const int N = 1010;
int a[N][N], b[N][N];
void insert(int x1, int y1, int x2, int y2, int c) {b[x1][y1] += c;b[x1][y2+1] -= c;b[x2+1][y1] -= c;b[x2+1][y2+1] += c;
}
int main() {ios::sync_with_stdio(false);int m, n, q;cin >> n >> m >> q;for (int i = 1; i <= n; ++i) {for (int j = 1; j <= m; ++j) {cin >> a[i][j];insert(i, j, i, j, a[i][j]);}}while (q--) {int x1, x2, y1, 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) {a[i][j] = a[i-1][j] + a[i][j-1] - a[i-1][j-1] + b[i][j];cout << a[i][j] << " ";}cout << endl;}return 0;
}

#include <iostream>
using namespace std;
const int N = 1010;
int a[N][N], b[N][N];
void insert(int x1, int y1, int x2, int y2, int c) {b[x1][y1] += c;b[x1][y2+1] -= c;b[x2+1][y1] -= c;b[x2+1][y2+1] += c;
}
int main() {ios::sync_with_stdio(false);int m, n, q;cin >> n >> m >> q;for (int i = 1; i <= n; ++i) {for (int j = 1; j <= m; ++j) {cin >> a[i][j];insert(i, j, i, j, a[i][j]);}}while (q--) {int x1, x2, y1, 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];cout << b[i][j] << " ";}cout << endl;}return 0;
}

双指针

快慢指针

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

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N], s[N];
int main() {ios::sync_with_stdio(false);int n;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 (j < i && s[a[i]] > 1)    --s[a[j++]];res = max(res, i - j + 1);} cout << res;return 0;
}

位运算

n的二进制第k位是几： n >> k & 1

lowbit(x)

返回x最后一个1以及后面部分

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

代码

#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 ans = 0;while (x) {x -= lowbit(x);++ans;}cout << ans << " ";}return 0;
}

x = 1010

原码 0…01010

反码 1…11010

补码（取反加一)11…11011

计算机负数用补码表示

离散化（整数）

$10^5$ 个数，值域 $0-10^9$ (个数比较少。数值比较大）
我们需要把值作为下标

我们把他们映射到1,2,3,4,5…自然数

核心代码

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

    sort(alls.begin(), alls.end());// 去重alls.erase(unique(alls.begin(), alls.end()), alls.end());

代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 3e5 + 10;
int a[N], s[N];
vector<int> alls;
vector<pair<int, int>> add, query;
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;
}
int main() {int n, m;cin >> n >> m;while (n--) {int x, c;cin >> x >> c;add.push_back({x, c});alls.push_back(x);}while (m--) {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 i: add) {// a数组从1开始计int x = find(i.first) + 1;a[x] += i.second; }//  前缀和数组for (int i = 1; i <= alls.size(); ++i) {s[i] = s[i-1] + a[i];}for (auto i: query) {int  l = find(i.first) + 1, r = find(i.second) + 1;cout << s[r] - s[l-1] << endl;}return 0;
}

区间合并(贪心)

按区间左端点排序
右端点合并

代码

#include <iostream>
#include <string>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#define ll long long
using namespace std;vector<pair<int, int>> merge(vector<pair<int, int>> &p) {vector<pair<int, int>> ans;sort(p.begin(), p.end());int st = -2e9, ed = -2e9;for (auto i: p) {if (i.first > ed) {if (st != -2e9)  ans.push_back({st, ed});st = i.first, ed = i.second;}else {ed = max(ed, i.second);}}if (st != -2e9)  ans.push_back({st, ed});return ans;
}
int main()
{vector<pair<int, int>> segs;int n;cin >> n;while (n--) {int l, r;cin >> l >> r;segs.push_back({l, r});} auto ans = merge(segs);cout << ans.size();return 0;
}