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