基础算法
排序
void quick_sort(int l, int r){ // l和r为左右端点
if(l >= r)
return;
int x = q[l + r >> 1], 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]);
else
quick_sort(l, j), quick_sort(j + 1, r);
}
}
// 快排求排好序后的第k个数
int quick_sort(int l, int r, int k){
if(l >= r)
return q[l];
int x = q[l + r >> 1], 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]);
}
int sl = j - l + 1;
if(sl >= k)
return quick_sort(l, j, k);
return quick_sort(j + 1, r, k - sl);
}
void merge_sort(int l, int r){ // 需要构造一个额外的辅助数组
if(l >= r)
return;
int mid = l + r >> 1;
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]) t[k ++ ] = q[i ++ ];
else
t[k ++ ] = q[j ++ ];
}
while(i <= mid)
t[k ++ ] = q[i ++ ];
while(j <= r)
t[k ++ ] = q[j ++ ];
for(i = l, j = 0; i <= r; j ++ , i ++)
q[i] = t[j];
}
// MergeSort 求逆序对的数量
long long merge_sort(int l, int r){
if(l >= r)
return 0;
int mid = l + r >> 1;
long long res = merge_sort(l, mid) + merge_sort(mid + 1, r);
int i = l, j = mid + 1, k = 0;
while(i <= mid && j <= r)
{
if(q[i] <= q[j])
temp[k ++ ] = q[i ++ ];
else
{
res += mid - i + 1;
temp[k ++ ] = q[j ++ ];
}
}
while(i <= mid)
temp[k ++ ] = q[i ++ ];
while(j <= r)
temp[k ++ ] = q[j ++ ];
for(int i = 0, j = l; j <= r;j ++, i ++)
q[j] = temp[i];
return res;
}
高精度
vector<int> add(vector<int>& A, vector<int>& B){
int temp = 0;
vector<int> v;
for(int i = 0; i < A.size() || i < B.size(); i ++)
{
if(i < A.size()) temp += A[i];
if(i < B.size()) temp += B[i];
v.push_back(temp % 10);
temp /= 10;
}
if(temp) v.push_back(1);
reverse(v.begin(), v.end());
return v;
}
vector<int> sub(vector<int>& A, vector<int>& B){
int temp = 0;
vector<int> v;
for(int i = 0; i < A.size(); i ++)
{
temp += A[i];
if(i < B.size()) temp -= B[i];
v.push_back((temp + 10) % 10);
if(temp < 0)
temp = -1;
else
temp = 0;
}
while(v.size() > 1 && !v.back()) v.pop_back();
reverse(v.begin(), v.end());
return v;
}
// 比较string大小
bool cmp(const string a, const string b){
if(a.size() ^ b.size()) return a.size() > b.size();
return a >= b;
}
vector<int> mul(vector<int>& A, int b){
int temp = 0;
vector<int> v;
for(int i = 0; temp || i < A.size(); i ++)
{
if(i < A.size()) temp += A[i] * b;
v.push_back(temp % 10);
temp /= 10;
}
reverse(v.begin(), v.end());
return v;
}
//带余数的高精度除法, 其中res为余数
int res;
vector<int> div(vector<int>& A, int b){
vector<int> v;
for(int i = A.size() - 1; ~i; i --)
{
res = res * 10 + A[i];
v.push_back(res / b);
res %= b;
}
reverse(v.begin(), v.end());
while(v.size() > 1 && !v.back()) v.pop_back();
reverse(v.begin(), v.end());
return v;
}
// 比较string大小
bool cmp(const string a, const string b){
if(a.size() ^ b.size()) return a.size() > b.size();
return a >= b;
}
其他
// 整数二分
int l = 0, r = n - 1;
while(l < r) // 当 r = mid的情况
{
int mid = l + r >> 1;
if(q[mid] >= x)
r = mid;
else
l = mid + 1;
}
while(l < r) // 当 l = mid的情况
{
int mid = l + r + 1 >> 1;
if(q[mid] <= x)
l = mid;
else
r = mid - 1;
}
// 浮点数二分 -> 求数的三次方根
double n; cin >> n;
while(r - l > 1e-8)
{
double mid = (l + r) / 2;
if(mid * mid * mid >= n)
r = mid;
else
l = mid;
}
// 一维差分
// 用函数差分
void insert(int l, int r, int c){
q[l] += c;
q[r + 1] -= c;
}
for(int i = 1; i <= n; i ++)
{
int x; cin >> x;
insert(i, i, x);
}
// 原地差分
int x;
for(int i = 1; i <= n; i ++)
cin >> x, q[i + 1] -= x, q[i] += x;
// 用额外差分数组来存储
int b[N], a[N];
for(int i = 1; i <= n; i ++) cin >> a[i];
b[1] = a[1];
for(int i = 2; i <= n; i ++)
b[i] = a[i] - a[i - 1];
// 将差分数组转为原数组
for(int i = 1; i <= n; i ++)
b[i] += b[i - 1], cout << b[i] << " \n"[i == n];
// 二维差分
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++)
cin >> a[i][j];
while(cin >> u >> v >> x >> y >> c)
{
x ++;
y ++;
b[u][v] +=c;
b[x][v] -=c;
b[u][y] -=c;
b[x][y] +=c;
}
// 输出差分数组
for(int i = 1; i <= n; i++, cout << endl)
for(int j = 1; j <= m; j ++)
b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1], cout << a[i][j] + b[i][j] << " ";
// 一维数组
for(int i = 1; i <= n; i ++)
cin >> s[i], s[i] += s[i - 1];
// 求 [L, R]的子段和
int l, r; cin >> l >> r;
cout << s[r] - s[l - 1] << endl;
// 二维数组
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++)
cin >> s[i][j], s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
// 求[x1][y1] -> [x2][y2]的面积和
int a, b, c, d;
cin >> a >> b >> c >> d;
cout << s[c][d] + s[a - 1][b - 1] - s[a - 1][d] - s[c][b - 1] << endl;
void init(){
for(int j = 0; j < M; j ++)
for(int i = 1; i + (1 << j) <= n + 1; i ++)
if(!j)
f[i][j] = q[i];
else
f[i][j] = max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
}
int query(int l, int r){
int len = r - l + 1;
int k = log(len) / log(2);
int res = max(f[l][k], f[r - (1 << k) + 1][k]);
return res;
}
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define fi first
#define se second
typedef pair<int, int> PII;
const int N = 300010;
int n, m;
vector<int> alls;
vector<PII> add, query;
int s[N];
int find(int x){
int l = 0, r = alls.size();
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;
while(n --)
{
int x, c;
cin >> x >> c;
alls.push_back(x);
add.push_back({x, c});
}
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 item : add)
{
int x = find(item.fi);
s[x] += item.se;
}
for(int i = 1; i <= alls.size(); i ++) s[i] += s[i - 1];
for(auto item : query)
{
int l = find(item.fi), r = find(item.se);
cout << s[r] - s[l - 1] << endl;
}
return 0;
}
数据结构
链表
const int N = 100010;
int h, ne[N], e[N], idx;
void init(){
h = -1, idx = 0;
}
void add_to_head(int x){
e[idx] = x;
ne[idx] = h;
h = idx ++ ;
}
void remove(int k){
ne[k] = ne[ne[k]];
}
void insert(int x, int k){
e[idx] = x;
ne[idx] = ne[k];
ne[k] = idx ++ ;
}
const int N = 100010;
int M;
int l[N], r[N], e[N], idx;
void init(){
r[0] = 1;
l[1] = 0;
idx = 2;
}
void add(int k, int x){
e[idx] = x;
r[idx] = r[k];
l[idx] = k;
l[r[k]] = idx;
r[k] = idx ++ ;
}
void remove(int x){
l[r[x]] = l[x];
r[l[x]] = r[x];
}
栈
// 初始化
const int N = 100010;
int q[N], tt = -1;
// 压栈
q[++ tt] = x;
// 弹出栈顶
cout << q[tt --] << endl;
// 判断数组中左边第一个比它小的元素
cin >> n;
while(n --)
{
int x;
cin >> x;
while(tt && q[tt] >= x)
tt -- ;
if(tt)
cout << q[tt] << " ";
else
cout << -1 << " ";
q[ ++ tt ] = x;
}
队列
// 初始化队列
const int N = 100010;
int q[N], hh = 0, tt = -1;
// push
q[ ++ tt ] = x;
// front
cout << q[hh ++] << endl;
// 滑动窗口判断 窗口大小为k 其中的Max & Min
for(int i = 0; i < n; i ++) // 最小值
{
if(hh <= tt && i - k + 1 > q[hh]) hh ++ ;
while(hh <= tt && a[i] < a[q[tt]]) tt -- ;
q[ ++ tt ] = i;
if(i - k + 1 >= 0)
cout << a[q[hh]] << " ";
}
cout << endl;
hh = 0, tt = -1;
for(int i = 0; i < n; i ++) // 最大值
{
if(hh <= tt && i - k + 1 > q[hh]) hh ++ ;
while(hh <= tt && a[i] > a[q[tt]]) tt -- ;
q[ ++ tt ] = i;
if(i - k + 1 >= 0)
cout << a[q[hh]] << " ";
}
字符串
#include <iostream>
using namespace std;
const int N = 1000010;
int n, m, ne[N];
char f[N], s[N];
int main(){
cin >> n >> f + 1 >> m >> s + 1;
for(int i = 2, j = 0; i <= n; i ++) // 初始化 ne[N] 数组
{
while(j && f[i] != f[j + 1])
j = ne[j];
if(f[i] == f[j + 1])
j ++ ;
ne[i] = j;
}
for(int i = 0; i < 7; i ++)
cout << ne[i];
for(int i = 1, j = 0; i <= m; i ++) // 跑一遍kmp
{
while(j && s[i] != f[j + 1])
j = ne[j];
if(s[i] == f[j + 1])
j ++ ;
if(j == n)
{
cout << i - n << " ";
j = ne[j];
}
}
}
const int N = 20010;
int n;
int s[N][26], cnt[N], idx;
char str[N];
void insert(char* st){
int p = 0;
for(int i = 0; st[i]; i ++)
{
int u = st[i] - 'a';
if(!s[p][u]) s[p][u] = ++ idx ;
p = s[p][u];
}
cnt[p] ++ ;
}
int query(char* st){
int p = 0;
for(int i = 0; st[i]; i ++)
{
int u = st[i] - 'a';
if(!s[p][u])
return 0;
p = s[p][u];
}
return cnt[p];
}
并查集
// 初始化并查集
for(int i = 1; i <= n; i ++)
p[i] = i;
// 查询
int find(int x){
return x ^ p[x] ? p[x] = find(p[x]) : p[x];
}
// 压缩路径d[N]
int d[N], p[N];
int find(int x){
if(p[x] ^ x)
{
int t = find(p[x]);
d[x] += d[p[x]];
p[x] = t;
}
return p[x];
}
哈希表
// 拉链法
const int N = 100003 ;
int h[N] , ne[N] , e[N] , idx ;
int n ;
void insert(int x){
int k = (x % N + N) % N ;
e[idx] = x ;
ne[idx] = h[k] ;
h[k] = idx ++ ;
}
bool find(int x){
int k = (x % N + N) % N ;
for (int i = h[k] ; i != -1; i = ne[i])
if (e[i] == x)
return true ;
return false ;
}
// 开放寻址法
const int N = 200003 , null = 0x3f3f3f3f;
int h[N] ;
int n ;
void init(){
memset(h, 0x3f, sizeof h);
}
int find(int x){
int k = (x % N + N) % N ;
while (h[k] != null && h[k] != x)
{
k ++ ;
if (k == N) k = 0 ;
}
return k ;
}
#include <iostream>
using namespace std;
typedef unsigned long long ULL;
const int N = 100010, P = 131;
ULL p[N], h[N];
char str[N];
int n, m;
ULL get(int l, int r){
return h[r] - h[l - 1] * p[r - l + 1];
}
int main (){
cin >> n >> m;
cin >> str + 1;
p[0] = 1;
for(int i = 1; i <= n; i ++)
{
h[i] = h[i - 1] * P + str[i] - 'a';
p[i] = p[i - 1] * P;
}
while(m --)
{
int l1, l2, r1, r2;
cin >> l1 >> r1 >> l2 >> r2;
bool flg = get(l1, r1) == get(l2, r2);
if(flg)
cout << "Yes" << endl;
else
cout << "No" << endl;
}
return 0;
}
堆
#include <iostream>
using namespace std;
const int N = 100010;
int n, m;
int h[N], len;
void down(int u){
if(2 * u > len) return ;
int t = u;
if(h[2 * u] < h[t]) t = 2 * u;
if(2 * u + 1 <= len && h[2 * u + 1] < h[t]) t = 2 * u + 1;
if(t ^ u)
{
swap(h[u], h[t]);
down(t);
}
}
int main (){
cin >> n >> m;
for(int i = 1; i <= n; i ++)
cin >> h[i];
len = n;
for(int i = n / 2; i; i --)
down(i);
while(m --)
{
cout << h[1] << " ";
h[1] = h[len --];
down(1);
}
}
#include <iostream>
using namespace std;
const int N = 100010;
int n;
int h[N], hp[N], ph[N], idx, len;
void heap_swap(int x, int y){
swap(ph[hp[x]], ph[hp[y]]);
swap(hp[x], hp[y]);
swap(h[x], h[y]); // 因为第一步操作已经换过了
}
void down(int u){
if(u * 2 > len)
return ;
int t = u;
if(h[2 * u] < h[t])
t = 2 * u;
if(2 * u + 1 <= len && h[2 * u + 1] < h[t])
t = 2 * u + 1;
if(u ^ t)
{
heap_swap(t, u);
down(t);
}
}
void up(int u){
while(h[u] < h[u / 2] && u / 2)
{
heap_swap(u, u / 2);
u /= 2;
}
}
int main (){
cin >> n;
while(n --)
{
string op;
int x, k;
cin >> op;
if(op == "I")
{
cin >> x;
len ++;
idx ++ ;
h[len] = x;
hp[len] = idx, ph[idx] = len;
up(len);
}
else if(op == "PM") cout << h[1] << endl;
else if(op == "DM")
{
heap_swap(1, len --);
down(1);
}
else if(op == "D")
{
cin >> k;
int t = ph[k]; // 第k个插入的数对应到堆中的位置
heap_swap(t, len -- );
down(t);
up(t);
}
else
{
cin >> k >> x;
int t = ph[k];
h[t] = x;
down(t);
up(t);
}
}
}
树状数组
线段树
平衡树
AC自动机
可持久化数据结构
搜索与图论
bool top_sort(){
for(int i = 1; i <= n; i ++)
if(!d[i]) // 表示入度
q[ ++ tt ] = i;
while(hh <= tt)
{
int t = q[hh ++ ];
for(int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
d[j] -- ;
if(!d[j])
q[ ++ tt ] =j;
}
}
return tt == n - 1;
}
// 朴素版dijkstra
int dijkstra(){
memset(d, 0x3f, sizeof d);
d[1] = 0;
for(int i = 1; i < n; i ++)
{
int t = -1;
for(int j = 1; j <= n; j ++)
if(!st[j] && (t == -1 || d[t] > d[j]))
t = j;
for(int j = 1; j <= n; j ++)
if(!st[j])
d[j] = min(d[j], d[t] + g[t][j]);
st[t] = true;
}
if(d[n] ^ 0x3f3f3f3f)
return d[n];
return -1;
}
// 堆优化版dijkstra
void dijkstra(){
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
priority_queue<PII, vector<PII>, greater<PII> > heap;
heap.push({0, 1});
while(heap.size())
{
auto t = heap.top();
heap.pop();
int distance = t.fi, index = t.se;
if(!st[index])
{
st[index] = true;
for(int i = h[index]; i != - 1; i = ne[i])
{
int j = e[i];
if(dist[j] > distance + w[i])
{
dist[j] = distance + w[i];
heap.push({dist[j], j});
}
}
}
}
if(dist[n] == 0x3f3f3f3f)
cout << -1 << endl;
else
cout << dist[n] << endl;
}`
// bellman-ford 适合解决有边数限制的最短路问题
#include <iostream>
#include <cstring>
using namespace std;
const int N = 510, M = 10010, Null = 0x3f3f3f3f;
int n, m, k;
int dist[N], last[N];
struct Edge{
int a, b, c;
}edges[M];
void bellman_ford(){
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for(int j = 0; j < k; j ++)
{
memcpy(last, dist, sizeof dist);
for(int i = 0; i < m; i ++)
{
auto e = edges[i];
dist[e.b] = min(dist[e.b], last[e.a] + e.c);
}
}
}
int main (){
cin >> n >> m >> k;
for(int i = 0; i < m; i ++)
{
int a, b, c;
cin >> a >> b >> c;
edges[i] = {a, b, c};
}
bellman_ford();
if(dist[n] > Null / 2)
cout << "impossible" << endl;
else
cout << dist[n] << endl;
return 0;
}
// spfa 求最短路
void spfa(){
memset(dist, 0x3f, sizeof dist);
queue<int> q;
q.push(1);
dist[1] = 0;
while(q.size())
{
auto t = q.front();
q.pop();
st[t] = false;
for(int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if(dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
if(!st[j])
{
st[j] = true;
q.push(j);
}
}
}
}
}
// spfa 判断负环
bool spfa(){
queue<int> q;
for(int i = 1; i <= n; i ++)
st[i] = true, q.push(i);
while(q.size())
{
auto t = q.front();
q.pop();
st[t] = false;
for(int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if(d[j] > d[t] + w[i])
{
d[j] = d[t] + w[i];
cnt[j] = cnt[t] + 1;
if(cnt[j] >= n) return true;
if(!st[j])
{
q.push(j);
st[j] = true;
}
}
}
}
return false;
}
// floyd求最短路
for (int k = 1; k <= n; k ++ )
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
// prim 求最小生成树
#include<bits/stdc++.h>
using namespace std;
const int N = 510, M = 100010;
int n, m;
int g[N][N];
int d[N];
bool st[N];
int prim(){
memset(d, 0x3f, sizeof d);
int res = 0;
for(int i= 0; i < n; i ++)
{
int t = -1;
for(int j = 1; j <= n; j ++)
if(!st[j] && (t == -1 || d[t] > d[j]))
t = j;
if(i && d[t] == 0x3f3f3f3f) return 0x3f3f3f3f;
if(i)
res += d[t];
for(int j = 1; j <= n; j ++)
d[j] = min(d[j], g[t][j]);
st[t] = true;
}
return res;
}
int main(){
memset(g, 0x3f, sizeof g);
cin >> n >> m;
for(int a, b, c; cin >> a >> b >> c; )
g[a][b] = g[b][a] = min(g[a][b], c);
int res = prim();
if(res == 0x3f3f3f3f)
cout << "impossible" << endl;
else
cout << res << endl;
return 0;
}
// kruskal 求最小生成树
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010, M = 2 * N, Null = 0x3f3f3f3f;
int n, m;
int p[N];
struct Edge{
int a, b, w;
bool operator< (const Edge& e){
return w < e.w;
}
}edges[M];
int find(int x){
return x ^ p[x] ? p[x] = find(p[x]) : p[x];
}
int kruskal(){
sort(edges, edges + m);
for(int i = 1; i <= n; i ++)
p[i] = i;
int res = 0, cnt = 0;
for(int i = 0; i < m; i ++)
{
auto e = edges[i];
int a = find(e.a), b = find(e.b);
if(a ^ b)
{
p[a] = b;
cnt ++ ;
res += e.w;
}
}
if(cnt < n - 1)
return Null;
return res;
}
int main (){
cin >> n >> m;
for(int i = 0; i < m; i ++)
{
int a, b, c;
cin >> a >> b >> c;
edges[i] = {a, b, c};
}
int res = kruskal();
if(res ^ Null)
cout << res << endl;
else
cout << "impossible" << endl;
return 0;
}
// 染色法判定二分图
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010, M = 2 * N;
int n, m;
int h[N], ne[M], e[M], idx;
int colors[N];
void init(){
memset(h, -1, sizeof h);
}
void add(int a, int b){
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++ ;
}
bool dfs(int u, int color){
colors[u] = color;
for(int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if(!colors[j])
{
if(!dfs(j, 3 - color))
return false;
}
else if(colors[j] == color)
return false;
}
return true;
}
int main (){
init();
cin >> n >> m;
while(m --)
{
int a, b;
cin >> a >> b;
add(a, b), add(b, a);
}
bool flg = true;
for(int i = 1; i <= n; i ++)
if(!colors[i])
{
if(!dfs(i, 1))
{
flg = false;
break;
}
}
if(flg)
cout << "Yes" << endl;
else
cout << "No" << endl;
return 0;
}
// 匈牙利求二分图的最大匹配
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010, M = 2 * N;
int n, m;
int h[N], ne[M], e[M], idx;
int colors[N];
void init(){
memset(h, -1, sizeof h);
}
void add(int a, int b){
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++ ;
}
bool dfs(int u, int color){
colors[u] = color;
for(int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if(!colors[j])
{
if(!dfs(j, 3 - color))
return false;
}
else if(colors[j] == color)
return false;
}
return true;
}
int main (){
init();
cin >> n >> m;
while(m --)
{
int a, b;
cin >> a >> b;
add(a, b), add(b, a);
}
bool flg = true;
for(int i = 1; i <= n; i ++)
if(!colors[i])
{
if(!dfs(i, 1))
{
flg = false;
break;
}
}
if(flg)
cout << "Yes" << endl;
else
cout << "No" << endl;
return 0;
}
// Flood Fill 求联通块的数量
void bfs(int x, int y){
queue<PII> q;
q.push({x, y});
st[x][y] = true;
while(q.size())
{
auto t = q.front();
q.pop();
for(int i = -1; i <= 1; i ++)
for(int j = -1; j <= 1; j ++)
if(i || j)
{
int a = i + t.fi, b = j + t.se;
if(a < 0 || a >= n || b < 0 || b >= m || st[a][b] || g[a][b] == '.')
continue;
q.push({a, b});
st[a][b] = true;
}
}
}
for(int i = 0; i < n; i ++)
for(int j = 0; j < m; j ++)
if(g[i][j] == 'W' && !st[i][j])
bfs(i, j), res ++ ;
数学
动态规划
数字三角形DP
最长上升子序列DP
背包模型DP
状态机DP
状态压缩DP
区间DP
树形DP
数位DP
我的博客即将搬运同步至腾讯云+社区,邀请大家一同入驻:https://cloud.tencent.com/developer/support-plan?invite_code=20oexlkq5gn48