首页 > itarticle > 故事再美 结局还是再见

故事再美 结局还是再见

admin 11月 13, 2020 0

from 23forever

数据结构

并查集:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
struct Ufs {
  int n, fa[MAXN + 5], rk[MAXN + 5];
  void operator() (const int _n) {
    n = _n;
    for (int i = 1; i <= n; ++i) {
      fa[i] = i;
      rk[i] = 1;
    }
  }
  int find(int x) {
    return fa[x] == x ? fa[x] : fa[x] = find(fa[x]);
  }
  void unionSet(int x, int y) {
    int p = find(x), q = find(y);
    if (p == q) return;
    if (rk[p] < rk[q]) {
      fa[p] = q;
    } else {
      if (rk[p] == rk[q]) ++rk[q];
      fa[q] = p;
    }
  }
}DSU;

字符串hash:

1
2
3
4
5
6
 
ULL getHsh(char *s) {
  int len = strlen(s);
  ULL ret = 0;
  for (int i = 0; i < len; ++i) ret = ret * P + s[i];
  return ret;
}

树状数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
struct BinaryIndexTree {
  int n, c[MAXN + 5];
  void operator() (int _n) {
    n = _n;
    memset(c, 0, sizeof(c));
  }
  int lowbit(int x) {
    return x & (-x);
  }
  void modify(int x, int v) {
    for (; x <= n; x += lowbit(x)) c[x] += v;
  }
  int getSum(int x) {
    int ret = 0;
    for (; x; x -= lowbit(x)) ret += c[x];
    return ret;
  }
} Bit;

ST表：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
void init() {
  n = read();
  m = read();
  for (int i = 1; i <= n; ++i) a[i] = read();
  for (int i = 1; i <= n; ++i) st[i][0] = a[i];
  for (int j = 1; (1 << j) <= n; ++j) {
    for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
      int a = st[i][j - 1], b = st[i + (1 << (j - 1))][j - 1];
      st[i][j] = max(a, b);
    }
  }
}
inline int query(int x, int y) {
  int k = log2(y - x + 1);
  int a = st[x][k], b = st[y - (1 << k) + 1][k];
  return max(a, b);
}

KMP：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
void getFail() {
  fail[0] = 0;
  fail[1] = 0;
  for (int i = 1; i <= m; ++i) {
    int j = fail[i];
    while (j && p[i] != p[j]) j = fail[j];
    fail[i + 1] = p[i] == p[j] ? j + 1 : 0;
  }
}
void calc() {
  int j = 0;
  for (int i = 0; i <= n; ++i) {
    while (j && t[i] != p[j]) j = fail[j];
    if (t[i] == p[j]) ++j;
    if (j == m) printf("%dn", i - m + 2);
  }
}

manacher：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
int manacher() {
  int ret = 0;
  s[n++] = '$';
  s[n++] = '#';
  for (int i = 0; i < len; ++i) {
    s[n++] = a[i];
    s[n++] = '#';
  }
  for (int i = 0; i < n; ++i) {
    f[i] = i < mx ? min(f[2 * id - i], mx - i) : 1;
    while (s[i + f[i]] == s[i - f[i]]) ++f[i];
    if (f[i] + i > mx) {
      mx = f[i] + i;
      id = i;
    }
    ret = max(ret, f[i]);
  }
  return --ret;
}

线段树：

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
 
struct SegmentTree {
  struct Node {
    LL delta, mul, sum;
  }s[MAXN * 4 + 5];
  SegmentTree() {}
  #define lson p << 1
  #define rson p << 1 | 1
  void add(int p, int len, LL v) {
    s[p].delta = (s[p].delta + v) % mod;
    s[p].sum = (s[p].sum + v * len) % mod;
  }
  void mul(int p, LL v) {
    s[p].mul = s[p].mul * v % mod;
    s[p].delta = s[p].delta * v % mod;
    s[p].sum = s[p].sum * v % mod;
  }
  void pd(int p, int len) {
    if (s[p].mul != 1) {
      mul(lson, s[p].mul);
      mul(rson, s[p].mul);
      s[p].mul = 1;
    }
    if (s[p].delta) {
      add(lson, len - len / 2, s[p].delta);
      add(rson, len / 2, s[p].delta);
      s[p].delta = 0;
    } 
  }
  void upd(int p) {
    s[p].sum = (s[lson].sum + s[rson].sum) % mod;
  }
  void build(int p, int l, int r) {
    s[p].mul = 1;
    if (l == r) {
      s[p].sum = a[l];
      return;
    }
    int mid = (l + r) >> 1;
    build(lson, l, mid);
    build(rson, mid + 1, r);
    upd(p);
  }
  void modify(int p, int l, int r, int x, int y, LL v) {
    if (x <= l && y >= r) {
      add(p, r - l + 1, v);
      return;
    }
    pd(p, r - l + 1);
    int mid = (l + r) >> 1;
    if (x <= mid) modify(lson, l, mid, x, y, v);
    if (y > mid) modify(rson, mid + 1, r, x, y, v);
    upd(p);
  }
  void update(int p, int l, int r, int x, int y, LL v) {
    if (x <= l && y >= r) {
      mul(p, v);
      return;
    }
    pd(p, r - l + 1);
    int mid = (l + r) >> 1;
    if (x <= mid) update(lson, l, mid, x, y, v);
    if (y > mid) update(rson, mid + 1, r, x, y, v);
    upd(p);
  }
  LL query(int p, int l, int r, int x, int y) {
    if (x <= l && y >= r) return s[p].sum % mod;
    pd(p, r - l + 1);
    int mid = (l + r) >> 1;
    LL ret = 0;
    if (x <= mid) ret = query(lson, l, mid, x, y);
    if (y > mid) ret = (ret + query(rson, mid + 1, r, x, y)) % mod;
    return ret;
  }
}Sgt;

AC自动机：

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
 
struct ACAutomaton {
  int tot, trie[MAXN + 5][CS], cnt[MAXN + 5];
  int fail[MAXN + 5], val[MAXN + 5];
  queue<int> que;
  ACAutomaton() {}
  void init() {
    tot = 0;
    memset(fail, 0, sizeof(fail));
    memset(cnt, 0, sizeof(cnt));
    memset(val, 0, sizeof(val));
    memset(trie, 0, sizeof(trie));
  }
  void insert(char *p, int id) {
    int m = strlen(p), now = 0;
    for (int i = 0; i < m; ++i) {
      int c = p[i] - 'a';
      if (!trie[now][c]) trie[now][c] = ++tot;
      now = trie[now][c];
    }
    val[now] = id;
  }
  void getFail() {
    for (int i = 0; i < CS; ++i) {
      int u = trie[0][i];
      if (u) {
        fail[u] = 0;
        que.push(u);
      }
    }
    while (!que.empty()) {
      int cur = que.front();
      que.pop();
      for (int i = 0; i < CS; ++i) {
        int u = trie[cur][i];
        if (u) {
          fail[u] = trie[fail[cur]][i];
          que.push(u);
        } else {
          trie[cur][i] = trie[fail[cur]][i];
        }
      }
    }
  }
  void query(char *t) {
    int n = strlen(t), now = 0;
    for (int i = 0; i < n; ++i) {
      now = trie[now][t[i] - 'a'];
      int j = now;
      while (j) {
        if (val[j]) ++cnt[val[j]];
        j = fail[j];
      }
    } 
    int mx = 0;
    for (int i = 1; i <= n; ++i) mx = max(mx, cnt[i]);
    printf("%dn", mx);
    for (int i = 1; i <= n; ++i) {
      if (cnt[i] == mx) puts(p[i]);
    }
  }
}AC;

线性基：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
struct LinearBasis {
  LL b[MAXL + 5];
  void insert(LL x) {
    for (int i = MAXL; ~i; --i) {
      if (x & (1LL << i)) {
        if (!b[i]) {
          b[i] = x;
          return;
        } else {
          x ^= b[i];
        }
      }
    }
  }
  LL query() {
    LL ret = 0;
    for (int i = MAXL; ~i; --i) ret = max(ret, (b[i] ^ ret));
    return ret;
  }
}LB;

左偏树：

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
 
struct Heap {
  int ls, rs, val, fa, dis;
}h[MAXN + 5];
struct LeftistHeap {
  #define u h[x]
  #define uls h[u.ls]
  #define urs h[u.rs]
  #define o h[y]
  LeftistHeap() {
    h[0].val = -1;
  }
  int find(int x) {
    return u.fa ? find(u.fa) : x;
  }
  int merge(int x, int y) {
    if (!x || !y) return x + y;
    if (u.val > o.val || (u.val == o.val && x > y)) swap(x, y);
    u.rs = merge(u.rs, y);
    urs.fa = x;
    if (uls.dis < urs.dis) swap(u.ls, u.rs);
    u.dis = urs.dis + 1;
    return x;
  }
  void delNode(int x) {
    u.val = -1;
    uls.fa = 0;
    urs.fa = 0;
  }
  int top(int x) {
    return u.val;
  }
  void del(int x) {
    delNode(x);
    merge(u.ls, u.rs);  
  }
  void build(int x, int v) {
    u.val = v;
  }
}SH;

非旋treap

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
 
struct Treap {
  int ls, rs, sz, key, val;
  bool rev;
  Treap() {}
}t[MAXN + 5];
struct FhqTreap {
  int tot;
  #define u t[x]
  #define uls t[u.ls]
  #define urs t[u.rs]
  #define o t[y]
  #define ols t[o.ls]
  #define ors t[o.rs]
  FhqTreap() {}
  void createNode(int x) {
    t[++tot].val = x;
    t[tot].sz = 1;
    t[tot].key = rand();
  }
  void upd(int x) {
    u.sz = uls.sz + urs.sz + 1;
  }
  void rev(int x) {
    u.rev ^= 1;
  }
  void pd(int x) {
    if (u.rev) {
      if (u.ls) rev(u.ls);
      if (u.rs) rev(u.rs);
      swap(u.ls, u.rs);
      u.rev ^= 1;
    }
  }
  pii split(int x, int n) {
    if (!n) return mp(0, x);
    pd(x);
    int m = uls.sz;
    if (n == m) {
      int tmp = u.ls;
      u.ls = 0;
      upd(x);
      return mp(tmp, x);
    } else if (n == m + 1) {
      int tmp = u.rs;
      u.rs = 0;
      upd(x);
      return mp(x, tmp);
    } else if (n < m) {
      pii tmp = split(u.ls, n);
      u.ls = tmp.se;
      upd(x);
      return mp(tmp.fi, x);
    }
    pii tmp = split(u.rs, n - m - 1);
    u.rs = tmp.fi;
    upd(x);
    return mp(x, tmp.se);
  }
  int merge(int x, int y) {
    if (!x || !y) return x + y;
    if (u.key < o.key) {
      pd(x);
      u.rs = merge(u.rs, y);
      upd(x);
      return x;
    } else {
      pd(y);
      o.ls = merge(x, o.ls);
      upd(y);
      return y;
    }
  }
  void insert(int k, int x) {
    pii tmp = split(rt, k - 1);
    createNode(x);
    rt = merge(tmp.fi, merge(tot, tmp.se));
  }
  void rever(int x, int y) {
    pii tmp1 = split(rt, x - 1), tmp2 = split(tmp1.se, y - x + 1);
    t[tmp2.fi].rev ^= 1;
    rt = merge(merge(tmp1.fi, tmp2.fi), tmp2.se);
  }
  void print(int x) {
    if (!x) return;
    pd(x);
    print(u.ls);
    printf("%d ", u.val);
    print(u.rs);
  }
}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
 
struct ChairTree {
  struct Node {
    int ls, rs, sz;
  }s[MAXN * 60 + 5];
  int tot;
  #define lson s[p].ls
  #define rson s[p].rs
  ChairTree() {} 
  void insert(int &p, int l, int r, int x) {
    s[++tot] = s[p];
    p = tot;
    ++s[p].sz;
    if (l == r) return; 
    int mid = (l + r) >> 1;
    if (x <= mid) {
      insert(lson, l, mid, x);
    } else {
      insert(rson, mid + 1, r, x);
    }
  }
  int query(int rtl, int rtr, int l, int r, int k) {
    if (l == r) return l;
    int sz = s[s[rtr].ls].sz - s[s[rtl].ls].sz;
    int mid = (l + r) >> 1;
    if (k <= sz) {
      return query(s[rtl].ls, s[rtr].ls, l, mid, k);
    } else {
      return query(s[rtl].rs, s[rtr].rs, mid + 1, r, k - sz);
    }
  }
}CT;

LCT：

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 LinkCutTree {
  struct Node {
    int ch[2], fa;
    bool rev;
  }s[MAXN + 5];
  #define ls ch[0]
  #define rs ch[1]
  #define u s[x]
  #define uls s[u.ls]
  #define urs s[u.rs]
  #define ufa s[u.fa]
  #define o s[y]
  #define ols s[s[y].ls]
  #define ors s[s[y].rs]
  #define ofa s[s[z].fa]
  #define v s[z]
  #define vls s[s[z].ls]
  #define vrs s[s[z].rs]
  int top, st[MAXN + 5];
  void pd(int x) {
    if (u.rev) {
      u.rev ^= 1;
      uls.rev ^= 1;
      urs.rev ^= 1;
      swap(u.ls, u.rs);
    }
  }
  bool isRoot(int x) {
    return ufa.ls != x && ufa.rs != x;
  } 
  void rotate(int x) {
    int y = u.fa, z = o.fa, l, r;
    if (o.ls == x) {
      l = 0;
    } else {
      l = 1;
    }
    r = l ^ 1;
    if (!isRoot(y)) {
      if (v.ls == y) {
        v.ls = x;
      } else {
        v.rs = x;
      }
    }
    u.fa = z;
    o.fa = x;
    s[u.ch[r]].fa = y;
    o.ch[l] = u.ch[r];
    u.ch[r] = y;
  }
  void splay(int x) {
    top = 0;
    st[++top] = x;
    for (int i = x; !isRoot(i); i = s[i].fa) {
      st[++top] = s[i].fa;
    }
    for (int i = top; i; --i) pd(st[i]);
    while (!isRoot(x)) {
      int y = u.fa, z = o.fa;
      if (!isRoot(y)) {
        if (v.ls == y ^ o.ls == x) {
          rotate(x);
        } else {
          rotate(y);
        }
      }
      rotate(x);
    }
  }
  void access(int x) {
    for (int last = 0; x; last = x, x = u.fa) {
      splay(x);
      u.rs = last;
    }
  }
  void makeRoot(int x) {
    access(x);
    splay(x);
    u.rev ^= 1;
  }
  void link(int x, int y) {
    makeRoot(x); 
    u.fa = y;
  }
}LCT;

后缀数组：

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
 
bool cmp(int i, int j, int k) {
  return y[i] == y[j] && y[i + k] == y[j + k];
}
void getSA(int m) {
  for (int i = 1; i <= m; ++i) b[i] = 0;
  for (int i = 1; i <= n; ++i) ++b[x[i] = r[i]];
  for (int i = 1; i <= m; ++i) b[i] += b[i - 1];
  for (int i = n; i; --i) sa[b[x[i]]--] = i;
  for (int k = 1; k <= n; k <<= 1) {
    int p = 0;
    for (int i = n - k + 1; i <= n; ++i) y[++p] = i;
    for (int i = 1; i <= n; ++i) if (sa[i] > k) y[++p] = sa[i] - k;
    for (int i = 1; i <= m; ++i) b[i] = 0;
    for (int i = 1; i <= n; ++i) ++b[x[y[i]]];
    for (int i = 1; i <= m; ++i) b[i] += b[i - 1];
    for (int i = n; i; --i) sa[b[x[y[i]]]--] = y[i];
    swap(x, y);
    p = 1, x[sa[1]] = 1;
    for (int i = 2; i <= n; ++i) x[sa[i]] = cmp(sa[i], sa[i - 1], k) ? p : ++p;
    m = p;
    if (m == n) break;
  }
}
void getHeight() {
  int k = 0;
  for (int i = 1; i <= n; ++i) rk[sa[i]] = i;
  for (int i = 1; i <= n; ++i) {
    if (k) --k;
    int j = sa[rk[i] - 1];
    while (r[i + k] == r[j + k]) ++k;
    height[rk[i]] = 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
 
struct SuffixAutomaton {
  int last, tot;
  int trans[MAXN + 5][CS], link[MAXN + 5], len[MAXN + 5], sz[MAXN + 5];
  int id[MAXN + 5], pre[MAXN + 5];
  SuffixAutomaton() : last(1), tot(1) {}
  void extend(int x) {
    int c = x - 'a', cur = ++tot, p = last;
    len[cur] = len[last] + 1;
    while (p && !trans[p][c]) {
      trans[p][c] = cur;
      p = link[p];
    }
    if (!p) {
      link[cur] = 1;
    } else {
      int q = trans[p][c];
      if (len[p] + 1 == len[q]) {
        link[cur] = q;
      } else {
        int nq = ++tot;
        len[nq] = len[p] + 1;
        memcpy(trans[nq], trans[q], sizeof(trans[q]));
        while (p && trans[p][c] == q) {
          trans[p][c] = nq;
          p = link[p];
        }
        link[nq] = link[q];
        link[q] = nq;
        link[cur] = nq;
      }
    }
    sz[cur] = 1;
    last = cur;
  }
}SAM;

树链剖分:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
void buildTree(int u) {
  depth[u] = depth[fa[u]] + 1;
  sz[u] = 1;
  for (int i = head[u]; ~i; i = edge[i].nxt) {
    int v = edge[i].to;
    if (v != fa[u]) {
      fa[v] = u;
      buildTree(v);
      sz[u] += sz[v];
      if (sz[son[u]] < sz[v]) son[u] = v;
    }
  }
}
void buildChain(int u, int topf) {
  top[u] = topf;
  id[u] = ++cnt;
  mp[id[u]] = u;
  if (!son[u]) return;
  buildChain(son[u], topf);
  for (int i = head[u]; ~i; i = edge[i].nxt) {
    int v = edge[i].to;
    if (v != fa[u] && v != son[u]) buildChain(v, v);
  }
}

图论

spfa：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
void spfa(const int s) {
  memset(d, 0x3f, sizeof(d));
  que.push(s);
  d[s] = 0;
  in_que[s] = true;
  while (!que.empty()) {
    int u = que.front();
    que.pop();
    in_que[u] = false;
    for (int i = head[u]; ~i; i = edge[i].nxt) {
      int v = edge[i].to, w = edge[i].w;
      if (d[u] + w < d[v]) {
        d[v] = d[u] + w;
        if (!in_que[v]) {
          in_que[v] = true;
          que.push(v);
        }
      }
    }
  }
}

dijkstra：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
void dijkstra(const int s) {
  memset(d, 0x3f, sizeof(d));
  Q.push(Node(s, 0));
  d[s] = 0;
  while (!Q.empty()) {
    int u = Q.top().u;
    Q.pop();
    if (vis[u]) continue;
    for (int i = head[u]; ~i; i = edge[i].nxt) {
      int v = edge[i].to, w = edge[i].w;
      if (d[u] + w < d[v]) {
        d[v] = d[u] + w;
        if (!vis[v]) Q.push(Node(v, d[v]));
      }
    }
    vis[u] = true;
  }
}

prim：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
int prim(const int s) {
  memset(d, 0x3f, sizeof(d));
  Q.push(HeapNode(s, 0));
  d[s] = 0;
  int cnt = 0, ret = 0;
  while (!Q.empty()) {
    int u = Q.top().u;
    Q.pop();
    if (vis[u]) continue;
    ++cnt;
    ret += d[u];
    for (int i = head[u]; ~i; i = edge[i].nxt) {
      int v = edge[i].to, w = edge[i].w;
      if (d[v] > w) {
        d[v] = w;
        if (!vis[v]) Q.push(HeapNode(v, w));
      }
    }
    vis[u] = true;
  }
  return cnt < n ? -1 : ret;
}

kruskal：

1
2
3
4
5
6
7
8
9
10
11
12
13
 
int kruskal() {
  sort(e + 1, e + 1 + m);
  int ret = 0, cnt = n;
  for (int i = 1; i <= m; ++i) {
    int u = e[i].u, v = e[i].v, w = e[i].w;
    if (DSU.find(u) != DSU.find(v)) {
      DSU.unionSet(u, v);
      ret += w;
      --cnt;
    }
  }
  return cnt == 1 ? ret : -1;
}

倍增求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
30
31
32
33
34
35
36
37
38
39
40
41
42
 
void buildTree(int u, int fa) {
  an[u][0] = fa;
  depth[u] = depth[fa] + 1;
  for (int i = head[u]; ~i; i = edge[i].nxt) {
    int v = edge[i].to;
    if (v == fa) continue;
    buildTree(v, u);
  }
}
int LCA(int u, int v) {
  if (depth[u] < depth[v]) swap(u, v);
  int k = depth[u] - depth[v];
  for (int i = 0; (1 << i) <= k; ++i) {
    if (k & (1 << i)) u = an[u][i];
  }
  if (u == v) return u;
  for (int i = MAXL - 1; ~i; --i) {
    if (an[u][i] != an[v][i]) {
      u = an[u][i];
      v = an[v][i];
    }
  }
  return an[u][0];
}
void init() {
  //enableFileIO();
  tot = 0;
  memset(head, -1, sizeof(head));
  n = read();
  m = read();
  rt = read();
  for (int i = 1; i < n; ++i) {
    int u = read(), v = read();
    add(u, v);
  }
  buildTree(rt, 0);
  for (int i = 1; i < MAXL; ++i) {
    for (int u = 1; u <= n; ++u) {
      an[u][i] = an[an[u][i - 1]][i - 1];
    }
  }
}

二分图匹配:

1
2
3
4
5
6
7
8
9
10
11
12
13
 
bool hungary(int u) {
  for (int i = head[u]; ~i; i = edge[i].nxt) {
    int v = edge[i].to;
    if (!vis[v]) {
      vis[v] = true;
      if (!res[v] || hungary(res[v])) {
        res[v] = u;
        return true;
      }
    }
  }
  return false;
}

求无向图割点：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
void tarjan(int u) {
  dfn[u] = low[u] = ++ind;
  int sum = 0;
  for (int i = head[u]; ~i; i = edge[i].nxt) {
    int v = edge[i].to;
    if (!dfn[v]) {
      tarjan(v);
      low[u] = min(low[u], low[v]);
      if (dfn[u] <= low[v]) {
        ++sum;
        if (u != rt || sum > 1) is_cut[u] = true;
      }
    } else {
      low[u] = min(low[u], dfn[v]);
    }
  }
}

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
 
bool spfa(const int s) {
  memset(d, 0x3f, sizeof(d));
  memset(in_que, false, sizeof(in_que));
  memset(cnt, 0, sizeof(cnt));
  que.push(s);
  in_que[s] = true;
  d[s] = 0;
  while (!que.empty()) {
    int u = que.front();
    que.pop();
    in_que[u] = false;
    for (int i = head[u]; ~i; i = edge[i].nxt) {
      int v = edge[i].to, w = edge[i].w;
      if (d[u] + w < d[v]) {
        d[v] = d[u] + w;
        cnt[v] = cnt[u] + 1;
        if (cnt[v] >= n) return false;
        if (!in_que[v]) {
          que.push(v);
          in_que[v] = true;
        }
      }
    }
  }
  return true;
}

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
 
void tarjan(int u) {
  dfn[u] = low[u] = ++ind;
  sta.push(u);
  in_sta[u] = true;
  for (int i = head[u]; ~i; i = edge[i].nxt) {
    int v = edge[i].to;
    if (!dfn[v]) {
      tarjan(v);
      low[u] = min(low[u], low[v]);
    } else if (in_sta[v]) {
      low[u] = min(low[u], dfn[v]);
    }
  }
  if (low[u] == dfn[u]) {
    int k;
    sum[++scc_num] = 0;
    do {
      k = sta.top();
      belong[k] = scc_num;
      sum[scc_num] += val[k];
      in_sta[k] = false;
      sta.pop();
    } while (k != u);
  }
}

拓扑排序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
void topsort() {
  for (int i = 1; i <= scc_num; ++i) { 
    if (!in[i]) {
      d[i] = sum[i];
      que.push(i);
    }
  }
  while (!que.empty()) {
    int u = que.front();
    que.pop();
    for (int i = h[u]; ~i; i = e[i].nxt) {
      int v = e[i].to;
      d[v] = max(d[v], d[u] + sum[v]);
      if (!--in[v]) que.push(v);
    }
  }
}

dinic求最大流：

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
 
struct Dinic {
  int level[MAXN + 5], cur[MAXN + 5];
  queue<int> que;
  bool makeLevelGraph(const int s, const int t) {
    memset(level, 0, sizeof(level));
    while (!que.empty()) que.pop();
    que.push(s);
    level[s] = 1;
    while (!que.empty()) {
      int u = que.front();
      que.pop();
      for (int i = head[u]; ~i; i = edge[i].nxt) {
        int v = edge[i].to, cap = edge[i].cap;
        if (cap && !level[v]) {
          level[v] = level[u] + 1;
          que.push(v);
        }
      }
      if (level[t]) return true;
    }
    return false;
  }
  int findAugPath(int u, int t, int flow) {
    if (u == t || !flow) return flow;
    int used = 0;
    for (int &i = cur[u]; ~i && used < flow; i = edge[i].nxt) {
      int v = edge[i].to, &cap = edge[i].cap, &rcap = edge[i ^ 1].cap;
      if (cap && level[v] == level[u] + 1) {
        int d = findAugPath(v, t, min(flow - used, cap));
        if (d) {
          used += d;
          rcap += d;
          cap -= d;
          return d;
        } else {
          level[v] = -INF;
        }
      }
    }
    return 0;
  }
  int operator()(const int s, const int t) {
    int ret = 0, f;
    while (makeLevelGraph(s, t)) {
      memcpy(cur, head, sizeof(head));
      while (f = findAugPath(s, t, INF)) ret += f;
    }
    return ret;
  }
}dinic;

最小费用最大流：

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
 
struct Mfmc {
  int d[MAXN + 5], pre[MAXN + 5], id[MAXN + 5];
  queue<int> que;
  bool in_que[MAXN + 5];
  bool spfa(const int s, const int t) {
    memset(d, 0x3f, sizeof(d));
    memset(pre, -1, sizeof(pre));
    que.push(s);
    d[s] = 0;
    pre[s] = 0;
    in_que[s] = true;
    while (!que.empty()) {
      int u = que.front();
      que.pop();
      in_que[u] = false;
      for (int i = head[u]; ~i; i = edge[i].nxt) {
        int v = edge[i].to, cap = edge[i].cap, cost = edge[i].cost;
        if (cap && d[u] + cost < d[v]) {
          d[v] = d[u] + cost;
          pre[v] = u;
          id[v] = i;
          if (!in_que[v]) {
            in_que[v] = true;
            que.push(v);
          }
        }
      }
    }
    return ~pre[t];
  }
  pii operator()(const int s, const int t) {
    int min_cost = 0, max_flow = 0;
    while (spfa(s, t)) {
      int f = INF;
      for (int u = t; u != s; u = pre[u]) f = min(f, edge[id[u]].cap);
      for (int u = t; u != s; u = pre[u]) {
        edge[id[u]].cap -= f;
        edge[id[u] ^ 1].cap += f;
      }
      max_flow += f;
      min_cost += f * d[t];
    }
    return mp(max_flow, min_cost);
  }
}mfmc;

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
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
 
stack<int> sta;
bool in_sta[MAXN + 5];
int dfn[MAXN + 5], low[MAXN + 5], idx, scc_num, belong[MAXN + 5];
void tarjan(int u) {
  dfn[u] = low[u] = ++idx;
  sta.push(u);
  in_sta[u] = true;
  for (int i = head[u]; ~i; i = edge[i].nxt) {
    int v = edge[i].to;
    if (!dfn[v]) {
      tarjan(v);
      low[u] = min(low[u], low[v]);
    } else if (in_sta[v]) {
      low[u] = min(low[u], dfn[v]);
    }
  }
  if (dfn[u] == low[u]) {
    int k;
    ++scc_num;
    do {
      k = sta.top();
      belong[k] = scc_num;
      in_sta[k] = false;
      sta.pop();
    } while (k != u);
  }
}
int n, m;
void init() {
  //enableFileIO();
  tot = 0;
  memset(head, -1, sizeof(head));
  n = read();
  m = read();
  for (int i = 1; i <= m; ++i) {
    int u = read(), a = read(), v = read(), b = read();
    if (a && b) {
      add(u + n, v);
      add(v + n, u);
    } else if (!a && b) {
      add(v + n, u + n);
      add(u, v);
    } else if (a && !b) {
      add(u + n, v + n);
      add(v, u);
    } else {
      add(u, v + n);
      add(v, u + n);
    }
  }
}
int main() {
  init();
  for (int i = 1; i <= 2 * n; ++i) {
    if (!dfn[i]) tarjan(i);
  }
  for (int i = 1; i <= n; ++i) {
    if (belong[i] == belong[i + n]) {
      puts("IMPOSSIBLE");
      return 0;
    }
  }
  puts("POSSIBLE");
  for (int i = 1; i <= n; ++i) {
    printf("%d ", belong[i] < belong[i + n]);
  }
  printf("n");
  return 0;
}

数论

快速幂：

1
2
3
4
5
6
7
8
9
10
 
LL fastPow(LL b, LL p, LL m) {
  LL ret = 1;
  b %= m;
  while (p) {
    if (p & 1) ret = ret % m * b % m;
    b = b % m * b % m;
    p >>= 1;
  }
  return ret % m;
}

埃氏筛：

1
2
3
4
5
6
 
for (int i = 2; i <= n; ++i) {
    if (c[i]) continue;
    for (int j = i; j <= n / i; ++j) {
      c[i * j] = true;
    }
  }

求1-n的phi值

1
2
3
4
5
6
7
8
 
for (int i = 2; i <= n; ++i) phi[i] = i;
for (int i = 2; i <= n; ++i) {
  if (phi[i] == i) {
    for (int j = i; j <= n; j += i) {
      phi[j] = phi[j] / i * (i - 1);
    }
  }
}

求1-n的所有约数

1
2
3
4
5
 
for (int i = 1; i <= n; ++i) {
  for (int j = 1; j <= n / i; ++j) {
    fac[i * j].push_back(i);
  }
}

矩阵快速幂：

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
 
struct Matrix {
  LL a[MAXN + 5][MAXN + 5];
  int n, m;
  Matrix() {}
  Matrix(int _n, int _m) : n(_n), m(_m) {
    memset(a, 0, sizeof(a));
  }
  void operator() (int _n, int _m) {
    n = _n;
    m = _m;
    memset(a, 0, sizeof(a));
  }
  void init() {
    memset(a, 0, sizeof(a));
    for (int i = 1; i <= n; ++i) a[i][i] = 1;
  }
  Matrix operator * (const Matrix &mat) {
    Matrix ret(n, m);
    for (int i = 1; i <= n; ++i) {
      for (int j = 1; j <= m; ++j) {
        for (int k = 1; k <= mat.n; ++k) {
          ret.a[i][j] = (ret.a[i][j] + a[i][k] * mat.a[k][j]) % MOD;
        }
      }
    }
    return ret;
  }
}a;
Matrix fastPow(Matrix mat, LL k) {
  Matrix ret(mat.n, mat.m);
  ret.init();
  while (k) {
    if (k & 1) ret = ret * mat;
    mat = mat * mat;
    k >>= 1;
  }
  return ret;
}

线性求逆元：

1
2
3
4
5
6
7
 
int main() {
  init();
  ans[1] = 1;
  for (int i = 2; i <= n; ++i) ans[i] = 1LL * (p - p / i) * ans[p % i] % p;
  for (int i = 1; i <= n; ++i) printf("%dn", ans[i]);
  return 0;
}

快速乘：

1
2
3
4
5
6
7
8
9
 
LL fastMul(LL b, LL p, LL m) {
  LL ret = 0;
  while (p) {
    if (p & 1) ret = (ret + b) % m;
    b = (b + b) % m;
    p >>= 1;
  }
  return ret;
}

拓展欧几里得：

1
2
3
4
5
6
7
8
9
 
LL exgcd(LL a, LL b, LL &x, LL &y) {
  if (!b) {
    x = 1, y = 0;
    return a;
  }
  LL g = exgcd(b, a % b, x, y), tmp = x;
  x = y, y = tmp - a / b * y;
  return g;
}

拓展中国剩余定理：

1
2
3
4
5
6
7
8
9
10
11
12
13
 
LL excrt(LL *a, LL *m) {
  LL ret = m[1], lcm = a[1], x, y;
  for (int i = 2; i <= n; ++i) {
    m[i] = (m[i] - ret % a[i] + a[i]) % a[i];
    LL g = exgcd(lcm, a[i], x, y);
    if (m[i] % g) return -1;
    LL k = fastMul(x, m[i] / g, a[i]); //x * m[i] / g % a[i];
    ret += k * lcm;
    lcm = lcm / g * a[i];
    ret = (ret % lcm + lcm) % lcm;
  }
  return ret;
}
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能