[关闭]
@ljt12138 2018-11-17T03:13:11.000000Z 字数 24722 阅读 995

NOI模板补全计划

这是一些luogu/loj/bzoj模板题的代码...

带修莫队：luogu1903

注意更新pre...

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 10005;
  6. int n, m, blk;
  8. struct node {
  9.     int l, r, id, ans;
  10.     friend bool operator < (const node &a, const node &b)
  11.     {
  12.         if (a.l/blk == b.l/blk && a.r/blk == b.r/blk) return a.id < b.id;
  13.         if (a.l/blk == b.l/blk) return a.r < b.r;
  14.         return a.l < b.l;
  15.     }
  16. } qy[MAXN];
  17. int qtop = 0;
  19. inline bool cmp(const node &a, const node &b)
  20. { return a.id < b.id; }
  22. int a[MAXN];
  23. int T[MAXN*100];
  24. int pos[MAXN], dt[MAXN], id[MAXN], pre[MAXN], mtop = 0, top = 0;
  26. int main()
  27. {
  28.     scanf("%d%d", &n, &m);
  29.     for (int i = 1; i <= n; i++)
  30.         scanf("%d", &a[i]);
  31.     blk = pow(n, 2.0/3.0);
  32.     for (int i = 1; i <= m; i++) {
  33.         char c;
  34.         int aa, b;
  35.         scanf("\n%c %d%d", &c, &aa, &b);
  36.         if (c == 'Q') qy[++qtop] = (node){aa, b, i, 0};
  37.         else pos[++mtop] = aa, pre[mtop] = a[aa], dt[mtop] = b, id[mtop] = i;
  38.     }
  39.     sort(qy+1, qy+qtop+1);
  40.     int L = 1, R = 0, Ans = 0;
  41.     memset(T, 0, sizeof T);
  42.     for (int i = 1; i <= qtop; i++) {
  43.         while (R < qy[i].r) R++, T[a[R]]++, Ans += (T[a[R]] == 1);
  44.         while (L > qy[i].l) L--, T[a[L]]++, Ans += (T[a[L]] == 1);
  45.         while (L < qy[i].l) T[a[L]]--, Ans -= (T[a[L]] == 0), L++;
  46.         while (R > qy[i].r) T[a[R]]--, Ans -= (T[a[R]] == 0), R--;
  47.         while (top+1 <= mtop && id[top+1] <= qy[i].id) {
  48.             top++;
  49.             if (a[pos[top]] != dt[top]) {
  50.                 pre[top] = a[pos[top]];
  51.                 if (pos[top] >= L && pos[top] <= R) {
  52.                     T[a[pos[top]]]--, T[dt[top]]++;
  53.                     Ans -= (T[a[pos[top]]] == 0), Ans += (T[dt[top]] == 1);
  54.                 }
  55.                 a[pos[top]] = dt[top];
  56.             }
  57.         }
  58.         while (id[top] > qy[i].id) {
  59.             if (a[pos[top]] != pre[top]) {
  60.                 if (pos[top] >= L && pos[top] <= R) {
  61.                     T[a[pos[top]]]--, T[pre[top]]++;
  62.                     Ans -= (T[a[pos[top]]] == 0), Ans += (T[pre[top]] == 1);
  63.                 }
  64.                 a[pos[top]] = pre[top];
  65.             }
  66.             top--;
  67.         }
  68.         qy[i].ans = Ans;
  69.     }
  70.     sort(qy+1, qy+qtop+1, cmp);
  71.     for (int i = 1; i <= qtop; i++)
  72.         printf("%d\n", qy[i].ans);
  73.     return 0;
  74. }

FFT(NTT) luogu1919

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 200005;
  5. const int mod = 998244353, g = 3;
  7. int A[MAXN], B[MAXN], C[MAXN];
  8. int n, m;
  9. int rev[MAXN];
  11. int power(int a, int n)
  12. {
  13.     int ans = 1;
  14.     for (int i = 0; i <= 30; i++) {
  15.         if (n&(1<<i)) ans = (long long)ans*a%mod;
  16.         a = (long long)a*a%mod;
  17.     }
  18.     return ans;
  19. }
  21. inline int inv(int n)
  22. { return power(n, mod-2); }
  24. void NTT(int A[], int n, int flag)
  25. {
  26.     int lgn = int(log2(n)+0.1);
  27.     rev[0] = 0;
  28.     for (int i = 1; i < n; i++) rev[i] = (rev[i>>1]>>1)|((i&1)<<(lgn-1));
  29.     for (int i = 0; i < n; i++)
  30.         if (rev[i] < i)
  31.             swap(A[i], A[rev[i]]);
  32.     for (int k = 2; k <= n; k <<= 1) {
  33.         int dw = power(g, (mod-1)/k);
  34.         if (flag == -1) dw = inv(dw);
  35.         for (int i = 0; i < n; i += k) {
  36.             int w = 1, u, t;
  37.             for (int j = 0; j < k>>1; j++) {
  38.                 u = A[i+j], t = (long long)w*A[i+j+(k>>1)]%mod;
  39.                 A[i+j] = (u+t)%mod, A[i+j+(k>>1)] = ((u-t)%mod+mod)%mod;
  40.                 w = (long long)w*dw%mod;
  41.             }
  42.         }
  43.     }
  44.     if (flag == -1) {
  45.         int invn = inv(n);
  46.         for (int i = 0; i < n; i++)
  47.             A[i] = (long long)A[i]*invn%mod;
  48.     }
  49. }
  51. char str[MAXN];
  53. int main()
  54. {
  55.     scanf("%d", &n);
  56.     scanf("%s", str);
  57.     for (int i = 0; i < n; i++) A[i] = str[n-i-1]-'0';
  58.     scanf("%s", str);
  59.     for (int i = 0; i < n; i++) B[i] = str[n-i-1]-'0';
  60.     int m = 1;
  61.     while (m < n*2) m <<= 1;
  62.     NTT(A, m, 1), NTT(B, m, 1);
  63.     for (int i = 0; i < m; i++) C[i] = (long long)A[i]*B[i]%mod;
  64.     NTT(C, m, -1);
  65.     for (int i = 0; i < m-1; i++) {
  66.         C[i+1] += C[i]/10;
  67.         C[i] %= 10;
  68.     }
  69.     int k = m-1;
  70.     while (C[k] == 0) k--;
  71.     for (int i = k; i >= 0; i--)
  72.         printf("%d", C[i]);
  73.     puts("");
  74.     return 0;
  75. }

点分治：luogu2634

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 20005;
  6. struct node {
  7.     int to, next, dis;
  8. } edge[MAXN*2];
  9. int head[MAXN], top = 0;
  10. inline void push(int i, int j, int d)
  11. { edge[++top] = (node) {j, head[i], d}, head[i] = top; }
  13. int vis[MAXN], siz[MAXN];
  14. int num[3];
  15. long long ans = 0;
  17. int n;
  19. void dfs_siz(int nd, int f)
  20. {
  21.     siz[nd] = 1;
  22.     for (int i = head[nd]; i; i = edge[i].next) {
  23.         int to = edge[i].to;
  24.         if (to == f || vis[to]) continue;
  25.         dfs_siz(to, nd), siz[nd] += siz[to];
  26.     }
  27. }
  29. void find_center(int nd, int f, const int tot_siz, int &cnt, int &ans)
  30. {
  31.     int maxs = tot_siz-siz[nd];
  32.     for (int i = head[nd]; i; i = edge[i].next) {
  33.         int to = edge[i].to;
  34.         if (to == f || vis[to]) continue;
  35.         find_center(to, nd, tot_siz, cnt, ans);
  36.         maxs = max(maxs, siz[to]);
  37.     }
  38.     if (maxs < cnt) cnt = maxs, ans = nd;
  39. }
  41. void dfs_calc(int nd, int f, int dt)
  42. {
  43.     ans += num[(3-dt)%3]*2;
  44.     for (int i = head[nd]; i; i = edge[i].next) {
  45.         int to = edge[i].to;
  46.         if (to == f || vis[to]) continue;
  47.         dfs_calc(to, nd, (dt+edge[i].dis)%3);
  48.     }
  49. }
  51. void dfs_paint(int nd, int f, int dt)
  52. {
  53.     num[dt]++;
  54.     for (int i = head[nd]; i; i = edge[i].next) {
  55.         int to = edge[i].to;
  56.         if (to == f || vis[to]) continue;
  57.         dfs_paint(to, nd, (dt+edge[i].dis)%3);
  58.     }
  59. }
  61. void calc(int nd)
  62. {
  63.     dfs_siz(nd, 0);
  64.     int cnt = INT_MAX, center = 0;
  65.     find_center(nd, 0, siz[nd], cnt, center);
  66.     vis[center] = 1, ans++, num[0]++;
  67.     for (int i = head[center]; i; i = edge[i].next) {
  68.         int to = edge[i].to, d = edge[i].dis;
  69.         if (vis[to]) continue;
  70.         dfs_calc(to, center, d%3);
  71.         dfs_paint(to, center, d%3);
  72.     }
  73.     num[0] = num[1] = num[2] = 0;
  74.     for (int i = head[center]; i; i = edge[i].next) {
  75.         int to = edge[i].to;
  76.         if (!vis[to]) calc(to);
  77.     }
  78. }
  80. inline long long gcd(long long a, long long b)
  81. { return b == 0 ? a : gcd(b, a%b); }
  83. int main()
  84. {
  85.     scanf("%d", &n);
  86.     for (int i = 1; i < n; i++) {
  87.         int u, v, d;
  88.         scanf("%d%d%d", &u, &v, &d);
  89.         push(u, v, d), push(v, u, d);
  90.     }
  91.     calc(1);
  92.     long long tot = (long long)n*n;
  93.     long long c = gcd(ans, tot);
  94.     cout << ans/c << "/" << tot/c << endl;
  95.     return 0;
  96. }

Tarjan LCA(luogu3379)

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 500005;
  5. struct node {
  6.     int to, next;
  7. } edge[MAXN*2];
  8. int head[MAXN], top = 0;
  9. inline void push(int i, int j)
  10. { edge[++top] = (node) {j, head[i]}, head[i] = top; }
  11. int n, m, S, u, v;
  13. vector<pair<int,int> > vec[MAXN];
  14. int fa[MAXN], vis[MAXN], ans[MAXN];
  15. inline int findf(int nd)
  16. { return fa[nd]?fa[nd]=findf(fa[nd]):nd; }
  18. void tarjan(int nd, int f)
  19. {
  20.     vis[nd] = 1;
  21.     for (int i = 0; i < vec[nd].size(); i++) {
  22.         int to = vec[nd][i].first, id = vec[nd][i].second;
  23.         if (vis[to]) ans[id] = findf(to);
  24.     }
  25.     for (int i = head[nd]; i; i = edge[i].next) {
  26.         int to = edge[i].to;
  27.         if (to == f) continue;
  28.         tarjan(to, nd);
  29.     }
  30.     fa[nd] = f;
  31. }
  33. int main()
  34. {
  35.     scanf("%d%d%d", &n, &m, &S);
  36.     for (int i = 1; i < n; i++) {
  37.         scanf("%d%d", &u, &v);
  38.         push(u, v), push(v, u);
  39.     }
  40.     for (int i = 1; i <= m; i++) {
  41.         scanf("%d%d", &u, &v);
  42.         vec[u].push_back(make_pair(v, i)), vec[v].push_back(make_pair(u, i));
  43.     }
  44.     tarjan(S, 0);
  45.     for (int i = 1; i <= m; i++)
  46.         printf("%d\n", ans[i]);
  47.     return 0;
  48. }

可并堆：luogu3377

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 100005;
  6. struct node {
  7.     pair<int, int> dat;
  8.     int lc, rc;
  9.     node()
  10.     { lc = rc = 0; }
  11. } hp[MAXN];
  13. int merge(int a, int b)
  14. {
  15.     if (a == 0 || b == 0) return a+b;
  16.     if (hp[a].dat > hp[b].dat) swap(a, b);
  17.     hp[a].lc = merge(hp[a].lc, b);
  18.     swap(hp[a].lc, hp[a].rc);
  19.     return a;
  20. }
  22. pair<int,int> pop(int &a)
  23. {
  24.     pair<int, int> ans = hp[a].dat;
  25.     a = merge(hp[a].lc, hp[a].rc);
  26.     return ans;
  27. }
  29. int del[MAXN], fa[MAXN], tree[MAXN];
  30. inline int findf(int nd)
  31. { return fa[nd]?fa[nd]=findf(fa[nd]):nd; }
  32. int n, m, u;
  34. int main()
  35. {
  36.     scanf("%d%d", &n, &m);
  37.     for (int i = 1; i <= n; i++) {
  38.         scanf("%d", &u);
  39.         hp[i].dat = make_pair(u, i);
  40.         tree[i] = i;
  41.     }
  42.     int opt, x, y;
  43.     for (int i = 1; i <= m; i++) {
  44.         scanf("%d", &opt);
  45.         if (opt == 1) {
  46.             scanf("%d%d", &x, &y);
  47.             if (del[x] || del[y] || findf(x) == findf(y)) continue;
  48.             x = findf(x), y = findf(y);
  49.             fa[x] = y, tree[y] = merge(tree[x], tree[y]);
  50.         } else {
  51.             scanf("%d", &x);
  52.             if (del[x]) puts("-1");
  53.             else {
  54.                 x = findf(x);
  55.                 pair<int, int> ans = pop(tree[x]);
  56.                 del[ans.second] = 1;
  57.                 printf("%d\n", ans.first);
  58.             }
  59.         }
  60.     }
  61.     return 0;
  62. }

LCT: luogu3690

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 300005;
  6. int chl[MAXN][2], fa[MAXN], dat[MAXN], sum[MAXN], rev[MAXN];
  7. int stk[MAXN], top;
  9. inline bool is_rt(int x)
  10. { return chl[fa[x]][0] != x && chl[fa[x]][1] != x; }
  12. inline void pdw(int nd)
  13. {
  14.     if (chl[nd][0]) rev[chl[nd][0]] ^= rev[nd];
  15.     if (chl[nd][1]) rev[chl[nd][1]] ^= rev[nd];
  16.     if (rev[nd]) swap(chl[nd][0], chl[nd][1]), rev[nd] = 0;
  17. }
  19. inline void update(int nd)
  20. { sum[nd] = dat[nd]^sum[chl[nd][0]]^sum[chl[nd][1]]; }
  21. void zig(int nd)
  22. {
  23.     int p = fa[nd], g = fa[p], tp = chl[p][0] != nd, tg = chl[g][0] != p;
  24.     int son = chl[nd][tp^1];
  25.     if (son) fa[son] = p;
  26.     if (!is_rt(p)) chl[g][tg] = nd;
  27.     fa[p] = nd, fa[nd] = g, chl[nd][tp^1] = p, chl[p][tp] = son;
  28.     update(p), update(nd);
  29. }
  31. void splay(int nd)
  32. {
  33.     stk[top = 1] = nd;
  34.     for (int i = nd; !is_rt(i); i = fa[i]) stk[++top] = fa[i];
  35.     while (top) pdw(stk[top--]);
  36.     while (!is_rt(nd)) {
  37.         int p = fa[nd], g = fa[p], tp = chl[p][0] != nd, tg = chl[g][0] != p;
  38.         if (is_rt(p)) { zig(nd); break; }
  39.         else if (tp == tg) zig(p), zig(nd);
  40.         else zig(nd), zig(nd);
  41.     }
  42. }
  44. void access(int x)
  45. {
  46.     for (int y = 0; x; x = fa[y = x])
  47.         splay(x), chl[x][1] = y, update(x); 
  48. }
  50. void make_rt(int x)
  51. {
  52.     access(x), splay(x), rev[x] ^= 1;
  53. }
  55. inline void link(int x, int y)
  56. { make_rt(x), fa[x] = y, access(x); }
  58. inline void cut(int x, int y)
  59. {
  60.     make_rt(x), access(y), splay(y);
  61.     if (chl[y][0] != x) return;
  62.     chl[y][0] = fa[x] = 0;
  63.     update(y);
  64. }
  66. int findf(int x)
  67. {
  68.     access(x), splay(x);
  69.     while (chl[x][0]) x = chl[x][0];
  70.     return x;
  71. }
  73. int query(int x, int y)
  74. {
  75.     make_rt(x), access(y), splay(y);
  76.     return sum[chl[y][0]]^dat[y];
  77. }
  79. void modify(int x, int y)
  80. {
  81.     access(x), splay(x), dat[x] = y, update(x);
  82. }
  84. int n, m;
  86. inline int read()
  87. {
  88.     int a = 0, c;
  89.     do c = getchar(); while (!isdigit(c));
  90.     while (isdigit(c)) {
  91.         a = a*10+c-'0';
  92.         c = getchar();
  93.     }
  94.     return a;
  95. }
  97. int main()
  98. {
  99.     n = read(), m = read();
  100.     for (int i = 1; i <= n; i++) 
  101.         dat[i] = read();
  102.     int opt, x, y;
  103.     for (int i = 1; i <= m; i++) {
  104.         opt = read(), x = read(), y = read();
  105.         if (opt == 0) {
  106.             printf("%d\n", query(x, y));
  107.         } else if (opt == 1) {
  108.             int a = findf(x), b = findf(y);
  109.             if (a == b) continue;
  110.             link(x, y);
  111.         } else if (opt == 2) {
  112.             cut(x, y);
  113.         } else {
  114.             modify(x, y);
  115.         }
  116.     }
  117.     return 0;
  118. }

tarjan求割点: luogu3388

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 100005;
  6. struct node { 
  7.     int to, next;
  8. } edge[MAXN*2];
  9. int head[MAXN], top = 0;
  10. inline void push(int i, int j)
  11. { edge[++top] = (node) {j, head[i]}, head[i] = top; }
  13. int dfn[MAXN], low[MAXN], dfn_top = 0;
  14. int cur[MAXN];
  15. int n, m;
  17. void tarjan(int nd, int f)
  18. {
  19.     // cerr << f << "-->" << nd << endl;
  20.     dfn[nd] = ++dfn_top, low[nd] = dfn[nd];
  21.     int cnt = 0;
  22.     for (int i = head[nd]; i; i = edge[i].next) {
  23.         int to = edge[i].to;
  24.         if (to == f) continue;
  25.         if (dfn[to]) low[nd] = min(low[nd], dfn[to]);
  26.         else {
  27.             cnt++, tarjan(to, nd), low[nd] = min(low[nd], low[to]);
  28.             if (f && low[to] >= dfn[nd]) cur[nd] = 1;
  29.         }
  30.     }
  31.     if (!f && cnt >= 2) cur[nd] = 1;
  32. }
  34. int main()
  35. {
  36.     scanf("%d%d", &n, &m);
  37.     for (int i = 1; i <= m; i++) {
  38.         int u, v;
  39.         scanf("%d%d", &u, &v);
  40.         push(u, v), push(v, u);
  41.     }
  42.     for (int i = 1; i <= n; i++)
  43.         if (!dfn[i])
  44.             tarjan(i, 0);
  45.     int cnt = 0;
  46.     for (int i = 1; i <= n; i++)
  47.         if (cur[i])
  48.             cnt++;
  49.     printf("%d\n", cnt);
  50.     for (int i = 1; i <= n; i++)
  51.         if (cur[i])
  52.             printf("%d ", i);
  53.     puts("");
  54.     return 0;
  55. }

AC自动机 luogu3796

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 20005;
  5. int chl[MAXN][26], fail[MAXN], top = 0, root = 0;
  6. int vis[MAXN];
  8. struct node {
  9.     int to, next;
  10. } edge[MAXN*2];
  11. int head[MAXN], top_tp = 0;
  12. inline void push(int i, int j)
  13. { edge[++top_tp] = (node) {j, head[i]}, head[i] = top_tp; }
  15. int pos[MAXN];
  16. inline void push(int &nd, const char *str, int id)
  17. {
  18.     if (!nd) nd = ++top;
  19.     if (*str != '\0') push(chl[nd][*str-'a'], str+1, id);
  20.     else pos[id] = nd;
  21. }
  23. queue<int> que;
  25. void build()
  26. {
  27.     int nd = root; que.push(nd);
  28.     while (!que.empty()) {
  29.         int nd = que.front(); que.pop();
  30.         for (int i = 0; i < 26; i++) {
  31.             if (!chl[nd][i]) continue;
  32.             int p = fail[nd];
  33.             while (p && !chl[p][i]) p = fail[p];
  34.             if (!p) fail[chl[nd][i]] = root;
  35.             else fail[chl[nd][i]] = chl[p][i];
  36.             que.push(chl[nd][i]);
  37.         }
  38.     }
  39.     for (int i = 2; i <= top; i++) push(fail[i], i);
  40. }
  42. void match(char *str)
  43. {
  44.     int nd = root;
  45.     for (char *p = str; *p != '\0'; ++p) {
  46.         while (nd && !chl[nd][*p-'a']) nd = fail[nd];
  47.         if (!nd) nd = root;
  48.         else { nd = chl[nd][*p-'a'], vis[nd]++; }
  49.     }
  50. }
  52. void display(int nd, int tab, char from)
  53. {
  54.     if (!nd) return;
  55.     for (int i = 1; i <= tab; i++) putchar(' ');
  56.     printf("--%c--> %d, fail = %d, vis = %d\n", from, nd, fail[nd], vis[nd]);
  57.     for (int i = 0; i < 26; i++) {
  58.         if (chl[nd][i]) display(chl[nd][i], tab+2, i+'a');
  59.     }
  60. }
  62. void dfs1(int nd)
  63. {
  64.     for (int i = head[nd]; i; i = edge[i].next) {
  65.         int to = edge[i].to;
  66.         dfs1(to), vis[nd] += vis[to];
  67.     }
  68. }
  70. char str[151][75];
  71. int n;
  72. char s[1000005];
  74. int main()
  75. {
  76.     while (scanf("%d", &n)) {
  77.         if (n == 0) break;
  78.         root = top = top_tp = 0;
  79.         memset(head, 0, sizeof head), memset(chl, 0, sizeof chl), memset(fail, 0, sizeof fail);
  80.         memset(vis, 0, sizeof vis);
  81.         for (int i = 1; i <= n; i++) scanf("%s", str[i]), push(root, str[i], i);
  82.         scanf("%s", s);
  83.         build();
  84.         match(s);
  85.         dfs1(root);
  86.         int max_val = 0;
  87.         for (int i = 1; i <= n; i++) {
  88.             max_val = max(max_val, vis[pos[i]]);
  89.         } 
  90.         printf("%d\n", max_val);
  91.         for (int i = 1; i <= n; i++)
  92.             if (vis[pos[i]] == max_val)
  93.                 puts(str[i]);
  94.     }
  95.     return 0;
  96. }

匈牙利算法 luogu3386

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 1005;
  6. int n, m, e, u, v;
  7. inline int read()
  8. {
  9.     int a = 0, c;
  10.     do c = getchar(); while (!isdigit(c));
  11.     while (isdigit(c)) {
  12.         a = a*10+c-'0';
  13.         c = getchar();
  14.     }
  15.     return a;
  16. }
  18. struct node {
  19.     int to, next;
  20. } edge[MAXN*MAXN];
  21. int head[MAXN], top = 0;
  22. inline void push(int i, int j)
  23. { edge[++top] = (node) {j, head[i]}, head[i] = top; }
  25. int link[MAXN], vis[MAXN];
  26. int s[MAXN];
  28. bool arg(int nd)
  29. {
  30.     for (int i = head[nd]; i; i = edge[i].next) {
  31.         int to = edge[i].to;
  32.         if (vis[to]) continue;
  33.         vis[to] = 1;
  34.         if (!link[to] || arg(link[to])) {
  35.             link[to] = nd;
  36.             s[nd] = 1;
  37.             return 1;
  38.         }
  39.     }
  40.     return 0;
  41. }
  43. void match()
  44. {
  45.     int cnt = 0;
  46.     for (int i = 1; i <= n; i++) {
  47.         memset(vis, 0, sizeof vis);
  48.         if (!s[i] && arg(i)) cnt++;
  49.     }
  50.     printf("%d\n", cnt);
  51. }
  53. int main()
  54. {
  55.     n = read(), m = read(), e = read();
  56.     for (int i = 1; i <= e; i++) {
  57.         u = read(), v = read();
  58.         if (u > n || v > m) continue;
  59.         push(u, v);
  60.     }
  61.     match();
  62.     return 0;
  63. }

高斯消元法 luogu3389

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 105;
  6. double A[MAXN][MAXN];
  7. int n;
  9. void solve()
  10. {
  11.     for (int i = 1; i <= n; i++) {
  12.         int pos = i;
  13.         while (pos <= n && A[pos][i] == 0) pos++;
  14.         if (pos > n) {
  15.             puts("No Solution");
  16.             return;
  17.         }
  18.         swap(A[pos], A[i]);
  19.         for (int j = 1; j <= n; j++) {
  20.             if (j == i) continue;
  21.             double tmp = -A[j][i]/A[i][i];
  22.             for (int k = 1; k <= n+1; k++)
  23.                 A[j][k] += A[i][k]*tmp;
  24.         }
  25.     }
  26.     for (int i = 1; i <= n; i++)
  27.         printf("%.2f\n", A[i][n+1]/A[i][i]);
  28. }
  30. int main()
  31. {
  32.     scanf("%d", &n);
  33.     for (int i = 1; i <= n; i++)
  34.         for (int j = 1; j <= n+1; j++)
  35.             scanf("%lf", &A[i][j]);
  36.     solve();
  37.     return 0;
  38. }

CRT：SDOI2010古代猪文

和拉格朗日插值法类似，就是构造一个方程满足所有方程组。考虑。设为满足的数，，则可以构造：

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int mod = 999911659;
  5. const int a[] = {2, 3, 4679, 35617}, M = mod-1;
  7. int power(int a, int b, int mod)
  8. {
  9.     int ans = 1;
  10.     for (int i = 0; i <= 30; i++) {
  11.         if ((b>>i)&1) ans = (long long)ans*a%mod;
  12.         a = (long long)a*a%mod;
  13.     }
  14.     return ans;
  15. }
  17. inline int gcd(int a, int b)
  18. { return b==0?a:gcd(b, a%b); }
  19. int ext_gcd(int a, int b, int &x, int &y)
  20. {
  21.     if (b == 0) {
  22.         x = 1, y = 0;
  23.         return a;
  24.     }
  25.     int ans = ext_gcd(b, a%b, y, x);
  26.     y = y-a/b*x;
  27.     return ans;
  28. }
  30. int inv(int a, int m) // (a, b) = 1
  31. { 
  32.     int x, y;
  33.     ext_gcd(a, m, x, y);
  34.     return (x%m+m)%m;
  35. }
  37. int fac[4][40005], ifac[4][40005];
  39. inline int choose(int n, int m, int mod_id)
  40. {
  41.     if (n < m) return 0;
  42.     return (long long)fac[mod_id][n]*ifac[mod_id][m]%a[mod_id]*ifac[mod_id][n-m]%a[mod_id];
  43. }
  45. inline int lucas(int n, int m, int mod_id)
  46. {
  47.     if (n < a[mod_id]) return choose(n, m, mod_id);
  48.     return (long long)lucas(n/a[mod_id], m/a[mod_id], mod_id)*choose(n%a[mod_id], m%a[mod_id], mod_id)%a[mod_id];
  49. }
  51. inline int choose_mod(int n, int m)
  52. {
  53.     int ans[4], x = 0;
  54.     // cerr << n << " " << m << endl;
  55.     for (int i = 0; i < 4; i++) {
  56.         ans[i] = lucas(n, m, i);
  57.         // cerr << ans[i] << " ";
  58.     }
  59.     // cerr << endl;
  60.     for (int i = 0; i < 4; i++) x = (x+(long long)M/a[i]*inv(M/a[i]%a[i], a[i])%M*ans[i]%M)%M;
  61.     // cerr << x << endl;
  62.     return x;
  63. }
  65. int n, g;
  67. int main()
  68. {
  69.     scanf("%d%d", &n, &g);
  70.     if (g%mod == 0) {
  71.         puts("0");
  72.         return 0;
  73.     }
  74.     for (int i = 0; i < 4; i++) fac[i][0] = ifac[i][0] = 1;
  75.     for (int i = 0; i < 4; i++) {
  76.         for (int j = 1; j < a[i]; j++)
  77.             fac[i][j] = (long long)fac[i][j-1]*j%a[i];
  78.         for (int j = 1; j < a[i]; j++) 
  79.             ifac[i][j] = (long long)ifac[i][j-1]*inv(j, a[i])%a[i];
  80.     }
  81.     // cerr << lucas(4, 1, 0) << endl;
  82.     int ans = 0;
  83.     for (int i = 1; i*i <= n; i++)
  84.         if (n%i == 0) {
  85.             ans = (ans+choose_mod(n, i))%M;
  86.             if (n/i > i) ans = (ans+choose_mod(n, n/i))%M;
  87.         }
  88.     printf("%d\n", power(g, ans, mod));
  89.     return 0;
  90. }

拉格朗日插值法

次多项式满足，则满足：

SAM：线段树合并/set启发式合并

2780: [Spoj]8093 Sevenk Love Oimaster

题意：给定若干个模式串，多组询问，问有多少个模式串包含作为其子串。

对模式串建立广义后缀自动机。对于每一个模式串，找到他所有前缀的状态并在其集合中加入。这样，对于一个询问，先找到他的位置，然后答案就是其子树中set并的大小。可以用平衡树/启发式合并，或者线段树合并来维护。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 100005;
  6. struct SAM {
  7.     int chl[MAXN][26], top, root, fa[MAXN], maxl[MAXN];
  8.     set<int> right_set[MAXN];
  9.     int pos[MAXN];
  10.     int dp[MAXN];
  12.     struct node {
  13.         int to, next;
  14.     } edge[MAXN];
  15.     int head[MAXN], top_tp;
  17.     inline void push_edge(int i, int j)
  18.     { edge[++top_tp] = (node) {j, head[i]}, head[i] = top_tp; }
  20.     void clear()
  21.     {
  22.         memset(chl, 0, sizeof chl), top_tp = top = root = 1;
  23.         memset(fa, 0, sizeof fa), memset(maxl, 0, sizeof maxl);
  24.     }
  25.     SAM()
  26.     { clear(); }
  28.     int push(int nd, int x)
  29.     {
  30.         int p = nd, np = ++top; maxl[np] = maxl[p]+1;
  31.         while (p && !chl[p][x]) chl[p][x] = np, p = fa[p];
  32.         if (!p) fa[np] = root;
  33.         else {
  34.             int q = chl[p][x];
  35.             if (maxl[q] == maxl[p]+1) fa[np] = q;
  36.             else {
  37.                 int nq = ++top; maxl[nq] = maxl[p]+1, memcpy(chl[nq], chl[q], sizeof chl[q]);
  38.                 fa[nq] = fa[q], fa[q] = fa[np] = nq;
  39.                 while (p && chl[p][x] == q) chl[p][x] = nq, p = fa[p];
  40.             }
  41.         }
  42.         return np;
  43.     }
  45.     int get_pos(char *str)
  46.     {
  47.         int nd = root;
  48.         for (char *p = str; *p != '\0'; ++p) {
  49.             if (!chl[nd][*p-'a']) return -1;
  50.             nd = chl[nd][*p-'a'];
  51.         }
  52.         return nd;
  53.     }
  55.     int merge(int a, int b)
  56.     {
  57.         if (right_set[a].size() < right_set[b].size()) swap(a, b);
  58.         for (set<int>::iterator j = right_set[b].begin(); j != right_set[b].end(); ++j)
  59.             right_set[a].insert(*j);
  60.         return a;
  61.     }
  63.     void dfs(int nd)
  64.     {
  65.         for (int i = head[nd]; i; i = edge[i].next) {
  66.             int to = edge[i].to;
  67.             dfs(to);
  68.         }
  69.         for (int i = head[nd]; i; i = edge[i].next) {
  70.             int to = edge[i].to;
  71.             pos[nd] = merge(pos[nd], pos[to]);
  72.         }
  73.         dp[nd] = right_set[pos[nd]].size();
  74.     }
  76.     inline void get_ans()
  77.     {
  78.         for (int i = 1; i <= top; i++) {
  79.             pos[i] = i;
  80.             if (fa[i]) push_edge(fa[i], i);
  81.         }
  82.         dfs(root);
  83.     }
  84. };
  86. struct trie {
  87.     int chl[MAXN][26], fa[MAXN], stat[MAXN], top, root;
  88.     SAM sam;
  89.     int fin[MAXN], fin_top;
  91.     void clear()
  92.     {
  93.         sam.clear(), fin_top = top = root = 0;
  94.         memset(stat, 0, sizeof stat);
  95.     }
  97.     trie()
  98.     { clear(); }
  100.     inline void push(int &nd, const char *str)
  101.     {
  102.         if (!nd) nd = ++top;
  103.         if (*str != '\0') push(chl[nd][*str-'a'], str+1), fa[chl[nd][*str-'a']] = nd;
  104.         else fin[++fin_top] = nd;
  105.     }
  107.     inline void push(const char *str)
  108.     { push(root, str); }
  110.     queue<int> que;
  111.     void build_sam()
  112.     {
  113.         stat[root] = sam.root, que.push(root);
  114.         while (!que.empty()) {
  115.             int nd = que.front(); que.pop();
  116.             for (int i = 0; i < 26; i++) {
  117.                 if (!chl[nd][i]) continue;
  118.                 stat[chl[nd][i]] = sam.push(stat[nd], i);
  119.                 que.push(chl[nd][i]);
  120.             }
  121.         }
  122.     }
  124.     void paint()
  125.     {
  126.         for (int i = 1; i <= fin_top; i++) {
  127.             for (register int j = fin[i]; j; j = fa[j])
  128.                 sam.right_set[stat[j]].insert(i);
  129.         }
  130.     }
  133. } T;
  135. int n, q;
  136. char s[400005];
  137. int pos[60005];
  139. int main()
  140. {
  141.     scanf("%d%d", &n, &q);
  142.     for (int i = 1; i <= n; i++) {
  143.         scanf("%s", s);
  144.         T.push(s);
  145.     }
  146.     T.build_sam();
  147.     T.paint();
  148.     for (int i = 1; i <= q; i++) {
  149.         scanf("%s", s);
  150.         pos[i] = T.sam.get_pos(s);
  151.     }
  152.     T.sam.get_ans();
  153.     for (int i = 1; i <= q; i++) {
  154.         if (pos[i] == -1) puts("0");
  155.         else printf("%d\n", T.sam.dp[pos[i]]);
  156.     }
  157.     return 0;
  158. }

树套树 二逼平衡树

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 8000005, N = 50005;
  6. int chl[MAXN][2], fa[MAXN], top = 0;
  7. int dat[MAXN];
  8. int root[N];
  9. int siz[MAXN];
  11. void update(int nd)
  12. { siz[nd] = (chl[nd][0]!=0)*siz[chl[nd][0]]+(chl[nd][1]!=0)*siz[chl[nd][1]]+1; }
  14. void zig(int nd, int id)
  15. {
  16.     int p = fa[nd], g = fa[p], tp = chl[p][0] != nd, tg = chl[g][0] != p;
  17.     int son = chl[nd][tp^1];
  18.     if (son) fa[son] = p;
  19.     if (g) chl[g][tg] = nd;
  20.     else root[id] = nd;
  21.     fa[p] = nd, fa[nd] = g, chl[nd][tp^1] = p, chl[p][tp] = son;
  22.     update(p), update(nd);
  23. }
  25. void splay(int nd, int id, int tar = 0)
  26. {
  27.     while (fa[nd] != tar) {
  28.         // cerr << nd << " " << fa[nd] << endl;
  29.         int p = fa[nd], g = fa[p], tp = chl[p][0] != nd, tg = chl[g][0] != p;
  30.         if (g == tar) { zig(nd, id); break; }
  31.         else if (tp == tg) zig(p, id), zig(nd, id);
  32.         else zig(nd, id), zig(nd, id);
  33.     }
  34. }
  36. int get_rank(int nd, int id)
  37. {
  38.     splay(nd, id);
  39.     return chl[nd][0]+1;
  40. }
  42. int number_ls(int k, int id)
  43. {
  44.     int ans = 0, nd = root[id];
  45.     while (nd) {
  46.         if (dat[nd] < k) ans += siz[chl[nd][0]]+1, nd = chl[nd][1];
  47.         else nd = chl[nd][0];
  48.     }
  49.     return ans;
  50. }
  52. int number_le(int k, int id)
  53. {
  54.     int ans = 0, nd = root[id];
  55.     while (nd) {
  56.         if (dat[nd] <= k) ans += siz[chl[nd][0]]+1, nd = chl[nd][1];
  57.         else nd = chl[nd][0];
  58.     }
  59.     return ans;
  60. }
  62. int find_kth(int k, int id)
  63. {
  64.     int nd = root[id];
  65.     while (1) {
  66.         if (siz[chl[nd][0]]+1 == k) break;
  67.         else if (siz[chl[nd][0]]+1 > k) nd = chl[nd][0];
  68.         else k -= siz[chl[nd][0]]+1, nd = chl[nd][1];
  69.     }
  70.     splay(nd, id);
  71.     return nd;
  72. }
  74. int pre_ele(int dt, int id)
  75. {
  76.     int ls = number_ls(dt, id);
  77.     if (ls == 0) return 0;
  78.     return find_kth(ls, id);
  79. }
  81. int nxt_ele(int dt, int id)
  82. {
  83.     int gt = number_le(dt, id)+1;
  84.     if (gt > siz[root[id]]) return 0;
  85.     return find_kth(gt, id);
  86. }
  88. int push(int &nd, int dt, int f = 0)
  89. {
  90.     if (nd == 0) {
  91.         nd = ++top, dat[nd] = dt, update(nd);
  92.         fa[nd] = f;
  93.         return top;
  94.     }
  95.     siz[nd]++;
  96.     if (dt <= dat[nd]) return push(chl[nd][0], dt, nd);
  97.     else return push(chl[nd][1], dt, nd);
  98. }
  100. int pop_ele(int dt, int id)
  101. {
  102.     // printf("pop %d ---> %d\n", dt, id);
  103.         int num = number_ls(dt, id)+1;
  104.     // cerr << id << "j" << num << endl;
  105.     int pre = find_kth(num-1, id), nxt = find_kth(num+1, id);
  106.     // cerr << pre << " " << nxt << endl;
  107.     // cerr << dat[nxt] << " " << dat[pre] << endl;
  108.     splay(pre, id), splay(nxt, id, pre);
  109.     chl[nxt][0] = 0, update(nxt), update(pre);
  110.     // puts("---");
  111. }
  113. void push_ele(int dt, int id)
  114. {
  115.     // printf("push %d --> %d\n", dt, id);
  116.     int nd = push(root[id], dt);
  117.     splay(nd, id);
  118. }
  120. void display(int nd, int tab)
  121. {
  122.     if (!nd) return;
  123.     for (int i = 1; i <= tab; i++) putchar(' ');
  124.     printf("siz = %d, dat = %d\n",  siz[nd], dat[nd]);
  125.     display(chl[nd][0], tab+2), display(chl[nd][1], tab+2);
  126. }
  128. int c[N], a[N], n, m;
  129. inline int lowbit(int i)
  130. { return i&(-i); }
  131. void del(int nd, int dt)
  132. {
  133.     for (; nd <= n; nd += lowbit(nd))
  134.         pop_ele(dt, nd);
  135. }
  136. void add(int nd, int dt)
  137. {
  138.     for (; nd <= n; nd += lowbit(nd))
  139.         push_ele(dt, nd);
  140. }
  141. void modify(int nd, int dt)
  142. {
  143.     del(nd, a[nd]), add(nd, dt), a[nd] = dt;
  144. }
  146. int number_prefix_ls(int pos, int dt)
  147. {
  148.     int ans = 0;
  149.     for (; pos; pos -= lowbit(pos))
  150.         ans += number_ls(dt, pos)-1;
  151.     return ans;
  152. }
  154. int number_seg_ls(int L, int R, int dt)
  155. { return number_prefix_ls(R, dt)-number_prefix_ls(L-1, dt); }
  157. int number_prefix_le(int pos, int dt)
  158. {
  159.     int ans = 0;
  160.     for (; pos; pos -= lowbit(pos))
  161.         ans += number_le(dt, pos)-1;
  162.     return ans;
  163. }
  165. int number_seg_le(int L, int R, int dt)
  166. { return number_prefix_le(R, dt)-number_prefix_le(L-1, dt); }
  168. int find_seg_kth(int Lpos, int Rpos, int dt)
  169. {
  170.     int L = 0, R = 1e8, Mid;
  171.     while (L <= R) {
  172.         Mid = (L+R)>>1;
  173.         if (number_seg_le(Lpos, Rpos, Mid) >= dt) R = Mid-1;
  174.         else L = Mid+1;
  175.     }
  176.     return R+1;
  177. }
  179. int find_seg_pre(int Lpos, int Rpos, int dt)
  180. {
  181.     int num = number_seg_ls(Lpos, Rpos, dt);
  182.     if (num == 0) return INT_MIN+1;
  183.     return find_seg_kth(Lpos, Rpos, num);
  184. }
  186. int find_seg_nxt(int Lpos, int Rpos, int dt)
  187. {
  188.     int num = number_seg_le(Lpos, Rpos, dt)+1;
  189.     if (num > Rpos-Lpos+1) return INT_MAX;
  190.     return find_seg_kth(Lpos, Rpos, num);
  191. }
  193. inline int read()
  194. {
  195.     int a = 0;
  196.     scanf("%d", &a);
  197.     return a;
  198. }
  200. int main()
  201. {
  202.     // freopen("psh.in", "r", stdin);
  203.     // freopen("psh.out", "w", stdout);
  204.     n = read(), m = read();
  205.     for (int i = 1; i <= n; i++) a[i] = read();
  206.     for (int i = 1; i <= n; i++)
  207.         push_ele(INT_MIN+1, i), push_ele(INT_MAX, i);
  208.     for (int i = 1; i <= n; i++) 
  209.             add(i, a[i]);
  210.     int cnt = 0;
  211.     for (int i = 1; i <= m; i++) {
  212.         int opt, l, r, k;
  213.         opt = read();
  214.         cnt++;
  215.         if (opt == 1) {
  216.             l = read(), r = read(), k = read();
  217.             printf("%d\n", number_seg_ls(l, r, k)+1);
  218.         } else if (opt == 2) {
  219.             l = read(), r = read(), k = read();
  220.             printf("%d\n", find_seg_kth(l, r, k));
  221.         } else if (opt == 3) {
  222.             l = read(), r = read();
  223.             modify(l, r);
  224.             cnt--;
  225.         } else if (opt == 4) {
  226.             l = read(), r = read(), k = read();
  227.             printf("%d\n", find_seg_pre(l, r, k));
  228.         } else {
  229.             l = read(), r = read(), k = read();
  230.             printf("%d\n", find_seg_nxt(l, r, k));
  231.         }
  232.     }
  233.     return 0;
  234. }

Tarjan缩点 HAOI2006受欢迎的牛

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 50005;
  6. struct node {
  7.     int to, next; 
  8. } edge[MAXN];
  9. int head[MAXN], top = 0;
  10. inline void push(int i, int j)
  11. { edge[++top] = (node) {j, head[i]}, head[i] = top; }
  13. int dfn[MAXN], dfn_top = 0, low[MAXN], vis[MAXN], stk[MAXN], stk_top = 0;
  14. int g[MAXN], gtop = 0, gsiz[MAXN];
  15. int d[MAXN];
  16. int n, m;
  18. void tarjan(int nd)
  19. {
  20.     stk[++top] = nd, vis[nd] = 1, dfn[nd] = low[nd] = ++dfn_top;
  21.     for (int i = head[nd]; i; i = edge[i].next) {
  22.         int to = edge[i].to;
  23.         if (!dfn[to]) tarjan(to), low[nd] = min(low[nd], low[to]);
  24.         else if (vis[to]) low[nd] = min(low[nd], dfn[to]);
  25.     }
  26.     if (dfn[nd] == low[nd]) {
  27.         gtop++;
  28.         int now;
  29.         do {
  30.             now = stk[top--];
  31.             vis[now] = 0;  // !!!
  32.             g[now] = gtop, gsiz[gtop]++;
  33.         } while (now != nd);
  34.     }
  35. }
  37. int main()
  38. {
  39.     scanf("%d%d", &n, &m);
  40.     for (int i = 1; i <= m; i++) {
  41.         int u, v;
  42.         scanf("%d%d", &u, &v);
  43.         push(u, v);
  44.     }
  45.     for (int i = 1; i <= n; i++)
  46.         if (!dfn[i])
  47.             tarjan(i);
  48.     for (int i = 1; i <= n; i++) {
  49.         for (int j = head[i]; j; j = edge[j].next) {
  50.             int to = edge[j].to;
  51.             d[g[i]] += (g[to] != g[i]);
  52.         }
  53.     }
  54.     int pos = 0, cnt = 0;
  55.     for (int i = 1; i <= gtop; i++)
  56.         if (d[i] == 0) {
  57.             pos = i, cnt++;
  58.         }
  59.     if (cnt != 1) puts("0");
  60.     else printf("%d\n", gsiz[pos]);
  61.     return 0;
  62. }

KMP loj103

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 1000005;
  6. char S[MAXN], T[MAXN];
  8. int nxt[MAXN];
  10. int main()
  11. {
  12.     scanf("%s", S+1), scanf("%s", T+1);
  13.     nxt[1] = 0;
  14.     int pL = strlen(T+1), sL = strlen(S+1), cnt = 0;
  15.     int p = 0;
  16.     for (int i = 2; i <= pL; i++) {
  17.         while (p && T[p+1] != T[i]) p = nxt[p];
  18.         if (T[p+1] == T[i]) p++;
  19.         nxt[i] = p;
  20.     }
  21.     p = 0;
  22.     for (int i = 1; i <= sL; i++) {
  23.         while (p && T[p+1] != S[i]) p = nxt[p];
  24.         if (T[p+1] == S[i]) p++;
  25.         if (p == pL) {
  26.             cnt++;
  27.             p = nxt[p];
  28.         }
  29.     }
  30.     printf("%d\n", cnt);
  31.     return 0;
  32. }

后缀数组 loj111

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 1000005;
  6. struct SA {
  7.     struct node {
  8.         int k[2], id;
  9.         node(){}
  10.         node(int x, int y) {k[0] = x, k[1] = y; }
  11.     } RE[MAXN], RT[MAXN];
  12.     int a[MAXN], sum[MAXN], SA[MAXN], rank[MAXN], n;
  13.     void radix_sort()
  14.     {
  15.         for (int y = 1; y >= 0; y--) {
  16.             memset(sum, 0, sizeof sum);
  17.             for (int i = 1; i <= n; i++) RT[i] = RE[i];
  18.             for (int i = 1; i <= n; i++) sum[RT[i].k[y]]++;
  19.             for (int i = 1; i < MAXN; i++) sum[i] += sum[i-1];
  20.             for (int i = n; i >= 1; i--) RE[sum[RT[i].k[y]]--] = RT[i];
  21.         }
  22.         for (int i = 1; i <= n; i++) {
  23.             rank[RE[i].id] = rank[RE[i-1].id];
  24.             if (RE[i].k[0] != RE[i-1].k[0] || RE[i].k[1] != RE[i-1].k[1])
  25.                 rank[RE[i].id]++;
  26.         }
  27.     }
  28.     void build_SA()
  29.     {
  30.         for (int i = 1; i <= n; i++) RE[i] = node(a[i], 0), RE[i].id = i;
  31.         radix_sort();
  32.         for (int k = 1; k < n; k <<= 1) {
  33.             for (int j = 1; j <= n; j++) RE[j] = node(rank[j], j+k<=n?rank[j+k]:0), RE[j].id = j;
  34.             radix_sort();
  35.         }
  36.         for (int i = 1; i <= n; i++)
  37.             SA[rank[i]] = i;
  38.     }
  39. } sa;
  41. char str[MAXN];
  43. int main()
  44. {
  45.     scanf("%s", str+1);
  46.     sa.n = strlen(str+1);
  47.     for (int i = 1; i <= sa.n; i++) sa.a[i] = str[i];
  48.     sa.build_SA();
  49.     for (int i = 1; i <= sa.n; i++)
  50.         printf("%d ", sa.SA[i]);
  51.     puts("");
  52.     return 0;
  53. }

线性基k大

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 100005;
  6. int have0 = 0;
  7. struct linear_base {
  8.     long long a[70];
  9.     int top;
  10.     linear_base()
  11.     { top = 0; }
  12.     void push(long long x)
  13.     {
  14.         for (int i = 1; i <= top; i++)
  15.             if ((x^a[i]) < x)
  16.                 x ^= a[i];
  17.         if (!x) { have0 = 1; return; }
  18.         a[++top] = x;
  19.         int i = top;
  20.         for (; i > 1 && a[i] > a[i-1]; i--)
  21.             swap(a[i], a[i-1]);
  22.         for (i--; i >= 1; i--)
  23.             if ((x^a[i]) < a[i])
  24.                 a[i] ^= x;
  25.     }
  27. } lb;
  29. int main()
  30. {
  31.     int n, m;
  32.     long long x;
  33.     scanf("%d", &n);
  34.     for (int i = 1; i <= n; i++) {
  35.         scanf("%lld", &x), lb.push(x);
  36.         // for (int i = 1; i <= lb.top; i++) cerr << lb.a[i] << " ";
  37.         // cerr << endl;
  38.     }
  39.     // puts("hahahahaha");
  40.     // cerr << lb.top << endl;
  41.     scanf("%d", &m);
  42.     for (int i = 1; i <= m; i++) {
  43.         scanf("%lld", &x);
  44.         x -= have0;
  45.         if (x > (1ll<<lb.top)) puts("-1");
  46.         else {
  47.             // cerr << "--" << x << " " << lb.top << endl;
  48.             // cerr << lb.a[9] << endl;
  49.             long long ans = 0;
  50.             for (int j = 0; j <= 60; j++)
  51.                 if (x&(1ll<<j)) {
  52.                     ans ^= lb.a[lb.top-j];
  53.                     // cerr << lb.top-j << endl;
  54.                 }
  55.             printf("%lld\n", ans);
  56.         }
  57.     }
  58.     return 0;
  59. }

spfa多路增广 bzoj1458

行列建点，增广路对应方案。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 205;
  6. int n, m, k;
  7. int l[MAXN], c[MAXN];
  9. struct node {
  10.     int to, next, flow, cost, neg;
  11. } edge[MAXN*MAXN*10];
  12. int head[MAXN], top = 0;
  13. inline void push(int i, int j, int f, int c)
  14. {
  15.     ++top, edge[top] = (node) {j, head[i], f, c, top+1}, head[i] = top;
  16.     ++top, edge[top] = (node) {i, head[j], 0, -c, top-1}, head[j] = top; 
  17. }
  19. const int SS = MAXN-1, ST = MAXN-2, S = MAXN-3, T = MAXN-4;
  21. int cnt = 0;
  23. inline void push(int i, int j, int lb)
  24. {
  25.     push(SS, j, lb, 0), push(i, ST, lb, 0);
  26.     cnt += lb;
  27. }
  29. int dis[MAXN], vis[MAXN];
  30. deque<int> que;
  32. bool spfa()
  33. {
  34.     memset(dis, 127/3, sizeof dis);
  35.     memset(vis, 0, sizeof vis);
  36.     vis[SS] = 1, dis[SS] = 0, que.push_back(SS);
  37.     while (!que.empty()) {
  38.         int nd = que.front(); que.pop_front(), vis[nd] = 0;
  39.         for (int i = head[nd]; i; i = edge[i].next) {
  40.             int to = edge[i].to, f = edge[i].flow, c = edge[i].cost;
  41.             if (!f || dis[to] <= dis[nd]+c) continue;
  42.             dis[to] = dis[nd]+c;
  43.             if (!vis[to]) {
  44.                 vis[to] = 1;
  45.                 if (que.empty() || dis[to] > dis[que.front()]) que.push_back(to);
  46.                 else que.push_front(to);
  47.             }
  48.         }
  49.     }
  50.     return dis[ST] <= 23333333;
  51. }
  53. int dfs(int nd, int flow)
  54. {
  55.     if (nd == ST || !flow) return flow;
  56.     vis[nd] = 1;
  57.     int ans = 0, t;
  58.     for (int i = head[nd]; i; i = edge[i].next) {
  59.         int to = edge[i].to, f = edge[i].flow, c = edge[i].cost;
  60.         if (vis[to] || dis[to] != dis[nd]+c || !f) continue;
  61.         t = dfs(to, min(flow, f));
  62.         ans += t, flow -= t, edge[i].flow -= t, edge[edge[i].neg].flow += t;
  63.         if (!flow) break;
  64.     }
  65.     return ans;
  66. }
  68. void mcf(int &c, int &f)
  69. {
  70.     c = f = 0;
  71.     int t;
  72.     while (spfa()) {
  73.         do {
  74.             memset(vis, 0, sizeof vis);
  75.             t = dfs(SS, INT_MAX);
  76.             f += t, c += t*dis[ST];
  77.         } while (t);
  78.     }
  79. }
  81. bool g[101][101];
  83. int main()
  84. {
  85.     scanf("%d%d%d", &n, &m, &k);
  86.     for (int i = 1; i <= n; i++) scanf("%d", &l[i]);
  87.     for (int i = 1; i <= m; i++) scanf("%d", &c[i]);
  88.     for (int i = 1; i <= k; i++) {
  89.         int u, v;
  90.         scanf("%d%d", &u, &v);
  91.         g[u][v] = true;
  92.     }
  93.     for (int i = 1; i <= n; i++) push(S, i, l[i]);
  94.     for (int j = 1; j <= m; j++) push(n+j, T, c[j]);
  95.     for (int i = 1; i <= n; i++)
  96.         for (int j = 1; j <= m; j++)
  97.             if (!g[i][j])
  98.                 push(i, n+j, 1, 1);
  99.     push(T, S, INT_MAX, 0);
  100.     int c, f;
  101.     mcf(c, f);
  102.     if (f != cnt) puts("JIONG!");
  103.     else printf("%d\n", c);
  104.     return 0;
  105. }

TODO LIST:

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注