马上就要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 + ;
const int mod = 1e9+; struct LCT {
int ch[M][], fa[M], sz[M]; bool rev[M];
# define ls ch[x][]
# define rs ch[x][]
inline void up(int x) {
if(!x) return ;
sz[x] = + sz[ls] + sz[rs];
}
inline void pushrev(int x) {
if(!x) return ;
rev[x] ^= ;
swap(ch[x][], ch[x][]);
}
inline void down(int x) {
if(!x) return ;
if(rev[x]) {
pushrev(ls);
pushrev(rs);
rev[x] = ;
}
}
# undef ls
# undef rs
inline bool isrt(int x) {
return ch[fa[x]][] != x && ch[fa[x]][] != x;
}
inline void rotate(int x) {
int y = fa[x], z = fa[y], ls = ch[y][] == x, rs = ls^;
if(!isrt(y)) ch[z][ch[z][] == 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 = , 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][] == y) ^ (ch[y][] == x)) rotate(x);
else rotate(y);
}
rotate(x);
}
}
inline int access(int x) {
int t = ;
for (; x; t=x, x=fa[x]) {
splay(x);
ch[x][] = 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][]) x = ch[x][];
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][] = fa[x] = ; up(y);
}
}T; int n, Q, x, y; int main() {
static char op[];
cin >> n >> Q;
for (int i=; i<=n; ++i) {
T.ch[i][] = T.ch[i][] = T.fa[i] = ;
T.sz[i] = ; T.rev[i] = ;
}
while(Q--) {
scanf("%s%d%d", op, &x, &y);
if(op[] == 'C') T.link(x, y);
else if(op[] == 'D') T.cut(x, y);
else puts(T.find(x) == T.find(y) ? "Yes" : "No");
}
return ;
}
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 + ;
const int mod = 1e9+; int n, a[N];
vector<int> ps;
int head[N], nxt[N], to[N], tot = ;
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, , 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 = ;
for (; x; x-=lb(x)) ret += c[x];
return ret;
}
inline int sum(int x, int y) {
if(x > y) return ;
return sum(y) - sum(x-);
}
# undef lb
}T; int sz[N], mx[N];
inline void dfs(int x) {
sz[x] = ; mx[x] = ;
for (int i=head[x]; i; i=nxt[i]) {
dfs(to[i]);
sz[x] += sz[to[i]];
if(mx[x] == || 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 = ) {
int son = mx[x];
for (int i=head[x]; i; i=nxt[i])
if(to[i] != son) dsu(to[i], );
if(son) big[son] = , dsu(son, );
count(x, );
ans[x] = T.sum(a[x] + , n);
if(son) big[son] = ;
if(!kep) count(x, -);
} int main() {
cin >> n; T.set(n);
for (int i=; 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=; i<=n; ++i) a[i] = lower_bound(ps.begin(), ps.end(), a[i]) - ps.begin() + ;
for (int i=, par; i<=n; ++i) {
scanf("%d", &par);
add(par, i);
}
dfs();
dsu();
for (int i=; i<=n; ++i) printf("%d\n", ans[i]);
return ;
}
线段树合并: 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 + , SN = * + ;
const int mod = 1e9+; int n, a[N];
vector<int> ps;
int head[N], nxt[N], to[N], tot = ;
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][];
# define ls ch[x][]
# define rs ch[x][]
inline void set() {
siz = ;
memset(ch, , sizeof ch);
memset(s, , 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] = ;
return;
}
int mid = l+r>>;
if(ps <= mid) edt(ls, l, mid, ps, d);
else edt(rs, mid+, r, ps, d);
up(x);
}
inline int sum(int x, int l, int r, int L, int R) {
if(!x || L>R) return ;
if(L <= l && r <= R) return s[x];
int mid = l+r>>, ret = ;
if(L <= mid) ret += sum(ls, l, mid, L, R);
if(R > mid) ret += sum(rs, mid+, 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>>;
ls = merge(ch[x][], ch[y][], l, mid);
rs = merge(ch[x][], ch[y][], mid+, 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]], , n);
}
ans[x] = T.sum(rt[x], , n, a[x] + , n);
} int main() {
cin >> n; T.set();
for (int i=; 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=; i<=n; ++i) a[i] = lower_bound(ps.begin(), ps.end(), a[i]) - ps.begin() + ;
for (int i=, par; i<=n; ++i) {
scanf("%d", &par);
add(par, i);
}
for (int i=; i<=n; ++i) T.edt(rt[i], , n, a[i], ); dfs(); for (int i=; i<=n; ++i) printf("%d\n", ans[i]);
return ;
}
线段树: 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 + , SN = + ;
const int mod = 1e9+; 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<<)
# define rs (x<<|)
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+);
mx[x] += tg, mi[x] += tg;
}
inline void pushcov(int x, int l, int r, ll tg) {
tag[x] = ; hc[x] = ; cov[x] = tg;
mx[x] = mi[x] = tg; s[x] = tg * (r-l+);
}
inline void down(int x, int l, int r) {
int mid = l+r>>;
if(hc[x]) {
pushcov(ls, l, mid, cov[x]);
pushcov(rs, mid+, r, cov[x]);
cov[x] = hc[x] = ;
}
if(tag[x]) {
pushtag(ls, l, mid, tag[x]);
pushtag(rs, mid+, r, tag[x]);
tag[x] = ;
}
}
inline void build(int x, int l, int r) {
tag[x] = cov[x] = hc[x] = ;
if(l == r) {
mx[x] = mi[x] = s[x] = a[l];
return ;
}
int mid = l+r>>;
build(ls, l, mid); build(rs, mid+, 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>>;
if(L <= mid) edt(ls, l, mid, L, R, p);
if(R > mid) edt(rs, mid+, 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>>;
if(L <= mid) cover(ls, l, mid, L, R, p);
if(R > mid) cover(rs, mid+, 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>>; ll ret = ;
if(L <= mid) ret += sum(ls, l, mid, L, R);
if(R > mid) ret += sum(rs, mid+, 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>>;
if(R <= mid) return gmax(ls, l, mid, L, R);
else if(L > mid) return gmax(rs, mid+, r, L, R);
else return max(gmax(ls, l, mid, L, R), gmax(rs, mid+, 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>>;
if(R <= mid) return gmin(ls, l, mid, L, R);
else if(L > mid) return gmin(rs, mid+, r, L, R);
else return min(gmin(ls, l, mid, L, R), gmin(rs, mid+, r, L, R));
}
}T; int main() {
register int Q, x, y, z;
register char op[];
cin >> n >> Q;
for (int i=; i<=n; ++i) scanf(LLD, a+i);
T.build(, , n);
while(Q--) {
scanf("%s%d%d", op, &x, &y);
if(op[] == 'd') {
scanf(LLD, &z);
T.edt(, , n, x, y, z);
}
else if(op[] == 'e') {
scanf(LLD, &z);
T.cover(, , n, x, y, z);
}
else if(op[] == 'u') printf(LLD "\n", T.sum(, , n, x, y));
else if(op[] == 'a') printf(LLD "\n", T.gmax(, , n, x, y));
else printf(LLD "\n", T.gmin(, , n, x, y));
}
return ;
}
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 = + ;
const int mod = 1e9+;
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[][M]; int n, lst[M];
inline void init(int _n) {
n = ;
while(n < _n) n <<= ;
for (int i=; i<n; ++i) w[][i] = cp(cos(pi * 2.0 / n * i), sin(pi * 2.0 / n * i)), w[][i] = cp(w[][i].x, -w[][i].y);
int len = ;
while(( << len) < n) ++len;
for (int i=; i<n; ++i) {
int t = ;
for (int j=; j<len; ++j) if(i & (<<j)) t |= (<<(len-j-));
lst[i] = t;
}
} inline void DFT(cp *a, int op) {
cp *o = w[op];
for (int i=; i<n; ++i) if(i < lst[i]) swap(a[i], a[lst[i]]);
for (int len=; len<=n; len<<=) {
int m = (len>>);
for (cp *p = a; p != a+n; p += len) {
for (int k=; 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=; 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=; i<n; ++i) a[i] = cp(str[n-i-] - '', );
scanf("%s", str);
for (int i=; i<n; ++i) b[i] = cp(str[n-i-] - '', );
for (int i=n; i<FFT :: n; ++i) a[i] = b[i] = cp(, );
FFT :: DFT(a, ); FFT :: DFT(b, );
for (int i=; i<FFT :: n; ++i) a[i] = a[i] * b[i];
FFT :: DFT(a, );
for (int i=; i<FFT :: n; ++i) c[i] = (int)(a[i].x + 0.5);
for (int i=; i<FFT::n; ++i) c[i+] += c[i] / , c[i] %= ;
int m = FFT :: n;
while(c[m] == ) --m;
while(~m) printf("%d", c[m--]);
return ;
}
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 = + ;
const int mod = , G = ;
const ld pi = acos(-1.0); int a[M], b[M]; int c[M]; inline int pwr(int a, int b) {
int ret = ;
while(b) {
if(b&) ret = 1ll * ret * a % mod;
a = 1ll * a * a % mod;
b >>= ;
}
return ret;
} namespace FFT {
int w[][M], n, lst[M], inv;
inline void init(int _n) {
n = ;
while(n < _n) n <<= ;
int g = pwr(G, (mod-)/n), invg = pwr(g, mod-);
w[][] = w[][] = ;
for (int i=; i<n; ++i) w[][i] = 1ll * w[][i-] * g % mod, w[][i] = 1ll * w[][i-] * invg % mod;
int len = ;
while(( << len) < n) ++len;
for (int i=; i<n; ++i) {
int t = ;
for (int j=; j<len; ++j) if(i & (<<j)) t |= (<<(len-j-));
lst[i] = t;
}
inv = pwr(n, mod-);
} inline void DFT(int *a, int op) {
int *o = w[op];
for (int i=; i<n; ++i) if(i < lst[i]) swap(a[i], a[lst[i]]);
for (int len=; len<=n; len<<=) {
int m = (len>>);
for (int *p = a; p != a+n; p += len) {
for (int k=; k<m; ++k) {
int t = 1ll * o[n/len*k] * p[k+m] % mod;
p[k+m] = p[k] - t;
if(p[k+m] < ) p[k+m] += mod;
p[k] = p[k] + t;
if(p[k] >= mod) p[k] -= mod;
}
}
}
if(op) for (int i=; 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=; i<n; ++i) a[i] = str[n-i-] - '';
scanf("%s", str);
for (int i=; i<n; ++i) b[i] = str[n-i-] - '';
for (int i=n; i<FFT :: n; ++i) a[i] = b[i] = ;
FFT :: DFT(a, ); FFT :: DFT(b, );
for (int i=; i<FFT :: n; ++i) a[i] = 1ll * a[i] * b[i] % mod;
FFT :: DFT(a, );
for (int i=; i<FFT :: n; ++i) c[i] = a[i];
for (int i=; i<FFT :: n; ++i) c[i+] += c[i] / , c[i] %= ;
int m = FFT :: n;
while(c[m] == ) --m;
while(~m) printf("%d", c[m--]);
return ;
}
网络流（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 + , M = 4e5 + ;
const int mod = 1e9+, inf = 1e9; int n, m, S, T;
namespace MF {
int head[N], nxt[M], to[M], flow[M], tot = ;
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, );
}
queue<int> q;
int c[N];
inline bool bfs() {
for (int i=; i<=n; ++i) c[i] = -;
while(!q.empty()) q.pop();
q.push(S); c[S] = ;
while(!q.empty()) {
int top = q.front(); q.pop();
for (int i=head[top]; i; i=nxt[i]) {
if(c[to[i]] != - || !flow[i]) continue;
c[to[i]] = c[top] + ;
q.push(to[i]);
if(to[i] == T) return ;
}
}
return ;
} 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]+ || !flow[i]) continue;
fl = dfs(to[i], min(r, flow[i]));
r -= fl; flow[i] -= fl; flow[i^] += fl;
if(flow[i] > ) cur[x] = i;
if(!r) return low;
}
if(low == r) c[x] = -;
return low-r;
} inline int main() {
int res = ;
while(bfs()) {
for (int i=; i<=n; ++i) cur[i] = head[i];
res += dfs(S, inf);
}
return res;
}
} int main() {
cin >> n >> m; S=, T=n;
for (int i=, u, v, fl; i<=m; ++i) {
scanf("%d%d%d", &u, &v, &fl);
MF :: adde(u, v, fl);
}
cout << MF :: main();
return ;
}
费用流: 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 + ;
const int mod = 1e9+, inf = 1e9; int n, deg[M], S, T; namespace MCF {
int head[M], nxt[M], to[M], w[M], flow[M], tot = ;
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, , -_w);
}
ll d[M]; int pre[M]; bool vis[M];
queue<int> q;
inline bool spfa() {
for (int i=; i<=T; ++i) vis[i] = pre[i] = , d[i] = 1e18;
d[S] = ; vis[S] = ; q.push(S);
while(!q.empty()) {
int top = q.front(); q.pop(); vis[top] = ;
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]] = ;
q.push(to[i]);
}
}
}
}
return d[T] < 1e18;
}
inline ll mcf() {
int xm = inf; ll ans = ;
for (int i=pre[T]; i; i=pre[to[i^]]) xm = min(xm, flow[i]);
for (int i=pre[T]; i; i=pre[to[i^]]) {
flow[i] -= xm, flow[i^] += xm;
ans += 1ll * xm * w[i];
}
return ans;
}
inline ll main() {
ll ans = ;
while(spfa()) ans += mcf();
return ans;
}
} int main() {
ll ans = ;
cin >> n;
for (int i=, 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 != ) MCF :: adde(i, , inf, );
}
S = n+, T = n+;
for (int i=; i<=n; ++i) {
if(deg[i] > ) MCF :: adde(S, i, deg[i], );
if(deg[i] < ) MCF :: adde(i, T, -deg[i], );
}
cout << MCF :: main() + ans << endl;
return ;
}
========================================分割线==========================================
【有上下界网络流集合】
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 + ;
const int mod = 1e9+;
const ld eps = 1e-; inline ld getld() {
static double x;
scanf("%lf", &x);
return (ld)x;
} int n;
ld z[][];
ld a[][], b[]; inline bool iszero(ld x) {
return fabs(x) < eps;
} inline void gauss() {
for (int i=; i<=n; ++i) {
int p = -;
for (int j=i; j<=n; ++j) if(!iszero(a[j][i])) {p = j; break;}
assert(p != -); // inf
for (int j=; j<=n; ++j) swap(a[p][j], a[i][j]);
swap(b[p], b[i]);
for (int j=i+; 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=; j<i; ++j) b[j] -= a[j][i] * b[i];
}
} int main() {
cin >> n;
for (int i=; i<=n+; ++i)
for (int j=; j<=n; ++j) z[i][j] = getld();
for (int i=; i<=n; ++i) {
for (int j=; j<=n; ++j) {
a[i][j] = 2.0 * (z[i][j] - z[i+][j]);
b[i] = b[i] + (z[i][j] * z[i][j] - z[i+][j] * z[i+][j]);
}
}
gauss();
for (int i=; i<=n; ++i) printf("%.3lf%c", (double)b[i], i==n ? '\n' : ' ');
puts("");
return ;
}
主席树：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 + ;
const int mod = 1e9+; struct BIT {
ll c[M]; int n;
# define lb(x) (x & (-x))
inline void set(int _n) {
memset(c, , 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 = ;
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+, -d);
b.edt(x, 1ll * d * x), b.edt(y+, -1ll * d * (y+));
}
inline ll sum(int x) {
return a.sum(x) * (x+) - b.sum(x);
}
inline ll sum(int x, int y) {
if(x > y) return ;
return sum(y) - sum(x-);
}
}T; int n; int main() {
cin >> n; T.set(n);
for (int i=, 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 == ) {
scanf("%d", &d);
T.edt(l, r, d);
} else printf("%lld\n", T.sum(l, r));
}
return ;
}
线性基: 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 + ;
const int mod = 1e9+; int n;
struct pa {
ll a; int b;
friend bool operator < (pa a, pa b) {
return a.b > b.b;
}
}p[M];
int Lbase[]; # define bit(x, i) (((x) >> (i)) & ) int main() {
ll ans = ;
cin >> n;
for (int i=; i<=n; ++i) scanf("%lld%d", &p[i].a, &p[i].b);
sort(p+, p+n+);
for (int i=; i<=n; ++i) {
ll t = p[i].a;
for (int j=; ~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 ;
}
点分治: 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 + , M = 2e4 + ;
const int mod = 1e9+; # define RG register
# define ST static int n, m, head[M], nxt[M], to[M], w[M], tot = ;
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 = ;
namespace DFZ {
bool vis[N];
int sz[N], mx[N]; inline void dfssz(int x, int fa = ) {
sz[x] = ; mx[x] = ;
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 = ) {
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 = ;
cn = ;
dfsans(x, fa, d);
sort(c+, c+cn+);
for (int i=, 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, , );
vis[x] = ;
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, , sizeof vis);
dfs();
}
} int main() {
while(cin >> n >> m && (n+m)) {
for (int i=, u, v, _w; i<n; ++i) {
scanf("%d%d%d", &u, &v, &_w);
adde(u, v, _w);
}
ans = ;
DFZ :: main();
cout << ans << endl;
tot = ;
fill(head+, head+n+, );
}
return ;
}
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 + ;
const int mod = 1e9+;
const ull HA = ; int n;
char s[M];
ull h[M], base[M]; inline void gh() {
h[] = ;
for (int i=; i<=n; ++i) h[i] = h[i-] * HA + (s[i] - 'a' + );
} inline ull ha(int i, int j) {
return h[j] - h[i-] * base[j-i+];
} inline void sol() {
scanf("%s", s+); n = strlen(s+);
gh();
ll ans = ;
for (int i=; i<n; ++i) {
int cnt1 = , cnt2 = ;
for (int j=i-, k=i; j>=; j-=, --k)
if(ha(j, k-) == ha(k, i)) ++cnt1;
for (int j=i+, k=i+; j<=n; j+=, ++k)
if(ha(i+, k) == ha(k+, j)) ++cnt2;
// cout << i << ' ' << cnt1 << ' ' << cnt2 << endl;
ans += 1ll * cnt1 * cnt2;
}
printf("%lld\n", ans);
} int main() {
base[] = ;
for (int i=; i<=; ++i) base[i] = base[i-] * HA;
int T; cin >> T;
while(T--) sol();
return ;
}
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 + ;
const int mod = 1e9+; int n, m;
int head[M], nxt[M], to[M], tot = ; inline void add(int u, int v) {
++tot; nxt[tot] = head[u]; head[u] = tot; to[tot] = v;
} int dfn[M], low[M], DFN = ;
bool ins[M]; int st[M], stn = ;
int belong[M], p[M], scc; inline void tarjan(int x) {
dfn[x] = low[x] = ++DFN; st[++stn] = x; ins[x] = ;
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 = ;
while(t != x) {
t = st[stn--];
ins[t] = ; belong[t] = scc;
}
}
} int main() {
cin >> n >> m;
for (int i=, u, v; i<=m; ++i) {
scanf("%d%d", &u, &v);
add(u, v);
}
for (int i=; i<=n; ++i) if(!dfn[i]) tarjan(i);
for (int i=; i<=n; ++i) p[belong[i]] ++;
int ans = ;
for (int i=; i<=scc; ++i) ans = max(ans, p[i]);
cout << ans;
return ;
}
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 + ;
const int mod = 1e9+; struct SAM {
int ch[M + M][], par[M + M], ml[M + M];
int rt, lst, siz;
inline void set() {
rt = lst = siz = ;
}
inline void extend(int c) {
int p = lst, cur = ++siz; ml[cur] = ml[p]+;
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] + ) par[cur] = q;
else {
int sq = ++siz; par[sq] = par[q];
for (int i=; i<; ++i) ch[sq][i] = ch[q][i];
ml[sq] = ml[p] + ;
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 = ;
scanf("%s", s);
for (int i=; s[i]; ++i) S.extend(s[i] - 'a');
for (int i=; i<=S.siz; ++i)
ans += S.ml[i] - S.ml[S.par[i]]; cout << ans;
return ;
}
模拟退火: 记得调参，和是否选择“可以接受更劣答案”。
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 + ;
const int mod = 1e9+; inline ll read() {
ll x = , f = ; char ch = getchar();
while(!isdigit(ch)) {
if(ch == '-') f = -;
ch = getchar();
}
while(isdigit(ch)) {
x = x*+ch-'';
ch = getchar();
}
return x*f;
} int D;
struct node {
int mi[], mx[], d[], l, r, siz;
ll v, s;
inline friend bool operator == (node a, node b) {
return a.d[] == b.d[] && a.d[] == b.d[];
}
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 = ;}
inline void up(int x) {
for (int i=; i<; ++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 = + T[ls].siz + T[rs].siz;
}
inline bool ins(int &x, int d, int dep) {
if(!x) {
x = ++siz;
for (int i=; i<; ++i)
T[x].mi[i] = T[x].mx[i] = T[x].d[i] = tmp.d[i];
T[x].siz = ; 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 ;
}
int id; bool ret;
if(tmp.d[d] < T[x].d[d]) ret = ins(ls, d^, dep+), id = ls;
else ret = ins(rs, d^, dep+), id = rs;
up(x);
if(ret) {
if(T[id].siz > REBUILD_FAC * T[x].siz) {
x = rebuild(x, d);
return ;
}
return ;
}
} inline ll query(int x, int x1, int y1, int x2, int y2) {
if(!x) return ;
if(in(x1, y1, x2, y2, T[x].mi[], T[x].mi[], T[x].mx[], T[x].mx[])) return T[x].s;
if(out(x1, y1, x2, y2, T[x].mi[], T[x].mi[], T[x].mx[], T[x].mx[])) return ;
ll ret = ;
if(in(x1, y1, x2, y2, T[x].d[], T[x].d[], T[x].d[], T[x].d[])) 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 ;
int mid = l+r>>; D = d;
nth_element(p+l, p+mid, p+r+, cmp);
int x = p[mid];
ls = build(l, mid-, d^);
rs = build(mid+, r, d^);
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 = ; getnode(x);
return build(, 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 = ;
scanf("%d", &op); T.set();
while() {
scanf("%d", &op);
if(op == ) break;
if(op == ) {
x1 = read() ^ lst, y1 = read() ^ lst, ad = read() ^ lst;
tmp.d[] = x1, tmp.d[] = y1, tmp.v = tmp.s = ad;
T.ins(T.rt, , );
} else {
x1 = read() ^ lst, y1 = read() ^ lst, x2 = read() ^ lst, y2 = read() ^ lst;
printf("%lld\n", T.query(T.rt, x1, y1, x2, y2));
}
}
return ;
}
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 + ;
const int mod = 1e9+; int n; char t[M];
int v[M], ps[M]; vector<int> G[M];
struct ACM {
int ch[M][], fail[M], siz, isend[M];
inline void set() {siz = ;}
inline int ins(char *t) {
int p = ;
for (int i=; 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=; c<; ++c) {
int p = ch[][c];
if(p) {
fail[p] = ;
q.push(p);
}
}
while(!q.empty()) {
int top = q.front(); q.pop();
for (int c=; c<; ++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=; i<=siz; ++i)
G[fail[i]].push_back(i);
}
}S; inline void dfs(int x) {
for (int i=; 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=; i<=n; ++i) {
scanf("%s", t);
ps[i] = S.ins(t);
}
S.build();
S.getfail();
dfs();
for (int i=; i<=n; ++i) printf("%d\n", v[ps[i]]);
return ;
}
那么就不管kmp了吧……kmp能做的AC自动机都能做
剩余复习内容：
1. SA（明天晚上）
noi 加油！