马上就要noi了……可能滚粗已经稳了……但是还是要复习模板啊
LCT: bzoj2049 1A 7min
# include <stdio.h> # include <string.h> # include <iostream> # include <algorithm> // # include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int M = 5e5 + 10; const int mod = 1e9+7; struct LCT { int ch[M][2], fa[M], sz[M]; bool rev[M]; # define ls ch[x][0] # define rs ch[x][1] inline void up(int x) { if(!x) return ; sz[x] = 1 + sz[ls] + sz[rs]; } inline void pushrev(int x) { if(!x) return ; rev[x] ^= 1; swap(ch[x][0], ch[x][1]); } inline void down(int x) { if(!x) return ; if(rev[x]) { pushrev(ls); pushrev(rs); rev[x] = 0; } } # undef ls # undef rs inline bool isrt(int x) { return ch[fa[x]][0] != x && ch[fa[x]][1] != x; } inline void rotate(int x) { int y = fa[x], z = fa[y], ls = ch[y][1] == x, rs = ls^1; if(!isrt(y)) ch[z][ch[z][1] == y] = x; fa[ch[x][rs]] = y; fa[y] = x, fa[x] = z; ch[y][ls] = ch[x][rs]; ch[x][rs] = y; up(y); up(x); } int st[M]; inline void splay(int x) { int stn = 0, tx = x; while(!isrt(tx)) st[++stn] = tx, tx = fa[tx]; st[++stn] = tx; for (int i=stn; i; --i) down(st[i]); while(!isrt(x)) { int y = fa[x], z = fa[y]; if(!isrt(y)) { if((ch[z][0] == y) ^ (ch[y][0] == x)) rotate(x); else rotate(y); } rotate(x); } } inline int access(int x) { int t = 0; for (; x; t=x, x=fa[x]) { splay(x); ch[x][1] = t; up(x); } return t; } inline void makeroot(int x) { access(x); splay(x); pushrev(x); } inline int find(int x) { access(x); splay(x); while(ch[x][0]) x = ch[x][0]; return x; } inline void link(int x, int y) { makeroot(x); fa[x] = y; } inline void cut(int x, int y) { makeroot(x); access(y); splay(y); ch[y][0] = fa[x] = 0; up(y); } }T; int n, Q, x, y; int main() { static char op[23]; cin >> n >> Q; for (int i=1; i<=n; ++i) { T.ch[i][0] = T.ch[i][1] = T.fa[i] = 0; T.sz[i] = 1; T.rev[i] = 0; } while(Q--) { scanf("%s%d%d", op, &x, &y); if(op[0] == 'C') T.link(x, y); else if(op[0] == 'D') T.cut(x, y); else puts(T.find(x) == T.find(y) ? "Yes" : "No"); } return 0; }
dsu on tree: bzoj4756 1A 10min
# include <vector> # include <stdio.h> # include <string.h> # include <iostream> # include <algorithm> // # include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int N = 1e5 + 10; const int mod = 1e9+7; int n, a[N]; vector<int> ps; int head[N], nxt[N], to[N], tot = 0; inline void add(int u, int v) { ++tot; nxt[tot] = head[u]; head[u] = tot; to[tot] = v; } struct BIT { int n, c[N]; # define lb(x) (x & (-x)) inline void set(int _n) { n = _n; memset(c, 0, sizeof c); } inline void edt(int x, int d) { for (; x<=n; x+=lb(x)) c[x] += d; } inline int sum(int x) { int ret = 0; for (; x; x-=lb(x)) ret += c[x]; return ret; } inline int sum(int x, int y) { if(x > y) return 0; return sum(y) - sum(x-1); } # undef lb }T; int sz[N], mx[N]; inline void dfs(int x) { sz[x] = 1; mx[x] = 0; for (int i=head[x]; i; i=nxt[i]) { dfs(to[i]); sz[x] += sz[to[i]]; if(mx[x] == 0 || sz[to[i]] > sz[mx[x]]) mx[x] = to[i]; } } int ans[N], big[N]; inline void count(int x, int p) { T.edt(a[x], p); for (int i=head[x]; i; i=nxt[i]) if(!big[to[i]]) count(to[i], p); } inline void dsu(int x, bool kep = 0) { int son = mx[x]; for (int i=head[x]; i; i=nxt[i]) if(to[i] != son) dsu(to[i], 0); if(son) big[son] = 1, dsu(son, 1); count(x, 1); ans[x] = T.sum(a[x] + 1, n); if(son) big[son] = 0; if(!kep) count(x, -1); } int main() { cin >> n; T.set(n); for (int i=1; i<=n; ++i) { scanf("%d", a+i); ps.push_back(a[i]); } sort(ps.begin(), ps.end()); ps.erase(unique(ps.begin(), ps.end()), ps.end()); for (int i=1; i<=n; ++i) a[i] = lower_bound(ps.begin(), ps.end(), a[i]) - ps.begin() + 1; for (int i=2, par; i<=n; ++i) { scanf("%d", &par); add(par, i); } dfs(1); dsu(1); for (int i=1; i<=n; ++i) printf("%d ", ans[i]); return 0; }
线段树合并: bzoj4756 2A 13min
warning: 需要注意节点数量为$O(nlogn)$。
# include <vector> # include <stdio.h> # include <string.h> # include <iostream> # include <algorithm> // # include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int N = 1e5 + 10, SN = 262144 * 20 + 5; const int mod = 1e9+7; int n, a[N]; vector<int> ps; int head[N], nxt[N], to[N], tot = 0; inline void add(int u, int v) { ++tot; nxt[tot] = head[u]; head[u] = tot; to[tot] = v; } int rt[N]; struct SMT { int siz; int s[SN], ch[SN][2]; # define ls ch[x][0] # define rs ch[x][1] inline void set() { siz = 0; memset(ch, 0, sizeof ch); memset(s, 0, sizeof s); } inline void up(int x) { if(!x) return; s[x] = s[ls] + s[rs]; } inline void edt(int &x, int l, int r, int ps, int d) { if(!x) x = ++siz; if(l == r) { s[x] = 1; return; } int mid = l+r>>1; if(ps <= mid) edt(ls, l, mid, ps, d); else edt(rs, mid+1, r, ps, d); up(x); } inline int sum(int x, int l, int r, int L, int R) { if(!x || L>R) return 0; if(L <= l && r <= R) return s[x]; int mid = l+r>>1, ret = 0; if(L <= mid) ret += sum(ls, l, mid, L, R); if(R > mid) ret += sum(rs, mid+1, r, L, R); return ret; } inline int merge(int x, int y, int l, int r) { if(!x || !y) return x+y; if(l == r) { s[x] += s[y]; return x; } int mid = l+r>>1; ls = merge(ch[x][0], ch[y][0], l, mid); rs = merge(ch[x][1], ch[y][1], mid+1, r); up(x); return x; } }T; int ans[N]; inline void dfs(int x) { for (int i=head[x]; i; i=nxt[i]) { dfs(to[i]); rt[x] = T.merge(rt[x], rt[to[i]], 1, n); } ans[x] = T.sum(rt[x], 1, n, a[x] + 1, n); } int main() { cin >> n; T.set(); for (int i=1; i<=n; ++i) { scanf("%d", a+i); ps.push_back(a[i]); } sort(ps.begin(), ps.end()); ps.erase(unique(ps.begin(), ps.end()), ps.end()); for (int i=1; i<=n; ++i) a[i] = lower_bound(ps.begin(), ps.end(), a[i]) - ps.begin() + 1; for (int i=2, par; i<=n; ++i) { scanf("%d", &par); add(par, i); } for (int i=1; i<=n; ++i) T.edt(rt[i], 1, n, a[i], 1); dfs(1); for (int i=1; i<=n; ++i) printf("%d ", ans[i]); return 0; }
线段树: codevs4927 2A 8min
warning: 区间覆盖后线清空tag标记，然后再传下来的tag标记是在cov之后的，所以要先传cov再传tag
# include <stdio.h> # include <string.h> # include <iostream> # include <algorithm> // # include <bits/stdc++.h> # ifdef WIN32 # define LLD "%I64d" # else # define LLD "%lld" # endif using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int N = 1e5 + 10, SN = 262144 + 5; const int mod = 1e9+7; int n, m; ll a[N]; struct SMT { ll s[SN], mx[SN], mi[SN], tag[SN], cov[SN]; bool hc[SN]; # define ls (x<<1) # define rs (x<<1|1) inline void up(int x) { s[x] = s[ls] + s[rs]; mx[x] = max(mx[ls], mx[rs]); mi[x] = min(mi[ls], mi[rs]); } inline void pushtag(int x, int l, int r, ll tg) { tag[x] += tg; s[x] += tg*(r-l+1); mx[x] += tg, mi[x] += tg; } inline void pushcov(int x, int l, int r, ll tg) { tag[x] = 0; hc[x] = 1; cov[x] = tg; mx[x] = mi[x] = tg; s[x] = tg * (r-l+1); } inline void down(int x, int l, int r) { int mid = l+r>>1; if(hc[x]) { pushcov(ls, l, mid, cov[x]); pushcov(rs, mid+1, r, cov[x]); cov[x] = hc[x] = 0; } if(tag[x]) { pushtag(ls, l, mid, tag[x]); pushtag(rs, mid+1, r, tag[x]); tag[x] = 0; } } inline void build(int x, int l, int r) { tag[x] = cov[x] = hc[x] = 0; if(l == r) { mx[x] = mi[x] = s[x] = a[l]; return ; } int mid = l+r>>1; build(ls, l, mid); build(rs, mid+1, r); up(x); } inline void edt(int x, int l, int r, int L, int R, ll p) { if(L <= l && r <= R) { pushtag(x, l, r, p); return ; } down(x, l, r); int mid = l+r>>1; if(L <= mid) edt(ls, l, mid, L, R, p); if(R > mid) edt(rs, mid+1, r, L, R, p); up(x); } inline void cover(int x, int l, int r, int L, int R, ll p) { if(L <= l && r <= R) { pushcov(x, l, r, p); return ; } down(x, l, r); int mid = l+r>>1; if(L <= mid) cover(ls, l, mid, L, R, p); if(R > mid) cover(rs, mid+1, r, L, R, p); up(x); } inline ll sum(int x, int l, int r, int L, int R) { if(L <= l && r <= R) return s[x]; down(x, l, r); int mid = l+r>>1; ll ret = 0; if(L <= mid) ret += sum(ls, l, mid, L, R); if(R > mid) ret += sum(rs, mid+1, r, L, R); return ret; } inline ll gmax(int x, int l, int r, int L, int R) { if(L <= l && r <= R) return mx[x]; down(x, l, r); int mid = l+r>>1; if(R <= mid) return gmax(ls, l, mid, L, R); else if(L > mid) return gmax(rs, mid+1, r, L, R); else return max(gmax(ls, l, mid, L, R), gmax(rs, mid+1, r, L, R)); } inline ll gmin(int x, int l, int r, int L, int R) { if(L <= l && r <= R) return mi[x]; down(x, l, r); int mid = l+r>>1; if(R <= mid) return gmin(ls, l, mid, L, R); else if(L > mid) return gmin(rs, mid+1, r, L, R); else return min(gmin(ls, l, mid, L, R), gmin(rs, mid+1, r, L, R)); } }T; int main() { register int Q, x, y, z; register char op[23]; cin >> n >> Q; for (int i=1; i<=n; ++i) scanf(LLD, a+i); T.build(1, 1, n); while(Q--) { scanf("%s%d%d", op, &x, &y); if(op[1] == 'd') { scanf(LLD, &z); T.edt(1, 1, n, x, y, z); } else if(op[1] == 'e') { scanf(LLD, &z); T.cover(1, 1, n, x, y, z); } else if(op[1] == 'u') printf(LLD " ", T.sum(1, 1, n, x, y)); else if(op[1] == 'a') printf(LLD " ", T.gmax(1, 1, n, x, y)); else printf(LLD " ", T.gmin(1, 1, n, x, y)); } return 0; }
FFT: bzoj2179 1A 10min
# include <math.h> # include <stdio.h> # include <string.h> # include <iostream> # include <algorithm> // # include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int M = 262144 + 10; const int mod = 1e9+7; const ld pi = acos(-1.0); struct cp { ld x, y; cp () {} cp (ld x, ld y) : x(x), y(y) {} inline friend cp operator + (cp a, cp b) { return cp(a.x + b.x, a.y + b.y); } inline friend cp operator - (cp a, cp b) { return cp(a.x - b.x, a.y - b.y); } inline friend cp operator * (cp a, cp b) { return cp(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x); } }a[M], b[M]; int c[M]; namespace FFT { cp w[2][M]; int n, lst[M]; inline void init(int _n) { n = 1; while(n < _n) n <<= 1; for (int i=0; i<n; ++i) w[0][i] = cp(cos(pi * 2.0 / n * i), sin(pi * 2.0 / n * i)), w[1][i] = cp(w[0][i].x, -w[0][i].y); int len = 0; while((1 << len) < n) ++len; for (int i=0; i<n; ++i) { int t = 0; for (int j=0; j<len; ++j) if(i & (1<<j)) t |= (1<<(len-j-1)); lst[i] = t; } } inline void DFT(cp *a, int op) { cp *o = w[op]; for (int i=0; i<n; ++i) if(i < lst[i]) swap(a[i], a[lst[i]]); for (int len=2; len<=n; len<<=1) { int m = (len>>1); for (cp *p = a; p != a+n; p += len) { for (int k=0; k<m; ++k) { cp t = o[n/len*k] * p[k+m]; p[k+m] = p[k] - t; p[k] = p[k] + t; } } } if(op) for (int i=0; i<n; ++i) a[i].x /= (ld)n, a[i].y /= (ld)n; } } int n; char str[M]; int main() { cin >> n; scanf("%s", str); FFT :: init(n + n); for (int i=0; i<n; ++i) a[i] = cp(str[n-i-1] - '0', 0); scanf("%s", str); for (int i=0; i<n; ++i) b[i] = cp(str[n-i-1] - '0', 0); for (int i=n; i<FFT :: n; ++i) a[i] = b[i] = cp(0, 0); FFT :: DFT(a, 0); FFT :: DFT(b, 0); for (int i=0; i<FFT :: n; ++i) a[i] = a[i] * b[i]; FFT :: DFT(a, 1); for (int i=0; i<FFT :: n; ++i) c[i] = (int)(a[i].x + 0.5); for (int i=0; i<FFT::n; ++i) c[i+1] += c[i] / 10, c[i] %= 10; int m = FFT :: n; while(c[m] == 0) --m; while(~m) printf("%d", c[m--]); return 0; }
NTT: bzoj2179 1A 10min
important: 找原根：找到$mod-1$的所有大于1小于$mod$的因数，然后暴力枚举原根$g$，满足条件一定是不存在上述条件的一个因数$x$，使得$g^x = 1$。$998244353$的原根是$3$。
warning: 记得处处取模。
# include <math.h> # include <stdio.h> # include <string.h> # include <iostream> # include <algorithm> // # include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int M = 262144 + 10; const int mod = 998244353, G = 3; const ld pi = acos(-1.0); int a[M], b[M]; int c[M]; inline int pwr(int a, int b) { int ret = 1; while(b) { if(b&1) ret = 1ll * ret * a % mod; a = 1ll * a * a % mod; b >>= 1; } return ret; } namespace FFT { int w[2][M], n, lst[M], inv; inline void init(int _n) { n = 1; while(n < _n) n <<= 1; int g = pwr(G, (mod-1)/n), invg = pwr(g, mod-2); w[0][0] = w[1][0] = 1; for (int i=1; i<n; ++i) w[0][i] = 1ll * w[0][i-1] * g % mod, w[1][i] = 1ll * w[1][i-1] * invg % mod; int len = 0; while((1 << len) < n) ++len; for (int i=0; i<n; ++i) { int t = 0; for (int j=0; j<len; ++j) if(i & (1<<j)) t |= (1<<(len-j-1)); lst[i] = t; } inv = pwr(n, mod-2); } inline void DFT(int *a, int op) { int *o = w[op]; for (int i=0; i<n; ++i) if(i < lst[i]) swap(a[i], a[lst[i]]); for (int len=2; len<=n; len<<=1) { int m = (len>>1); for (int *p = a; p != a+n; p += len) { for (int k=0; k<m; ++k) { int t = 1ll * o[n/len*k] * p[k+m] % mod; p[k+m] = p[k] - t; if(p[k+m] < 0) p[k+m] += mod; p[k] = p[k] + t; if(p[k] >= mod) p[k] -= mod; } } } if(op) for (int i=0; i<n; ++i) a[i] = 1ll * a[i] * inv % mod; } } int n; char str[M]; int main() { cin >> n; scanf("%s", str); FFT :: init(n + n); for (int i=0; i<n; ++i) a[i] = str[n-i-1] - '0'; scanf("%s", str); for (int i=0; i<n; ++i) b[i] = str[n-i-1] - '0'; for (int i=n; i<FFT :: n; ++i) a[i] = b[i] = 0; FFT :: DFT(a, 0); FFT :: DFT(b, 0); for (int i=0; i<FFT :: n; ++i) a[i] = 1ll * a[i] * b[i] % mod; FFT :: DFT(a, 1); for (int i=0; i<FFT :: n; ++i) c[i] = a[i]; for (int i=0; i<FFT :: n; ++i) c[i+1] += c[i] / 10, c[i] %= 10; int m = FFT :: n; while(c[m] == 0) --m; while(~m) printf("%d", c[m--]); return 0; }
网络流（Dinic）: szoj334 1A 10min
warning: 记得清空队列。
# include <queue> # include <stdio.h> # include <string.h> # include <iostream> # include <algorithm> // # include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int N = 3e3 + 10, M = 4e5 + 10; const int mod = 1e9+7, inf = 1e9; int n, m, S, T; namespace MF { int head[N], nxt[M], to[M], flow[M], tot = 1; inline void add(int u, int v, int fl) { ++tot; nxt[tot] = head[u]; head[u] = tot; to[tot] = v; flow[tot] = fl; } inline void adde(int u, int v, int fl) { add(u, v, fl), add(v, u, 0); } queue<int> q; int c[N]; inline bool bfs() { for (int i=1; i<=n; ++i) c[i] = -1; while(!q.empty()) q.pop(); q.push(S); c[S] = 0; while(!q.empty()) { int top = q.front(); q.pop(); for (int i=head[top]; i; i=nxt[i]) { if(c[to[i]] != -1 || !flow[i]) continue; c[to[i]] = c[top] + 1; q.push(to[i]); if(to[i] == T) return 1; } } return 0; } int cur[N]; inline int dfs(int x, int low) { if(x == T) return low; int r = low, fl; for (int i=cur[x]; i; i=nxt[i]) { if(c[to[i]] != c[x]+1 || !flow[i]) continue; fl = dfs(to[i], min(r, flow[i])); r -= fl; flow[i] -= fl; flow[i^1] += fl; if(flow[i] > 0) cur[x] = i; if(!r) return low; } if(low == r) c[x] = -1; return low-r; } inline int main() { int res = 0; while(bfs()) { for (int i=1; i<=n; ++i) cur[i] = head[i]; res += dfs(S, inf); } return res; } } int main() { cin >> n >> m; S=1, T=n; for (int i=1, u, v, fl; i<=m; ++i) { scanf("%d%d%d", &u, &v, &fl); MF :: adde(u, v, fl); } cout << MF :: main(); return 0; }
费用流: bzoj3876 1A 10min
# include <queue> # include <stdio.h> # include <string.h> # include <iostream> # include <algorithm> // # include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int M = 3e5 + 10; const int mod = 1e9+7, inf = 1e9; int n, deg[M], S, T; namespace MCF { int head[M], nxt[M], to[M], w[M], flow[M], tot = 1; inline void add(int u, int v, int fl, int _w) { ++tot; nxt[tot] = head[u]; head[u] = tot; to[tot] = v; w[tot] = _w, flow[tot] = fl; } inline void adde(int u, int v, int fl, int _w) { add(u, v, fl, _w); add(v, u, 0, -_w); } ll d[M]; int pre[M]; bool vis[M]; queue<int> q; inline bool spfa() { for (int i=1; i<=T; ++i) vis[i] = pre[i] = 0, d[i] = 1e18; d[S] = 0; vis[S] = 1; q.push(S); while(!q.empty()) { int top = q.front(); q.pop(); vis[top] = 0; for (int i=head[top]; i; i=nxt[i]) { if(d[to[i]] > d[top] + w[i] && flow[i]) { d[to[i]] = d[top] + w[i]; pre[to[i]] = i; if(!vis[to[i]]) { vis[to[i]] = 1; q.push(to[i]); } } } } return d[T] < 1e18; } inline ll mcf() { int xm = inf; ll ans = 0; for (int i=pre[T]; i; i=pre[to[i^1]]) xm = min(xm, flow[i]); for (int i=pre[T]; i; i=pre[to[i^1]]) { flow[i] -= xm, flow[i^1] += xm; ans += 1ll * xm * w[i]; } return ans; } inline ll main() { ll ans = 0; while(spfa()) ans += mcf(); return ans; } } int main() { ll ans = 0; cin >> n; for (int i=1, t, B, T; i<=n; ++i) { scanf("%d", &t); while(t--) { scanf("%d%d", &B, &T); MCF :: adde(i, B, inf, T); deg[B] ++; deg[i] --; ans += T; } if(i != 1) MCF :: adde(i, 1, inf, 0); } S = n+1, T = n+2; for (int i=1; i<=n; ++i) { if(deg[i] > 0) MCF :: adde(S, i, deg[i], 0); if(deg[i] < 0) MCF :: adde(i, T, -deg[i], 0); } cout << MCF :: main() + ans << endl; return 0; }
========================================分割线==========================================
【有上下界网络流集合】
1. 无源汇最大流：增加S和T，对于边(a->b, [c, d])，连(a->b, d-c), (a->T, c), (S->b, c)。注意这个部分可以整合顶点连出去的所有边，汇总流量。对于S到T做最大流，如果每条S连出去的和连到T的边都流满了，说明有可行流。
2. 有源汇最大流：连(T->S, [0, inf])后就和无源汇可行流一样了。建立超级源汇SS、TT，按照无源汇最大流的方法做，判断是否有可行解。有可行流后，删除超级源汇SS、TT，从S到T做最大流，两次的和就是答案了。（第一次保证下界流满，第二次补流）。【需要注意要去掉(T->S, inf)的边】
3. 有源汇最小流：先不连(T->S, inf)，跑一遍SS到TT最大流，再连边，跑最大流，那么答案就是这条边的反向弧。
4. 最小费用可行流：按照无源汇最大流一样连，然后上费用流即可。
========================================分割线==========================================
高斯消元: bzoj1013 1A 13min（推式子推了好久）
# include <math.h> # include <stdio.h> # include <assert.h> # include <string.h> # include <iostream> # include <algorithm> // # include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int M = 5e5 + 10; const int mod = 1e9+7; const ld eps = 1e-7; inline ld getld() { static double x; scanf("%lf", &x); return (ld)x; } int n; ld z[23][23]; ld a[23][23], b[23]; inline bool iszero(ld x) { return fabs(x) < eps; } inline void gauss() { for (int i=1; i<=n; ++i) { int p = -1; for (int j=i; j<=n; ++j) if(!iszero(a[j][i])) {p = j; break;} assert(p != -1); // inf for (int j=1; j<=n; ++j) swap(a[p][j], a[i][j]); swap(b[p], b[i]); for (int j=i+1; j<=n; ++j) { ld x = a[i][i] / a[j][i]; for (int k=i; k<=n; ++k) a[j][k] = a[j][k] * x - a[i][k]; b[j] = b[j] * x - b[i]; } } for (int i=n; i; --i) { b[i] = b[i] / a[i][i]; for (int j=1; j<i; ++j) b[j] -= a[j][i] * b[i]; } } int main() { cin >> n; for (int i=1; i<=n+1; ++i) for (int j=1; j<=n; ++j) z[i][j] = getld(); for (int i=1; i<=n; ++i) { for (int j=1; j<=n; ++j) { a[i][j] = 2.0 * (z[i][j] - z[i+1][j]); b[i] = b[i] + (z[i][j] * z[i][j] - z[i+1][j] * z[i+1][j]); } } gauss(); for (int i=1; i<=n; ++i) printf("%.3lf%c", (double)b[i], i==n ? ' ' : ' '); puts(""); return 0; }
主席树：bzoj3524 1A 8min
warning: 需要注意节点数量为$O(nlogn)$。
http://www.cnblogs.com/galaxies/p/bzoj3524.html
========================================分割线==========================================
好累啊休息一下
早上抽空看了个《Going in Style》，三个老头演的真好啊qwq（逃
========================================分割线==========================================
LCA，树链剖分: bzoj3083 3A 20min（2个WA都不是模板的问题，是自己傻逼了。。）
http://www.cnblogs.com/galaxies/p/bzoj3083.html
warning: 树链剖分放在边上的话，要注意不能把lca代表的边算进去！！！
BIT区修区查: codevs1082 1A 5min
# include <stdio.h> # include <string.h> # include <iostream> # include <algorithm> // # include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int M = 5e5 + 10; const int mod = 1e9+7; struct BIT { ll c[M]; int n; # define lb(x) (x & (-x)) inline void set(int _n) { memset(c, 0, sizeof c); n = _n; } inline void edt(int x, ll d) { for (; x<=n; x+=lb(x)) c[x] += d; } inline ll sum(int x) { ll ret = 0; for (; x; x-=lb(x)) ret += c[x]; return ret; } # undef lb }; struct BIT2 { BIT a, b; inline void set(int n) { a.set(n), b.set(n); } inline void edt(int x, int y, int d) { a.edt(x, d); a.edt(y+1, -d); b.edt(x, 1ll * d * x), b.edt(y+1, -1ll * d * (y+1)); } inline ll sum(int x) { return a.sum(x) * (x+1) - b.sum(x); } inline ll sum(int x, int y) { if(x > y) return 0; return sum(y) - sum(x-1); } }T; int n; int main() { cin >> n; T.set(n); for (int i=1, t; i<=n; ++i) { scanf("%d", &t); T.edt(i, i, t); } int Q, op, l, r, d; cin >> Q; while(Q--) { scanf("%d%d%d", &op, &l, &r); if(op == 1) { scanf("%d", &d); T.edt(l, r, d); } else printf("%lld ", T.sum(l, r)); } return 0; }
线性基: bzoj2460 2A 10min（没开long long）
conclusion: （这题没用）考虑$n$个数组成的基，大小为$k$，那么每种方案都有$2^{n-k}$可以取到。
# include <stdio.h> # include <string.h> # include <iostream> # include <algorithm> // # include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int M = 5e5 + 10; const int mod = 1e9+7; int n; struct pa { ll a; int b; friend bool operator < (pa a, pa b) { return a.b > b.b; } }p[M]; int Lbase[65]; # define bit(x, i) (((x) >> (i)) & 1) int main() { ll ans = 0; cin >> n; for (int i=1; i<=n; ++i) scanf("%lld%d", &p[i].a, &p[i].b); sort(p+1, p+n+1); for (int i=1; i<=n; ++i) { ll t = p[i].a; for (int j=62; ~j; --j) { if(bit(t, j)) { if(!Lbase[j]) { Lbase[j] = t; break; } t ^= Lbase[j]; } } if(t) ans += p[i].b; } cout << ans; return 0; }
点分治: poj1741 2A 10min
warning: 如果是涉及根的统计，注意容斥的时候对其子树，需要有本来的那条边的长度！
# include <stdio.h> # include <string.h> # include <iostream> # include <algorithm> // # include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int N = 1e4 + 10, M = 2e4 + 10; const int mod = 1e9+7; # define RG register # define ST static int n, m, head[M], nxt[M], to[M], w[M], tot = 0; inline void add(int u, int v, int _w) { ++tot; nxt[tot] = head[u]; head[u] = tot; to[tot] = v; w[tot] = _w; } inline void adde(int u, int v, int _w) { add(u, v, _w), add(v, u, _w); } int ans = 0; namespace DFZ { bool vis[N]; int sz[N], mx[N]; inline void dfssz(int x, int fa = 0) { sz[x] = 1; mx[x] = 0; for (int i=head[x]; i; i=nxt[i]) { if(to[i] == fa || vis[to[i]]) continue; dfssz(to[i], x); sz[x] += sz[to[i]]; if(sz[to[i]] > mx[x]) mx[x] = sz[to[i]]; } } int mi, centre; inline void dfscentre(int x, int tp, int fa = 0) { if(sz[tp] - sz[x] > mx[x]) mx[x] = sz[tp] - sz[x]; if(mx[x] < mi) mi = mx[x], centre = x; for (int i=head[x]; i; i=nxt[i]) { if(to[i] == fa || vis[to[i]]) continue; dfscentre(to[i], tp, x); } } int c[N], cn; inline void dfsans(int x, int fa, int d) { if(d > m) return ; c[++cn] = d; for (int i=head[x]; i; i=nxt[i]) { if(to[i] == fa || vis[to[i]]) continue; dfsans(to[i], x, d+w[i]); } } inline int calc(int x, int fa, int d) { int ret = 0; cn = 0; dfsans(x, fa, d); sort(c+1, c+cn+1); for (int i=1, j=cn; i<=n; ++i) { while(j && c[i] + c[j] > m) --j; if(j < i) break; ret += (j-i); } return ret; } inline void dfs(int x) { dfssz(x); mi = n; dfscentre(x, x); x = centre; ans += calc(x, 0, 0); vis[x] = 1; for (int i=head[x]; i; i=nxt[i]) if(!vis[to[i]]) { ans -= calc(to[i], x, w[i]); dfs(to[i]); } } inline void main() { memset(vis, 0, sizeof vis); dfs(1); } } int main() { while(cin >> n >> m && (n+m)) { for (int i=1, u, v, _w; i<n; ++i) { scanf("%d%d%d", &u, &v, &_w); adde(u, v, _w); } ans = 0; DFZ :: main(); cout << ans << endl; tot = 0; fill(head+1, head+n+1, 0); } return 0; }
Splay: bzoj3224 2A 20min
warning: 需要注意每次操作都要splay下保证复杂度。
http://www.cnblogs.com/galaxies/p/bzoj3224.html
莫队: bzoj2038 1A 7min
http://www.cnblogs.com/galaxies/p/bzoj2038.html
字符串哈希: noi2016 day1t1 95pts: 1A 10min
# include <stdio.h> # include <string.h> # include <iostream> # include <algorithm> // # include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int M = 3e4 + 10; const int mod = 1e9+7; const ull HA = 20000713; int n; char s[M]; ull h[M], base[M]; inline void gh() { h[0] = 0; for (int i=1; i<=n; ++i) h[i] = h[i-1] * HA + (s[i] - 'a' + 1); } inline ull ha(int i, int j) { return h[j] - h[i-1] * base[j-i+1]; } inline void sol() { scanf("%s", s+1); n = strlen(s+1); gh(); ll ans = 0; for (int i=1; i<n; ++i) { int cnt1 = 0, cnt2 = 0; for (int j=i-1, k=i; j>=1; j-=2, --k) if(ha(j, k-1) == ha(k, i)) ++cnt1; for (int j=i+2, k=i+1; j<=n; j+=2, ++k) if(ha(i+1, k) == ha(k+1, j)) ++cnt2; // cout << i << ' ' << cnt1 << ' ' << cnt2 << endl; ans += 1ll * cnt1 * cnt2; } printf("%lld ", ans); } int main() { base[0] = 1; for (int i=1; i<=30000; ++i) base[i] = base[i-1] * HA; int T; cin >> T; while(T--) sol(); return 0; }
tarjan: szoj9 2A
warning: 注意判断是否在栈中，找环可以用并查集，找到在环上的点，顺着dfs即可。
# include <stdio.h> # include <string.h> # include <iostream> # include <algorithm> // # include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int M = 5e5 + 10; const int mod = 1e9+7; int n, m; int head[M], nxt[M], to[M], tot = 0; inline void add(int u, int v) { ++tot; nxt[tot] = head[u]; head[u] = tot; to[tot] = v; } int dfn[M], low[M], DFN = 0; bool ins[M]; int st[M], stn = 0; int belong[M], p[M], scc; inline void tarjan(int x) { dfn[x] = low[x] = ++DFN; st[++stn] = x; ins[x] = 1; for (int i=head[x]; i; i=nxt[i]) { if(!dfn[to[i]]) { tarjan(to[i]); low[x] = min(low[x], low[to[i]]); } else if(ins[to[i]]) low[x] = min(low[x], dfn[to[i]]); } if(dfn[x] == low[x]) { ++scc; int t = 0; while(t != x) { t = st[stn--]; ins[t] = 0; belong[t] = scc; } } } int main() { cin >> n >> m; for (int i=1, u, v; i<=m; ++i) { scanf("%d%d", &u, &v); add(u, v); } for (int i=1; i<=n; ++i) if(!dfn[i]) tarjan(i); for (int i=1; i<=n; ++i) p[belong[i]] ++; int ans = 0; for (int i=1; i<=scc; ++i) ans = max(ans, p[i]); cout << ans; return 0; }
FWT: 就看看就行
1. 如果是异或（xor）卷积的话：
$A_0$和$A_1$是按照$A$的最高位分成的两部分
$f(A) = (f(A_0) + f(A_1), f(A_0) - f(A_1))$
$f_T(A) = (f_T(frac{A_0 + A_1}{2}), f_T(frac{A_0 - A_1}{2}))$
正确性可以用归纳法证明。
其实只要记住正变换的式子即可，逆变换可以从正变换推导出来。
2. 如果是与（and）卷积的话
$f(A) = (f(A_0) + f(A_1), f(A_1))$
$f_T(A) = (f_T(A_0) - f_T(A_1), f_T(A_1))$
3. 如果是或（or）卷积的话
$f(A) = (f(A_0), f(A_1) + f(A_0))$
$f_T(A) = (f_T(A_0), f_T(A_1) - f_T (A_0))$
直接套FFT板子即可。
后缀自动机: hihocoder1445 1A 10min
# include <stdio.h> # include <string.h> # include <iostream> # include <algorithm> // # include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int M = 1e6 + 10; const int mod = 1e9+7; struct SAM { int ch[M + M][26], par[M + M], ml[M + M]; int rt, lst, siz; inline void set() { rt = lst = siz = 1; } inline void extend(int c) { int p = lst, cur = ++siz; ml[cur] = ml[p]+1; for (; p && !ch[p][c]; p = par[p]) ch[p][c] = cur; if(!p) par[cur] = rt; else { int q = ch[p][c]; if(ml[q] == ml[p] + 1) par[cur] = q; else { int sq = ++siz; par[sq] = par[q]; for (int i=0; i<26; ++i) ch[sq][i] = ch[q][i]; ml[sq] = ml[p] + 1; par[q] = par[cur] = sq; for (; p && ch[p][c] == q; p = par[p]) ch[p][c] = sq; } } lst = cur; } }S; char s[M]; int main() { S.set(); ll ans = 0; scanf("%s", s); for (int i=0; s[i]; ++i) S.extend(s[i] - 'a'); for (int i=2; i<=S.siz; ++i) ans += S.ml[i] - S.ml[S.par[i]]; cout << ans; return 0; }
模拟退火: 记得调参，和是否选择“可以接受更劣答案”。
KDTREE: bzoj2683 2A 一个小地方写错了。。 25min
# include <math.h> # include <stdio.h> # include <string.h> # include <iostream> # include <algorithm> // # include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int M = 5e5 + 10; const int mod = 1e9+7; inline ll read() { ll x = 0, f = 1; char ch = getchar(); while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); } while(isdigit(ch)) { x = x*10+ch-'0'; ch = getchar(); } return x*f; } int D; struct node { int mi[2], mx[2], d[2], l, r, siz; ll v, s; inline friend bool operator == (node a, node b) { return a.d[0] == b.d[0] && a.d[1] == b.d[1]; } inline friend bool operator < (node a, node b) { return a.d[D] < b.d[D]; } }; inline bool in(int x1, int y1, int x2, int y2, int xx1, int yy1, int xx2, int yy2) { return x1 <= xx1 && xx2 <= x2 && y1 <= yy1 && yy2 <= y2; } inline bool out(int x1, int y1, int x2, int y2, int xx1, int yy1, int xx2, int yy2) { return x1 > xx2 || x2 < xx1 || y1 > yy2 || y2 < yy1; } inline int cmp(int, int); const double REBUILD_FAC = 0.713, REBUILD_LOG = log(1.0 - REBUILD_FAC); node tmp; struct KDT { node T[M]; # define ls (T[x].l) # define rs (T[x].r) int siz, p[M], pn, rt; inline void set() {siz = rt = 0;} inline void up(int x) { for (int i=0; i<2; ++i) { T[x].mi[i] = T[x].mx[i] = T[x].d[i]; if(ls) T[x].mi[i] = min(T[x].mi[i], T[ls].mi[i]), T[x].mx[i] = max(T[x].mx[i], T[ls].mx[i]); if(rs) T[x].mi[i] = min(T[x].mi[i], T[rs].mi[i]), T[x].mx[i] = max(T[x].mx[i], T[rs].mx[i]); } T[x].s = T[ls].s + T[rs].s + T[x].v; T[x].siz = 1 + T[ls].siz + T[rs].siz; } inline bool ins(int &x, int d, int dep) { if(!x) { x = ++siz; for (int i=0; i<2; ++i) T[x].mi[i] = T[x].mx[i] = T[x].d[i] = tmp.d[i]; T[x].siz = 1; T[x].v = tmp.v; T[x].s = tmp.s; return dep * REBUILD_LOG > log(siz); } if(tmp == T[x]) { T[x].v += tmp.v; T[x].s += tmp.v; return 0; } int id; bool ret; if(tmp.d[d] < T[x].d[d]) ret = ins(ls, d^1, dep+1), id = ls; else ret = ins(rs, d^1, dep+1), id = rs; up(x); if(ret) { if(T[id].siz > REBUILD_FAC * T[x].siz) { x = rebuild(x, d); return 0; } return 1; } } inline ll query(int x, int x1, int y1, int x2, int y2) { if(!x) return 0; if(in(x1, y1, x2, y2, T[x].mi[0], T[x].mi[1], T[x].mx[0], T[x].mx[1])) return T[x].s; if(out(x1, y1, x2, y2, T[x].mi[0], T[x].mi[1], T[x].mx[0], T[x].mx[1])) return 0; ll ret = 0; if(in(x1, y1, x2, y2, T[x].d[0], T[x].d[1], T[x].d[0], T[x].d[1])) ret += T[x].v; ret += query(ls, x1, y1, x2, y2) + query(rs, x1, y1, x2, y2); return ret; } inline int build(int l, int r, int d) { if(l > r) return 0; int mid = l+r>>1; D = d; nth_element(p+l, p+mid, p+r+1, cmp); int x = p[mid]; ls = build(l, mid-1, d^1); rs = build(mid+1, r, d^1); up(x); return x; } inline void getnode(int x) { if(!x) return ; p[++pn] = x; getnode(ls); getnode(rs); } inline int rebuild(int x, int d) { pn = 0; getnode(x); return build(1, pn, d); } }T; inline int cmp(int a, int b) { return T.T[a] < T.T[b]; } int main() { int op, x1, y1, x2, y2, ad; ll lst = 0; scanf("%d", &op); T.set(); while(1) { scanf("%d", &op); if(op == 3) break; if(op == 1) { x1 = read() ^ lst, y1 = read() ^ lst, ad = read() ^ lst; tmp.d[0] = x1, tmp.d[1] = y1, tmp.v = tmp.s = ad; T.ins(T.rt, 0, 1); } else { x1 = read() ^ lst, y1 = read() ^ lst, x2 = read() ^ lst, y2 = read() ^ lst; printf("%lld ", T.query(T.rt, x1, y1, x2, y2)); } } return 0; }
AC自动机，fail树: bzoj3172 1A 20min
# include <queue> # include <stdio.h> # include <string.h> # include <iostream> # include <algorithm> // # include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int M = 1.6e6 + 10; const int mod = 1e9+7; int n; char t[M]; int v[M], ps[M]; vector<int> G[M]; struct ACM { int ch[M][26], fail[M], siz, isend[M]; inline void set() {siz = 0;} inline int ins(char *t) { int p = 0; for (int i=0; t[i]; ++i) { int c = t[i] - 'a'; if(!ch[p][c]) ch[p][c] = ++siz; p = ch[p][c]; v[p] ++; } return p; } queue<int> q; inline void build() { while(!q.empty()) q.pop(); for (int c=0; c<26; ++c) { int p = ch[0][c]; if(p) { fail[p] = 0; q.push(p); } } while(!q.empty()) { int top = q.front(); q.pop(); for (int c=0; c<26; ++c) { int p = ch[top][c]; if(!p) { ch[top][c] = ch[fail[top]][c]; continue; } q.push(p); int v = fail[top]; while(v && !ch[v][c]) v = fail[v]; fail[p] = ch[v][c]; } } } inline void getfail() { for (int i=1; i<=siz; ++i) G[fail[i]].push_back(i); } }S; inline void dfs(int x) { for (int i=0; i<G[x].size(); ++i) { int y = G[x][i]; dfs(y); v[x] += v[y]; } } int main() { cin >> n; S.set(); for (int i=1; i<=n; ++i) { scanf("%s", t); ps[i] = S.ins(t); } S.build(); S.getfail(); dfs(0); for (int i=1; i<=n; ++i) printf("%d ", v[ps[i]]); return 0; }
那么就不管kmp了吧……kmp能做的AC自动机都能做
剩余复习内容：
1. SA（明天晚上）
noi 加油！