板子

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
#include <bits/stdc++.h>

#define x first
#define y second
#define endl '\n'

using namespace std;

using ll = long long;
using i128 = __int128; 
using PII = pair<int, int>;
using PLI = pair<ll, int>;
using PIL = pair<int, ll>;
using PLL = pair<ll, ll>; 

constexpr int mod = 1e9 + 7;
// constexpr int mod = 998244353;

i128 read(){i128 x = 0, f = 1;char ch = getchar();while (ch < '0' || ch > '9'){if (ch == '-') f = -1;ch = getchar();}while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;}
void print(i128 x){if (x < 0){putchar('-');x = -x;}if (x > 9) print(x / 10);putchar(x % 10 + '0');}
ll qmi(ll a, int b){ll res = 1;while (b){if (b & 1) res = res * a % mod;b >>= 1;a = a * a % mod;}return res;}

void solve()
{	

}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int T = 1;
    // cin >> T;
    while (T--)
    {
        solve();
    }

    return 0;
}

基础算法

高精度加法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<int> add(vector<int> a, vector<int> b)  //倒进倒出
{
    vector<int> c;
    int t = 0;

    for (int i = 0; i < a.size() || i < b.size(); i++)
    {
        if (i < a.size()) t += a[i];
        if (i < b.size()) t += b[i];
        c.push_back(t % 10);
        t /= 10;
    }
    if (t) c.push_back(t);
    while (c.size() > 1 && !c.back()) c.pop_back();

    return c;
}

高精度减法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
bool cmp(vector<int> a, vector<int> b)  //倒进倒出
{
    if (a.size() != b.size()) return a.size() > b.size();
    for (int i = a.size() - 1; i >= 0; i--)
        if (a[i] != b[i])
            return a[i] > b[i];
    return true;
}

vector<int> sub(vector<int> a, vector<int> b)   
{
    vector<int> c;
    for (int i = 0, t = 0; i < a.size(); i++)
    {
        t = a[i] - (t < 0);
        if (i < b.size()) t -= b[i];
        c.push_back((t + 10) % 10);
    }
    while (c.size() > 1 && !c.back()) c.pop_back();

    return c;
}

高精度乘法

大乘小 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> mul(vector<int> &a, int b)  //倒进倒出
{
    vector<int> c;
    int t = 0;
    for (int i = 0; i < a.size() || t; i++)
    {
        if (i < a.size()) t += a[i] * b;
        c.push_back(t % 10);
        t /= 10;
    }
    while (c.size() > 1 && c.back() == 0) c.pop_back();

    return c;
}
大乘大 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<int> mul(vector<int> a, vector<int> b)  //倒进倒出
{
    vector<int> c(N * N);
    for (int i = 1; i < a.size(); i++)
    {
        for (int j = 1; j < b.size(); j++)
        {
            c[i + j - 1] += a[i] * b[j];
            c[i + j] += c[i + j - 1] / 10;
            c[i + j - 1] %= 10;
        }
    }
    while (c.size() > 1 && !c.back()) c.pop_back();

    return c;
}

高精度除法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> div(vector<int> a, int b, int &r)  //倒进倒出
{
    vector<int> c;
    r = 0;
    for (int i = a.size() - 1; i >= 0; i--)
    {
        r = r * 10 + a[i];
        c.push_back(r / b);
        r %= b;
    }
    reverse(c.begin(), c.end());
    while (c.size() > 1 && c.back() == 0) c.pop_back();
    
    return c;
}

二维前缀和

1
2
3
4
5
6
7
8
9
10
11
12
int main()
{
    for (int i = 1; i <= n; i++)  //把s处理成前缀和矩阵
        for (int j = 1; j <= m; j++)
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];

    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    cout << s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 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
void insert(int x1, int y1, int x2, int y2, int c)
{
    b[x1][y1] += c;
    b[x2 + 1][y1] -= c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y2 + 1] += c;
}

int main()
{
    for (int i = 1; i <= n; i++)   //把a处理成差分矩阵
        for (int j = 1; j <= m; j++)
            insert(i, j, i, j, a[i][j]);

    int x1, y1, x2, y2, c;
    cin >> x1 >> y1 >> x2 >> y2 >> c;
    insert(x1, y1, x2, y2, c);     //把这个矩阵的所有元素+1

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];

    for (int i = 1; i <= n; i ++)
    {
        for (int j = 1; j <= m; j ++ ) cout << b[i][j] << ' '; 
        cout << endl;
    }

    return 0;
}

返回二进制最低位1

1
2
3
4
int lowbit(int x)
{
    return x & -x;
}

离散化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int main()
{
    for (int i = 1; i <= n; i++) b[i] = a[i];
    sort(b + 1, b + 1 + n);

    int bn = unique(b + 1, b + 1 + n) - b - 1;
    for (int i = 1; i <= n; i++)
    {
        int l = 1, r = bn;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (b[mid] < a[i]) l = mid + 1;
            else r = mid;
        }
        a[i] = l;
    }
	
    return 0;
}

区间合并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
vector<PII> merge()
{
    sort(a, a + n);

    vector<PII> res;
    int st = -2e9, ed = -2e9;
    for (int i = 0; i < n; i++)
    {
        if (ed < a[i].x)
        {
            if (st != -2e9) res.push_back({st, ed});
            st = a[i].x, ed = a[i].y;
        }
        else ed = max(ed, a[i].y);
    }
    if (st != -2e9) res.push_back({st, ed});

    return res;
}

st表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> f[i][0];

    for (int j = 1; j <= 20; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
            f[i][j] = max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);  //初始化

    while (m--)
    {
        int l, r;
        cin >> l >> r;
        int k = log2(r - l + 1);
        cout << max(f[l][k], f[r - (1 << k) + 1][k]) << endl;  //查询
    }
	
    return 0;
}

数据结构

kmp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int main()
{
    ne[0] = -1;
    for (int i = 1, j = -1; i < n; i++)   //初始化
    {
        while (j != -1 && p[i] != p[j + 1]) j = ne[j];
        if (p[i] == p[j + 1]) j++;
        ne[i] = j;
    }

    for (int i = 0, j = -1; i < m; i++)
    {
        while (j != -1 && s[i] != p[j + 1])  j = ne[j];
        if (s[i] == p[j + 1]) j++;
        if (j == n - 1)
        {
            cout << i - j << ' ';   //匹配位置的起点，从0开始
            j = ne[j];
        }
    }

    return 0;
}

单调队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
deque<int> q;

int main()
{
    for (int i = 0; i < n; i++)  //窗口最小值
    {
        while (q.size() && a[q.back()] >= a[i]) q.pop_back();
        while (q.size() && i - k + 1 > q.front()) q.pop_front();
        q.push_back(i);
        if (i >= k - 1) cout << a[q.front()] << ' ';
    }

    return 0;
}

单调栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
stack<int> s;

int main()
{
    for (int i = 0; i < n; i++)  //左边第一个比它小的值
    {
        while (s.size() && s.top() >= a[i]) s.pop();
        if (s.size()) cout << s.top() << ' ';
        else cout << "-1 ";
        s.push(a[i]);
    }

    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
struct DSU
{
    int p[N], sz[N];
    void init(int n)
    {
        for (int i = 1; i <= n; i++) p[i] = i, sz[i] = 1;
    }
    int find(int x)
    {
        return (p[x] == x)? p[x] : p[x] = find(p[x]);
    }
    bool check(int x, int y)
    {
        return find(x) == find(y);
    }
    void merge(int x, int y)
    {
        if (check(x, y)) return;
        x = find(x), y = find(y);
        p[x] = y;
        sz[y] += sz[x];
    }
};

字符串哈希

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const int P = 13331;

ull p[N], h[N];

ull get(int l, int r) 
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

int main()
{
    p[0] = 1;
    for (int i = 1; i <= n; i++)   
    {
        p[i] = p[i - 1] * P;
        h[i] = h[i - 1] * P + s[i - 1];
    }

    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
struct Bit
{
    int s[N], n;
    void init(int len)
    {
        n = len;
        for (int i = 0; i <= len; i++) s[i] = 0;
    }
    int lowbit(int x)
    {
        return x & -x;
    }
    void modify(int x, int k)
    {
        while (x <= n)
        {
            s[x] += k;
            x += lowbit(x);
        } 
    }
    int query(int x)
    {
        int res = 0;
        while (x)
        {
            res += s[x];
            x -= lowbit(x);
        }
        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
// 二维树状数组+差分 区修+区查 O(q*logn*logn)
#include <cstdio>
using namespace std;

#define lowb(x) x&-x
int n,m,a,b,c,d,v; char op[2];
struct Tree{ //二维树状数组
  int s[2050][2050];
  void change(int x,int y,int v){ //向后修
    for(int i=x;i<=n;i+=lowb(i))
      for(int j=y;j<=m;j+=lowb(j))
        s[i][j]+=v;
  }
  int query(int x,int y){ //向前查
    int t=0;
    for(int i=x;i;i-=lowb(i))
      for(int j=y;j;j-=lowb(j))
        t+=s[i][j];
    return t;
  }
}A,B,C,D; //维护 d,d*i,d*j,d*i*j

void add(int x,int y,int v){ //点加
  A.change(x,y,v);
  B.change(x,y,v*x);
  C.change(x,y,v*y);
  D.change(x,y,v*x*y);
}
int sum(int x,int y){ //前缀和
  return A.query(x,y)*(x*y+x+y+1)
        -B.query(x,y)*(y+1)
        -C.query(x,y)*(x+1)
        +D.query(x,y);
}
int main(){
  scanf("X%d%d",&n,&m);
  while(~scanf("%s",&op)){
    scanf("%d%d%d%d",&a,&b,&c,&d);
    if(op[0]=='L'){ //区修变差分
      scanf("%d",&v);
      add(a,b,v);
      add(a,d+1,-v);
      add(c+1,b,-v);
      add(c+1,d+1,v);
    }
    else           //区间和
      printf("%d\n",sum(c,d)
      -sum(a-1,d)-sum(c,b-1)
      +sum(a-1,b-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
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
struct Seg
{
    #define ls u << 1
    #define rs u << 1 | 1
    struct Node
    {
        int l, r;
        ll sum, lz;
    }tr[N * 4];
    vector<ll> a;
    void init(vector<ll> s){a = s;}
    void pushup(int u)
    {
        tr[u].sum = tr[ls].sum + tr[rs].sum;
    }
    void pushdown(Node &u, Node &l, Node &r)
    {
        if (u.l == u.r) return;
        l.sum += u.lz * (l.r - l.l + 1);
        r.sum += u.lz * (r.r - r.l + 1);
        l.lz += u.lz, r.lz += u.lz, u.lz = 0;
    }
    void build(int u, int l, int r)
    {
        tr[u] = {l, r, a[l], 0};
        if (l == r) return;
        int mid = l + r >> 1;
        build(ls, l, mid), build(rs, mid + 1, r);
        pushup(u);
    }
    void modify(int u, int l, int r, ll x)
    {
        if (tr[u].l >= l && tr[u].r <= r)
        {
            tr[u].sum += x * (tr[u].r - tr[u].l + 1);
            tr[u].lz += x;
        }
        else
        {
            pushdown(tr[u], tr[ls], tr[rs]);
            int mid = tr[u].l + tr[u].r >> 1;
            if (l <= mid) modify(ls, l, r, x);
            if (r > mid) modify(rs, l, r, x);
            pushup(u);
        }
    }
    ll query(int u, int l, int r)
    {
        if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
        pushdown(tr[u], tr[ls], tr[rs]);
        int mid = tr[u].l + tr[u].r >> 1;
        ll res = 0;
        if (l <= mid) res += query(ls, l, r);
        if (r > mid) res += query(rs, l, r);
        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
int root[N], tot;
int ls[N * 25], rs[N * 25], val[N * 25];

void build(int &u, int l, int r)  //建树
{
    u = ++tot;
    if (l == r) val[u] = a[l];
    else
    {
        int mid = l + r >> 1;
        build(ls[u], l, mid);
        build(rs[u], mid + 1, r);
    }
}

void modify(int &u, int v, int l, int r, int p, int x)  //把位置p的值修改为x
{
    u = ++tot;
    ls[u] = ls[v], rs[u] = rs[v], val[u] = val[v];
    if (l == r) val[u] = x;
    else
    {
        int mid = l + r >> 1;
        if (p <= mid) modify(ls[u], ls[v], l, mid, p, x);
        else modify(rs[u], rs[v], mid + 1, r, p, x);
    }
}

int query(int u, int l, int r, int p)  //查询
{
    if (l == r) return val[u];
    int mid = l + r >> 1;
    if (p <= mid) return query(ls[u], l, mid, p);
    else return query(rs[u], mid + 1, r, p);
}

静态区间第 \(k\) 小数 

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 <bits/stdc++.h>

using namespace std;

const int N = 200010;

int n, m;
int a[N], b[N];
int root[N], tot;
int ls[N * 25], rs[N * 25], sum[N * 25];

void modify(int &u, int v, int l, int r, int p)
{
    u = ++tot;
    ls[u] = ls[v], rs[u] = rs[v], sum[u] = sum[v] + 1;
    if (l == r) return;
    int mid = l + r >> 1;
    if (p <= mid) modify(ls[u], ls[v], l, mid, p);
    else modify(rs[u], rs[v], mid + 1, r, p);
}

int query(int u, int v, int l, int r, int k)   //查询区间第k小
{
    if (l == r) return l;
    int s = sum[ls[u]] - sum[ls[v]];
    int mid = l + r >> 1;
    if (k <= s) return query(ls[u], ls[v], l, mid, k);
    else return query(rs[u], rs[v], mid + 1, r, k - s);
}

int query(int u, int v, int l, int r, int k)   //查询区间比k小的个数
{
    if (l == r) return sum[u] - sum[v];
    int mid = l + r >> 1;
    int res = 0;
    if (k <= mid) res += query(ls[u], ls[v], l, mid, k);
    else
    {
        res += sum[ls[u]] - sum[ls[v]];
        res += query(rs[u], rs[v], mid + 1, r, k);
    }
    return res;
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];

    for (int i = 1; i <= n; i++) b[i] = a[i];
    sort(b + 1, b + 1 + n);

    int bn = unique(b + 1, b + 1 + n) - b - 1;
    for (int i = 1; i <= n; i++)
    {
        int l = 1, r = bn;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (b[mid] < a[i]) l = mid + 1;
            else r = mid;
        }
        modify(root[i], root[i - 1], 1, bn, l);
    }

    while (m--)
    {
        int l, r, k;
        cin >> l >> r >> k;
        int p = query(root[r], root[l - 1], 1, bn, k);
        cout << b[p] << 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
struct Trie
{
    int idx, cnt;
    int rt[N], p[N * 35][2], sz[N * 35];
    void init(){idx = cnt = 0;}
    void insert(int v)
    {
        rt[++idx] = ++cnt;
        int x = rt[idx - 1], y = rt[idx];
        for (int i = 30; i >= 0; i--)
        {
            int j = v >> i & 1;
            p[y][!j] = p[x][!j];
            p[y][j] = ++cnt;
            x = p[x][j], y = p[y][j];
            sz[y] = sz[x] + 1;
        }
    }
    int query(int l, int r, int v)
    {
        int x = rt[l], y = rt[r], res = 0;
        for (int i = 30; i >= 0; i--)
        {
            int j = v >> i & 1;
            if (sz[p[y][!j]] - sz[p[x][!j]]) 
            {
                res += 1 << i;
                x = p[x][!j], y = p[y][!j];
            } 
            else x = p[x][j], y = p[y][j];
        }
        return res;
    }
}T;

莫队

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
struct Q
{
    int id, l, r;
}q[N];
int n, m, k;
int b, sum;
int a[N], c[N];

bool cmp(Q A, Q B)
{
    if (A.l / b != B.l / b) return A.l < B.l;
    if (A.l / b & 1) return A.r < B.r;
    return A.r > B.r;
}

void add(int x)  //添加
{
    c[x]++;
}

void del(int x)  //删除
{
    c[x]--;
}

int main()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];

    for (int i = 1; i <= m; i++)  //离线查询
    {
        int l, r;
        cin >> l >> r;
        q[i] = {i, l, r};
    }

    b = sqrt(n);
    sort(q + 1, q + 1 + m, cmp);

    for (int i = 1, l = 1, r = 0; i <= m; i++)  //查询区间每个数的出现次数
    {
        while (l > q[i].l) add(a[--l]);
        while (r < q[i].r) add(a[++r]);
        while (l < q[i].l) del(a[l++]);
        while (r > q[i].r) del(a[r--]);
    }
    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
35
36
37
map<int, ll> dfs(int u, int fa)
{
    f[u] = 1;
    int hv = 0;
    map<int, ll> pu, pv;
    pv[c[u]]++;
    for (auto v: h[u])
    {
        if (v == fa) continue;
        map<int, ll> cp = dfs(v, u);
        f[u] += f[v];
        if (f[v] > f[hv]) 
        {
            swap(pu, cp);
            hv = v;
        }
        for (auto [x, y]: cp) pv[x] += y;
    }

    ll maxv = pu[0];
    for (auto [x, y]: pv)
    {
        if (!x || x == n + 1) continue;
        pu[x] += y;
        if (pu[x] >= maxv)
        {
            if (pu[x] > maxv) res[u] = 0;
            maxv = pu[x];
            res[u] += x;
        }
    }

    if (maxv == pu[0]) res[u] += pu[n + 1];
    pu[0] = maxv, pu[n + 1] = res[u];

    return pu;
}

图论

堆优化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
int dijkstra()
{
    memset(d, 0x3f, sizeof d);
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});
    d[1] = 0;

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int ver = t.y;
        if (st[ver]) continue;
        st[ver] = true;

        for (int i = 0; i < h[ver].size(); i++)
        {
            int j = h[ver][i].x, w = h[ver][i].y;
            if (d[j] > d[ver] + w)
            {
                d[j] = d[ver] + w;
                heap.push({d[j], j});
            }
        }
    }

    return (d[n] == 0x3f3f3f3f)? -1 : d[n];
}

bellman-ford

有边数限制的最短路 

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
const int N = 510, M = 10010;

int n, m, k;
int dist[N], last[N];
struct Edge
{
    int a, b, c;
}edge[M];

void bellman_ford()
{
    memset(dist, 0x3f, sizeof dist);

    dist[1] = 0;
    for (int i = 0; i < k; i++)
    {
        memcpy(last, dist, sizeof dist);
        for (int j = 0; j < m; j++)
        {
            auto e = edge[j];
            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++)
        cin >> edge[i].a >> edge[i].b >> edge[i].c;
        
    bellman_ford();
        
    if (dist[n] > 0x3f3f3f3f / 2) cout << "impossible" << endl;
    else cout << dist[n] << endl;

    return 0;
}

spfa

判断负环 

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
bool spfa()
{
	queue<int> q;
    for (int i = 1; i <= n; i++)
    {
        st[i] = true;
        q.push(i);
    }

    while (q.size())
    {
        int t = q.front();
        q.pop();
        st[t] = false;

        for (int i = 0; i < h[t].size(); i++)
        {
            int j = h[t][i].x, w = h[t][i].y;
            if (dist[j] > dist[t] + w)
            {
                dist[j] = dist[t] + w;
                cnt[j] = cnt[t] + 1;

                if (cnt[j] >= n) return true;

                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    
    return false;
}

floyd

1
2
3
4
5
6
7
void 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

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
int prim()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    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 || dist[t] > dist[j]))
                t = j;

        if (dist[t] == INF) return INF;

        st[t] = true;
        res += dist[t];

        for (int j = 1; j <= n; j++)
            dist[j] = min(dist[j], g[t][j]);
    }

    return res;
}

int main()
{
    memset(g, 0x3f, sizeof g);

    cin >> n >> m;
    while (m--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = min(g[a][b], c);
    }

    int t = prim();
    if (t == INF) cout << "impossible" << endl;
    else cout << t << endl;

    return 0;
}

kruskal

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
int find(int x)
{
    if (x != p[x]) p[x] = find(p[x]);
    return p[x];
}

int kruskal()
{
    for (int i = 1; i <= n; i++) p[i] = i;

    int cnt = 0, res = 0;
    for (int i = 0; i < m; i++)
    {
        int a = edge[i].a, b = edge[i].b, w = edge[i].w;

        a = find(a), b = find(b);
        if (a != b)
        {
            p[a] = b;
            res += w;
            cnt++;
        }
    }

    if (cnt < n - 1) return INF;
    else return res;
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < m; i++)
        cin >> edge[i].a >> edge[i].b >> edge[i].w;

    sort(edge, edge + m);

    int t = kruskal();
    if (t == INF) cout << "impossible" << endl;
    else cout << t << 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
35
36
37
38
39
40
41
42
43
44
bool dfs(int u, int c)
{
    color[u] = c;
    for (int i = 0; i < h[u].size(); i++)
    {
        int j = h[u][i];
        if (!color[j])
        {
            if (!dfs(j, 3 - c)) return false;
        }
        else if (color[j] == c) return false;
    }

    return true;
}

int main()
{
    cin >> n >> m;
    while (m--)
    {
        int a, b;
        cin >> a >> b;
        h[a].push_back(b), h[b].push_back(a);
    }

    bool flag = true;
    for (int i = 1; i <= n; i++)
    {
        if (!color[i])
        {
            if (!dfs(i, 1))
            {
                flag = false;
                break;
            }
        }
    }

    if (flag == true) cout << "Yes" << endl;
    else cout << "No" << 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
35
36
37
38
39
40
bool find(int x)
{
    for (int i = 0; i < h[x].size(); i++)
    {
        int j = h[x][i];
        if (!st[j])
        {
            st[j] = true;
            if (match[j] == 0 || find(match[j]))
            {
                match[j] = x;
                return true;
            }
        }
    }

    return false;
}

int main()
{
    cin >> n1 >> n2 >> m;
    while (m--)
    {
        int a, b;
        cin >> a >> b;
        h[a].push_back(b);
    }

    int res = 0;
    for (int i = 1; i <= n1; i++)
    {
        memset(st, false, sizeof st);
        if (find(i)) res++;
    }

    cout << res << endl;

    return 0;
}

lca

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
void dfs(int u, int father)
{
    dep[u] = dep[father] + 1;
    f[u][0] = father;

    for (int i = 1; i <= 15; i++) 
        f[u][i] = f[f[u][i - 1]][i - 1];

    for (int i = 0; i < s[u].size(); i++)
        if (s[u][i] != father)
            dfs(s[u][i], u);
}

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

    for (int i = 15; i >= 0; i--)
        if (dep[f[u][i]] >= dep[v])
            u = f[u][i];

    if (u == v) return u;

    for(int i = 15; i >= 0; i--)
        if (f[u][i] != f[v][i])
            u = f[u][i], v = f[v][i];

    return f[u][0];
}

tarjan SCC缩点

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
void tarjan(int u)
{
    dfn[u] = low[u] = ++tot;
    stk[++top] = u, instk[u] = 1;
    for (int i = 0; i < h[u].size(); i++)
    {
        int v = h[u][i];
        if (!dfn[v]) 
        {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if (instk[v]) low[u] = min(low[u], dfn[v]);
    }

    if (dfn[u] == low[u])
    {
        cnt++;
        int v;
        do 
        {
            v = stk[top--];
            instk[v] = 0;
            scc[v] = cnt;
            sz[cnt] += w[v];
        } while (u != v);
    }
}

拓扑排序

基环树找环 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void topsort()
{
    queue<int> q;
    for (int i = 1; i <= n; i++)
    {
        d[i] = h[i].size();
        if (d[i] == 1) q.push(i);
    }

    while (q.size())
    {
        auto t = q.front();
        q.pop();
        for (int i = 0; i < h[t].size(); i++)
        {
            int j = h[t][i];
            d[j]--;
            if (d[j] == 1) q.push(j);
        }
    }
}

2—SAT

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
int main()
{
    cin >> n >> m;
    while (m--)
    {
        int u, a, v, b;
        cin >> u >> a >> v >> b;
        h[u + !a * n].push_back(v + b * n);
        h[v + !b * n].push_back(u + a * n);
    }

    for (int i = 1; i <= n * 2; i++)
        if (!dfn[i])
            tarjan(i);

    bool flag = false;
    for (int i = 1; i <= n; i++)
        if (scc[i] == scc[i + n])
        {
            flag = true;
            break;
        }
        
    if (flag) cout << "IMPOSSIBLE" << endl;
    else 
    {
        cout << "POSSIBLE" << endl;
        for (int i = 1; i <= n; i++) cout << (scc[i] > scc[i + n]) << ' ';
    }

    return 0;
}

数学

线性筛质数

1
2
3
4
5
6
7
8
9
10
11
12
void get_prime(int n)
{
    for (int i = 2; i <= n; i++)
    {
        if(!st[i]) prime[cnt++] = i;
        for (int j = 0; prime[j] <= n / i; j++)
        {
            st[prime[j] * i] = true;
            if (i % prime[j] == 0) break;
        }
    }
}

筛法求欧拉函数

欧拉函数，即 \(\phi(n)\)，表示的是小于等于 \(n\) 和 \(n\) 互质的数的个数。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void get_eulers(int n)
{
    phi[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (!st[i])
        {
            prime[cnt++] = i;
            phi[i] = i - 1;
        }

        for (int j = 0; prime[j] <= n / i; j++)
        {
            st[prime[j] * i] = true;
            if (i % prime[j] == 0)
            {
                phi[prime[j] * i] = prime[j] * phi[i];
                break;
            }
            phi[prime[j] * i] = (prime[j] - 1) * phi[i];
        }
    }
}

筛法求莫比乌斯函数

\[ \mu \text{为莫比乌斯函数，定义为} \\ \mu(n) = \begin{cases} 1 & n = 1 \\ 0 & n \text{ 含有平方因子} \\ (-1)^k & k \text{为} n \text{的本质不同质因子个数} \end{cases} \]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void get_mobius(int n)
{
    mobius[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (!st[i])
        {
            prime[cnt++] = i;
            mobius[i] = -1;
        }
        for (int j = 0; prime[j] <= n / i; j++)
        {
            int m = prime[j] * i;
            st[m] = true;
            if (i % prime[j] == 0)
            {
                mobius[m] = 0;
                break;
            }
            else mobius[m] = -mobius[i];
        }
    }
}

快速幂

1
2
3
4
5
6
7
8
9
10
11
ll qmi(ll a, int b)
{
    ll res = 1;
    while (b)
    {
        if (b & 1) res = (ll)res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

龟速乘

1
2
3
4
5
6
7
8
9
10
11
ll qmul(ll a, int b)
{
    ll res = 0;
    while (b)
    {
        if (b & 1) res = (res + a % p);
        a = (ll)(a + a) % p;
        b >>= 1;
    }
    return res;
}

扩展欧几里得

给定 \(n\) 对正整数 \(a_i,b_i\)，对于每对数，求出一组 \(x_i,y_i\)，使其满足 \(a_i \times x_i+b_i \times y_i=gcd(a_i,b_i)\)。 \(x\) 每次变化 \(b / d\), y 每次变化 \(a / d\)。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int exgcd(int a, int b, int &x, int &y)
{
    if (!b)
    {
        x = 1, y = 0;
        return a;
    }
    else
    {
        int x1 = 0, y1 = 0;
        int d = exgcd(b, a % b, x1, y1);
        x = y1, y = x1 - a / b * y1;
        return d;
    }
}
// (x / d % b + b) % b    x的最小非负整数解

扩展中国剩余定理

\[ \text{求解线性同余方程组} \begin{cases} x \equiv r_1 \ (\text{mod} \ m_1) \\ x \equiv r_2 \ (\text{mod} \ m_2) \\ \vdots \\ x \equiv r_n \ (\text{mod} \ m_n) \end{cases} \] 求 \(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
int excrt(int a[], int m[])
{
    int m1, m2, a1, a2, x, y;
    m1 = m[0], a1 = a[0];
    for (int i = 1; i < n; i++)
    {
        m2 = m[i], a2 = a[i];
        int d = exgcd(m1, m2, x, y);
        if ((a2 - a1) % d) return -1;
        x = x * (a2 - a1) / d;
        x = (x % (m2 / d) + m2 / d) % (m2 / d);
        a1 = m1 * x + a1;
        m1 = m1 * m2 / d;
    }
    
    return (a1 % m1 + m1) % m1;
}

signed main()
{
    cin >> n;
    for (int i = 0; i < n; i++) cin >> m[i] >> a[i];
    
    cout << excrt(a, m) << 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
35
36
37
38
int gauss()
{
    int r = 0;
    for (int i = 0; i < n; i++)
    {
        int t = r;
        for (int j = r; j < n; j++)
           if (fabs(a[j][i]) > fabs(a[t][i]))
            t = j;

        if (fabs(a[t][i]) < eps) continue;

        if (t != r) swap(a[t], a[r]);

        for (int j = n; j >= i; j--) 
            a[r][j] /= a[r][i];

        for (int j = r + 1; j < n; j++)
            if (fabs(a[j][i]) > eps)
                for (int k = n; k >= i; k--)
                    a[j][k] -= a[r][k] * a[j][i];
        r++;
    }

    if (r < n)
    {
        for (int i = r; i < n; i++)
            if (fabs(a[i][n]) > eps) 
                return 0;  //无解
        return 2;   //无数解
    }

    for (int i = n - 2; i >= 0; i--)
        for (int j = i + 1; j < n; j++)
            a[i][n] -= a[i][j] * a[j][n];

    return 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
26
27
28
29
30
31
32
33
34
35
36
int gauss()
{
    int r = 0;
    for (int i = 0; i < n; i++)
    {
        int t = r;
        for (int j = r; j < n; j++)
            if (a[j][i] > a[t][i])
                t = j;

        if (!a[t][i]) continue;

        if (t != r) swap(a[t], a[r]);

        for (int j = r + 1; j < n; j++)
            if (a[j][i])
                for (int k = n; k >= i; k--)
                    a[j][k] ^= a[r][k];

        r++;
    }

    if (r < n)
    {
        for (int i = r; i < n; i++)
            if (a[i][n])
                return 0;
        return 2;
    }

    for (int i = n - 1; i >= 0; i--)
        for (int j = i + 1; j <= n; j++)
            a[i][n] ^= a[i][j] * a[j][n];

    return 1;
}

组合数I

1
2
3
4
5
6
7
8
9
void init()
{
    for (int i = 0; i < N; i++)
        for (int j = 0; j <= i; j++)
        {
            if (!j) c[i][j] = 1;
            else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
        }
}

组合数II

1
2
3
4
5
6
7
8
9
10
11
12
void init()
{
    f[0] = 1;
    for (int i = 1; i <= N; i++) f[i] = (ll)f[i - 1] * i % mod;
    inv[N] = qmi(f[N], mod - 2);
    for (int i = N - 1; i >= 0; i--) inv[i] = (ll)inv[i + 1] * (i + 1) % mod; 
}
int C(int a, int b)
{
    if (a < b) return 0;
    return (ll)f[a] * inv[b] % mod * inv[a - b] % mod;
}

组合数III

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
int qmi(int a, int k)
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }

    return res;
}

int C(int a, int b)
{
    if (b > a) return 0;

    int res = 1;
    for (int i = 1, j = a; i <= b; i++, j--)
    {
        res = (LL)res * j % p;
        res = (LL)res * qmi(i, p - 2) % p;
    }

    return res;
}

int lucas(LL a, LL b)
{
    if (a < p && b < p) return C(a, b);
    return (LL)C(a % p, b % p) * lucas(a / p, b / p) % p;
}

组合数IV

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
int get_num(int a, int b)
{
    int res = 0;
    while (a)
    {
        res += a / b;
        a /= b;
    }

    return res;
}

int main()
{
    cin >> n >> m;

    get_primes(n);
    for (int i = 0; i < cnt; i++) 
        num[i] = get_num(n, p[i]) - get_num(m, p[i]) - get_num(n - m, p[i]);

    vector<int> res;
    res.push_back(1);

    for (int i = 0; i < cnt; i++)
        for (int j = 0; j < num[i]; j++)
            res = mul(res, p[i]);

    for (int i = res.size() - 1; i >= 0; i--) cout << res[i];

    return 0;
}

第一类斯特林数

将 \(n\) 个不同的元素，划分为 \(m\) 个非空圆排列。 

1
2
3
4
5
6
7
void init()
{
    f[0][0] = 1;
    for (int i = 1; i < N; i++)
        for (int j = 1; j < N; j++)
            f[i][j] = (f[i - 1][j - 1] + (i - 1) * f[i - 1][j]) % mod;
}

第二类斯特林数

将 \(n\) 个不同的元素，划分为 \(m\) 个非空子集。 

1
2
3
4
5
6
7
void init()
{
    f[0][0] = 1;
    for (int i = 1; i < N; i++)
        for (int j = 1; j < N; j++)
            f[i][j] = (f[i - 1][m - 1] + m * f[i - 1][j]) % mod;
}
O(1) 公式 \[ \begin{equation} S(n,k) = \frac{1}{k!} \sum_{j=0}^k (-1)^{\,k-j} \binom{k}{j} \, j^n \end{equation} \] 
1
2
3
4
5
6
7
8
9
10
11
12
ll calc(int a, int b)
{
    ll res = 0;
    for (int i = 0; i <= b; i++)
    {
        //inv[]:阶乘的逆元
        ll sum = qmi(mod - 1, b - i) * qmi(i, a) % mod);
        sum = sum * inv[i] % mod * inv[b - i] % mod;  
        res = (res + sum) % mod;
    }
    return res;
}

Nim博弈论

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int main()
{
    cin >> n;

    while (n--)
    {
        int x;
        cin >> x;
        res ^= x;
    }

    if (res == 0) cout << "No" << endl;
    else cout << "Yes" << endl;

    return 0;
}

Sg函数

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
int sg(int x)
{
    if (f[x] != -1) return f[x];

    unordered_set<int> S;
    for (int i = 0; i < x; i ++ )
        for (int j = 0; j <= i; j ++ )
            S.insert(sg(i) ^ sg(j));

    for (int i = 0;; i ++ )
        if (!S.count(i))
            return f[x] = i;
}


int main()
{
    cin >> n;

    memset(f, -1, sizeof f);

    int res = 0;
    while (n -- )
    {
        int x;
        cin >> x;
        res ^= sg(x);
    }

    if (res) puts("Yes");
    else puts("No");

    return 0;
}

异或线性基

对于一个数组 \(a\)，若 \(p\) 是它的一组异或线性基，则

  • \(p\) 中任意非空子集异或和不为 \(0\)
  • \(p\) 中每个数的最高位 \(1\) 唯一
  • \(a\) 中任意元素都可以通过 \(p\) 的子集异或出来
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void gauss()
{
    cnt = 0;
    for (int i = 63; i >= 0; i--)
    {
        for (int j = cnt; j < n; j++)
            if (p[j] >> i & 1) 
                swap(p[j], p[cnt]);
        
        if (!(p[cnt] >> i & 1)) continue;
        
        for (int j = 0; j < n; j++)
            if (j != cnt && p[j] >> i & 1)
                p[j] ^= p[cnt];
                
        cnt++;
        if (cnt == n) break;
    }
}

裴蜀定理

\[ 设\ a, b\ 是不全为零的整数， 对任意整数\ x,\ y, 满足\ \gcd(a, b) \mid ax + by, 且存在整数\ x,\ y, 使得\ ax + by = \gcd(a, b). \]

费马小定理

\(若\ p\ 为 素数，gcd(a,p)=1，则\ a^{p-1} \equiv 1(mod\ p)\)

\(另一个形式：对于任意整数\ a，有\ a^p \equiv a(mod\ p)\)

欧拉定理

\(\ 若 gcd(a,m)=1，则\ a^{phi(m)} \equiv 1(mod\ m)\)

威尔逊定理

\(对于素数\ p\ 有 (p-1)! \equiv -1(mod\ p)\)

组合数性质

当 \(n\ \&\ m = m\) 时，\(C(n, m) \% 2 == 0\)

曼哈顿距离转切比雪夫距离

对于\((x1, y1)\) 和 \((x2,y2)\)

设 \(u1 = x1 + y1, v1 = x1 - y1, u1 = x2 + y2, v2 = x2 - y2\)

则两点之间的曼哈顿距离可以转换为 \((u1,v1)\) 和 \((u2, v2)\) 之间的切比雪夫距离

即 \(max(|u1 - u2|, |v1 - v2|)\)

动态规划

二进制优化多重背包

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
int main()
{
    cin >> n >> m;

    int cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        int a, b, s;
        cin >> a >> b >> s;

        int k = 1;
        while (k <= s)
        {
            cnt++;
            v[cnt] = a * k;
            w[cnt] = b * k;
            s -= k;
            k *= 2;
        }

        if (s > 0)
        {
            cnt++;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }
    }

    n = cnt;
    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]);

    cout << f[m] << 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
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        int v, w, s;
        cin >> v >> w >> s;

        memcpy(g, f, sizeof f);

        for (int j = 0; j < v; j++)
        {
            int hh = 0, tt = -1;
            for (int k = j; k <= m; k += v)
            {
                if (hh <= tt && q[hh] < k - s * v) hh++;
                while (hh <= tt && g[q[tt]] - (q[tt] - j) / v * w <= g[k] - (k - j) / v * w) tt--;
                q[++tt] = k;
                f[k] = g[q[hh]] + (k - q[hh]) / v * w;
            }
        }
    }

    cout << f[m] << 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
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];

    int len = 0;
    for(int i = 0; i < n; i++)  //严格单调递增
    {
        int l = 0, r = len;
        while(l < r)
        {
            int mid = l + r + 1 >> 1;
            if (q[mid] < a[i]) l = mid;
            else r = mid - 1;
        }
        len = max(len, r + 1);
        q[r + 1] = a[i];
    }

    cout << len << 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
int main()
{
    cin >> n >> m;
    cin >> k;
    s = ' ' + k;
    cin >> k;
    p = ' ' + k;
    
    for (int i = m; i; i--) c[p[i] - 'a'].push_back(i);
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < c[s[i] - 'a'].size(); j++)
            w.push_back(c[s[i] - 'a'][j]);
    
    for (int i = 0; i < w.size(); i++)
    {
        int l = 0, r = len;
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (q[mid] < w[i]) l = mid;
            else r = mid - 1;
        }
        q[r + 1] = w[i];
        len = max(len, r + 1);
    }
    
    cout << len << endl;
    
    return 0;
}

数位dp

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
int dp(int u, int cnt, int op)  
{
    if (u == -1) return cnt == k;
    if (!op && ~f[u][cnt]) return f[u][cnt];

    int res = 0, maxv = op? min(1, num[u]) : 1;
    for (int i = 0; i <= maxv; i++)
    {
        if (cnt + i > k) continue;
        res += dp(u - 1, cnt + i, op && i == num[u]);
    }

    return op? res : f[u][cnt] = res;
}

int cal(int n)
{
    num.clear();
    memset(f, -1, sizeof f);

    while (n)
    {
        num.push_back(n % b);
        n /= b;
    }

    return dp(num.size() - 1, 0, 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
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
struct Point
{
    double x, y;
    bool operator< (const Point &b) const
    {
        if (x != b.x) return x < b.x;
        return y < b.y;
    }
};
Point operator+ (Point a, Point b)  //向量加
{
    return {a.x + b.x, a.y + b.y};  
}
Point operator- (Point a, Point b)  //向量减
{
    return {a.x - b.x, a.y - b.y}; 
}
Point operator* (Point a, double b) //数乘
{
    return {a.x * b, a.y * b};
}
Point operator/ (Point a, double b) //数除
{
    return {a.x / b, a.y / b};
}
double operator* (Point a, Point b) //叉积
{
    return a.x * b.y - a.y * b.x;
}
double operator& (Point a, Point b) //点积
{
    return a.x * b.x + a.y * b.y;
}
double len(Point a) //模长
{
    return sqrt(a & a);
}
double cross(Point A, Point B, Point C) //AC和BC的叉积(二倍三角形ABC的面积)
{
	return (B - A) * (C - A);
}
double dot(Point A, Point B, Point C) //AC和BC的点积
{
	return ((B - A) & (C - A));
}
double dis1(Point a, Point b) //距离
{
    return len(b - a);
}
int dis2(Point a, Point b) //距离的平方
{
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
Point getNode(Point a, Point u, Point b, Point v) //直线交点
{
    double t = (a - b) * v / (v * u);
    return a + u * t;
}
Point rotate(Point a, double b) //逆转角
{
    return {a.x * cos(b) - a.y * sin(b), a.x * sin(b) + a.y * cos(b)};
}
bool onseg(Point p, Point a, Point b)  //p 在线段ab上
{
    return fabs((a - p) * (b - p) < eps && ((a - p) & (b - p))) <= 0;
}	
Point norm(Point a) //单位向量
{
    return a / len(a);  
}
void zero (Point & a)
{
    if (fabs(a.x) < eps) a.x = 0;
    if (fabs(a.y) < eps) a.y = 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
double getDP2(Point a, Point b, Point &pa, Point & pb) 
{
    Point e = getNode(a, b - a, o, rotate(b - a, PI / 2)); //垂足
    double d = dis(o, e);
    if(!onseg(e, a, b)) d = min(dis(o, a), dis(o, b));
    if(R <= d) return d; //线段在圆外
    double len = sqrt(R * R - dis(o, e) * dis(o, e));
    pa = e + norm(a - b) * len;
    pb = e + norm(b - a) * len; //pa,pb:线段与圆的两交点
    return d; //d:圆心到线段的最近距离   
}

double sector(Point a, Point b) //扇形面积
{ 
    double angle = acos((a & b) / len(a) / len(b)); //[0,Pi]
    if(a * b < 0) angle = -angle;
    return R * R * angle / 2;
}

double getArea(Point a, Point b) //面积的交
{ 
    if(fabs(a * b) < eps) return 0; //共线
    double da = dis(o, a), db = dis(o, b);
    if(R >= da && R >= db) return a * b / 2; //ab在圆内
    Point pa, pb;
    double d = getDP2(a,b,pa,pb); //d:圆心到线段的最近距离
    if(R <= d) return sector(a,b); //ab在圆外
    if(R >= da) return a*pb/2+sector(pb,b); //a在圆内
    if(R >= db) return sector(a, pa) + pa * b / 2; //b在圆内
    return sector(a, pa) + pa * pb / 2 + sector(pb, b); //ab是割线
}

凸包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
double andrew() //凸包
{
    sort(a + 1, a + n + 1);

    for (int i = 1; i <= n; i++)
    {
        while (tt > 1 && cross(s[tt - 1], s[tt], a[i]) <= 0) tt--;
        s[++tt] = a[i];
    }

    int t = tt;
    for (int i = n - 1; i > 0; i--)
    {
        while (tt > t && cross(s[tt - 1], s[tt], a[i]) <= 0) tt--;
        s[++tt] = a[i];
    } 
    n = tt - 1; //凸包的点数

    double res = 0;
    for (int i = 1; i < tt; i++) res += dis1(s[i], s[i + 1]); //周长

    return res;
}

旋转卡壳

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
double rotating_calipers() // 需配合凸包使用
{
    double res = 0;
    for (int i = 1, j = 2; i <= n; i++) //边-点
    {
        while (cross(s[i], s[i + 1], s[j]) < cross(s[i], s[i + 1], s[j  + 1])) j = j % n + 1;
        res = max({res, dis1(s[i], s[j]), dis1(s[i + 1], s[j])}); //最大两点距离
    }
    return res;
    double res = 0;
    for (int i = 1; i < n; i++) //以i，j为对角线，找上下两个对锺点
    {
        int a = i, b = i + 1; //a为i到j的点，b为j到i的点
        for (int j = i + 1; j <= n; j++)
        {
            while (cross(s[i], s[j], s[a]) > cross(s[i], s[j], s[a + 1])) a = a % n + 1;
            while (cross(s[i], s[j], s[b]) < cross(s[i], s[j], s[b + 1])) b = b % n + 1;
            res = max(res, cross(s[i], s[j], s[b]) - cross(s[i], s[j], s[a])); //最大四边形面积
        }
    }
    return res / 2;
}

扫描线

区间小于等于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
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
struct Bit
{
    int s[N], n;
    void init(int len)
    {
        n = len;
        for (int i = 0; i <= len; i++) s[i] = 0;
    }
    int lowbit(int x)
    {
        return x & -x;
    }
    void modify(int x, int k)
    {
        while (x <= n)
        {
            s[x] += k;
            x += lowbit(x);
        } 
    }
    int query(int x)
    {
        int res = 0;
        while (x)
        {
            res += s[x];
            x -= lowbit(x);
        }
        return res;
    }
}T;

void solve()
{	
    int n, m;
    cin >> n >> m;

    T.init(n);

    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    struct Node
    {
        int x, id, st;
    };
    vector<vector<Node>> t(n + 1);
    for (int i = 0; i < m; i++)
    {
        int l, r, x;
        cin >> l >> r >> x;
        t[l - 1].push_back({x, i, -1});
        t[r].push_back({x, i, 1});
    }

    vector<int> res(m);
    for (int i = 1; i <= n; i++)
    {
        T.modify(a[i], 1);
        for (auto [x, id, st]: t[i]) 
            res[id] += T.query(x) * st; 
    }

    for (auto x: res) cout << x << endl;
}

所有区间不同元素个数和 

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
76
77
78
79
80
81
82
83
84
85
86
struct Bit
{
    ll s[N], n;
    void init(int len)
    {
        n = len;
        for (int i = 0; i <= len; i++) s[i] = 0;
    }
    int lowbit(int x)
    {
        return x & -x;
    }
    void modify(int x, int k)
    {
        while (x <= n)
        {
            s[x] = (s[x] + k) % mod;
            x += lowbit(x);
        } 
    }
    ll query(int x)
    {
        ll res = 0;
        while (x)
        {
            res = (res + s[x]) % mod;
            x -= lowbit(x);
        }
        return res;
    }
}B1, B2, B3, B4;

void solve()
{	
    int n, q;
    cin >> n >> q;

    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    struct Node
    {
        int l, r, id;
        bool operator< (const Node &B) const
        {
            return r < B.r;
        }
    };
    vector<Node> t(q);
    for (int i = 0; i < q; i++)
    {
        int l, r;
        cin >> l >> r;
        t[i] = {l, r, i};
    }

    sort(t.begin(), t.end());

    B1.init(n), B2.init(n), B3.init(n), B4.init(n);

    vector<ll> last(n + 1, -1), res(q);
    for (int i = 1, j = 0; i <= n && j < q; i++)
    {
        if (~last[a[i]])
        {
            B1.modify(last[a[i]], last[a[i]]);
            B2.modify(last[a[i]], last[a[i]] * i % mod);
            B3.modify(last[a[i]], i);
            B4.modify(last[a[i]], 1);
        }
        last[a[i]] = i;
        for (; j < q && t[j].r == i; j++)
        {
            auto [l, r, id] = t[j];
            ll len = r - l + 1;
            res[id] = len * (len + 1) % mod * (len + 2) % mod * qmi(6, mod - 2) % mod;
            ll s1 = (B1.query(r) - B1.query(l - 1) + mod) % mod * (r + 1) % mod;
            ll s2 = (B2.query(r) - B2.query(l - 1) + mod) % mod;
            ll s3 = (B3.query(r) - B3.query(l - 1) + mod) % mod * (l - 1) % mod;
            ll s4 = (B4.query(r) - B4.query(l - 1) + mod) % mod * (((ll)l * r - r + l - 1) % mod) % mod;
            res[id] = (res[id] - s1 + s2 - s3 + s4 + mod + mod) % mod;
        }
    }

    for (auto x: res) cout << x << endl;
}

矩形面积并 

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
struct Seg
{
    #define ls u << 1
    #define rs u << 1 | 1
    struct Node
    {
        int l, r;
        ll sum, cnt;
    }tr[N * 4];
    vector<ll> a;
    void init(vector<ll> s){a = s;}
    void pushup(int u)
    {
        if (!tr[u].cnt) tr[u].sum = tr[ls].sum + tr[rs].sum;
        else tr[u].sum = a[tr[u].r + 1] - a[tr[u].l];
    }
    void build(int u, int l, int r)
    {
        tr[u] = {l, r, 0, 0};
        if (l == r) return;
        int mid = l + r >> 1;
        build(ls, l, mid), build(rs, mid + 1, r);
    }
    void modify(int u, int l, int r, ll x)
    {
        if (tr[u].l >= l && tr[u].r <= r)
        {
            tr[u].cnt += x;
            pushup(u);
        }
        else
        {
            int mid = tr[u].l + tr[u].r >> 1;
            if (l <= mid) modify(ls, l, r, x);
            if (r > mid) modify(rs, l, r, x);
            pushup(u);
        }
    }
    ll query(int u, int l, int r)
    {
        if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
        int mid = tr[u].l + tr[u].r >> 1;
        ll res = 0;
        if (l <= mid) res += query(ls, l, r);
        if (r > mid) res += query(rs, l, r);
        return res;
    }
}T;

void solve()
{	
    int n;
    cin >> n;

    struct line
    {
        int x1, x2, y, st;
        bool operator <(const line &B) const
        {
            return y < B.y;
        }
    };
    vector<ll> s;
    vector<line> t;
    for (int i = 0; i < n; i++)
    {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        t.push_back({x1, x2, y1, 1});
        t.push_back({x1, x2, y2, -1});
        s.push_back(x1), s.push_back(x2);
    }

    sort(t.begin(), t.end());
    sort(s.begin(), s.end());
    s.erase(unique(s.begin(), s.end()), s.end());

    T.init(s);
    T.build(1, 0, s.size() - 2);

    ll res = 0;
    for (int i = 0; i < n * 2; i++)
    {
        int l = lower_bound(s.begin(), s.end(), t[i].x1) - s.begin();
        int r = lower_bound(s.begin(), s.end(), t[i].x2) - s.begin();
        T.modify(1, l, r - 1, t[i].st);
        res += T.query(1, 0, s.size() - 2) * (t[i + 1].y - t[i].y);
    }

    cout << res << endl;
}