Adamska's Blog

发表于 更新于 分类于

并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 不带权并查集
const int N;

int p[N];

//merge
p[find(a)] = find(b);

int find(int x)
{
    if (x == p[x])
        return x;
    return p[x] = find(p[x]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 带权并查集
const int N;

int p[N];
int d[N];
int l[N];

void merge(int a, int b) // add a to end of b
{
    int ra = find(a), rb = find(b);
    p[ra] = rb;
    d[ra] = l[rb];
    l[rb] += l[ra];
}

int find(int x)
{
    if (x == p[x])
        return x;
    int root = find(p[x]);
    d[x] += d[p[x]];
    p[x] = root;
}

二叉堆

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
// 以小根堆为例
const int N = 10010;

int heap[N], size = 0;

void up(int p)
{
    if (p == 1)
        return;
    if (heap[p] < heap[p / 2])
    {
        swap(heap[p], heap[p / 2]);
        up(p / 2);
    }
}

void down(int p)
{
    int s = p * 2;
    if (s > size)
        return;
    if (heap[s + 1] < heap[s])
        s++;
    if (heap[s] < heap[p])
    {
        swap(heap[p], heap[s]);
        down(s);
    }
}

void insert(int val)
{
    heap[++size] = val;
    up(size);
}

void pop()
{
    heap[1] = heap[size--];
    down(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
const int N;
int n;
int a[N];
int p[N];
int tr[N];

inline int lowbit(int x) {return x & -x;}

void build()
{
    for (int i = 1; i <= n; i++)
        p[i] = p[i - 1] + a[i];
    for (int i = 1; i <= n; i++)
        tr[i] = p[i] - p[i - lowbit(i)];
}

void add(int x, int c)
{
    for (int i = x; i <= n; i += lowbit(i))
        tr[i] += c;
}

void sum(int x)
{
    int res;
    for (int i = x; i >= 1; i -= lowbit(i))
        sum += tr[i];
    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
// 无 lazy tag （以存储最大值为例）
const int N;

int a[N];

struct TreeNode
{
    int l;
    int r;
    int v;
} tr[N << 2];

void pushup(int u)
{
    tr[u].v = max(tr[u << 1].v, tr[u << 1 | 1].v);
}

void build(int u, int l, int r)
{
    tr[u] = {l, r};
    if (l == r)
        tr[u].v = a[l];
    else
    {
        int mid = l + r >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void modify(int u, int x, int v)
{
    if (tr[u].l == x && tr[u].r == x)
        tr[u].v = v;
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if (x <= mid)
            modify(u << 1, x, v);
        else
            modify(u << 1 | 1, x, v);
        pushup(u);
    }
}

int query(int u, int l, int r)
{
    if (l <= tr[u].l && tr[u].r <= r)
        return tr[u].v;
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        int res = 0;
        if (l <= mid)
            res = query(u << 1, l, r);
        if (r > mid)
            res = max(res, query(u << 1 | 1, 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
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
// 含lazy tag （以存储区间和为例）
using ll = long long;
const int N;

ll a[N];

struct TreeNode
{
    ll l, r;
    ll sum;
    ll add;
} tr[N << 2];

void pushup(int u)
{
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

void pushdown(int u)
{
    if (!tr[u].add)
        return;
    auto &root = tr[u],
         &left = tr[u << 1],
         &right = tr[u << 1 | 1];
    left.add += root.add;
    left.sum += (left.r - left.l + 1) * root.add;
    right.add += root.add;
    right.sum += (right.r - right.l + 1) * root.add;
    root.add = 0;
}

void build(int u, int l, int r)
{
    if (l == r)
    {
        tr[u] = {l, r, a[l], 0};
        return;
    }
    tr[u] = {l, r, 0, 0};
    int mid = l + r >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

void modify(int u, int l, int r, int x)
{
    if (l <= tr[u].l && tr[u].r <= r)
    {
        tr[u].sum += (tr[u].r - tr[u].l + 1) * x;
        tr[u].add += x;
        return;
    }
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid)
        modify(u << 1, l, r, x);
    if (r > mid)
        modify(u << 1 | 1, l, r, x);
    pushup(u);
}

ll query(int u, int l, int r)
{
    if (l <= tr[u].l && tr[u].r <= r)
        return tr[u].sum;
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    ll res = 0;
    if (l <= mid)
        res += query(u << 1, l, r);
    if (r > mid)
        res += query(u << 1 | 1, l, r);
    return res;
}

AC自动机

1

发表于 更新于 分类于

字符串哈希

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
using ull = unsigned long long;
const int P = 131;
int n;
char str[N];
ull h[N], p[N];

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

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

trie

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
const int N = 100010;
int son[N][26], cnt[N], idx;
char str[N];

void insert(char str[])
{
    int p = 0;
    for (int i = 0; str[i] != 0; i++)
    {
        int u = str[i] - 'a';
        if (!son[p][u])
            son[p][u] = ++idx;
        p = son[p][u];
    }
    cnt[p]++;
}

int query(char str[])
{
    int p = 0;
    for (int i = 0; str[i] != 0; i++)
    {
        int u = str[i] - 'a';
        if (!son[p][u])
            return 0;
        p = son[p][u];
    }
    return cnt[p];
}

kmp

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
const int N, M;
int n, m;
char p[N],s[M];
void init()
{
    ne[0] = -1;
    for (int i = 0, j = -1; i < n;)
    {
        if (j == -1 || p[i] == p[j])
        {
            ++i, ++j;
            ne[i] = j;
        }
        else
            j = ne[j];
    }
}

void kmp()
{
    for (int i = -1, j = -1; i < m;)
    {
        if (j == -1 || p[j] == s[i])
            ++i, ++j;
        else
            j = ne[j];
        
        if (j == n)
        {
            // do something such as:
            cout << i - j << " ";
        }
    }
}

发表于 更新于 分类于

扩展欧几里得算法

(a mod b)x+by=(a−[ab]×b)x+by=ax+b(y−[ab]×x) (a \ mod \ b)x + by \\ = (a - [\frac{a}{b}] \times b)x+by \\ = ax + b(y-[\frac{a}{b}]\times x) 

1
2
3
4
5
6
7
8
9
10
11
12
int exgcd(int a, int b, int& x, int& y)
{
    if (b == 0)
    {
        x = 1, y = 0;
        return a;
    }

    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

线性同余方程

a×x≡b (mod m)a\times x \equiv b \ (mod \ m)
即
∃y, ax−my=b\exists y,\ ax-my=b

1
2
3
4
5
6
7
8
int solve(int a, int b, int m)
{
    int x, y;
    int d = exgcd(a, m, x, y);
    if (b % d != 0)
        return -1;
    return b / d * x;
}

筛法

朴素筛法 O(nlogn)O(nlogn)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool st[N];
int p[N];
int sieve(int n)
{
    memset(st, 1, sizeof(st))
    int cnt = 0;
    for (int i = 2; i <= n; i++)
    {
        if (st[i])
            p[cnt++] = i;
        for (int j = 2 * i; j <= n; j += i)
            st[j] = false;
    }
    return cnt;
}
埃氏筛 O(nloglogn)O(nloglogn)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool st[N];
int p[N];
int sieve(int n)
{
    memset(st, 1, sizeof(st))
    int cnt = 0;
    for (int i = 2; i <= n; i++)
    {
        if(st[i])
        {
            p[cnt++] = i;
            for (int j = 2 * i; j <= n; j += i)
                st[j] = false;
        }
    }
    return cnt;
}
欧式筛 O(n)O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int st[N];
int primes[N], idx = 0;
void sieve(int n = N - 5)
{
    memset(st, 1, sizeof(st));
    st[1] = st[0] = 0;
    for (int i = 2; i <= n; i++)
    {
        if (st[i])
            primes[idx++] = i;
        for (int j = 0; i * primes[j] <= n; j++)
        {
            st[i * primes[j]] = false;
            if (i % primes[j] == 0)
                break;
        }
    }
}

快速幂

1
2
3
4
5
6
7
8
9
10
11
12
int quick_pow(int x, int n)
{
    int timer = x, res = 1;
    while (n != 0)
    {
        if (n & 1)
            res *= timer;
        timer *= timer;
        n >>= 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
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
const int N; // 矩阵维数
using matrix  = array<array<int, N>, N>;

matrix mul(matrix a, matrix b)
{
    matrix ans;
    for (int i = 0; i < N; i++)
    	for (int j = 0; j < N; j++)
    	{
            ans[i][j] = 0;
            for (int k = 0; k < N; k++)
            {
            	ans[i][j] += (a[i][k] * b[k][j]);	
    	    	ans[i][j] %= m;
    	    }
    	}
    return ans;
}

matrix quick_pow(matrix x, int n)
{
    matrix timer = x, res;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            if (i == j)
                res[i][j] = 1;
            else
                res[i][j] = 0;
    while(n != 0)
    {
    	if (n & 1)
    	    res = mul(res, timer);
    	timer = mul(timer, timer);	
    	n >>= 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
23
24
25
26
27
28
29
int st[N];
int primes[N], idx = 0;
void sieve(int n = N - 5)
{
    memset(st, 1, sizeof(st));
    st[1] = st[0] = 0;
    for (int i = 2; i <= n; i++)
    {
        if (st[i])
            primes[idx++] = i;
        for (int j = 0; i * primes[j] <= n; j++)
        {
            st[i * primes[j]] = false;
            if (i % primes[j] == 0)
                break;
        }
    }
}

int c[N];
for (int i = 0; i < idx; i++)
{
    int s = n, p = primes[i];
    while (s)
    {
        c[i] += s / p;
        s /= p;
    }
}

组合数

1
2
3
4
5
6
7
8
9
10
const int N, MOD;
int c[N][N];
int get_cab(int a, int b)
{
    if (c[a][b] != -1)
        return c[a][b];
    if (b == 0 || a == b)
        return c[a][b] = 1;
    return c[a][b] = (get_cab(a - 1, b) + get_cab(a - 1, b - 1)) % MOD;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
using ll = long long;
const int N, MOD;
int fact[N];
int infact[N];
void init()
{
    fact[0] = infact[0] = 1;
    for (int i = 1; i < N; i++)
    {
        fact[i] = (ll)fact[i - 1] * i % MOD;
        infact[i] = (ll)
    }
}
int get_cab(int a,int b)
{

}

高斯消元法

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
const int N;
const double eps = 1e-6;
int n;
double a[N][N];

int gauss()
{
    int c, r;
    for (c = 0, r = 0; c < n; c++) // 枚举每一列
    {
        int t = r;
        for (int i = r; i < n; i++) // 找到绝对值最大的一行
            if (fabs(a[i][c]) > fabs(a[t][c]))
                t = i;

        if (fabs(a[t][c]) < eps) // 如果最大值是0， 忽略这一行
            continue;

        for (int i = c; i < n + 1; i++) //  把这一行换到最上面
            swap(a[t][i], a[r][i]);

        for (int i = n; i >= c; i--) //将第一个数变成1
            a[r][i] /= a[r][c];

        for (int i = r + 1; i < n; i++) //将下面所有行的第c列清零
            if (fabs(a[i][c]) > eps)
                for (int j = n; j >= c; j--)
                    a[i][j] -= a[r][j] * a[i][c];
        r++;
    }

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

    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 0; //唯一解
}

发表于 更新于 分类于

邻接表存图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int h[N], ne[M], e[M], idx = 0;
// h[i] 指向节点i的第一个边，ne[i]为边i的下一条边，e[i]为边i的目标节点
void init()
{
    memset(h, -1, sizeof(h));
}

void add(int u, int v)
{
    e[idx] = v;
    ne[idx] = h[u];
    h[u] = idx++;
}

void do_something_to_all_adjacent_side(int u)
{
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int v = e[i];
        do_something(v);
    }
}

拓补排序

将所有入度为0的节点入队。每次入队时，更新相邻节点的度数，并判断跟新后是否为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
vector<int> topo;

bool topsort()
{
    int cnt = 0;
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (din[i] == 0)
        {
            din[i]--;
            q.push(i);
            topo.push(i);
            cnt++;
        }
    while(q.size())
    {
        int u = q.front();
        q.pop();
        for (int i = h[u]; i != -1; i = ne[i])
        {
            int v = e[i];
            din[v]--;
            if (din[v] == 0)
            {
                q.push(i);
                topo.push(i);
                cnt++;
            }
        }
    }
    return cnt == n;
}

朴素Dijstra

在所有未确定最短路的点中，寻找dist最小的点，用这个点更新所有相邻节点，并确定该点距离已经为最短。

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 g[N][N];  // 存储每条边
int dist[N];  // 存储1号点到每个点的最短距离
bool vis[N];   // 存储每个点的最短路是否已经确定

// 求1号点到n号点的最短路，如果不存在则返回-1
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for (int i = 0; i < n - 1; i ++ )
    {
        int u = -1;     // 在还未确定最短路的点中，寻找距离最小的点
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (u == -1 || dist[u] > dist[j]))
                u = j;

        // 用t更新其他点的距离
        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], dist[u] + g[u][j]);

        vis[u] = true;
    }

    if (dist[n] == 0x3f3f3f3f) 
        return -1;
    return dist[n];
}

堆优化Dijstra

使用堆维护距离与相应的节点。

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
using PII = pair<int,int>;

int n;      // 点的数量
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N];        // 存储所有点到1号点的距离
bool vis[N];     // 存储每个点的最短距离是否已确定

// 求1号点到n号点的最短距离，如果不存在，则返回-1
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> pq;
    pq.push({0, 1});      // first存储距离，second存储节点编号

    while (pq.size())
    {
        int d, u;
        tie(d, u) = pq.top();
        // C++ 17 or above: auto [d, u] = pq.top();
        pq.pop();
        

        if (vis[u] || dist[u] < d)
            continue;
        vis[u] = true;

        for (int i = h[u]; i != -1; i = ne[i])
        {
            int v = e[i];
            if(dist[v] > dist[u] + w[i])
            {
                dist[v] = dist[u] + w[i];
                pq.push({dist[v], v});
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f) 
        return -1;
    return dist[n];
}

Bellman-Ford算法

遍历所有边n次，对于每条边{a, b, w}，判断b是否能被a与w更新。

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 n, m;       // n表示点数，m表示边数
int dist[N];        // dist[x]存储1到x的最短路距离

struct Edge     // 边，a表示出点，b表示入点，w表示边的权重
{
    int a, b, w;
}edges[M];

// 求1到n的最短路距离，如果无法从1走到n，则返回-1。
int bellman_ford()
{
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;

    // 如果第n次迭代仍然会松弛三角不等式，就说明存在一条长度是n+1的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。
    for (int i = 0; i < n; i ++ )
    {
        for (int j = 0; j < m; j ++ )
        {
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            if (dist[b] > dist[a] + w)
                dist[b] = dist[a] + w;
        }
    }

    if (dist[n] > 0x3f3f3f3f / 2) 
        return -1;
    return dist[n];
}

spfa 算法

考虑到在BF算法中，只有当一个节点被更新过后才可能用其更新相邻节点，所以记录哪些节点被更新过，并且只从这些节点中取点更新相邻节点。

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
int n;      // 总点数
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N];        // 存储每个点到1号点的最短距离
bool st[N];     // 存储每个点是否在队列中

// 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
int spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    queue<int> q;
    q.push(1);
    st[1] = true;

    while (q.size())
    {
        auto u = q.front();
        q.pop();
        st[u] = false;

        for (int i = h[u]; i != -1; i = ne[i])
        {
            int v = e[i];
            if (dist[v] > dist[u] + w[i])
            {
                dist[v] = dist[u] + w[i];
                if (!st[v])     // 如果队列中已存在j，则不需要将j重复插入
                {
                    q.push(v);
                    st[v] = true;
                }
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f) 
        return -1;
    return dist[n];
}

floyd算法

考虑到任何一条路径都可以转化为两条更短的路径，所以通过枚举拆分路径的方式维护最短路。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void init()
{
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            if (i == j) 
                d[i][j] = 0;
            else 
                d[i][j] = 0x3f3f3f3f;
}

// 算法结束后，d[a][b]表示a到b的最短距离
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
int n;              // n表示点数
int g[N][N];        // 邻接矩阵，存储所有边
int dist[N];        // 存储其他点到当前最小生成树的距离
bool st[N];         // 存储每个点是否已经在生成树中


// 如果图不连通，则返回INF(值是0x3f3f3f3f), 否则返回最小生成树的树边权重之和
int prim()
{
    memset(dist, 0x3f, sizeof dist);
    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 (i && dist[t] == INF) 
            return INF;
        if (i) 
            res += dist[t];
        st[t] = true;   
        for (int j = 1; j <= n; j ++ ) 
            dist[j] = min(dist[j], g[t][j]);
    }

    return res;
}

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
43
int n, m;       
int p[N];       

struct Edge
{
    int a, b, w;
} edges[M * 2];

int n, m;
int dist[N];
int p[N];

int find(int x)
{
    if (p[x] == x)
        return x;
    else
        return p[x] = find(p[x]);
}

void add(int a, int b)
{
    p[find(a)] = find(b);
}

int kruskal()
{
    for (int i = 1; i <= n; i++)
        p[i] = i;
    sort(edges + 1, edges + m + 1, [](Edge a, Edge b) -> bool
         { return a.w < b.w; });
    int sum = 0;
    for (int i = 1; i <= m; i++)
    {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;
        if (find(a) != find(b))
        {
            add(a, b);
            sum += w;
        }
    }
    return sum;
}

染色法判断二分图

考虑到二分图等价于图中是否存在偶数环，故选取两种颜色，相邻节点染不同的颜色，当出现矛盾时，则不存在偶数环，故不为二分图。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int color[N];
bool flag;

bool dfs(int u, int c)
{
    color[u] = c;
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int v = e[i];
        if (!color[v])
        {
            if (!dfs(v, 3 - c))
                return false;
        }
        else if (color[v] == c)
            return false;
    }
    return true;
}

匈牙利算法求二分图最大匹配

将二分图划分为左右两侧。对于每个左侧节点，逐个考虑是否可以连接右侧节点。若右侧节点不存在连接，则直接连接。若右侧节点存在连接，则检测该连接对应的左侧节点是否可以重新分配右侧节点。需要注意的是，当需要重新分配时，应直接从下一个右侧节点开始检测而非检测所有右侧节点。

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
int n1, n2;
int match[N];
bool st[N];

bool find(int u)
{
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int v = e[i];
        if (!st[v])
        {
            st[v] = true;
            if (match[v] == 0 || find(match[v]))
            {
                match[v] = u;
                return true;
            }
        }
    }
    return false;
}

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

二分图中求最小点覆盖、最大独立集与最大团

可以证明二分图中最小点覆盖等于最大匹配数，所以直接求一遍最大匹配即可。

在二分图中，求最大独立集只需把最小点覆盖去掉即可，故解为 n−mn - m （mm 为最小点覆盖）。否则为NP问题。

最大团与最大独立集为互补关系。

Tarjan算法求强连通分量

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 timestamp = 0, scc_cnt = 0;
stack<int> stk;
bool in_stk[N];
int dfn[N], low[N], id[N];

void tarjan(int u)
{
    dfn[u] = low[u] = timestamp++;
    stk.push(u), in_stk[u] = true;
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int v = e[i];
        if (!dfn[v])
        {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if (in_stk[v])
            low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u])
    {
        ++scc_cnt;
        do
        {
            v = stk.top();
            stk.pop();
            in_stk[v] = false;
            id[v] = scc_cnt;
        } while (v != u);
    }
}

LCA (倍增 在线)

预处理 fa(i,j)fa(i, j) 表示从节点 ii 开始往上跳 2j2^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
35
36
37
38
39
40
41
int depth[N], fa[N][K + 1];

void bfs(int r)
{
    memset(depth, 0x3f, sizeof(depth));
    depth[0] = 0, depth[r] = 1;
    queue<int> q;
    q.push(r);
    while (q.size())
    {
        int u = q.front();
        q.pop();
        for (int i = h[u]; i != -1; i = ne[i])
        {
            int v = e[i];
            if (depth[v] > depth[u] + 1)
            {
                depth[v] = depth[u] + 1;
                q.push(v);
                fa[v][0] = u;
                for (int k = 1; fa[v][k - 1]; k++)
                    fa[v][k] = fa[fa[v][k - 1]][k - 1];
            }
        }
    }
}

int lca(int a, int b)
{
    if (depth[a] < depth[b])
        swap(a, b);
    for (int k = K; k >= 0; k--)
        if (depth[fa[a][k]] >= depth[b])
            a = fa[a][k];
    if (a == b)
        return a;
    for (int k = K; k >= 0; k--)
        if (fa[a][k] != fa[b][k])
            a = fa[a][k], b = fa[b][k];
    return fa[a][0];
}

LCA(tarjan 离线)

在一次dfs中，将所有节点分为三类：未遍历，遍历中，遍历结束。在遍历的过程中，若要查找某个遍历结束的节点和遍历中的节点的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
void tarjan(int u)
{
    st[u] = 1;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int v = e[i];
        if (!st[v])
        {
            tarjan(v);
            p[v] = u;
        }
    }

    for (auto p : query[u])
    {
        int v, i;
        tie(v, i) = p;
        if (st[v] == 2)
        {
            int anc = find(v);
            res[i] = dist[v] + dist[u] - 2 * dist[anc];
        }
    }
    st[u] = 2;
}

发表于 更新于

如代码

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
// 当看到一只鸟走起来像鸭子、游泳起来像鸭子、叫起来也像鸭子，那么这只鸟就可以被称为鸭子。
// 对于iterator，实现如下方法：operator!=(), operator*(), operator++()
// 对于容器，实现如下方法：begin(), end()
class Iter
{
public:
    explicit Iter(int a) : _value(a) {}
    bool operator!=(const Iter i) { return this->GetValue() != i.GetValue(); }
    int operator*() const { return this->GetValue(); }
    const Iter &operator++() { return ++_value, *this; }
    int GetValue() const { return _value; }

private:
    int _value;
};

class range
{
public:
    explicit range(int a, int b) : _begin(a), _end(b) {}
    Iter begin() { return Iter(_begin); }
    Iter end() { return Iter(_end); }

private:
    int _begin;
    int _end;
};

效果

1
2
for (auto x : range(0, 10))
    cout << x << " ";
1
2
#output
0 1 2 3 4 5 6 7 8 9

发表于 更新于 分类于

此文提供解决日期问题的模板。

简介

日期问题是一类难度不大，但极为烦人的模拟题，一般要求如下：

已知xxxx年yy月zz日为星期k，则aaaa年bb月cc日为星期几？

解决这类题，一般使用如下模板

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 months[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

bool is_leap(int year)
{
    return year % 400 == 0 || (year % 4 == 0 && year % 100 != 0);
}

int get_days(int year, int month)
{
    if (month == 2)
        return months[2] + is_leap(year);
    return months[month];
}

int main()
{
    for (int year = begin; year <= end; year++)
    {
        \*
            code
        *\
        for (int month = 1; month <= 12; month++)
        {
            \*
                code
            *\
            for (int day = 1; day <= get_days(year, month); i++)
            {
                \*
                    code
                *\
            }
        }  
    }
}

我们以CSP上的一道题为例。

201503-3 节日

问题描述

有一类节日的日期并不是固定的，而是以“a月的第b个星期c”的形式定下来的，比如说母亲节就定为每年的五月的第二个星期日。

现在，给你 a，b，ca，b，c 和 y1,y2(1850≤y1,y2≤2050)y1, y2(1850 ≤ y1, y2 ≤ 2050) ，希望你输出从公元 y1y1 年到公元 y2y2 年间的每年的 aa 月的第 bb 个星期 cc 的日期。

提示：关于闰年的规则：年份是400的整数倍时是闰年，否则年份是4的倍数并且不是100的倍数时是闰年，其他年份都不是闰年。例如1900年就不是闰年，而2000年是闰年。

为了方便你推算，已知1850年1月1日是星期二。

输入格式

输入包含恰好一行，有五个整数 a,b,c,y1,y2a, b, c, y1, y2 。其中 c=1,2,……,6,7c=1, 2, ……, 6, 7 分别表示星期一、二、……、六、日。

输出格式

对于 y1y1 和 y2y2 之间的每一个年份，包括 y1y1 和 y2y2，按照年份从小到大的顺序输出一行。

如果该年的 aa 月第 bb 个星期 cc 确实存在，则以 yyyy/mm/dd 的格式输出，即输出四位数的年份，两位数的月份，两位数的日期，中间用斜杠 // 分隔，位数不足时前补零。

如果该年的 aa 月第 bb 个星期 cc 并不存在，则输出 none。

数据范围

1≤a≤12，1≤a≤12，
1≤b≤5，1≤b≤5，
1≤c≤7，1≤c≤7，
1850≤y1,y2≤20501850≤y1,y2≤2050

输入样例：

1
5 2 7 2014 2015

输出样例：

1
2
2014/05/11
2015/05/10

题解

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
#include <iostream>
using namespace std;

int months[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

bool is_leap(int year)
{
    return year % 400 == 0 || (year % 4 == 0 && year % 100 != 0);
}

int get_days(int month, int year)
{
    if (month == 2)
        return months[2] + is_leap(year);
    return months[month];
}

int main()
{
    int a, b, c, y1, y2;
    cin >> a >> b >> c >> y1 >> y2;
    int days = 0;
    for (int year = 1850; year <= y2; year++)
    {
        for (int month = 1; month <= 12; month++)
        {
            if (year >= y1 && month == a)
            {
                int w = (1 + days) % 7, cnt = 0;
                for (int d = 1; d <= get_days(month, year); d++)
                {
                    if (w == c - 1)
                    {
                        cnt++;
                        if (cnt == b)
                        {
                            printf("%04d/%02d/%02d\n", year, month, d);
                            break;
                        }
                    }
                    w = (w + 1) % 7;
                }
                if (cnt < b)
                {
                    puts("none");
                }
            }
            days += get_days(month, year);
        }
    }
}
0%