计划

动态规划

模拟

图论

数据结构

构造

模拟

动态规划

Dijkstra

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
const int N = 2e5;
#define ll long long
class Solution {
public:
    struct node{
        int to,nxt,w;
    }e[N];
    int cnt = 0;
    int head[N];
    void add(int u,int v,int w){
        e[++cnt].nxt = head[u];
        e[cnt].to = v;
        e[cnt].w = w;
        head[u] = cnt;
    }   
    int countRestrictedPaths(int n, vector<vector<int>>& edges) {
        int mod = 1e9 + 7;
        int m = edges.size();  
        for(int i = 0; i < m;++i){
            int u = edges[i][0],v = edges[i][1] , w = edges[i][2];
            add(v - 1, u - 1, w);
            add(u - 1, v - 1, w);
        }
        vector<int>d(n, INT_MAX);
        priority_queue<pair<int,int>>q;
        q.push({0, n - 1});
        d[n - 1] = 0;
        while(!q.empty()){
            auto p = q.top();
            q.pop();
            int u = p.second;
            int w = p.first;
            for(int i = head[u];i; i = e[i].nxt){
                int v = e[i].to;
                int w = e[i].w;
                if(w + d[u] < d[v]){
                    d[v] = w + d[u];
                    q.push({d[v], v});
                }
            }
        }
    }
};

弗罗伊德算法

1
2
3
4
5
6
7
8
9
int d[n + 1][n + 1];
memset(d, 0x3f, sizeof d);
for(int k = 0; k < n; ++k){
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
        }
    }
}

树状数组

  • 权值树状数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
   int tree[26000];
   int lowbit(int i){
       return i&-i;
    }
   int sum(int i){
       int a = 0;
       for(;i;i-=lowbit(i))
       a+=tree[i];
        return a;
   }
    void add(int i,int val){
        for(; i<=26999; i+=lowbit(i)){
            tree[i] += val;
        }
    }
    vector<int> countSmaller(vector<int>& nums) {
        int n = nums.size();
        vector<int>ans(n);
        //memset(tree,0,sizeof(tree));
        for(int i = 0; i < n;++i){
            nums[i] += (1e4+1);
 
        }
        reverse(nums.begin(),nums.end());
        for(int i = 0; i<n;++i){
            ans[i] = sum(nums[i]-1);
            add(nums[i],1);
        }
        reverse(ans.begin(),ans.end());
        return ans;
    }
};
  • 普通树状数组

维护某个区间小于 x的个数

可以 从小的数， 开始维护到大的数， 这样子就可以，实现这个功能

并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    int f[1001];
    int find(int x){
        if(x!=f[x])f[x] = find(f[x]);
        return f[x]; 
    }
    void un(int x,int y){
        int fx = find(x);
        int fy = find(y);
        if(fx!=fy)
        f[fy] = fx;
        // 可以设置一个sum ， 表示当前节点的所在联通分量大小
    }
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        vector<int>ans;
        for(int i = 1; i <= n;++i){
            f[i] = i;
        }
        for(auto t : edges){
            int x = t[0], y = t[1];
            if(find(x)!=find(y)){
                un(x,y);
            }else{
                ans.push_back(x);
                ans.push_back(y);
            }
        }
        return ans;
    }
};

拓扑排序

  • 判断环
  • 内向基环树找环
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
auto dfs = [&](auto &&dfs, int u, int from) -> void {
    v[u] = true;
    ins[u] = true;
    for(auto [j, id] : g[u]){
        if (id == from) continue;
        if (!v[j]) dfs(dfs, j, id);
        else if (ins[j]){
            int t = j;
            cycle.clear();
            cycle.push_back(j);
            while(1){
                t = a[t];
                if (t == j) break;
                cycle.push_back(t);
            }
            // 找到环了 
        }
    }
    ins[u] = false;
};

异或树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int T,l,r,a[N],cnt,trie[N][30],b[N];
void insert(int sum){
	int now=0;
	for(int i=17;i>=0;i--){
		bool tmp=(1<<i)&sum;
		if(!trie[now][tmp])trie[now][tmp]=++cnt;
		now=trie[now][tmp];
	}
}
int Max(int sum){
	int now=0,res=0;
	for(int i=17;i>=0;i--){
		bool tmp=(1<<i)&sum;
		if(!trie[now][tmp^1])now=trie[now][tmp];
		else now=trie[now][tmp^1],res+=(1<<i);
	}
	return res;
}
int Min(int sum){
	int now=0,res=0;
	for(int i=17;i>=0;i--){
		bool tmp=(1<<i)&sum;
		if(!trie[now][tmp])now=trie[now][tmp^1],res+=(1<<i);
		else now=trie[now][tmp];
	}
	return res;
}

线段树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
struct SegmentTree{
    int n;
    vector<Info> info;

    SegmentTree() {}

    SegmentTree(int n, Info _init = Info()){
        init(vector<Info>(n, _init));
    }

    SegmentTree(const vector<Info> &_init){
        init(_init);
    }

    void init(const vector<Info> &_init){
        n = (int)_init.size();
        info.assign((n << 2) + 1, Info());
        function<void(int, int, int)> build = [&](int p, int l, int r){
            if (l == r){
                info[p] = _init[l - 1];
                return;
            }
            int m = (l + r) / 2;
            build(2 * p, l, m);
            build(2 * p + 1, m + 1, r);
            pull(p);
        };
        build(1, 1, n);
    }

    void pull(int p){
        info[p] = info[2 * p] + info[2 * p + 1];
    }

    void modify(int p, int l, int r, int x, const Info &v){
        if (l == r){
            info[p] = v;
            return;
        }
        int m = (l + r) / 2;
        if (x <= m){
            modify(2 * p, l, m, x, v);
        } 
        else{
            modify(2 * p + 1, m + 1, r, x, v);
        }
        pull(p);
    }

    void modify(int p, const Info &v){
        modify(1, 1, n, p, v);
    }

    Info query(int p, int l, int r, int x, int y){
        if (l > y || r < x){
            return Info();
        }
        if (l >= x && r <= y){
            return info[p];
        }
        int m = (l + r) / 2;
        return query(2 * p, l, m, x, y) + query(2 * p + 1, m + 1, r, x, y);
    }

    Info query(int l, int r){
        return query(1, 1, n, l, r);
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
public:
    struct node{
        int l,r, cnt = 0; 
    }t[500000];
    void build(int l, int r ,int p){
        t[p].l = l, t[p].r = r;
        if(t[p].l == t[p].r){
            return ;
        }
        int m = (l + r)>>1;
        build(l , m , p<<1);
        build(m+1, r, p<<1|1);
        t[p].cnt = max(t[p<<1].cnt, t[p<<1|1].cnt);
    }
    void modify(int l, int p,int res){
        if(t[p].l == t[p].r){
            t[p].cnt = max(t[p].cnt, res);
            return ;
        }
        int m = (t[p].l +t[p].r)>>1;
        if(l <= m)modify(l ,p<<1, res);
        else modify(l, p<<1|1, res);
        t[p].cnt = max(t[p<<1].cnt, t[p<<1|1].cnt);
    }
    int query(int l, int r, int p){
        if(t[p].l >= l && t[p].r <= r){
            return t[p].cnt;
        }
        int m = (t[p].l + t[p].r)>>1;
        int ans = 0;
        if(l <= m)ans = query(l, r, p<<1);
        if(r > m)ans = max(ans, query(l, r, p<<1|1));
        return ans;
    }
    int lengthOfLIS(vector<int>& nums, int k) {
        int ans = 1;
        build(1, 100030,1);
        for(int v : nums){
            int res = 0;
            if(v == 1){
                modify(1, 1, 1);
            }
            else{
                res = query(max(1, v - k), v - 1, 1) + 1;
                ans = max(res, ans);
                modify(v, 1, res);
            }
        }   
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdio>
using namespace std;
const int N = 1e6 + 7;
#define ll long long
ll a[N];
struct node {
    ll lazy = 0, l = 0, r = 0, cnt = 0;
}t[N * 3];
void build(int p, int l, int r) {
    t[p].l = l, t[p].r = r;
    if (l == r) {
        t[p].cnt = a[l];
        return;
    }
    int m = (t[p].l + t[p].r) >> 1;
    build(p<<1, l, m);
    build(p<<1|1, m + 1, r);
    t[p].cnt=t[p<<1].cnt+t[p<<1|1].cnt;
}
void spread(int p) {
    int k = t[p].lazy;
    if(k==0)return;
    int l = t[p].l, r = t[p].r;
    int m = (l + r) >> 1;
    t[p << 1].cnt += 1ll*(m - l + 1)*(ll)k;
    t[p << 1 | 1].cnt += 1ll*(r - m)*(ll)k;
    t[p << 1].lazy += k;
    t[p << 1 | 1].lazy += k;
    t[p].lazy = 0;
    return;
}
void add(int l, int r, ll plus, int p) {
    if (t[p].l >= l && t[p].r <= r) {
        t[p].cnt += (t[p].r - t[p].l + 1)*plus;
        t[p].lazy += plus;
        return;
    }
    spread(p);
    int m = (t[p].l + t[p].r) >> 1;
    if (l <= m)add(l, r, plus, p << 1);
    if (r > m)add(l, r, plus, p << 1 | 1);
    t[p].cnt = t[p << 1].cnt + t[p << 1 | 1].cnt;
}
ll query(int l, int r, int p) {
    if (t[p].l >= l && t[p].r <= r) {
        return t[p].cnt;
    }
    spread(p);
    int m = (t[p].l + t[p].r) >> 1;
    ll ans = 0;
    if (l <= m)ans += query(l, r, p << 1);
    if (r > m)ans += query(l, r, p << 1 | 1);
    return ans;
}
int main() {    
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)cin >> a[i];
    build(1, 1, n);
    for (int i = 1; i <= m; ++i) {
        int status, x, y, k;
        cin >> status >> x >> y;
        if (status == 1) {
            cin >> k;
            add(x, y, k, 1);
        }
        else {
            cout << query(x, y, 1) << endl;
        }
    }
    return 0;
}

倍增树

最近公共祖先类似思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
using ll = long long;
const int N = 1e5 + 10;
const int L = 35;
int nxt[N][L];
ll val[N][L];
class Solution {
public:
    long long getMaxFunctionValue(vector<int>& a, long long k) {
        int n = a.size();
        for(int i=0; i<n; ++i){
            nxt[i][0] = a[i];
            val[i][0] = a[i];
        }
        for(int j=1; j<L; ++j){
            for(int i=0; i<n; ++i){
                nxt[i][j] = nxt[nxt[i][j-1]][j-1];
                val[i][j] = val[nxt[i][j-1]][j-1] + val[i][j-1];
            }
        }
        ll ans = 0;
        for(int i=0; i<n; ++i){
            ll cur = i;
            int u = i;
            for(int j= L-1; j>=0; --j){
                if(k >> j & 1){
                    cur += val[u][j];
                    u = nxt[u][j];
                }
            }
            ans = max(ans, cur);
        }
        return ans;
    }
};

kmp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
string part = "abc";
vector<int>nt(part.size(), -1);
for(int i = 1; i < part.size() ;++i){
    int j = nt[i - 1];
    while(j != -1 && part[j + 1] != part[i])j = nt[j];
    if(part[j + 1] == part[i])j++;
    nt[i] = j;
}
while(!s.empty()){
    int k = -1;
    for(int i = 0,j = -1; i < s.size(); ++i){
        while(j != -1 && part[j + 1] != s[i])j = nt[j];
        if(part[j + 1] == s[i])j++;
        if(j == part.size() - 1){
            k = i - part.size() + 1;
            break;
        }
    }
    if(k == -1)return false;
    string cur = s.substr(0, k) + s.substr(k + part.size());
    s = cur;
}

预处理阶乘

  • 可以用来计算 组合数
1
2
3
4
5
6
fac[0]=1;
for(int i=1;i<=n;i++)
    fac[i]=fac[i-1]*i%p;
ifac[n]=qpow(fac[n],p-2);
for(int j=n-1;j>=0;j--)
    ifac[j]=ifac[j+1]*(j+1)%p;
  • 计算组合数
1
2
3
4
ll c(ll n,ll m)
{
    return fac[n]*ifac[m]%p*ifac[n-m]%p;
}

二进制枚举

  • 枚举所有的子集
1
2
3
4
5
6
7
8
for(int i = 0; i < (1 << n); ++i){
    for(int j = 0; j < 31; ++j){
        if(i >> j & 1){
            /// 执行流程
        }
        // 处理结果
    }
}

树的直径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
for(int i = 0; i < n - 1; ++i){
       int u, v;
       cin>>u>>v;
       u--, v--;
       e[u].push_back(v);
       e[v].push_back(u);
   }
   int ans = 0;
   function<int(int, int )>dfs = [&](int u, int fa){
       int max1 = 0, max2 = 0;
       for(int i = 0; i < e[u].size(); ++i){
           int to = e[u][i];
           if(to == fa) continue;
           int maxv = dfs(to, u);
           if(maxv > max1){
               max2 = max1;
               max1 = maxv;
           }
           else if(maxv > max2){
               max2 = maxv;
           }
       }     
	ans = max(ans, max1, max2);
       return max(max1, max2)  + 1;
   };