一.图论
1.最短路（dij+zkw线段树）
#include<iostream> #include<cstdio> #define INF (1<<30) int N,n; int c[131072+5],id[262145+5],d[100010]; int h[101000],nxt[201000],to[201000],cost[201000],K=0; void ins(int u,int v,int c){nxt[++K]=h[u];h[u]=K;to[K]=v;cost[K]=c;} void init() { N=1; while(N<n)N<<=1; for(int i=1;i<=N;i++)c[i]=INF; for(int i=N;i<N+N;i++) id[i]=i-N+1; for(int i=N-1;i>=1;i--)id[i]=id[i<<1]; } void add(int x,int p) { c[x]=p; for(int i=(x+N-1)>>1;i;i>>=1) id[i]=c[id[i<<1]]<=c[id[i<<1|1]]?id[i<<1]:id[i<<1|1]; } void dij(int S) { for(int i=1;i<=n;i++)d[i]=INF; add(S,0);d[S]=0; for(int T=1;T<=n;T++) { int u=id[1]; add(u,INF); for(int i=h[u];i;i=nxt[i]) { if(d[to[i]]>d[u]+cost[i]) { d[to[i]]=d[u]+cost[i]; add(to[i],d[to[i]]); } } } } int main() { int m,S;scanf("%d%d%d",&n,&m,&S); for(int i=1;i<=m;i++) { int a,b,c;scanf("%d%d%d",&a,&b,&c); ins(a,b,c); } init(); dij(S); for(int i=1;i<=n;i++)printf("%d ",d[i]); return 0; }
2.点双连通分量（圆方树）
#include <cstdio> #include <iostream> #include <cstring> #define MN 401000 int h[MN], nxt[2 * MN], to[2 * MN], K = 0; int st[MN], top = 0, tt = 0; int v[MN], U[MN], V[MN], tot = 0; int dfn[MN], low[MN];int id, n, m;void ins(int u, int v) {nxt[++K] = h[u]; h[u] = K; to[K] = v;} void tarjan(int x, int fa) { v[x] = -1; dfn[x] = low[x] = ++tt; st[++top] = x; for(int i = h[x]; i; i = nxt[i]) { if(to[i] == fa) continue; if(!dfn[to[i]]) { tarjan(to[i], x); low[x] = std::min(low[x], low[to[i]]); if(low[to[i]] >= dfn[x]) { ++id; do { ++tot; U[tot] = st[top]; V[tot] = id + n; v[id + n]++; } while(st[top--] != to[i]); ++tot; U[tot] = x; V[tot] = id + n; v[id + n]++; } } else low[x] = std::min(low[x], dfn[to[i]]); } }
3.强连通分量
void tarjan(int x) { dfs[x]=low[x]=++dfn;st[++top]=x;inq[x]=1; for(int i=h[x];i;i=nxt[i]) { if(!dfs[to[i]]) { tarjan(to[i]); low[x]=min(low[x],low[to[i]]); } else if(inq[to[i]])low[x]=min(low[x],dfs[to[i]]); } if(low[x]==dfs[x]) { ++tot; do{ id[st[top]]=tot;inq[st[top]]=0;V[tot].push_back(st[top]); }while(st[top--]!=x); } }
4.2-SAT
void tarjan(int x) { dfs[x]=low[x]=++dfn;st[++top]=x;inq[x]=1; for(int i=h[x];i;i=nxt[i]) { if(!dfs[to[i]]) { tarjan(to[i]); low[x]=min(low[x],low[to[i]]); } else if(inq[to[i]])low[x]=min(low[x],dfs[to[i]]); } if(low[x]==dfs[x]) { ++tot; do{ id[st[top]]=tot;inq[st[top]]=0;V[tot].push_back(st[top]); }while(st[top--]!=x); } } int two_SAT(int n,int m) { memset(dfs,0,sizeof(dfs)); memset(low,0,sizeof(low)); memset(ans,-1,sizeof(ans)); memset(in,0,sizeof(in)); hh=tt=0;tot=0;dfn=0; for(int i=1;i<=200000;i++)V[i].clear(); for(int i=1;i<=n;i++)if(!dfs[i])tarjan(i); for(int i=1;i<=n;i+=2) { if(id[i]==id[i+1])return -1; p[id[i]]=id[i+1];p[id[i+1]]=id[i]; } memset(h,0,sizeof(h));K=0; for(int i=1;i<=m;i++) { if(id[u[i]]==id[v[i]])continue; ins(id[v[i]],id[u[i]]);in[id[u[i]]]++; } for(int i=1;i<=tot;i++) if(in[i]==0)q[tt++]=i; while(hh<tt) { int x=q[hh++]; if(ans[x]!=-1)continue; ans[x]=1;ans[p[x]]=0; for(int i=h[x];i;i=nxt[i]) if(--in[to[i]]==0)q[tt++]=to[i]; } for(int i=1;i<=tot;i++) { if(ans[i]==1) { int siz=V[i].size(); for(int j=0;j<siz;j++) { int t=V[i][j]; Ans[++len]=t; } } } return 1; }
5.dinic
#include<cstdio> #include<iostream> #include<cstring> int h[10100],nxt[201000],to[201000],cap[201000],K=1; int level[10100],iter[10100],hh,tt,q[10100]; void ins(int u,int v,int c){nxt[++K]=h[u];h[u]=K;to[K]=v;cap[K]=c;} void insw(int u,int v,int c){ins(u,v,c);ins(v,u,0);} int bfs(int S,int T) { hh=tt=0;q[tt++]=S;memset(level,0,sizeof(level));level[S]=1; while(hh<tt) { int u=q[hh++];iter[u]=h[u]; for(int i=h[u];i;i=nxt[i]) { if(cap[i]&&!level[to[i]]) { level[to[i]]=level[u]+1; q[tt++]=to[i]; } } } return level[T]; } int dfs(int u,int f,int T) { if(u==T)return f; int used=0,w; for(int &i=iter[u];i;i=nxt[i]) { if(cap[i]&&level[to[i]]==level[u]+1) { w=dfs(to[i],std::min(f-used,cap[i]),T); if(w) { cap[i]-=w;cap[i^1]+=w;used+=w;if(used==f)return f; } } } return used; } int dinic(int S,int T) { int f=0; while(bfs(S,T))f+=dfs(S,1e9,T); return f; } int main() { int n,m,S,T;scanf("%d%d%d%d",&n,&m,&S,&T); for(int i=1;i<=m;i++) { int a,b,c;scanf("%d%d%d",&a,&b,&c); insw(a,b,c); } printf("%d ",dinic(S,T));return 0; }
6.01bfs
int bfs(int x,int mid) { memset(d,-1,sizeof(d)); H=2000000;T=1999999; q[++T]=x;d[x]=0; while(H<=T) { int u=q[H++]; for(int i=h[u];i;i=nxt[i]) { int c=(cost[i]<=mid?0:1); if(d[to[i]]==-1||d[to[i]]>d[u]+c) { d[to[i]]=d[u]+c; if(c==0)q[--H]=to[i]; else q[++T]=to[i]; } } } if(d[n]==-1)return -1; else if(d[n]>k)return 0; else return 1; }
二.树
1.长链剖分（求x的d级祖先）
vector<int> vu[101000],vd[101000],v; int len[101000],top[101000],dep[101000],dd[101000],son[101000],fa[101000]; int h[101000],to[201000],nxt[201000],K=0; int st[101000][20],c[101000],n; void ins(int u,int v){nxt[++K]=h[u];h[u]=K;to[K]=v;} void dfs1(int x,int f,int d) { fa[x]=f;dep[x]=d;dd[x]=0; for(int i=h[x];i;i=nxt[i]) { if(to[i]==f)continue; dfs1(to[i],x,d+1);dd[x]=max(dd[x],dd[to[i]]); if(dd[to[i]]>dd[son[x]])son[x]=to[i]; } dd[x]++; } void dfs2(int x,int t) { top[x]=t;len[t]++;vd[t].push_back(x); if(son[x])dfs2(son[x],t); for(int i=h[x];i;i=nxt[i]) { if(to[i]==fa[x]||to[i]==son[x])continue; dfs2(to[i],to[i]);v.push_back(to[i]); } } void init() { int siz=v.size(); for(int j=0;j<siz;j++) { int x=fa[v[j]]; for(int i=1;i<=len[v[j]];i++) { if(x==0)break; vu[v[j]].push_back(x); x=fa[x]; } } for(int i=1;i<=n;i++)st[i][0]=fa[i]; for(int j=1;j<=18;j++) { for(int i=1;i<=n;i++) { st[i][j]=st[st[i][j-1]][j-1]; } } for(int i=1;i<=n;i++) { for(int j=0;j<=18;j++)if((i>>j)&1)c[i]=j; } } int query(int x,int d) { if(d==0)return x; x=st[x][c[d]]; if(x==0)return 0; d-=1<<c[d]; if(dep[x]-d>=dep[top[x]]) { return vd[top[x]][dep[x]-dep[top[x]]-d]; } else { if(vu[top[x]].size()<=d-(dep[x]-dep[top[x]])-1)return 0; return vu[top[x]][d-(dep[x]-dep[top[x]])-1]; } }
2.O(nlogn) - O(1) 求lca
void dfs(int x, int fa) { dep2[x] = dep2[fa] + 1; a[++tot] = x; for(int i = h[x]; i; i = nxt[i]) { if(to[i] == fa) continue; dfs(to[i], x); a[++tot] = x; } } void init() { for(int i = 1; i <= tot; i++) st[i][0] = a[i]; for(int i = 1; i <= 18; i++) for(int j = 1; j + (1 << i) - 1 <= tot; j++) { if(dep2[st[j][i - 1]] < dep2[st[j + (1 << (i - 1))][i - 1]]) st[j][i] = st[j][i - 1]; else st[j][i] = st[j + (1 << (i - 1))][i - 1]; } for(int i = 1; i <= tot; i++) if(!fi[a[i]]) fi[a[i]] = i; for(int i = 2; i <= tot; i <<= 1) b[i] = b[i / 2] + 1; for(int i = 1; i <= tot; i++) if(!b[i]) b[i] = b[i - 1]; } int lca(int u, int v) { int l = fi[u], r = fi[v]; if(l > r) std::swap(l, r); int len = r - l + 1; if(dep2[st[l][b[len]]] < dep2[st[r - (1 << b[len]) + 1][b[len]]]) return st[l][b[len]]; return st[r - (1 << b[len]) + 1][b[len]]; }
3.dfs手写栈
typedef pair<int, bool> P; void dfs() { T = 0; st[++T] = P(1, 0); //do something with node 1 while(T) { P p = st[T--]; int x = p.first; if(p.second) { //当第x个点的子树都被遍历完后要做的事 } else { st[++T] = P(x, 1); //当第x个点的子树还未被遍历时要做的事 } } }
举例：以下是链剖的第一个dfs的递归版转非递归版
void dfs1(int x, int f, int d) { fa[x] = f; siz[x] = 1; dep[x] = d; for(int i = h[x]; i; i = nxt[i]) { if(to[i] == f) continue; dfs1(to[i], x, d + 1); siz[x] += siz[to[i]]; if(siz[to[i]] > siz[son[x]]) son[x] = to[i]; } }
void dfs1() { T = 0; st[++T] = P(1, 0); fa[1] = 0; dep[1] = 1; siz[1] = 1;while(T) { P p = st[T--]; int x = p.first; if(p.second) { for(int i = h[x]; i; i = nxt[i]) { if(to[i] == fa[x]) continue; siz[x] += siz[to[i]]; if(siz[son[x]] < siz[to[i]]) son[x] = to[i]; } } else { st[++T] = P(x, 1); for(int i = h[x]; i; i = nxt[i]) { if(to[i] == fa[x]) continue; fa[to[i]] = x; siz[to[i]] = 1; dep[to[i]] = dep[x] + 1; st[++T] = P(to[i], 0); } } } }
4.dsu on tree（以子树众数举例）
#include <cstdio> #include <algorithm> int cnt[101000], ans; int Ans[101000], son[101000], siz[101000]; int b[101000], a[101000]; int h[101000], nxt[201000], to[201000], K = 0; void ins(int u, int v) {nxt[++K] = h[u]; h[u] = K; to[K] = v;} void rw(int id) { if(cnt[id] == cnt[ans] && id < ans || cnt[id] > cnt[ans]) ans = id; } void _dfs(int x, int fa) { siz[x] = 1; for(int i = h[x]; i; i = nxt[i]) { if(to[i] == fa) continue; _dfs(to[i], x); siz[x] += siz[to[i]]; if(siz[to[i]] > siz[son[x]]) son[x] = to[i]; } } void del(int x, int fa, int s, int v) { cnt[a[x]] += v; rw(a[x]); for(int i = h[x]; i; i = nxt[i]) { if(to[i] == fa) continue; if(s && to[i] == son[x]) continue; del(to[i], x, 0, v); } } void dfs(int x, int fa, int s) { for(int i = h[x]; i; i = nxt[i]) { if(to[i] == fa || to[i] == son[x]) continue; dfs(to[i], x, 0); } if(son[x]) dfs(son[x], x, 1); ans = Ans[son[x]]; del(x, fa, 1, 1); Ans[x] = ans; if(!s) del(x, fa, 0, -1); } int main() { freopen("violet.in", "r", stdin); freopen("violet.out", "w", stdout); int n; scanf("%d", &n); for(int i = 1; i <= n; i++) { scanf("%d", &b[i]); a[i] = b[i]; } std::sort(b + 1, b + n + 1); int N = std::unique(b + 1, b + n + 1) - b - 1; for(int i = 1; i <= n; i++) { a[i] = std::lower_bound(b + 1, b + N + 1, a[i]) - b; } for(int i = 1; i < n; i++) { int u, v; scanf("%d%d", &u, &v); ins(u, v); ins(v, u); } _dfs(1, 0); dfs(1, 0, 1); int q; scanf("%d", &q); for(int i = 1; i <= q; i++) { int x; scanf("%d", &x); printf("%d ", b[Ans[x]]); } return 0; }
二.数论
1.数论分块(求∑g[i]*[a/i]*[b/i] )
for(int l=1;l<=n;l=r+1) { r=min(a/(a/l),b/(b/l)); ans+=1ll*(g[r]-g[l-1])*(a/l)*(b/l); }
2.线性筛
void init() { for(int i=2;i<=50000;i++) { if(!is[i])pri[++tot]=i; for(int j=1;j<=tot&&i*pri[j]<=50000;j++) { is[i*pri[j]]=1; if(i%pri[j]==0){break;} } } }
3.扩展中国剩余定理（ExCRT）
ll ExCRT() { for(int i=2;i<=n;i++) { ll a1=c[i-1],a2=c[i],p1=m[i-1],p2=m[i]; ll t=gcd(p1,p2),x,y; if((a2-a1)%t!=0)return -1; exgcd(p1,p2,x,y); x=(x%p2+p2)%p2; m[i]=p1/t*p2; ll k1=mul(x,(a2-a1)/gcd(p1,p2),m[i]); c[i]=(mul(k1,p1,m[i])+a1)%m[i]; } return c[n]; }
4.矩阵求逆
#include<iostream> #include<cstdio> #define mod 1000000007 using namespace std; long long A[410][410],B[410][410]; int n; long long qpow(long long x,int p) { int ans=1; while(p) { if(p&1)ans=ans*x%mod; x=x*x%mod;p>>=1; } return ans; } bool gauss() { for(int i=1;i<=n;i++)B[i][i]=1; for(int i=1;i<=n;i++) { for(int j=i;j<=n;j++) { if(A[j][i]!=0) { for(int k=1;k<=n;k++)swap(A[i][k],A[j][k]); for(int k=1;k<=n;k++)swap(B[i][k],B[j][k]); break; } } if(A[i][i]==0)return 0; int I=qpow(A[i][i],mod-2); for(int j=i;j<=n;j++)A[i][j]=A[i][j]*I%mod; for(int j=1;j<=n;j++)B[i][j]=B[i][j]*I%mod; for(int k=1;k<=n;k++) { if(k==i)continue; if(A[k][i])for(int j=i+1;j<=n;j++){if(!A[i][j])continue;A[k][j]-=A[k][i]*A[i][j]%mod;A[k][j]<0?A[k][j]+=mod:233;} if(A[k][i])for(int j=1;j<=n;j++){if(!B[i][j])continue;B[k][j]-=A[k][i]*B[i][j]%mod;B[k][j]<0?B[k][j]+=mod:233;} A[k][i]=0; } } return 1; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)scanf("%d",&A[i][j]); if(!gauss())return 0*puts("No Solution"); for(int i=1;i<=n;i++,puts("")) for(int j=1;j<=n;j++)printf("%lld ",B[i][j]); return 0; }
三.字符串
1.KMP
void init(char *s) { nxt[0]=-1;int len=strlen(s); int i=0,j=-1; while(i<len) { if(j==-1||s[i]==s[j]) { i++;j++;nxt[i]=j; } else { j=nxt[j]; } } } int kmp(char *s,char *t,int l) { int lens=strlen(s),lent=strlen(t);int r=lent-1; int j=0,i=0; while(i<lens) { if(j==-1||s[i]==t[j]) { i++;j++; } else { j=nxt[j]; } if(j==lent)return i; } return -1; }
2.回文自动机
int len[301000],cnt[301000],fail[301000],nxt[301000][30],tot=1; char s[301000]; void build() { s[0]='@';fail[0]=1;len[0]=0;len[1]=-1; int n=strlen(s),lst=0; for(int i=1;i<n;i++) { int k=lst; while(s[i-len[k]-1]!=s[i]) k=fail[k]; if(!nxt[k][s[i]-'a']) { nxt[k][s[i]-'a']=++tot; len[tot]=len[k]+2; int cur=k; if(cur==1)fail[tot]=0; else { cur=fail[cur]; while(s[i-len[cur]-1]!=s[i])cur=fail[cur]; fail[tot]=nxt[cur][s[i]-'a']; } } lst=nxt[k][s[i]-'a']; cnt[lst]++; } for(int i=tot;i>=2;i--)cnt[fail[i]]+=cnt[i]; }
3.字符串hash
#define base 83 #define mod 998244353 long long get_hash(int l, int r) { return ( p[r] - mi[r - l + 1] * p[l - 1] % mod + mod ) % mod; } void init() { for(int i = 1; i <= n; i++) p[j][i] = ( p[i - 1] * base + c[i] - 'a' ) % mod; mi[0] = 1; for(int i = 1; i <= n; i++) mi[i] = mi[i - 1] * base % mod; }
常用字符串hash质数：
1e18级别：999999999999999989 （16个9 + 89）
1e17级别：99999999999999997
1e9级别：998244853 （出题人一般卡998244353）
1e8级别：99999989 （6个9 + 89）
1e7级别：9875321 （这个很好记）
4.manacher
char s[1010000]; int p[1010000]; void manacher() { int mx = -1, id = 0; int len = strlen(s); for(int i = 0; i < len; i++) { if(i <= mx) { int j = id - (i - id); if(i + p[j] < mx) {p[i] = p[j]; continue;} } int l = mx - i + 1; while(i + l < len && i - l >= 0 && s[i + l] == s[i - l]) l++; p[i] = l - 1; mx = i + l - 1; id = i; } }
五.其它
1.set维护下凸壳（支持二分斜率）
typedef long long ll; struct xxx { ll x, y; double k; xxx(){} xxx(ll a, ll b, double c) {x = a; y = b; k = c;} }; typedef std::set<xxx>::iterator IT; std::set<xxx> st; int Q; bool operator < (xxx a, xxx b) {return Q ? a.k < b.k : a.x < b.x;} xxx operator - (xxx a, xxx b) {return xxx(a.x - b.x, a.y - b.y, 0);} ll operator / (xxx a, xxx b) {return a.x * b.y - a.y * b.x;} void add(xxx a) { IT it, it2, it3; it = st.lower_bound(a); if(it != st.end() && it -> x == a.x) { if(it -> y > a.y) st.erase(it); else return; } st.insert(a); it = st.lower_bound(a); if(it != st.begin()) { it--; it2 = it; it++; it++; it3 = it; it--; if(it3 != st.end()) if((*it - *it2) / (*it3 - *it) <= 0) { st.erase(a); return; } } while(1) { if(it != st.begin()) it--, it2 = it; else break; if(it != st.begin()) it--, it3 = it; else break; it++; it++; if((*it2 - *it3) / (*it - *it2) <= 0) st.erase(it2); else break; } it = st.lower_bound(a); while(1) { it++; if(it != st.end()) it2 = it; else break; it++; if(it != st.end()) it3 = it; else break; it--; it--; if((*it2 - *it) / (*it3 - *it2) <= 0) st.erase(it2); else break; } double k1 = 0, k2 = 0; it = st.lower_bound(a); it++; it3 = it; it--; if(it3 == st.end()) k2 = 1e18; else k2 = 1.0 * (it3 -> y - it -> y) / (it3 -> x - it -> x); if(it != st.begin()) { it--; it3 = it; it++; k1 = 1.0 * (it3 -> y - it -> y) / (it3 -> x - it -> x); xxx v = xxx(it3 -> x, it3 -> y, k1); st.erase(it3); st.insert(v); } st.erase(a); a.k = k2; st.insert(a); } xxx query(double k) { Q = 1; xxx v = xxx(0, 0, k); IT it = st.lower_bound(v); Q = 0; return *it; }