二维前缀和
s[i][j] += s[i-1][j] + s[i][j-1] - s[i-1][j-1];
sum = s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1];
二维差分
void add(int x1, int y1, int x2, int y2, int c){
s[x1][y1] += c;
s[x1][y2 + 1] -= c;
s[x2 + 1][y1] -= c;
s[x2 + 1][y2 + 1] += c;
}
二分
整数二分
// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用:
// 如果有多个相同数,返回第一次出现的位置
int bsearch_1(int l, int r){
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid; // check()判断mid是否满足性质
else l = mid + 1;
}
return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用:
// 如果有多个相同数,返回最后一次出现的位置
int bsearch_2(int l, int r){
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
浮点数二分
double bsearch_3(double l, double r){
const double eps = 1e-6; // eps 表示精度,取决于题目对精度的要求
while (r - l > eps)
{
double mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid;
}
return l;
}
树的几个遍历转换
int build(int il, int ir, int pl, int pr){ // 中序后序建树
int root = pre[pl];
int k = pos[root];
if (il < k) l[root] = build(il, k - 1, pl + 1, pl + (k - il));
if (k < ir) r[root] = build(k + 1, ir, pl + 1 + (k-il), pr);
return root;
}
int build(int pl, int pr, int il, int ir, int d){ // 前序中序建树
int root = post[pr];
level[d].push_back(root);
int k = pos[root];
if (il < k) l[root] = build(pl, pl + k - 1 - il, il, k - 1, d + 1);
if (k < ir) r[root] = build(pl + k - il, pr - 1, k + 1, ir,d + 1);
return root;
}
void dfs(int root){ // 递归输出前序遍历
cout << root << ' ';
if (l[root]) dfs(l[root]);
if (r[root]) dfs(r[root]);
}
并查集
朴素并查集
int p[N]; //存储每个点的祖宗节点
// 返回x的祖宗节点
int find(int x){
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
// 初始化,假定节点编号是1~n
for (int i = 1; i <= n; i ++ ) p[i] = i;
// 合并a和b所在的两个集合:
p[find(a)] = find(b);
维护size的并查集
int p[N], size[N];
//p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义,表示祖宗节点所在集合中的点的数量
// 返回x的祖宗节点
int find(int x){
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
// 初始化,假定节点编号是1~n
for (int i = 1; i <= n; i ++ ){
p[i] = i;
size[i] = 1;
}
// 合并a和b所在的两个集合:
size[find(b)] += size[find(a)];
p[find(a)] = find(b);
维护距离的并查集
int p[N], d[N];
//p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离
// 返回x的祖宗节点
int find(int x){
if (p[x] != x){
int u = find(p[x]);
d[x] += d[p[x]];
p[x] = u;
}
return p[x];
}
// 初始化,假定节点编号是1~n
for (int i = 1; i <= n; i ++ ){
p[i] = i;
d[i] = 0;
}
// 合并a和b所在的两个集合:
p[find(a)] = find(b);
d[find(a)] = distance; // 根据具体问题,初始化find(a)的偏移量
字符串哈希
using ull = unsigned long long;
const int P = 131;
ull h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64
// 初始化
p[0] = 1;
for (int i = 1; i <= n; i ++ ){
h[i] = h[i - 1] * P + str[i];
p[i] = p[i - 1] * P;
}
// 计算子串 str[l ~ r] 的哈希值
ull get(int l, int r){
return h[r] - h[l - 1] * p[r - l + 1];
}
单调队列
Deque
deque <int> q; //存放编号
for (int i = 1; i <= n; i++){ // 单调递增
while (!q.empty() && i - k >= q.back()) q.pop_back(); // 淘汰太老的
while (!q.empty() && a[q.front()] >= a[i]) q.pop_front(); // 淘汰能力不足的
q.emplace_front(i); // 增加新血液
if (i >= k) cout << a[q.back()] << " ";
} puts("");
q.clear();
数组模拟
int hh = 0, tt = -1;
int a[N], q[N];
for (int i = 0; i < n; i ++){
while (hh <= tt && q[hh] < i - k + 1) hh ++;
while (hh <= tt && a[q[tt]] >= a[i]) tt --;
q[++ tt] = i;
if (i >= k - 1) printf("%d ", a[q[hh]]);
} puts("");
Dijkstra
朴素
int dijkstra(){
memset(dist, 0x3f, sizeof 0x3f);
dist[1] = 0; // 初始化一号点的距离
for (int i = 0; i < n - 1; i ++){
int t = -1;
for (int j = 1; j <= n; j ++)
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
st[t] = true;
for (int j = 1; j <= n; j ++)
if (dist[j] > dist[t] + g[t][j])
dist[j] = dist[t] + g[t][j];
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
堆优化
#define x first
#define y second
using pii = pair<int, int>;
memset(h, -1, sizeof h); // !!切记初始化
void add(int a, int b, int c){
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
int dijkstra(){
memset(dist, 0x3f, sizeof dist);
priority_queue<pii, vector<pii>, greater<pii>> q;
q.push({0, 1});
while (q.size()){
auto t = q.top();
q.pop();
int ver = q.y, distance = q.x;
if (st[ver]) continue;
st[ver] = true;
for (int i = h[ver]; ~i; i = ne[i]){
int j = e[i];
if (dist[j] > dist[t] + w[i]){
dist[j] = dist[t] + w[i];
q.push({dist[j], j});
}
}
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
SPFA
关于SPFA,它…
求最短路
int spfa(){
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
queue<int> q;
q.push(1);
st[1] = true;
while (q.size()){
int t = q.front();
q.pop();
st[t] = false;
for (int i = h[t]; ~i; 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);
}
}
}
}
return dist[n];
}
判负环
bool spfa(){
queue<int> q;
for (int i = 1; i <= n; i ++){
q.push(i); // 放入所有点,存在负环的单向图可能某个点到达不了负环
st[i] = true;
}
while (q.size()){
int t = q.front();
q.pop();
st[t] = false;
for (int i = h[t]; ~i; i = ne[i]){
int j = e[i];
if (dist[j] > dist[t] + w[i]){
dist[j] = dist[t] + w[i];
cnt[j] = cnt[t] + 1;
if (cnt[j] >= n) return true;
if (!st[j]){
st[j] = true;
q.push(j);
}
}
}
}
return false;
}
Floyd
// 初始化:
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
if (i == j) d[i][j] = 0;
else d[i][j] = INF;
// 算法结束后,d[a][b]表示a到b的最短距离
void floyd()
{
for (int k = 1; k <= n; k ++ ) // 通过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]);
}
筛质数
埃氏筛法
void getPirme(int n){
for (int i = 2; i <= n; i ++){
if (!st[i]) {
primes[cnt ++] = i;
for (int j = i + i; j <= n; j + i)
st[j] = true
}
}
}
线性筛法
void getPrime(int n){
for (int i = 2; i <= n; i ++){
if (!st[i]) primes[cnt ++] = i;
for (int j = 0; primes[j] <= n / i; j ++){
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}
扩展欧几里得公式
$ a_i×x_i+b_i×y_i=gcd(a_i,b_i) $
int exgcd(int a, int b, int &x, int &y){
if (!b){
x = 1, y = 0;
return a;
}
int d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
快速幂
int qmi(int a, int k, int p){
int res = 1;
while (k){
if (k & 1) res = (gg) res * a % p;
a = (gg) a * a % p;
k >>= 1;
}
return res;
}
// 费马小定理
// p是质数,求a模p的乘法逆元
int res = qmi(a, p - 2, p);
裴蜀定理
两个互质的数凑不出来的最小的数是$(p−1)∗(q−1)−1$
背包DP
01背包
for (int i = 1; i <= n; i ++)
for (int j = m; j >= v[i]; j --)
f[j] = max(f[j], f[j - v[i]] + w[i]);
完全背包
for (int i = 1; i <= n; i ++)
for (int j = v[i]; j <= m; j ++)
f[j] = max(f[j], f[j - v[i]] + w[i]);
分组背包
for (int i = 1; i <= n; i ++) // 枚举组
for (int j = m; j; j --) // 枚举面积
for (int k = 1; k <= s[i]; k ++) // 枚举选择
if (j >= v[i][k])
f[j] = max(f[j], f[j-v[i][k]]+ w[i][k]);
线性DP
数字三角形
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= i; j ++)
cin >> f[i][j];
for (int i = n - 1; i >= 1; i --)
for (int j = 1; j <= i; j ++)
f[i][j] += max(f[i + 1][j], f[i + 1][j + 1]);
LIS
for (int i = 1; i <= n; i ++){
f[i] = 1;
for (int j = 1; j < i; j ++)
if (a[j] < a[i])
f[i] = max(f[i], f[j] + 1);
}
int res = 0;
for (int i = 1; i <= n; i ++)
res = max(res, f[i]);
LCS
for (int i = 1; i <= n; i ++){
for (int j = 1; j <= m; j ++){
f[i][j] = max(f[i-1][j], f[i][j-1]);
if (a[i] == b[j])
f[i][j] = max(f[i][j], f[i-1][j-1] + 1);
}
}
LCIS
for (int i = 1; i <= n; i ++){
int maxv = 1;
for (int j = 1; j <= n; j ++){
f[i][j] = f[i - 1][j];
if (a[i] == b[j]) f[i][j] = max(maxv, f[i][j]);
if (b[j] < a[i]) maxv = max(maxv, f[i][j] + 1);
}
}
int res = 0;
for (int i = 1; i <= n; i ++) res = max(res, f[n][i]);
区间合并
不带链(石子合并)
for (int len = 2; len <= n; len ++) // 遍历区间长度
for (int i = 1; i + len - 1 <= n; i ++){ // 遍历左端点
int l = i, r = i + len - 1;
f[l][r] = 1e8;
for (int k = l; k < r; k ++) // 遍历分界点
f[l][r] = min(f[l][r], f[l][k] + f[k+1][r] + s[r] - s[l-1]);
}
cout << f[1][n] << '\n';
破链成环(能量石)
for (int i = 1; i <= n; i ++){ // 破链成环、特殊处理输入
cin >> w[i];
w[i + n] = w[i];
}
for (int len = 3; len <= n + 1; len ++) // 记住是n + 1,因为要返回开头
for (int l = 1; l + len - 1 <= 2 * n; l ++){ // 这里是2 * n
int r = l + len - 1;
for (int k = l + 1; k < r; k ++)
f[l][r] = max(f[l][r], f[l][k] + f[k][r] + w[l] * w[k] * w[r]);
}
int ans = 0;
for (int l = 1; l <= n; l ++ )
ans = max(ans, f[l][l + n]);
树形DP
没有上司的舞会
void dfs(int u){
f[u][1] = happy[u];
for (int i = h[u]; ~i; i = ne[i]){
int j = e[i];
dfs(j);
f[u][0] += max(f[j][0], f[j][1]);
f[u][1] += f[j][0];
}
}
cout << max(f[root][0], f[root][1]) << '\n';
树的最长路径
int dfs(int u, int fa){
int d1 = 0, d2 = 0;
for (int i = h[u]; ~i; i = ne[i]){
int j = e[i];
if (j == fa) continue;
int d = dfs(j, u) + w[i];
if (d > d1) d2 = d1, d1 = d;
else if (d > d2) d2 = d;
}
ans = max(ans, d1 + d2);
return d1;
}
Orz