Amekai 's 板子 - Amekai's home

基础#

cin关流#

1
ios::sync_with_stdio(false);
2
cin.tie(0);
3
cout.tie(0);

快读#

1
#ifdef __linux__
2
#define gc getchar_unlocked
3
#define pc putchar_unlocked
4
#else
5
#define gc _getchar_nolock
6
#define pc _putchar_nolock
7
#endif
8
inline bool blank(const char x) {return !(x^32)||!(x^10)||!(x^13)||!(x^9);}
9
template<typename Tp> inline void read(Tp &x) {x=0; register bool z=true; register char a=gc(); for(;!isdigit(a);a=gc()) if(a=='-') z=false; for(;isdigit(a);a=gc()) x=(x<<1)+(x<<3)+(a^48); x=(z?x:~x+1);}
10
inline void read(double &x) {x=0.0; register bool z=true; register double y=0.1; register char a=gc(); for(;!isdigit(a);a=gc()) if(a=='-') z=false; for(;isdigit(a);a=gc()) x=x*10+(a^48); if(a!='.') return x=z?x:-x,void(); for(a=gc();isdigit(a);a=gc(),y/=10) x+=y*(a^48); x=(z?x:-x);}
11
inline void read(char &x) {for(x=gc();blank(x)&&(x^-1);x=gc());}
12
inline void read(char *x) {register char a=gc(); for(;blank(a)&&(a^-1);a=gc()); for(;!blank(a)&&(a^-1);a=gc()) *x++=a; *x=0;}
13
inline void read(string &x) {x=""; register char a=gc(); for(;blank(a)&&(a^-1);a=gc()); for(;!blank(a)&&(a^-1);a=gc()) x+=a;}
14
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y) {read(x),read(y...);}
15
template<typename Tp> inline void write(Tp x) {if(!x) return pc(48),void(); if(x<0) pc('-'),x=~x+1; register int len=0; register char tmp[64]; for(;x;x/=10) tmp[++len]=x%10+48; while(len) pc(tmp[len--]);}
16
inline void write(const double x) {register int a=6; register double b=x,c=b; if(b<0) pc('-'),b=-b,c=-c; register double y=5*powl(10,-a-1); b+=y,c+=y; register int len=0; register char tmp[64]; if(b<1) pc(48); else for(;b>=1;b/=10) tmp[++len]=floor(b)-floor(b/10)*10+48; while(len) pc(tmp[len--]); pc('.'); for(c*=10;a;a--,c*=10) pc(floor(c)-floor(c/10)*10+48);}
17
inline void write(const pair<int,double>x) {register int a=x.first; if(a<7) {register double b=x.second,c=b; if(b<0) pc('-'),b=-b,c=-c; register double y=5*powl(10,-a-1); b+=y,c+=y; register int len=0; register char tmp[64]; if(b<1) pc(48); else for(;b>=1;b/=10) tmp[++len]=floor(b)-floor(b/10)*10+48; while(len) pc(tmp[len--]); a&&(pc('.')); for(c*=10;a;a--,c*=10) pc(floor(c)-floor(c/10)*10+48);} else cout<<fixed<<setprecision(a)<<x.second;}
18
inline void write(const char x) {pc(x);}
19
inline void write(const bool x) {pc(x?49:48);}
20
inline void write(char *x) {fputs(x,stdout);}
21
inline void write(const char *x) {fputs(x,stdout);}
22
inline void write(const string &x) {fputs(x.c_str(),stdout);}
23
template<typename T,typename ...Tp> inline void write(T x,Tp ...y) {write(x),write(y...);}

数论#

快速幂与快速乘法#

1
long long q_mul(long long a, long long b, long long mod) //快速乘法,a*b%mod
2
{
3
    long long res = 0;
4
    while (b){
5
        if (b & 1)
6
            res = (res + a) % mod;
7
        a = (a + a) % mod;
8
        b >>= 1;
9
    }
10
    return res;
11
}
12
long long q_pow(long long a, long long b, long long mod) //快速幂,a^b%mod
13
{
14
    long long res = 1;
15
    while (b){
16
        if (b & 1)
17
            res = q_mul(res, a, mod);
18
        a = q_mul(a, a, mod);
19
        b >>= 1;
20
    }
21
    return res;
22
}
23
//普通写法
24
int qpow(int a, int b){
25
  int ans = 1;
26
  a %= mod;
27
  while (b){
28
    if (b & 1)
29
      ans = (ans * a) % mod;
30
        a = (a * a) % mod;
31
    b >>= 1;
32
  }
33
  return ans;
34
}

gcd与lcm#

1
int gcd(int a, int b){return b == 0? a : gcd(b, a % b);}
2
int lcm(int a, int b){return a * b / gcd(a, b);}

矩阵快速幂#

1
inline void init()
2
{
3
  int c[105][105] = {0};
4
    for (int i = 1; i <= n; i++)
5
    for (int j = 1; j <= n; j++)
6
      c[i][j] = 0;
7
  for (int k = 1; k <= n; k++)
8
    for (int i = 1; i <= n; i++)
9
      for (int j = 1; j <= n; j++)
10
        c[i][j] = (c[i][j] + ans[i][k] * a[k][j]);
11
  for (int i = 1; i <= n; i++)
12
    for (int j = 1; j <= n; j++)
13
      ans[i][j] = c[i][j];
14
}
15
inline void init2()
16
{
17
  int c[105][105] = {0};
18
    for (int i = 1; i <= n; i++)
19
    for (int j = 1; j <= n; j++)
20
      c[i][j] = 0;
21
  for (int k = 1; k <= n; k++)
22
    for (int i = 1; i <= n; i++)
23
      for (int j = 1; j <= n; j++)
24
        c[i][j] = (c[i][j] + a[i][k] * a[k][j]) % mod;
25
  for (int i = 1; i <= n; i++)
26
    for (int j = 1; j <= n; j++)
27
      a[i][j] = c[i][j];
28
}
29
void gett()
30
{
31
  while (b)
32
  {
33
    if (b & 1)
34
      init();
35
    init2();
36
    b >>= 1;
37
  }
38
}
39
signed main()
40
{
41
  cin >> n >> b;
42
  for (int i = 1; i <= n; i++)
43
    for (int j = 1; j <= n; j++)
44
      cin >> a[i][j];
45
  for (int i = 1; i <= n; i++)
46
    ans[i][i] = 1;
47
  gett();
48
  for (int i = 1; i <= n; i++)
49
    for (int j = 1; j <= n; j++)
50
      cout << ans[i][j] % mod << " \n"[j == n];
51
  return 0;
52
}

欧拉筛#

1
bool isprime[100005];
2
int prime[100005];
3
int cnt = 0;
4
void euler()
5
{
6
    isprime[0] = isprime[1] = 1;
7
    for (int i = 2; i <= N; i++)
8
    {
9
        if (!isprime[i])
10
            prime[++cnt] = i;
11
        for (int j = 1; j <= cnt && i * prime[j] <= N; j++)
12
        {
13
            isprime[i * prime[j]] = 1;
14
            if (i % prime[j] == 0)
15
                break;
16
        }
17
    }
18
}

中国剩余定理#

求解同余方程组：

$a_i \le 1012$ 。 $a_i$ 的 $lcm$ 不超过 $1018$ 。

1
#include <bits/stdc++.h>
2
using namespace std;
3
void exgcd(long long a, long long b, long long &x, long long &y)
4
{
5
    if (!b)
6
        return x = 1, y = 0, void();
7
    exgcd(b, a % b, y, x), y -= a / b * x;
8
}
9
long long ny(long long a, long long mod)
10
{
11
    a %= mod;
12
    long long x, y;
13
    exgcd(a, mod, x, y);
14
    return (x % mod + mod) % mod;
15
}
16
int n;
17
long long a[100011], b[100011];
18
long long p[111], mod[111], rem[111], idx;
19
void Insert(long long &x, long long y, int i)
20
{
21
    long long nmod = 1;
22
    while (x % p[i] == 0)
23
        x /= p[i], nmod *= p[i];
24
    if (nmod > mod[i])
25
        mod[i] = nmod, rem[i] = y % nmod;
26
}
27
int main()
28
{
29
    ios::sync_with_stdio(false);
30
    cin.tie(0), cout.tie(0);
31
    cin >> n;
32
    for (int i = 1; i <= n; i++)
33
    {
34
        cin >> a[i] >> b[i];
35
        for (int j = 1; j <= idx; j++)
36
            Insert(a[i], b[i], j);
37
        if (a[i] > 1)
38
        {
39
            for (long long np = 2; np * np <= a[i]; np++)
40
                if (a[i] % np == 0)
41
                    p[++idx] = np, Insert(a[i], b[i], idx);
42
            if (a[i] > 1)
43
                p[++idx] = a[i], Insert(a[i], b[i], idx);
44
        }
45
    }
46
    long long M = 1;
47
    for (int i = 1; i <= idx; i++)
48
        M *= mod[i];
49
    long long ans = 0;
50
    for (int i = 1; i <= idx; i++)
51
        (ans += (__int128)(M / mod[i]) * ny(M / mod[i], mod[i]) % M * rem[i] % M) %= M;
52
    cout << ans;
53
    return 0;
54
}

组合数#

1
const int MOD = 998244353;
2
const int N = 4000005;
3
int fact[N], inv_fact[N], inv[N];
4
int qpow(int a, long long b){
5
    int res = 1;
6
    while (b){
7
        if (b & 1) res = 1LL * res * a % MOD;
8
        a = 1LL * a * a % MOD;
9
        b >>= 1;
10
    }
11
    return res;
12
}
13

14
void init_comb(int n){
15
    fact[0] = 1;
16
    for (int i = 1; i <= n; i++)
17
        fact[i] = 1LL * fact[i - 1] * i % MOD;
18

19
    inv_fact[n] = qpow(fact[n], MOD - 2);
20
    for (int i = n; i >= 1; i--)
21
        inv_fact[i - 1] = 1LL * inv_fact[i] * i % MOD;
22

23
    inv[1] = 1;
24
    for (int i = 2; i <= n; i++)
25
        inv[i] = 1LL * (MOD - MOD / i) * inv[MOD % i] % MOD;
26
}
27

28
int C(int n, int m){
29
    if (m < 0 || m > n) return 0;
30
    return 1LL * fact[n] * inv_fact[m] % MOD * inv_fact[n - m] % MOD;
31
}
32

33
int A(int n, int m){
34
    if (m < 0 || m > n) return 0;
35
    return 1LL * fact[n] * inv_fact[n - m] % MOD;
36
}

逆序数#

1
class FenwickTree//0-base
2
{
3
public:
4
    int n;
5
    vector<int> fen;
6
    FenwickTree(int n) : n(n), fen(n + 1) {}
7
    void upd(int x){
8
        while (x <= n){
9
            fen[x]++;
10
            x += x & -x;
11
        }
12
    }
13
    int que(int x){
14
        int ans = 0;
15
        while (x){
16
            ans += fen[x];
17
            x -= x & -x;
18
        }
19
        return ans;
20
    }
21
    int f(vector<int> x){
22
        ff(i, 0, n) fen[i] = 0;
23
        int ans = 0;
24
        ffg(i, x.size() - 1, 0){
25
            ans += que(x[i]);
26
            upd(x[i]);
27
        }
28

29
        return ans;
30
    }
31
};

线性基#

P3812 【模板】线性基 - 洛谷

给定 $n$ 个整数（数字可能重复），求在这些数中选取任意个，使得他们的异或和最大。

1
long long n, k;
2
vector<long long> p(105);
3
const int bit = 51;
4
void ins(vector<long long> &p){
5
    for (int i = bit; i >= 0; i--){
6
        for (int j = k; j < n; j++)
7
            if ((p[j] >> i) & 1){
8
                swap(p[j], p[k]);
9
                break;
10
            }
11

12
        if (((p[k] >> i) & 1) == 0)
13
            continue;
14
        for (int j = 0; j < n; j++)
15
            if (j != k && ((p[j] >> i) & 1))
16
                p[j] ^= p[k];
17
        k++;
18
        if (k == n)
19
            break;
20
    }
21
}
22

23
long long ans = 0;
24
signed main(){
25
    cin >> n;
26
    for (int i = 0; i < n; i++){
27
        cin >> p[i];
28
    }
29
    ins(p);
30
    for (int i = k; i >= 0; i--){
31
        ans ^= p[i];
32
    }
33
    cout << ans << '\n';
34
    return 0;
35
}

树状数组求 $a_i$ 前比它小的数量#

1
#include <bits/stdc++.h>
2
using namespace std;
3
const int N = 200005;
4
int n;
5
int a[N], rk_[N];
6
int tr[N];
7
int lowbit(int x) {
8
    return x & -x;
9
}
10
void add(int x, int v) {
11
    for (; x <= n; x += lowbit(x)) tr[x] += v;
12
}
13
int query(int x) {
14
    int res = 0;
15
    for (; x > 0; x -= lowbit(x)) res += tr[x];
16
    return res;
17
}
18
void clear_tree() {
19
    for (int i = 1; i <= n; i++) tr[i] = 0;
20
}
21

22
void solve() {
23
    cin >> n;
24
    vector<int> b;
25
    for (int i = 1; i <= n; i++) {
26
        cin >> a[i];
27
        b.push_back(a[i]);
28
    }
29
    // 离散化
30
    sort(b.begin(), b.end());
31
    b.erase(unique(b.begin(), b.end()), b.end());
32
    for (int i = 1; i <= n; i++) {
33
        rk_[i] = lower_bound(b.begin(), b.end(), a[i]) - b.begin() + 1;
34
    }
35
    vector<int> pre_less(n + 1), pre_greater(n + 1);
36
    vector<int> suf_less(n + 1), suf_greater(n + 1);
37

38
    // 1) 前面比它小 / 大
39
    clear_tree();
40
    for (int i = 1; i <= n; i++) {
41
        int r = rk_[i];
42
        pre_less[i] = query(r - 1);
43
        pre_greater[i] = (i - 1) - query(r);
44
        add(r, 1);
45
    }
46

47
    // 2) 后面比它小 / 大
48
    clear_tree();
49
    for (int i = n; i >= 1; i--) {
50
        int r = rk_[i];
51
        suf_less[i] = query(r - 1);
52
        suf_greater[i] = (n - i) - query(r);
53
        add(r, 1);
54
    }
55

56
    for (int i = 1; i <= n; i++) cout << pre_less[i] << " ";
57
    cout << '\n';
58

59
    for (int i = 1; i <= n; i++) cout << pre_greater[i] << " ";
60
    cout << '\n';
61

62
    for (int i = 1; i <= n; i++) cout << suf_less[i] << " ";
63
    cout << '\n';
64

65
    for (int i = 1; i <= n; i++) cout << suf_greater[i] << " ";
66
    cout << '\n';
67
}

搜索#

DFS#

1
int n, a[100005], book[100005];
2
void dfs(int step){
3
  int i;
4
  if (step == n + 1){
5
    for (i = 1; i <= n; i++)
6
      cout << setw(5) << a[i];
7
    printf("\n");
8
    return;
9
  }
10
  for (int i = 1; i <= n; i++){
11
    if (book[i] == 0){
12
      a[step] = i;
13
      book[i] = 1;
14
      dfs(step + 1);
15
      book[i] = 0;
16
    }
17
  }
18
}
19
int main(){
20
  scanf("%d", &n);
21
  dfs(1);
22
  return 0;
23
}

BFS#

1
struct node{int x, y, step;};
2
int n, m;
3
int next1[8][2] = {{1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}};
4
queue<node> q;
5
void bfs(int step){
6
  vector<vector<int>> vis(n + 1, vector<int>(m + 1, 0));
7
  int cnt = 1;
8
  while (!q.empty())
9
    q.pop();
10
  q.push({0, 0, 0});
11
  vis[0][0] = 1;
12
  node now = {0, 0, 0};
13
  node next;
14
  auto ok = [=](int x, int y) -> bool
15
  { return x >= 1 && x <= n && y >= 1 && y <= m && !vis[x][y]; };
16
  while (!q.empty())
17
  {
18
    now = q.front();
19
    q.pop();
20
    for (int i = 0; i < 8; i++){
21
      next.x = now.x + next1[i][0];
22
      next.y = now.y + next1[i][1];
23
      next.step = now.step + 1;
24
      if (ok(next.x, next.y)){
25
        vis[next.x][next.y] = 1;
26
        q.push(next);
27
        cnt++;
28
      }
29
    }
30
  }
31
  cout << cnt << endl;
32
}

二分搜索#

1
int binary_search1(int start, int end, int key){
2
    int ret = -1; // 未搜索到数据返回-1下标
3
    int mid;
4
    while (start <= end){
5
        mid = start + ((end - start) >> 1); // 直接平均可能会溢出，所以用这个算法
6
        if (arr[mid] < key)
7
            start = mid + 1;
8
        else if (arr[mid] > key)
9
            end = mid - 1;
10
        else{ // 最后检测相等是因为多数搜索情况不是大于就是小于
11
            ret = mid;
12
            break;
13
        }
14
    }
15
    return ret; // 单一出口
16
}
17
int binary_search2(vector<int> &arr, int key){
18
    return lower_bound(all(arr), key) - arr.begin();
19
    // 二分查找，返回下标,首个大于等于key的元素的下标
20
}
21
int binary_search3(vector<int> &arr, int key){
22
    return upper_bound(all(arr), key) - arr.begin();
23
    // 二分查找，返回下标,首个大于key的元素的下标
24
}

二分答案#

“至少多少 / 最小多少 / 最短多少” → 找最小可行值

“至多多少 / 最大多少 / 最长多少” → 找最大可行值

check(mid) 越大越容易成立 → 常常是 找最小可行值

check(mid) 越大越不容易成立 → 常常是 找最大可行值

1
// 1. 先确定 check(mid) 是否单调
2
// 2. 决定是找最小可行值还是最大可行值
3
// 3. 保证边界覆盖答案
4

5
// 最小可行值
6
long long l = L, r = R;
7
while (l < r)
8
{
9
    long long mid = l + (r - l) / 2;
10
    if (check(mid))
11
        r = mid;
12
    else
13
        l = mid + 1;
14
}
15
return l;
16

17
// 最大可行值
18
long long l = L, r = R;
19
while (l < r)
20
{
21
    long long mid = l + (r - l + 1) / 2;
22
    if (check(mid))
23
        l = mid;
24
    else
25
        r = mid - 1;
26
}
27
return l;

DP#

记忆化搜索#

第一行有 2 个整数 $T$ （1≤ $T$ ≤1000）和 $M$ （1≤ $M$ ≤100），用一个空格隔开， $T$ 代表总共能够用来采药的时间， $M$ 代表山洞里的草药的数目。

接下来的 $M$ 行每行包括两个在 1 到 100 之间（包括 1 和 100）的整数，分别表示采摘某株草药的时间和这株草药的价值。

输出在规定的时间内可以采到的草药的最大总价值。

1
int n, t;
2
int tcost[103], mget[103];
3
int mem[103][1003];
4

5
int dfs(int pos, int tleft){
6
    if (mem[pos][tleft] != -1)
7
        return mem[pos][tleft]; // 已经访问过的状态，直接返回之前记录的值
8
    if (pos == n + 1)
9
        return mem[pos][tleft] = 0;
10
    int dfs1, dfs2 = -INF;
11
    dfs1 = dfs(pos + 1, tleft);
12
    if (tleft >= tcost[pos])
13
        dfs2 = dfs(pos + 1, tleft - tcost[pos]) + mget[pos]; // 状态转移
14
    return mem[pos][tleft] = max(dfs1, dfs2);                // 最后将当前状态的值存下来
15
}
16

17
int main(){
18
    memset(mem, -1, sizeof(mem));
19
    cin >> t >> n;
20
    for (int i = 1; i <= n; i++)
21
        cin >> tcost[i] >> mget[i];
22
    cout << dfs(1, t) << endl;
23
    return 0;
24
}

背包DP#

01背包#

题意概要：有 $n$ 个物品和一个容量为 $W$ 的背包，每个物品有重量 $w_i$ 和价值 $v_i$ 两种属性，要求选若干物品放入背包使背包中物品的总价值最大且背包中物品的总重量不超过背包的容量。

在上述例题中，由于每个物体只有两种可能的状态（取与不取），对应二进制中的 0 和 1，这类问题便被称为「0-1 背包问题」。

1
int main(){
2
    cin >> n >> W;
3
    for (int i = 1; i <= n; i++)
4
        cin >> w[i] >> v[i]; // 读入数据
5
    for (int i = 1; i <= n; i++)
6
        for (int j = W; j >= w[i]; j--) // 从W到小枚举背包容量
7
            f[j] = max(f[j], f[j - w[i]] + v[i]);
8
    cout << f[W];
9
    return 0;
10
}

完全背包#

完全背包模型与 0-1 背包类似，与 0-1 背包的区别仅在于一个物品可以选取无限次，而非仅能选取一次。

我们可以借鉴 0-1 背包的思路，进行状态定义：设 $f_{i,j}$ 为只能选前 $i$ 个物品时，容量为 $j$ 的背包可以达到的最大价值。

需要注意的是，虽然定义与 0-1 背包类似，但是其状态转移方程与 0-1 背包并不相同。

1
int main(){
2
    cin >> W >> n;
3
    for (int i = 1; i <= n; i++)
4
        cin >> w[i] >> v[i];
5
    for (int i = 1; i <= n; i++)
6
        for (int j = w[i]; j <= W; j++) // 从小到大枚举背包容量
7
            f[j] = max(f[j], f[j - w[i]] + v[i]);
8
    cout << f[W];
9
    return 0;
10
}

多重背包#

多重背包也是 0-1 背包的一个变式。与 0-1 背包的区别在于每种物品有 $k$ 个，而非一个。

考虑二进制优化。

1
void erjz() // 二进制优化
2
{
3
    int a, b, s;
4
    cin >> b >> a >> s;
5
    int k = 1;
6
    while (k <= s){
7
        cnt++;
8
        w[cnt] = a * k;
9
        v[cnt] = b * k;
10
        s -= k;
11
        k <<= 1;
12
    }
13
    if (s > 0){
14
        cnt++;
15
        w[cnt] = a * s;
16
        v[cnt] = b * s;
17
    }
18
}
19
signed main(){
20
    cin >> n >> W;
21
    for (int i = 1; i <= n; i++)
22
        erjz();
23
    n = cnt;
24
    for (int i = 1; i <= n; i++){
25
        for (int j = W; j >= w[i]; j--){
26
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
27
        }
28
    }
29
    cout << dp[W];
30
    return 0;
31
}

也可以单调队列优化。

1
constexpr int MAXV = 4e4 + 10;
2
constexpr int MAXN = 1e2 + 10;
3

4
using namespace std;
5

6
int n, W, last = 0, now = 1;
7
array<int, MAXN> v, w, k;
8
array<array<int, MAXV>, 2> f;
9
deque<int> q;
10

11
int main(){
12
    ios::sync_with_stdio(false);
13
    cin >> n >> W;
14
    for (int i = 1; i <= n; i++)
15
        cin >> v[i] >> w[i] >> k[i];
16
    for (int i = 1; i <= n; i++){
17
        for (int y = 0; y < w[i]; y++){
18
            // 清空队列
19
            deque<int>().swap(q);
20
            for (int x = 0; x * w[i] + y <= W; x++){
21
                // 弹出不在范围的元素
22
                while (!q.empty() && q.front() < x - k[i]){
23
                    q.pop_front();
24
                }
25
                // 保证队列单调
26
                while (!q.empty() &&
27
                       f[last][q.back() * w[i] + y] - q.back() * v[i] <
28
                           f[last][x * w[i] + y] - x * v[i])
29
                    q.pop_back();
30
                q.push_back(x);
31
                f[now][x * w[i] + y] =
32
                    f[last][q.front() * w[i] + y] - q.front() * v[i] + x * v[i];
33
            }
34
        }
35
        swap(last, now);
36
    }
37
    cout << f[last][W] << endl;
38
    return 0;
39
}

混合背包#

混合背包就是将前面三种的背包问题混合起来，有的只能取一次，有的能取无限次，有的只能取 k 次。

这种题目看起来很吓人，可是只要领悟了前面几种背包的中心思想，并将其合并在一起就可以了。下面给出伪代码：

1
for (循环物品种类)
2
{
3
  if (是 0 - 1 背包)
4
    套用 0 - 1 背包代码;
5
  else if (是完全背包)
6
    套用完全背包代码;
7
  else if (是多重背包)
8
    套用多重背包代码;
9
}

有 $n$ 种樱花树和长度为 $T$ 的时间，有的樱花树只能看一遍，有的樱花树最多看 $A_i$ 遍，有的樱花树可以看无数遍。每棵樱花树都有一个美学值 $C_i$ ，求在 T 的时间内看哪些樱花树能使美学值最高。

1
for (int i = 1; i <= n; i++)
2
{
3
    if (cnt[i] == 0)
4
    { // 如果数量没有限制使用完全背包的核心代码
5
        for (int weight = w[i]; weight <= W; weight++)
6
            dp[weight] = max(dp[weight], dp[weight - w[i]] + v[i]);
7
    }
8
    else
9
    { // 物品有限使用多重背包的核心代码，它也可以处理0-1背包问题
10
        for (int weight = W; weight >= w[i]; weight--)
11
            for (int k = 1; k * w[i] <= weight && k <= cnt[i]; k++)
12
                dp[weight] = max(dp[weight], dp[weight - k * w[i]] + k * v[i]);
13
    }
14
}

二维费用背包#

有 $n$ 个任务需要完成，完成第 $i$ 个任务需要花费 $t_i$ 分钟，产生 $c_i$ 元的开支。

现在有 $T$ 分钟时间， $W$ 元钱来处理这些任务，求最多能完成多少任务。

1
for (int k = 1; k <= n; k++)
2
  for (int i = m; i >= mi; i--)    // 对经费进行一层枚举
3
    for (int j = t; j >= ti; j--)  // 对时间进行一层枚举
4
      dp[i][j] = max(dp[i][j], dp[i - mi][j - ti] + 1);

分组背包#

有 $n$ 件物品和一个大小为 $m$ 的背包，第 $i$ 个物品的价值为 $w_i$ ，体积为 $v_i$ 。同时，每个物品属于一个组，同组内最多只能选择一个物品。求背包能装载物品的最大总价值。

这种题怎么想呢？其实是从「在所有物品中选择一件」变成了「从当前组中选择一件」，于是就对每一组进行一次 0-1 背包就可以了。

再说一说如何进行存储。我们可以将 $t_{k,i}$ 表示第 $k$ 组的第 $i$ 件物品的编号是多少，再用 $cnt_k$ 表示第 $k$ 组物品有多少个。

1
for (int k = 1; k <= ts; k++)          // 循环每一组
2
  for (int i = m; i >= 0; i--)         // 循环背包容量
3
    for (int j = 1; j <= cnt[k]; j++)  // 循环该组的每一个物品
4
      if (i >= w[t[k][j]])             // 背包容量充足
5
        dp[i] = max(dp[i],
6
                    dp[i - w[t[k][j]]] + c[t[k][j]]);  // 像0-1背包一样状态转移

有依赖的背包#

金明有 $n$ 元钱，想要买 $m$ 个物品，第 i 件物品的价格为 $v_i$ ，重要度为 $p_i$ 。有些物品是从属于某个主件物品的附件，要买这个物品，必须购买它的主件。

即树形DP。

树形DP#

基础#

某大学有 $n$ 个职员，编号为 $1…n$ 。

他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。

现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 $r_i$ ，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。

求最大的快乐指数。

1
void dfs(int u, vector<int> &vis, vector<vector<int>> &dp, vector<vector<int>> &g){
2
    vis[u] = 1;
3
    for (int v : g[u]){
4
        if (vis[v])
5
            continue;
6
        dfs(v, vis, dp, g);
7
        dp[u][1] += dp[v][0];
8
        dp[u][0] += max(dp[v][0], dp[v][1]);
9
    }
10
}
11
void solve(){
12
    int n;
13
    cin >> n;
14
    vector<vector<int>> dp(n + 1, vector<int>(2));
15
    vector<int> du(n + 1), vis(n + 1);
16
    vector<vector<int>> g(n + 1);
17
    for (int i = 1; i <= n; i++)
18
        cin >> dp[i][1];
19
    for (int i = 1; i < n; i++){
20
        int u, v;
21
        cin >> u >> v;
22
        du[u]++;
23
        g[v].pb(u);
24
    }
25
    for (int i = 1; i <= n; i++){
26
        if (du[i])
27
            continue;
28
        dfs(i, vis, dp, g);
29
        cout << max(dp[i][0], dp[i][1]) << endl;
30
        return;
31
    }
32
}

树上背包#

现在有 $n$ 门课程，第 $i$ 门课程的学分为 $a_i$ ，每门课程有零门或一门先修课，有先修课的课程需要先学完其先修课，才能学习该课程。

一位学生要学习 $m$ 门课程，求其能获得的最多学分数。

1
vc<int> g[100005];
2
vc<int> t(100005, 0);
3
int n, m;
4
int dp[1005][1005];
5
int dfs(int u){
6
    int p = 1;
7
    for (auto v : g[u]){
8
        int siz = dfs(v);
9
        for (int i = min(p, m + 1); i; i--)
10
            for (int j = 1; j <= siz && i + j <= m + 1; j++)
11
                dp[u][i + j] = max(dp[u][i + j], dp[u][i] + dp[v][j]);
12
        p += siz;
13
    }
14
    return p;
15
}
16
void solve(){
17
    cin >> n >> m;
18
    ff(i, 1, n + 1){
19
        int u;
20
        cin >> u >> dp[i][1];
21
        g[u].pb(i);
22
    }
23
    dfs(0);
24
    cout << dp[0][m + 1] << endl;
25
}

最长上升子序列#

1
#include <vector>
2
#include <algorithm>
3
using namespace std;
4
int lengthOfLIS(vector<int>& nums) {
5
    if (nums.empty()) return 0;
6
    vector<int> dp(nums.size(), 1);
7
    int max_len = 1;
8
    for (int i = 0; i < nums.size(); ++i) {
9
        for (int j = 0; j < i; ++j) {
10
            if (nums[j] < nums[i]) {
11
                dp[i] = max(dp[i], dp[j] + 1);
12
            }
13
        }
14
        max_len = max(max_len, dp[i]);
15
    }
16
    return max_len;
17
}
18

19
//贪心 + 二分查找：
20
//lower_bound 函数（需包含 <algorithm> 头文件）用于在有序的 tails 数组中查找插入位置。
21
//直接操作 tails 数组维护最小末尾元素，时间复杂度优化到 O(n log n)，适用于大规模数据。
22
int lengthOfLIS(vector<int>& nums) {
23
    vector<int> tails;
24
    for (int num : nums) {
25
        // 使用 lower_bound 找到第一个 >= num 的位置（类似 bisect_left）
26
        auto it = lower_bound(tails.begin(), tails.end(), num);
27
        if (it == tails.end()) {
28
            tails.push_back(num);
29
        } else {
30
            *it = num;
31
        }
32
    }
33
    return tails.size();
34
}

ST表#

1
#include <cstdio>
2
#include <cmath>
3
#include <algorithm>
4
using namespace std;
5
int f[100001][40], a, x, LC, n, m, p, len, l, r;
6
int main(){
7
    scanf("%d%d", &n, &m);
8
    for (int i = 1; i <= n; i++){
9
        scanf("%d", &a);
10
        f[i][0] = a;
11
    }
12
    LC = (int)(log(n) / log(2));
13
    for (int j = 1; j <= LC; j++)
14
        for (int i = 1; i <= n - (1 << j) + 1; i++)
15
            f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
16
    for (int i = 1; i <= m; i++){
17
        scanf("%d%d", &l, &r);
18
        p = (int)(log(r - l + 1) / log(2));
19
        printf("%d\n", max(f[l][p], f[r - (1 << p) + 1][p]));
20
    }
21
    return 0;
22
}
23

24
template <typename T>
25
class ST{
26
public: // 1-based
27
    int n;
28
    vector<vector<T>> st;
29
    ST(vector<T> &a = {}) : n((int)a.size()){
30
        st = vector<vector<T>>(n + 1, vector<T>(22 + 1));
31
        build(n, a);
32
    }
33
    inline T get(const T &a, const T &b) const { return min(a, b); };
34
    void build(int n, vector<T> &a){
35
        for (int i = 1; i <= n; i++)
36
            st[i][0] = a[i];
37
        for (int p = 1, t = 2; t <= n; t <<= 1, p++){
38
            for (int i = 1; i <= n; i++){
39
                if (i + t - 1 > n)
40
                    break;
41
                st[i][p] = min(st[i][p - 1], st[i + (t >> 1)][p - 1]);
42
            }
43
        }
44
    }
45
    inline T find(int l, int r){
46
        int t = (int)log2(r - l + 1);
47
        return get(st[l][t], st[r - (1 << t) + 1][t]);
48
    }
49
};
50

51
template <typename T>
52
class ST2{
53
public: // 记得加上public
54
    int n;
55
    vector<vector<T>> st;
56
    ST2(vector<T> &a = {}) : n((int)a.size()){
57
        st = vector<vector<T>>(n + 1, vector<T>(22 + 1));
58
        build(n, a);
59
    }
60
    inline T get(const T &a, const T &b) const { return max(a, b); };
61
    void build(int n, vector<T> &a){
62
        for (int i = 1; i <= n; i++)
63
            st[i][0] = a[i];
64
        for (int p = 1, t = 2; t <= n; t <<= 1, p++){
65
            for (int i = 1; i <= n; i++){
66
                if (i + t - 1 > n)
67
                    break;
68
                st[i][p] = max(st[i][p - 1], st[i + (t >> 1)][p - 1]);
69
            }
70
        }
71
    }
72
    inline T find(int l, int r){
73
        int t = (int)log2(r - l + 1);
74
        return get(st[l][t], st[r - (1 << t) + 1][t]);
75
    }
76
};

图论#

链式前向星#

1
struct edge{
2
    int to, w, next;
3
} e[100005];
4
int head[100005], tot = 0;
5
void add(int u, int v, int w){
6
    e[++tot].to = v;
7
    e[tot].w = w;
8
    e[tot].next = head[u];
9
    head[u] = tot;
10
}
11
//遍历
12
for (int i = head[u]; i; i = e[i].next)
13
    int v = e[i].to;

并查集#

1
int fa[100005];
2
int find(int x){
3
    return fa[x] == x ? x : fa[x] = find(fa[x]);
4
}
5
void merge(int x, int y){
6
    int fx = find(x), fy = find(y);
7
    if (fx != fy)
8
        fa[fx] = fy;
9
}
10
void init(int n){
11
    for (int i = 1; i <= n; i++)
12
        fa[i] = i;
13
}

拓扑排序#

给你一个食物网，你要求出这个食物网中最大食物链的数量。

1
const int N = 5e3 + 2; //定义常量大小
2
const int mod = 80112002; //定义最终答案mod的值
3

4
int n, m; //n个点 m条边
5
int in[N], out[N]; //每个点的入度和出度
6
vector<int>nei[N]; //存图，即每个点相邻的点
7
queue<int>q; //拓扑排序模板所需队列
8
int ans; //答案
9
int num[N]; //记录到这个点的类食物连的数量，可参考图
10

11
signed main(){
12
  n = read(), m = read();
13
  for(rg int i = 1; i <= m; ++i){ //输入边
14
    int x = read(), y = read();
15
    ++in[y], ++out[x]; //右节点入度+1,左节点出度+1
16
    nei[x].push_back(y); //建立一条单向边
17
  }
18
  for(rg int i = 1; i <= n; ++i) //初次寻找入度为0的点(最佳生产者)
19
    if(!in[i]){ //是最佳生产者
20
      num[i] = 1; //初始化
21
      q.push(i); //压入队列
22
    }
23
  while(!q.empty()){ //只要还可以继续Topo排序
24
    int tot = q.front();//取出队首
25
    q.pop();//弹出
26
    int len = nei[tot].size();
27
    for(rg int i = 0;i < len; ++i){ //枚举这个点相邻的所有点
28
      int next = nei[tot][i]; //取出目前枚举到的点
29
      --in[next];//将这个点的入度-1(因为目前要删除第tot个点)
30
      num[next] = (num[next] + num[tot]) % mod;//更新到下一个点的路径数量
31
      if(in[next] == 0)q.push(nei[tot][i]);//如果这个点的入度为0了,那么压入队列
32
    }
33
  }
34
  for(rg int i = 1; i <= n; ++i) //寻找出度为0的点(最佳消费者)
35
    if(!out[i]) //符合要求
36
      ans = (ans + num[i]) % mod;//累加答案
37
  write(ans);//输出
38
  return 0;//end
39
}

最小生成树#

Prim 算法#

1
// 使用二叉堆优化的 Prim 算法。
2
#include <cstring>
3
#include <iostream>
4
#include <queue>
5
using namespace std;
6
constexpr int N = 5050, M = 2e5 + 10;
7
struct E{
8
    int v, w, x;
9
} e[M * 2];
10
int n, m, h[N], cnte;
11
void adde(int u, int v, int w) { e[++cnte] = E{v, w, h[u]}, h[u] = cnte; }
12
struct S{
13
    int u, d;
14
};
15
bool operator<(const S &x, const S &y) { return x.d > y.d; }
16
priority_queue<S> q;
17
int dis[N];
18
bool vis[N];
19
int res = 0, cnt = 0;
20
void Prim(){
21
    memset(dis, 0x3f, sizeof(dis));
22
    dis[1] = 0;
23
    q.push({1, 0});
24
    while (!q.empty())
25
    {
26
        if (cnt >= n)
27
            break;
28
        int u = q.top().u, d = q.top().d;
29
        q.pop();
30
        if (vis[u])
31
            continue;
32
        vis[u] = true;
33
        ++cnt;
34
        res += d;
35
        for (int i = h[u]; i; i = e[i].x)
36
        {
37
            int v = e[i].v, w = e[i].w;
38
            if (w < dis[v])
39
                dis[v] = w, q.push({v, w});
40
        }
41
    }
42
}
43
int main(){
44
    cin >> n >> m;
45
    for (int i = 1, u, v, w; i <= m; ++i){
46
        cin >> u >> v >> w, adde(u, v, w), adde(v, u, w);
47
    }
48
    Prim();
49
    if (cnt == n)
50
        cout << res;
51
    else
52
        cout << "No MST.";
53
    return 0;
54
}

Kruskal#

1
struct Edge{
2
    int u, v, w;
3
} edge[200005];
4
int fa[5005], n, m, ans, eu, ev, cnt;
5
il bool cmp(Edge a, Edge b){return a.w < b.w;}
6
// 快排的依据（按边权排序）
7
il int find(int x){
8
    while (x != fa[x])
9
        x = fa[x] = fa[fa[x]];
10
    return x;
11
}
12
il void kruskal(){
13
    sort(edge, edge + m, cmp);
14
    // 将边的权值排序
15
    for (re int i = 0; i < m; i++){
16
        eu = find(edge[i].u), ev = find(edge[i].v);
17
        if (eu == ev)
18
            continue;
19
        // 若出现两个点已经联通了，则说明这一条边不需要了
20
        ans += edge[i].w;
21
        // 将此边权计入答案
22
        fa[ev] = eu;
23
        // 将eu、ev合并
24
        if (++cnt == n - 1)
25
            break;
26
        // 循环结束条件，及边数为点数减一时
27
    }
28
}
29
int main(){
30
    n = read(), m = read();
31
    for (re int i = 1; i <= n; i++)
32
        fa[i] = i;
33
    // 初始化并查集
34
    for (re int i = 0; i < m; i++)
35
        edge[i].u = read(), edge[i].v = read(), edge[i].w = read();
36
    kruskal();
37
    printf("%d", ans);
38
    return 0;
39
}

DP 求最长（短）路#

1
struct edge{
2
    int v, w;
3
};
4
int n, m;
5
vector<edge> e[MAXN];
6
vector<int> L;                              // 存储拓扑排序结果
7
int max_dis[MAXN], min_dis[MAXN], in[MAXN]; // in 存储每个节点的入度
8
void toposort(){ // 拓扑排序
9
    queue<int> S;
10
    memset(in, 0, sizeof(in));
11
    for (int i = 1; i <= n; i++){
12
        for (int j = 0; j < e[i].size(); j++)
13
            in[e[i][j].v]++;
14
    }
15
    for (int i = 1; i <= n; i++)
16
        if (in[i] == 0)
17
            S.push(i);
18
    while (!S.empty()){
19
        int u = S.front();
20
        S.pop();
21
        L.push_back(u);
22
        for (int i = 0; i < e[u].size(); i++){
23
            if (--in[e[u][i].v] == 0)
24
                S.push(e[u][i].v);
25
        }
26
    }
27
}
28
void dp(int s){               // 以 s 为起点求单源最长（短）路
29
    toposort(); // 先进行拓扑排序
30
    memset(min_dis, 0x3f, sizeof(min_dis));
31
    memset(max_dis, 0, sizeof(max_dis));
32
    min_dis[s] = 0;
33
    for (int i = 0; i < L.size(); i++){
34
        int u = L[i];
35
        for (int j = 0; j < e[u].size(); j++){
36
            min_dis[e[u][j].v] = min(min_dis[e[u][j].v], min_dis[u] + e[u][j].w);
37
            max_dis[e[u][j].v] = max(max_dis[e[u][j].v], max_dis[u] + e[u][j].w);
38
        }
39
    }
40
}

单源最短路径#

P4779 【模板】单源最短路径（标准版） - 洛谷

给定一个 $n$ 个点， $m$ 条有向边的带非负权图，请你计算从 $s$ 出发，到每个点的距离。

1
const int N = 1e5 + 5;
2
vector<pair<int, int>> g[N];
3
vector<int> dis(N), vis(N);
4
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
5
void dijkstar(int s){
6
    dis[s] = 0;
7
    pq.push({0, s});
8
    while (!pq.empty()){
9
        auto [d, u] = pq.top();
10
        pq.pop();
11
        if (vis[u])
12
            continue;
13
        vis[u] = 1;
14
        for (auto [w, v] : g[u]){
15
            if (dis[v] > dis[u] + w){
16
                dis[v] = dis[u] + w;
17
                if (!vis[v])
18
                    pq.push({dis[v], v});
19
            }
20
        }
21
    }
22
}
23
void solve(){
24
    int n, m, s;
25
    cin >> n >> m >> s;
26
    fill(dis.begin(), dis.end(), INT32_MAX);
27
    for (int i = 1; i <= m; i++){
28
        int u, v, w;
29
        cin >> u >> v >> w;
30
        g[u].push_back({w, v});
31
    }
32
    dijkstar(s);
33
    for (int i = 1; i <= n; i++){
34
        cout << dis[i] << " ";
35
    }
36
}

Dijkstra#

1
#include <bits/stdc++.h>
2
using namespace std;
3
typedef pair<int, int> pii; // 存储 {距离, 节点}
4
void dijkstra(vector<vector<pii>> &graph, int start, vector<int> &dist){
5
    int n = graph.size();
6
    dist.assign(n, INT_MAX);
7
    dist[start] = 0;
8
    // 最小堆优先队列，按距离从小到大排序
9
    priority_queue<pii, vector<pii>, greater<pii>> pq;
10
    pq.push({0, start});
11
    while (!pq.empty()){
12
        int u = pq.top().second;
13
        int d = pq.top().first;
14
        pq.pop();
15
        // 如果当前距离大于已记录的最短距离，跳过
16
        if (d > dist[u])
17
            continue;
18
        // 遍历所有邻接节点
19
        for (auto &edge : graph[u]){
20
            int v = edge.first;
21
            int w = edge.second;
22
            // 松弛操作（Relaxation）
23
            if (dist[v] > dist[u] + w){
24
                dist[v] = dist[u] + w;
25
                pq.push({dist[v], v});
26
            }
27
        }
28
    }
29
}
30
int main()
31
{
32
    int n, m, s, t;
33
    cin >> n >> m >> s >> t;
34
    vector<vector<pii>> graph(n);
35
    for (int i = 0; i < m; i++){
36
        int u, v, w;
37
        cin >> u >> v >> w;
38
        graph[u].push_back({v, w});
39
        graph[v].push_back({u, w});
40
    }
41
    vector<int> dist;
42
    dijkstra(graph, s, dist);
43
    cout << dist[t] << endl;
44
    return 0;
45
}

全源最短路(Johnson)#

P5905 【模板】全源最短路（Johnson） - 洛谷

给定一个包含 $n$ 个结点和 $m$ 条带权边的有向图，求所有点对间的最短路径长度，一条路径的长度定义为这条路径上所有边的权值和。

边权可能为负，且图中可能存在重边和自环；部分数据卡 $n$ 轮 SPFA 算法。

$1\leq n\leq 3\times 10^3,\ \ 1\leq m\leq 6\times 10^3,\ \ 1\leq u,v\leq n,\ \ -3\times 10^5\leq w\leq 3\times 10^5$ 。

1
const int N = 2e3 + 10;
2
const int INF = 1e18;
3
struct edge{
4
    int v, w;
5
};
6
vector<edge> e[N];
7
vector<int> dis(N), vis(N), cnt(N), val(N);
8

9
queue<int> q;
10
bool spfa(int n){
11
    fill(dis.begin(), dis.end(), INF);
12
    dis[0] = 0;
13
    vis[0] = 1;
14
    q.push(0);
15
    while (!q.empty()){
16
        int u = q.front();
17
        q.pop();
18
        vis[u] = 0;
19
        for (auto &it : e[u]){
20
            int v = it.v, w = it.w;
21
            if (dis[v] > dis[u] + w){
22
                dis[v] = dis[u] + w;
23
                cnt[v] = cnt[u] + 1; // 记录最短路经过的边数
24
                if (cnt[v] >= n + 1)
25
                    return false;
26
                if (!vis[v]){
27
                    q.push(v);
28
                    vis[v] = 1;
29
                }
30
            }
31
        }
32
    }
33
    return true;
34
}
35
vector<int> dis2(N);
36
void dijkstra(int s){
37
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
38
    fill(dis2.begin(), dis2.end(), INF);
39
    fill(vis.begin(), vis.end(), 0);
40
    dis2[s] = 0;
41
    q.push({0, s});
42
    while (!q.empty()){
43
        int u = q.top().second;
44
        q.pop();
45
        if (vis[u])
46
            continue;
47
        vis[u] = 1;
48
        for (auto &it : e[u]){
49
            int v = it.v, w = it.w;
50
            if (dis2[v] > dis2[u] + w){
51
                dis2[v] = dis2[u] + w;
52
                q.push({dis2[v], v});
53
            }
54
        }
55
    }
56
}
57
void solve(){
58
    ios::sync_with_stdio(false);
59
    cin.tie(0);
60
    int n, m;
61
    cin >> n >> m;
62
    for (int i = 1; i <= n; i++){
63
        cin >> val[i];
64
    }
65
    for (int i = 1; i <= m; i++){
66
        int u, v, w;
67
        cin >> u >> v >> w;
68
        e[u].push_back({v, w});
69
    }
70
    for (int i = 1; i <= n; i++){
71
        e[0].push_back({i, 0});
72
    }
73
    if (!spfa(n)){
74
        cout << -1 << '\n';
75
        return;
76
    }
77
    for (int i = 1; i <= n; i++){
78
        for (auto &it : e[i]){
79
            it.w += dis[i] - dis[it.v];
80
        }
81
    }
82
    int ans = LLONG_MAX;
83
    for (int i = 1; i <= n; i++){
84
        dijkstra(i);
85
        int tmp = 0;
86
        for (int j = 1; j <= n; j++){
87
            if (dis2[j] == INF){
88
                tmp += 1e9 * val[j];
89
            }
90
            else{
91
                tmp += val[j] * (dis2[j] + dis[j] - dis[i]);
92
            }
93
        }
94
        ans = min(ans, tmp);
95
    }
96
    cout << ans << '\n';
97
}

割点#

P3388 【模板】割点（割顶） - 洛谷

1
const int N = 1e5 + 6;
2
int n, m, u, v;
3
vvi g(N);
4
int dfn[N], low[N], idx, res;
5
// dfn：记录每个点的时间戳
6
// low：能不经过父亲到达最小的编号，idx：时间戳，res：答案数量
7
bool vis[N], flag[N]; // flag: 答案 vis：标记是否重复
8
void tarjan(int u, int fa){
9
    vis[u] = 1;
10
    dfn[u] = low[u] = ++idx; // 时间戳
11
    int child = 0;
12
    for (auto v : g[u]){
13
        if (!vis[v]){
14
            child++;
15
            tarjan(v, u);
16
            low[u] = min(low[u], low[v]);
17
            if (fa != u && low[v] >= dfn[u] && !flag[u]){
18
                flag[u] = 1;
19
                res++;
20
            }
21
        }
22
        else if (v != fa){
23
            low[u] = min(low[u], dfn[v]);
24
        }
25
    }
26
    if (fa == u && child > 1 && !flag[u]){
27
        flag[u] = 1;
28
        res++;
29
    }
30
}
31
void Murasame(){
32
    read(n, m);
33
    ff(i, 1, m){
34
        read(u, v);
35
        g[u].pb(v);
36
        g[v].pb(u);
37
    }
38
    ff(i, 1, n){
39
        if (!vis[i]){
40
            idx = 0;
41
            tarjan(i, i);
42
        }
43
    }
44
    wl(res);
45
    ff(i, 1, n){
46
        if (flag[i])
47
            wr(i);
48
    }
49
    wl();
50
}

二分图最大匹配#

P3386 【模板】二分图最大匹配 - 洛谷

给定一个二分图，其左部点的个数为 $n$ ，右部点的个数为 $m$ ，边数为 $e$ ，求其最大匹配的边数。

1
// 匈牙利算法
2
// O(n*e)
3
const int N = 505;
4
int n, m, e;
5
int tim[N];   // 时间戳
6
int match[N]; // 匹配
7
vector<int> g[N];
8
bool dfs(int u, int t) // 当前节点, 时间戳
9
{
10
    if (tim[u] == t)
11
        return false;
12
    tim[u] = t;
13
    for (auto v : g[u]){
14
        if (!match[v] || dfs(match[v], t)){
15
            match[v] = u;
16
            return true;
17
        }
18
    }
19
    return false;
20
}
21
void solve1(){
22
    cin >> n >> m >> e;
23
    for (int i = 1; i <= e; i++){
24
        int u, v;
25
        cin >> u >> v;
26
        g[u].push_back(v);
27
    }
28
    int ans = 0;
29
    for (int i = 1; i <= n; i++){
30
        if (dfs(i, i))
31
            ans++;
32
    }
33
    cout << ans << '\n';
34
}
35

36
// Hopcroft–Karp算法
37
// O(sqrt(n)*e)
38
const int N = 1005; // 左部最大点数
39
const int M = 1005; // 右部最大点数
40

41
int n, m, e;
42
vector<int> g[N];
43
int matchX[N]; // 表示左部顶点 u 当前匹配到的右部顶点编号（如果未匹配则为 0）
44
int matchY[M]; // 表示右部顶点 v 当前匹配到的左部顶点编号（如果未匹配则为 0）
45
int distX[N];
46
/*BFS 阶段构建层次图时，记录左部点 u 的“层次”或“距离”。
47
如果为 -1，表示该点在当前轮层次图中不可达。*/
48
bool visY[M]; // 记录右部顶点是否访问过。
49

50
// BFS：建立层次图，返回是否存在增广路径
51
bool bfs(){
52
    queue<int> q;
53
    memset(distX, -1, sizeof(distX));
54

55
    for (int u = 1; u <= n; ++u){
56
        if (matchX[u] == 0){ // 左部未匹配点入队
57
            distX[u] = 0;
58
            q.push(u);
59
        }
60
    }
61

62
    bool found = false;
63
    while (!q.empty()){
64
        int u = q.front();
65
        q.pop();
66
        for (int v : g[u]){
67
            int w = matchY[v];
68
            if (w == 0){ // 到达右部未匹配点
69
                found = true;
70
            }
71
            else if (distX[w] == -1){
72
                distX[w] = distX[u] + 1;
73
                q.push(w);
74
            }
75
        }
76
    }
77
    return found;
78
}
79

80
// DFS：在层次图中寻找增广路
81
bool dfs(int u){
82
    for (int v : g[u]){
83
        int w = matchY[v];
84
        if (w == 0 || (distX[w] == distX[u] + 1 && dfs(w))){
85
            matchX[u] = v;
86
            matchY[v] = u;
87
            return true;
88
        }
89
    }
90
    distX[u] = -1; // 当前路径走不通，剪枝
91
    return false;
92
}
93

94
void solve2(){
95
    cin >> n >> m >> e;
96
    for (int i = 0; i < e; ++i){
97
        int u, v;
98
        cin >> u >> v;
99
        g[u].push_back(v);
100
    }
101
    int ans = 0;
102
    while (bfs()){
103
        for (int u = 1; u <= n; ++u){
104
            if (matchX[u] == 0 && dfs(u)){
105
                ans++;
106
            }
107
        }
108
    }
109
    cout << ans << '\n';
110
}

树状数组#

单点修改，区域查询#

1
ll n, m;
2
ll bit[1000005];
3
ll arr[1000005];
4
ll lowbit(ll x) { return x & -x; }
5
void add(ll x, ll y){
6
    for (int i = x; i <= n; i += lowbit(i))
7
        bit[i] += y;
8
}
9
ll ask(ll l, ll r){
10
    ll sum = 0;
11
    for (int i = l - 1; i >= 1; i -= lowbit(i))
12
        sum -= bit[i];
13
    for (int i = r; i >= 1; i -= lowbit(i))
14
        sum += bit[i];
15
    return sum;
16
}
17
void solve(){
18
    cin >> n >> m;
19
    for (int i = 1; i <= n; i++){
20
        cin >> arr[i];
21
        add(i, arr[i]);
22
    }
23
    while (m--){
24
        int op;
25
        cin >> op;
26
        if (op == 1){
27
            ll a, b;
28
            cin >> a >> b;
29
            add(a, b);
30
        }
31
        else if (op == 2){
32
            ll a, b;
33
            cin >> a >> b;
34
            cout << ask(a, b) << endl;
35
        }
36
    }
37
}

区域修改，单点查询#

1
ll n, m;
2
ll arr[1000010];
3
ll tree[1000010];
4
ll lowbit(ll x) { return x & -x; }
5
void add(ll x, ll val){
6
    while (x <= n){
7
        tree[x] += val;
8
        x += lowbit(x);
9
    }
10
}
11
ll ask(ll x){
12
    ll sum = 0;
13
    while (x > 0){
14
        sum += tree[x];
15
        x -= lowbit(x);
16
    }
17
    return sum;
18
}
19
void solve(){
20
    cin >> n >> m;
21
    for (int i = 1; i <= n; i++){
22
        cin >> arr[i];
23
        add(i, arr[i] - arr[i - 1]);
24
    }
25
    while (m--){
26
        ll op;
27
        cin >> op;
28
        if (op == 1){
29
            ll l, r, val;
30
            cin >> l >> r >> val;
31
            add(l, val);
32
            add(r + 1, -val);
33
        }
34
        else{
35
            ll x;
36
            cin >> x;
37
            cout << ask(x) << endl;
38
        }
39
    }
40
}

1
struct Fenwick {
2
    //1 - index
3
    int n;
4
    std::vector<i64> t;
5
    Fenwick(int n_ = 0, int a = 0) : t(n_ + 1, a), n(n_) {}
6
    Fenwick(std::vector<int> a) : t(a.size()), n(a.size() - 1) {
7
        for (int i = 1; i <= n; i++) {
8
            t[i] += a[i];
9

10
            int j = i + Lowbit(i);
11
            if (j <= n) {
12
                t[j] += t[i];
13
            }
14
        }
15
    }
16

17
    void operator=(const std::vector<int>& a) {
18
        t.clear();
19
        t.resize(a.size());
20
        n = a.size() - 1;
21

22
        for (int i = 1; i <= n; i++) {
23
            t[i] += a[i];
24

25
            int j = i + Lowbit(i);
26
            if (j <= n) {
27
                t[j] += t[i];
28
            }
29
        }
30
    }
31

32
    void clear() {
33
        n = 0;
34
        t.clear();
35
    }
36

37
    void resize(int x) {
38
        n = x;
39
        t.resize(x);
40
    }
41

42
    int Lowbit(int x) {
43
        return x & -x;
44
    }
45

46
    void Add(int x, int k) {
47
        while (x <= n) {
48
            t[x] += k;
49
            x += Lowbit(x);
50
        }
51
    }
52

53
    i64 Prefix(int x) {
54
        i64 sum = 0;
55
        while (x > 0) {
56
            sum += t[x];
57
            x -= Lowbit(x);
58
        }
59

60
        return sum;
61
    }
62

63
    i64 RangeSum(int l, int r) {
64
        return Prefix(r) - Prefix(l - 1);
65
    }
66
};

线段树#

1
#include <bits/stdc++.h>
2

3
using namespace std;
4
const int N = 2e5 + 5;
5
const long long INF = LLONG_MAX >> 1;
6

7
struct SegTree
8
{
9
    struct Node
10
    {
11
        int l, r;            // 当前区间范围
12
        long long sum, maxx; // 区间和 & 最大值（用于区间查询 / 单点修改）
13
        long long num;       // 区域修改 & 单点查询（普通做法）
14
        long long lazy;      // lazy 标签（用于区间修改）
15
    } tree[N * 4];
16

17
    long long a[N + 5];
18

19
    // --------------------------------------------
20
    // 建树：初始化区间信息
21
    // --------------------------------------------
22
    void build(int i, int l, int r)
23
    {
24
        tree[i].l = l, tree[i].r = r;
25
        tree[i].num = 0; // 默认无 lazy 区域修改
26

27
        if (l == r)
28
        { // 叶子节点赋值
29
            tree[i].sum = a[l];
30
            // tree[i].maxx = a[l];
31
            tree[i].num = a[l];
32
            return;
33
        }
34
        int mid = (l + r) >> 1;
35
        build(i << 1, l, mid);
36
        build(i << 1 | 1, mid + 1, r);
37

38
        tree[i].sum = tree[i << 1].sum + tree[i << 1 | 1].sum;
39
        // tree[i].maxx = max(tree[i << 1].maxx, tree[i << 1 | 1].maxx);
40
    }
41

42
    // --------------------------------------------
43
    // 不带 lazy：区间查询 sum
44
    // --------------------------------------------
45
    long long query_sum(int i, int l, int r)
46
    {
47
        if (tree[i].l >= l && tree[i].r <= r)
48
            return tree[i].sum;
49

50
        long long ans = 0;
51
        int mid = (tree[i].l + tree[i].r) >> 1;
52
        if (tree[i].r >= l)
53
            ans += query_sum(i << 1, l, r);
54
        if (tree[i].l <= r)
55
            ans += query_sum(i << 1 | 1, l, r);
56
        return ans;
57
    }
58

59
    // --------------------------------------------
60
    // 不带 lazy：区间查询 max
61
    // --------------------------------------------
62
    long long query_max(int i, int l, int r)
63
    {
64
        if (tree[i].l >= l && tree[i].r <= r)
65
            return tree[i].maxx;
66

67
        long long ans = -INF;
68
        int mid = (tree[i].l + tree[i].r) >> 1;
69
        if (tree[i].r >= l)
70
            ans = max(ans, query_max(i << 1, l, r));
71
        if (tree[i].l <= r)
72
            ans = max(ans, query_max(i << 1 | 1, l, r));
73
        return ans;
74
    }
75

76
    // --------------------------------------------
77
    // 单点修改（sum & max）
78
    // --------------------------------------------
79
    void update_point(int i, int pos, int val)
80
    {
81
        if (tree[i].l == tree[i].r)
82
        {
83
            tree[i].sum += val;
84
            tree[i].maxx += val;
85
            return;
86
        }
87
        if (pos <= tree[i << 1].r)
88
            update_point(i << 1, pos, val);
89
        else
90
            update_point(i << 1 | 1, pos, val);
91

92
        tree[i].sum = tree[i << 1].sum + tree[i << 1 | 1].sum;
93
        tree[i].maxx = max(tree[i << 1].maxx, tree[i << 1 | 1].maxx);
94
    }
95

96
    // --------------------------------------------
97
    // 区域修改（无 lazy） → 保存到 num 数组
98
    // --------------------------------------------
99
    void update_range(int i, int l, int r, int val)
100
    {
101
        if (tree[i].l >= l && tree[i].r <= r)
102
        {
103
            tree[i].num += val;
104
            return;
105
        }
106
        int mid = (tree[i].l + tree[i].r) >> 1;
107
        if (l <= mid)
108
            update_range(i << 1, l, r, val);
109
        if (r > mid)
110
            update_range(i << 1 | 1, l, r, val);
111
    }
112

113
    // --------------------------------------------
114
    // 单点查询（使用 num 数组溯源）
115
    // --------------------------------------------
116
    long long query_point(int i, int pos)
117
    {
118
        static long long s = 0; // 累加 num
119
        s += tree[i].num;
120
        if (tree[i].l == tree[i].r)
121
            return s; // 到叶子
122
        int mid = (tree[i].l + tree[i].r) >> 1;
123
        if (pos <= mid)
124
            return query_point(i << 1, pos);
125
        else
126
            return query_point(i << 1 | 1, pos);
127
    }
128

129
    // --------------------------------------------
130
    // lazy 下推
131
    // --------------------------------------------
132
    void push_down(int i)
133
    {
134
        if (tree[i].lazy)
135
        {
136
            tree[i << 1].lazy += tree[i].lazy;
137
            tree[i << 1 | 1].lazy += tree[i].lazy;
138

139
            int mid = (tree[i].l + tree[i].r) >> 1;
140
            tree[i << 1].sum += tree[i].lazy * (mid - tree[i << 1].l + 1);
141
            tree[i << 1 | 1].sum += tree[i].lazy * (tree[i << 1 | 1].r - mid);
142

143
            tree[i << 1].maxx += tree[i].lazy;
144
            tree[i << 1 | 1].maxx += tree[i].lazy;
145

146
            tree[i].lazy = 0;
147
        }
148
    }
149

150
    // --------------------------------------------
151
    // 带 lazy：区间加 k
152
    // --------------------------------------------
153
    void update_range_lazy(int i, int l, int r, long long k)
154
    {
155
        if (tree[i].l >= l && tree[i].r <= r)
156
        {
157
            tree[i].sum += k * (tree[i].r - tree[i].l + 1);
158
            tree[i].maxx += k;
159
            tree[i].lazy += k;
160
            return;
161
        }
162
        push_down(i);
163

164
        if (tree[i << 1].r >= l)
165
            update_range_lazy(i << 1, l, r, k);
166
        if (tree[i << 1 | 1].l <= r)
167
            update_range_lazy(i << 1 | 1, l, r, k);
168

169
        tree[i].sum = tree[i << 1].sum + tree[i << 1 | 1].sum;
170
        tree[i].maxx = max(tree[i << 1].maxx, tree[i << 1 | 1].maxx);
171
    }
172

173
    // --------------------------------------------
174
    // 带 lazy：区间查询 sum
175
    // --------------------------------------------
176
    long long query_sum_lazy(int i, int l, int r)
177
    {
178
        if (tree[i].l >= l && tree[i].r <= r)
179
            return tree[i].sum;
180
        if (tree[i].r < l || tree[i].l > r)
181
            return 0;
182

183
        push_down(i);
184
        long long ans = 0;
185
        if (tree[i << 1].r >= l)
186
            ans += query_sum_lazy(i << 1, l, r);
187
        if (tree[i << 1 | 1].l <= r)
188
            ans += query_sum_lazy(i << 1 | 1, l, r);
189
        return ans;
190
    }
191

192
    // --------------------------------------------
193
    // 带 lazy：区间查询 max
194
    // --------------------------------------------
195
    long long query_max_lazy(int i, int l, int r)
196
    {
197
        if (tree[i].l >= l && tree[i].r <= r)
198
            return tree[i].maxx;
199
        if (tree[i].r < l || tree[i].l > r)
200
            return -INF;
201

202
        push_down(i);
203
        long long ans = -INF;
204
        if (tree[i << 1].r >= l)
205
            ans = max(ans, query_max_lazy(i << 1, l, r));
206
        if (tree[i << 1 | 1].l <= r)
207
            ans = max(ans, query_max_lazy(i << 1 | 1, l, r));
208
        return ans;
209
    }
210
};
211

212
SegTree st;
213
int main()
214
{
215
    ios::sync_with_stdio(false);
216
    cin.tie(0);
217
    cout.tie(0);
218
    int n, m;
219
    cin >> n >> m;
220
    for (int i = 1; i <= n; i++)
221
        cin >> st.a[i];
222
    st.build(1, 1, n);
223
    int op, l, r;
224
    long long k;
225
    while (m--)
226
    {
227
        cin >> op >> l >> r;
228
        if (op == 1)
229
        {
230
            cin >> k;
231
            st.update_range_lazy(1, l, r, k);
232
        }
233
        else
234
        {
235
            cout << st.query_sum_lazy(1, l, r) << endl;
236
        }
237
    }
238
    return 0;
239
}

树上问题#

树的直径#

1
//树形DP
2
void dfs(int u, int fa){
3
    for (auto v : g[u]){
4
        if (v == fa)
5
            continue;
6
        dfs(v, u);
7
        ans = max(ans, dp[u] + dp[v] + 1);
8
        dp[u] = max(dp[u], dp[v] + 1);
9
    }
10
}

树的中心#

1
const int N = 1e5 + 5;
2
int d1[N]; // 节点 𝑥 子树内的最长链。
3
int d2[N]; // 不与d1[𝑥]重叠最长链。
4
int up[N]; // 节点 𝑥 外的最长链。
5
int x, y, mn = LLONG_MAX, n;
6
struct edge{
7
    int v, w;
8
};
9
vector<edge> g[N];
10
void dfs(int u, int fa) { // 求取len1和len2
11
    for (auto &[v, w] : g[u]){
12
        if (v == fa)
13
            continue;
14
        dfs(v, u);
15
        if (d1[v] + w > d1[u]){
16
            d2[u] = d1[u];
17
            d1[u] = d1[v] + w;
18
        }
19
        else if (d1[v] + w > d2[u]){
20
            d2[u] = d1[v] + w;
21
        }
22
    }
23
}
24
void dfs2(int u, int fa) {// 求取up
25
    for (auto &[v, w] : g[u]){
26
        if (v == fa)
27
            continue;
28
        up[v] = up[u] + w;
29
        if (d1[v] + w != d1[u]) { // 如果自己子树里的最长链不在v子树里
30
            up[v] = max(up[v], d1[u] + w);
31
        }
32
        else{
33
            up[v] = max(up[v], d2[u] + w);
34
        }
35
        dfs2(v, u);
36
    }
37
}
38

39
void get_center(){
40
    dfs(1, 0);
41
    dfs2(1, 0);
42
    for (int i = 1; i <= n; i++){
43
        if (max(d1[i], up[i]) < mn) { // 找到了当前max(len1[x],up[x])最小点
44
            mn = max(d1[i], up[i]);
45
            x = i, y = 0;
46
        }
47
        else if (max(d1[i], up[i]) == mn) { // 另一个点
48
            y = i;
49
        }
50
    }
51
}

树的重心#

1
#include <bits/stdc++.h>
2
#define ff(i, a, b) for (int i = (a); i <= (b); ++i)
3
#define ffg(i, a, b) for (int i = (a); i >= (b); --i)
4
#define endl '\n'
5
using namespace std;
6
const int N = 1e5 + 5;
7
int n;
8
vector<int> g[N];
9
class DfsW //DFS解
10
{
11
public:
12
    int siz[N];            // 这个节点的「大小」（所有子树上节点数 + 该节点）
13
    int w[N];              // 这个节点的「重量」，即所有子树「大小」的最大值
14
    vector<int> centroids; // 重心集合
15

16
    void dfs(int u, int fa){
17
        siz[u] = 1;
18
        w[u] = 0;
19
        for (int v : g[u]){
20
            if (v == fa)
21
                continue;
22
            dfs(v, u);
23
            siz[u] += siz[v];
24
            w[u] = max(w[u], siz[v]);
25
        }
26
        w[u] = max(w[u], n - siz[u]);
27
        if (w[u] <= n / 2){
28
            centroids.push_back(u);
29
        }
30
    }
31
    vector<int> get_centroids(){
32
        dfs(1, 0);
33
        return centroids;
34
    }
35
};
36

37
class DpW //换根DP
38
{
39
public:
40
    long long dp[N], ans[N], res = -1, res2 = -1;
41
    int siz[N];
42
    vector<int> centroids;
43
    void dfs(int u, int fa){
44
        siz[u] = 1;
45
        dp[u] = 0;
46
        for (int v : g[u]){
47
            if (v == fa)
48
                continue;
49
            dfs(v, u);
50
            siz[u] += siz[v];
51
            dp[u] += dp[v] + siz[v];
52
        }
53
    }
54

55
    void dfs2(int u, int fa){
56
        for (int v : g[u]){
57
            if (v == fa)
58
                continue;
59
            ans[v] = ans[u] - siz[v] + (n - siz[v]);
60
            dfs2(v, u);
61
        }
62
    }
63

64
    vector<int> get_centroids(){
65
        dfs(1, 0);
66
        ans[1] = dp[1];
67
        dfs2(1, 0);
68
        long long mini = LLONG_MAX;
69
        for (int i = 1; i <= n; i++){
70
            if (ans[i] <= mini){
71
                mini = ans[i];
72
                centroids.push_back(i);
73
            }
74
        }
75
        return centroids;
76
    }
77
};
78

79
int main(){
80
    cin >> n;
81
    for (int i = 1; i <= n; i++){
82
        int u, v, w;
83
        cin >> u >> v >> w;
84
        g[u].push_back(v);
85
        g[v].push_back(u);
86
    }
87
    DfsW dfsw;
88
    dfsw.get_centroids();
89
    DpW dpw;
90
    dpw.get_centroids();
91

92
    cout << dfsw.centroids.size() << endl;
93
    for (int i : dfsw.centroids)
94
        cout << i << " ";
95
    cout << endl;
96

97
    cout << dpw.centroids.size() << endl;
98
    for (int i : dpw.centroids)
99
        cout << i << " ";
100
    cout << endl;
101
    return 0;
102
}

LCA#

P3379 【模板】最近公共祖先（LCA） - 洛谷

给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。

倍增法（在线）#

预处理 $O(n log n)$ ，查询 $O(log n)$

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
const int MAXN = 200005;
5
const int LOG = 20; // 因为 2^20 > 1e6，若 n 更大可再调大
6

7
vector<int> g[MAXN];
8
int up[MAXN][LOG];   // up[u][j] 表示 u 的 2^j 级祖先
9
int dep[MAXN];
10
int n, q, s;
11

12
void dfs(int u, int fa) {
13
    up[u][0] = fa;
14
    dep[u] = dep[fa] + 1;
15

16
    for (int j = 1; j < LOG; j++) {
17
        up[u][j] = up[up[u][j - 1]][j - 1];
18
    }
19

20
    for (int v : g[u]) {
21
        if (v == fa) continue;
22
        dfs(v, u);
23
    }
24
}
25

26
int lca(int u, int v) {
27
    if (dep[u] < dep[v]) swap(u, v);
28

29
    // 1. 先把 u 提到和 v 同一深度
30
    int diff = dep[u] - dep[v];
31
    for (int j = LOG - 1; j >= 0; j--) {
32
        if (diff >> j & 1) {
33
            u = up[u][j];
34
        }
35
    }
36

37
    if (u == v) return u;
38

39
    // 2. 从大到小一起跳
40
    for (int j = LOG - 1; j >= 0; j--) {
41
        if (up[u][j] != up[v][j]) {
42
            u = up[u][j];
43
            v = up[v][j];
44
        }
45
    }
46

47
    // 3. 此时它们的父亲就是 LCA
48
    return up[u][0];
49
}
50

51
void solve() {
52
    cin >> n >> q >> s;
53
    for (int i = 1; i <= n - 1; i++) {
54
        int u, v;
55
        cin >> u >> v;
56
        g[u].push_back(v);
57
        g[v].push_back(u);
58
    }
59
    dfs(s, 0);
60

61
    while (q--) {
62
        int u, v;
63
        cin >> u >> v;
64
        cout << lca(u, v) << '\n';
65
    }
66

67
}

Tarjan（离线）#

预处理 $O(n + q)$

1
const int MAXN = 200005;
2

3
vector<int> g[MAXN];
4
vector<pair<int, int>> query[MAXN]; // query[u] 里存 (v, id)，表示第 id 个询问是 (u, v)
5

6
int fa[MAXN];     // 并查集
7
int fa_u[MAXN];    // 当前并查集代表对应的祖先
8
bool vis[MAXN];
9
int ans[MAXN];
10

11
int n, q, s;
12

13
int finds(int x) {
14
    if (fa[x] == x) return x;
15
    return fa[x] = finds(fa[x]);
16
}
17

18
void mer(int x, int y) {
19
    x = finds(x);
20
    y = finds(y);
21
    if (x != y) fa[y] = x;
22
}
23

24
void tarjan(int u, int parent) {
25
    fa[u] = u;
26
    fa_u[u] = u;
27

28
    for (int v : g[u]) {
29
        if (v == parent) continue;
30

31
        tarjan(v, u);
32
        mer(u, v);
33
        fa_u[finds(u)] = u;
34
    }
35

36
    vis[u] = true;
37

38
    for (auto [v, id] : query[u]) {
39
        if (vis[v]) {
40
            ans[id] = fa_u[finds(v)];
41
        }
42
    }
43
}
44

45
void solve(){
46
    cin >> n >> q >> s;
47
    for (int i = 1; i <= n - 1; i++) {
48
        int u, v;
49
        cin >> u >> v;
50
        g[u].push_back(v);
51
        g[v].push_back(u);
52
    }
53

54
    for (int i = 1; i <= q; i++) {
55
        int u, v;
56
        cin >> u >> v;
57
        query[u].push_back({v, i});
58
        query[v].push_back({u, i});
59
    }
60

61
    tarjan(s, 0);
62

63
    for (int i = 1; i <= q; i++) {
64
        cout << ans[i] << '\n';
65
    }
66
}

计算几何#

【模板】二维凸包#

Graham#

1
using i64 = long long;
2

3
constexpr long double eps = 1e-6;
4

5
class Point
6
{
7
public:
8
    long double x, y;
9
    Point(long double a = 0, long double b = 0) : x(a), y(b) {}
10
    bool operator<(const Point &p) { return x != p.x ? x < p.x : y < p.y; }
11
    Point operator+(const Point &p) { return Point(x + p.x, y + p.y); }
12
    Point operator-(const Point &p) { return Point(x - p.x, y - p.y); }
13
    long double len() { return sqrtl(x * x + y * y); }
14
    long double operator*(const Point &p) { return x * p.x + y * p.y; }
15
    long double Angle(Point &p) { return acos((*this) * p / (len() * p.len())); }
16
    long double OuterProduct(Point p) { return x * p.y - p.x * y; }
17
    bool same(Point &p) { return x == p.x && y == p.y; }
18
    long long dis(Point &p) { return ((x - p.x) * (x - p.x) + (y - p.y) * (y - p.y)); }
19
    long double dis2(Point &p) { return sqrtl((x - p.x) * (x - p.x) + (y - p.y) * (y - p.y)); }
20
    long double area(Point &p1, Point &p2) { return abs((p1 - (*this)).OuterProduct(p2 - p1)) / 2; }
21
    friend istream &operator>>(istream &in, Point &p) { in >> p.x >> p.y; return in; }
22
    friend ostream &operator<<(ostream &out, const Point &p) { out << p.x << " " << p.y; return out; }
23
};
24

25
class ConvexHull
26
{
27
public:
28
    vector<Point> p;
29
    ConvexHull(vector<Point> &_p)
30
    {
31
        int n = _p.size();
32
        sort(_p.begin(), _p.end(), [&](const Point &p1, const Point &p2)
33
             { return p1.x != p2.x ? p1.x < p2.x : p1.y < p2.y; });
34
        vector<int> vis(n), stk;
35
        stk.push_back(0);
36
        p.push_back(_p[0]);
37
        for (int i = 1; i < n; i++)
38
        {
39
            while (stk.size() >= 2 && (_p[stk.back()] - _p[stk[stk.size() - 2]])
40
                                              .OuterProduct(_p[i] - _p[stk.back()]) <= eps)
41
            {
42
                vis[stk.back()] = 0;
43
                stk.pop_back();
44
                p.pop_back();
45
            }
46
            vis[i] = 1;
47
            stk.push_back(i);
48
            p.push_back(_p[i]);
49
        }
50

51
        int low = stk.size();
52
        for (int i = n - 2; i >= 0; i--)
53
        {
54
            if (!vis[i])
55
            {
56
                while (stk.size() > low && (_p[stk.back()] - _p[stk[stk.size() - 2]])
57
                                                   .OuterProduct(_p[i] - _p[stk.back()]) <= eps)
58
                {
59
                    vis[stk.back()] = 0;
60
                    stk.pop_back();
61
                    p.pop_back();
62
                }
63
                vis[i] = 1;
64
                stk.push_back(i);
65
                p.push_back(_p[i]);
66
            }
67
        }
68
    }
69
    long long diameter()
70
    {
71
        if (p.size() <= 3)
72
        {
73
            return p[0].dis(p[1]);
74
        }
75
        else
76
        {
77
            long long ans = 0;
78
            int j = 2;
79
            for (int i = 0; i < p.size() - 1; i++)
80
            {
81
                while (p[j].area(p[i], p[i + 1]) <= p[j % (p.size() - 1) + 1].area(p[i], p[i + 1]))
82
                {
83
                    j = j % (p.size() - 1) + 1;
84
                }
85

86
                ans = max(ans, (i64)max(p[i].dis(p[j]), p[i + 1].dis(p[j])));
87
            }
88

89
            return ans;
90
        }
91
    }
92

93
    long double length()
94
    {
95
        double ans = 0;
96
        for (int i = 0; i < p.size(); ++i)
97
        {
98
            // cout << p[i] << endl;
99
            ans += p[i].dis2(p[(i + 1) % p.size()]);
100
        }
101
        return ans;
102
    }
103

104
    long double area()
105
    {
106
        long double a = 0;
107
        int m = p.size();
108
        for (int i = 0; i < m; ++i)
109
        {
110
            a += p[i].x * p[(i + 1) % m].y - p[(i + 1) % m].x * p[i].y;
111
        }
112
        return abs(a) / 2.0;
113
    }
114
};

字符串#

KMP#

1
// 计算部分匹配表（next数组）
2
void getNext(const string &pattern, vector<int> &next){
3
    int m = pattern.size();
4
    next.resize(m);
5
    int j = 0;
6
    for (int i = 1; i < m; ++i){
7
        while (j > 0 && pattern[i] != pattern[j])
8
            j = next[j - 1];
9
        if (pattern[i] == pattern[j])
10
            ++j;
11
        next[i] = j;
12
    }
13
}
14

15
// KMP算法搜索匹配串出现的所有位置
16
vector<int> kmpSearch(const string &text, const string &pattern){
17
    int n = text.size();
18
    int m = pattern.size();
19
    vector<int> next;
20
    getNext(pattern, next);
21
    vector<int> positions;
22
    int j = 0;
23
    for (int i = 0; i < n; ++i){
24
        while (j > 0 && text[i] != pattern[j])
25
            j = next[j - 1];
26
        if (text[i] == pattern[j])
27
            ++j;
28
        if (j == m){
29
            positions.push_back(i - m + 1);
30
            j = next[j - 1];
31
        }
32
    }
33
    return positions;
34
}

字典树#

1
struct trie{
2
    int nex[100000][26], cnt;
3
    bool exist[100000]; // 该结点结尾的字符串是否存在
4

5
    void insert(char *s, int l){ // 插入字符串
6
        int p = 0;
7
        for (int i = 0; i < l; i++){
8
            int c = s[i] - 'a';
9
            if (!nex[p][c])
10
                nex[p][c] = ++cnt; // 如果没有，就添加结点
11
            p = nex[p][c];
12
        }
13
        exist[p] = true;
14
    }
15

16
    bool find(char *s, int l){ // 查找字符串
17
        int p = 0;
18
        for (int i = 0; i < l; i++){
19
            int c = s[i] - 'a';
20
            if (!nex[p][c])
21
                return 0;
22
            p = nex[p][c];
23
        }
24
        return exist[p];
25
    }
26
};

常用工具#

离散化#

1
// 离散化主函数：返回排序去重后的数组
2
vector<int> discretize(vector<int> &nums){
3
    vector<int> sorted = nums;
4
    sort(sorted.begin(), sorted.end());                               // 1. 排序
5
    sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end()); // 2. 去重
6
    return sorted;
7
}
8
// 查询数值 x 的离散化后索引（从 0 开始）
9
int get_index(vector<int> &sorted, int x){
10
    return lower_bound(sorted.begin(), sorted.end(), x) - sorted.begin(); // 3. 二分查找
11
}
12
// 示例用法
13
int main(){
14
    vector<int> nums = {3, 1, 100, 2, 1, 200, 3}; // 原始数据
15
    vector<int> sorted = discretize(nums);        // 离散化数组：[1,2,3,100,200]
16

17
    int idx_3 = get_index(sorted, 3);     // 返回索引 2
18
    int idx_200 = get_index(sorted, 200); // 返回索引 4
19
    return 0;
20
}

哈希表#

1
const int SZ = 1000003; // 定义哈希表大小
2
struct hash_map {  // 哈希表模板
3

4
  struct data {
5
    long long u;
6
    int v, nex;
7
  };  // 前向星结构
8

9
  data e[SZ << 1];  // SZ 是 const int 表示大小
10
  int h[SZ], cnt;
11

12
  int hash(long long u) { return (u % SZ + SZ) % SZ; }
13

14
  // 这里使用 (u % SZ + SZ) % SZ 而非 u % SZ 的原因是
15
  // C++ 中的 % 运算无法将负数转为正数
16

17
  int& operator[](long long u) {
18
    int hu = hash(u);  // 获取头指针
19
    for (int i = h[hu]; i; i = e[i].nex)
20
      if (e[i].u == u) return e[i].v;
21
    return e[++cnt] = data{u, -1, h[hu]}, h[hu] = cnt, e[cnt].v;
22
  }
23

24
  hash_map() {
25
    cnt = 0;
26
    memset(h, 0, sizeof(h));
27
  }
28
};
29
int main()
30
{
31
    hash_map mp;
32
    mp[123] = 10;
33
    mp[456] = 20;
34
    mp[-789] = 30; // 支持负键
35
    // 更新数据
36
    mp[123] = 100;
37
    // 查找数据
38
    cout << "键 123 的值: " << mp[123] << endl; // 输出 100
39
    cout << "键 999 的值: " << mp[999] << endl; // 输出 -1（未找到）
40
    // 遍历所有键值对
41
    cout << "\n所有键值对：" << endl;
42
    for (int i = 1; i <= mp.cnt; ++i)
43
    {
44
        cout << "键: " << mp.e[i].u << ", 值: " << mp.e[i].v << endl;
45
    }
46
}

单调栈#

1
int ans[3000005];
2
int a[3000005];
3
void solve(){
4
    int n;
5
    cin >> n;
6
    for (int i = 1; i <= n; i++)
7
        cin >> a[i];
8
    stack<int> st;
9
    for (int i = n; i >= 1; i--){
10
        while (!st.empty() && a[st.top()] <= a[i])
11
            st.pop();
12
        ans[i] = st.empty() ? 0 : st.top();
13
        st.push(i);
14
    }
15
    for (int i = 1; i <= n; i++)
16
        cout << ans[i] << " ";
17
    cout << endl;
18
}

单调队列#

有一个长为 $n$ 的序列 $a$ ，以及一个大小为 $k$ 的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。

1
int n, a;
2
int arr[1000005];
3
int ans[1000005][2];
4
deque<pair<int, int>> q1, q2;
5
void solve(){
6
    cin >> n >> a;
7
    for (int i = 1; i <= n; i++){
8
        int x;
9
        cin >> x;
10
        while (!q1.empty() && q1.back().fi <= x)
11
            q1.pop_back();
12
        while (!q2.empty() && q2.back().fi >= x)
13
            q2.pop_back();
14
        q1.push_back({x, i});
15
        q2.push_back({x, i});
16
        while (i - a >= q1.front().se)
17
            q1.pop_front();
18
        while (i - a >= q2.front().se)
19
            q2.pop_front();
20
        if (i >= a){
21
            ans[i - a + 1][0] = q1.front().fi;
22
            ans[i - a + 1][1] = q2.front().fi;
23
        }
24
    }
25
    for (int i = 1; i <= n - a + 1; i++)
26
        cout << ans[i][1] << " ";
27
    cout << endl;
28
    for (int i = 1; i <= n - a + 1; i++)
29
        cout << ans[i][0] << " ";
30
    cout << endl;
31
}

アメカーの部屋

基础#