upd：19.4.5 放出来了。如果明天考了我没复习到的认了。考到了复习了的还没拿到理想分的就回来谢罪（bushi
www
SDOI一轮倒计时4天啦w
所以得有个小计划吧QwQ
4.2
目标：BZOJ5407
模板：
✔最小树形图
//Love and Freedom. #include<cstdio> #include<cmath> #include<algorithm> #include<cstring> #define ll long long #define inf 20021225 #define M 10010 #define N 110 #define totsize sizeof(int)*(n+1) using namespace std; struct edge{int u,v,w;}e[M]; int id[N],mn[N],pre[N],vis[N]; int n,m; int zlal(int rt) { int res=0; while(1) { for(int i=1;i<=n;i++) mn[i]=inf; for(int i=1;i<=m;i++) if(e[i].u!=e[i].v && e[i].w<mn[e[i].v]) mn[e[i].v]=e[i].w,pre[e[i].v]=e[i].u; for(int i=1;i<=n;i++) if(i!=rt) if(mn[i]==inf) return -1; int tn=0,u,v; memset(id,0,totsize); memset(vis,0,totsize); mn[rt]=0; for(int i=1;i<=n;i++) { res+=mn[i]; v=i; while(v!=rt&&!id[v]&&vis[v]!=i) vis[v]=i,v=pre[v]; if(v!=rt&&!id[v]) { ++tn; for(u=pre[v];u!=v;u=pre[u]) id[u]=tn; id[v]=tn; } } if(!tn) return res; for(int i=1;i<=n;i++) if(!id[i]) id[i]=++tn; for(int i=1;i<=m;i++) { int v=e[i].v; e[i].u=id[e[i].u]; e[i].v=id[e[i].v]; if(e[i].u!=e[i].v) e[i].w-=mn[v]; } n=tn; rt=id[rt]; } } int main() { int r; scanf("%d%d%d",&n,&m,&r); for(int i=1;i<=m;i++) scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w); printf("%d ",zlal(r)); return 0; }
✔主席树
//Love and Freedom. #include<cstdio> #include<cmath> #include<algorithm> #include<cstring> #define ll long long #define inf 20021225 #define N 200010 using namespace std; int read() { int s=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();} while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar(); return s; } struct node{int ls,rs,s;}; struct SGT { node t[N*40]; int poi; void pushup(int x){t[x].s=t[t[x].ls].s+t[t[x].rs].s;} void build(int &x,int l,int r) { x=++poi; if(l==r) return; int mid=l+r>>1; build(t[x].ls,l,mid); build(t[x].rs,mid+1,r); } void modify(int &x,int l,int r,int lt,int d) { x=++poi; t[x]=t[lt]; t[x].s++; if(l==r) return; int mid=l+r>>1; if(d<=mid) modify(t[x].ls,l,mid,t[lt].ls,d); else modify(t[x].rs,mid+1,r,t[lt].rs,d); } int query(int x,int y,int l,int r,int d) { if(l==r) return l; int s=t[t[y].ls].s-t[t[x].ls].s,mid=l+r>>1; if(s>=d) return query(t[x].ls,t[y].ls,l,mid,d); else return query(t[x].rs,t[y].rs,mid+1,r,d-s); } }sgt; int a[N],rt[N],n,m,h[N]; int main() { n=read(); m=read(); for(int i=1;i<=n;i++) a[i]=read(),h[i]=a[i]; sort(h+1,h+n+1); int nn=unique(h+1,h+n+1)-h-1; sgt.build(rt[0],1,nn); for(int i=1;i<=n;i++) a[i]=lower_bound(h+1,h+nn+1,a[i])-h,sgt.modify(rt[i],1,nn,rt[i-1],a[i]); for(int i=1;i<=m;i++) { int l,r,k; l=read(); r=read(); k=read(); printf("%d ",h[sgt.query(rt[l-1],rt[r],1,nn,k)]); } return 0; }
（菜死了 11min才写完还手贱wa了一发QAQ）
✔Tarjan 割点/缩点
✔FFT（快读神tm加速1/4）
//Love and Freedom. #include<cstdio> #include<cmath> #include<algorithm> #include<cstring> #define ll long long #define inf 20021225 #define db double #define N 4000100 using namespace std; const db pi=acos(-1.0); int read() { char ch=getchar(); int s=0; while(ch>'9'||ch<'0') ch=getchar(); while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar(); return s; } struct cpx { db x,y; cpx(){} cpx(db xx,db yy){x=xx,y=yy;} }; cpx operator+(cpx a,cpx b){return cpx(a.x+b.x,a.y+b.y);} cpx operator-(cpx a,cpx b){return cpx(a.x-b.x,a.y-b.y);} cpx operator*(cpx a,cpx b){return cpx(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);} int rev[N]; int pre(int n) { int lim=1,l=0; while(lim<n) lim<<=1,l++; for(int i=0;i<lim;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1)); return lim; } void fft(cpx *a,int lim,bool f) { for(int i=0;i<lim;i++) if(rev[i]>i) swap(a[i],a[rev[i]]); for(int k=2,mid=1;k<=lim;mid<<=1,k<<=1) { cpx Wn=cpx(cos(pi/mid),sin(pi/mid)); if(f) Wn.y=-Wn.y; for(int i=0;i<lim;i+=k) { cpx w=cpx(1.0,0.0); for(int j=0;j<mid;j++,w=w*Wn) { cpx x=a[i+j],y=w*a[i+j+mid]; a[i+j]=x+y,a[i+j+mid]=x-y; } } } } cpx f[N],g[N]; int main() { int n,m; n=read(); m=read(); n++;m++; for(int i=0;i<n;i++) f[i].x=read(); for(int i=0;i<m;i++) g[i].x=read(); int lim=pre(n+m); fft(f,lim,0); fft(g,lim,0); for(int i=0;i<lim;i++) f[i]=f[i]*g[i]; fft(f,lim,1); for(int i=0;i<n+m-1;i++) printf("%d ",(int)(f[i].x/lim+0.5)); return 0; }
✔NTT
✔多项式求逆
✔多项式ln
✔多项式exp
✔多项式除法
✔多项式开根
//Love and Freedom. #include<cstdio> #include<cmath> #include<algorithm> #include<cstring> #define ll long long #define inf 20021225 #define N 400100 #define mdn 998244353 #define G 3 using namespace std; int read() { char ch=getchar(); int s=0; while(ch>'9'||ch<'0') ch=getchar(); while(ch<='9'&&ch>='0') s=s*10+ch-'0',ch=getchar(); return s; } int rev[N]; int f[N]; int ksm(int bs,int mi) { int ans=1; while(mi) { if(mi&1) ans=(ll)ans*bs%mdn; bs=(ll)bs*bs%mdn; mi>>=1; } return ans; } int inv; int pre(int n) { int lim=1,l=0; while(lim<n) lim<<=1,l++; for(int i=0;i<lim;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1)); inv=ksm(lim,mdn-2); return lim; } void NTT(int *a,int lim,int f) { for(int i=0;i<lim;i++) if(rev[i]<i) swap(a[rev[i]],a[i]); for(int k=2,mid=1;k<=lim;mid<<=1,k<<=1) { int Wn=ksm(G,(mdn-1)/k); if(f) Wn=ksm(Wn,mdn-2); for(int i=0,w=1;i<lim;i+=k,w=1) for(int j=0;j<mid;j++,w=(ll)w*Wn%mdn) { int x=a[i+j],y=(ll)w*a[i+j+mid]%mdn; a[i+j]=x+y>=mdn?x+y-mdn:x+y; a[i+j+mid]=x-y<0?x-y+mdn:x-y; } } if(f) for(int i=0;i<lim;i++) a[i]=(ll)a[i]*inv%mdn; } /** poly_inv 求 f*g=1(% x^n) 因此 g=1(% x^[n/2]) 已知 f*h=1(% x^[n/2]) 可得 g-h=0(% x^[n/2]) 平方 g^2+h^2-2g*h=0(% x^n) 左乘f得到 g=2fh-fh^2(% x^n) 递归求解 */ struct poly_inv { int g[N],h[N]; void inv(int *a,int n) { if(n==1){g[0]=ksm(a[0],mdn-2);return;} int mid=(n+1)>>1; inv(a,mid); int lim=pre(n<<1); for(int i=0;i<n;i++) h[i]=a[i]; for(int i=n;i<lim;i++) h[i]=0; NTT(h,lim,0); NTT(g,lim,0); for(int i=0;i<lim;i++) g[i]=(2ll-(ll)g[i]*h[i]%mdn+mdn)%mdn*g[i]%mdn; NTT(g,lim,1); for(int i=n;i<lim;i++) g[i]=0; } void print(int n) { for(int i=0;i<n;i++) printf("%d ",g[i]); } }INV; /** poly_ln 求g=ln(f) 对复合函数g(f)求导 (ln(f))'=ln'(f)f'=(1/f)*f' 即 g'=1/f*f' 积分回去就行了 */ struct poly_ln { int g[N],h[N]; void ln(int *a,int n) { INV.inv(a,n); for(int i=0;i<n;i++) g[i]=INV.g[i]; for(int i=1;i<n;i++) h[i-1]=(ll)f[i]*i%mdn; int lim=pre(n<<1); NTT(g,lim,0); NTT(h,lim,0); for(int i=0;i<lim;i++) h[i]=(ll)g[i]*h[i]%mdn; NTT(h,lim,1); for(int i=0;i<n;i++) g[i+1]=(ll)h[i]*ksm(i+1,mdn-2)%mdn; g[0]=0; } void print(int n) { for(int i=0;i<n;i++) printf("%d ",g[i]); } }LN; /** poly_exp 求 g=e^f 根据牛顿迭代+泰勒展开 可以得到 h(f)=0(% x^n) 展开一次【开方 h(f0)=0(% x^n/2) h(f0)+h'(f0)(f-f0)=0(% x^n) 移项 f=f0-h(f0)/h'(f0) 由于我们求的g=e^f 取h为lng-f=0(% x^n) 所以带进去就是 g=g0-(lng0-f)/lng0=g0*(1-lng0+f) */ struct poly_exp { int s[N],g[N],tmp[N]; void exp(int *a,int n) { if(n==1){s[0]=1;return;} int mid=n+1>>1; exp(a,mid); for(int i=0;i<(n<<1);i++) g[i]=0; LN.ln(g,n); for(int i=0;i<n;i++) g[i]=LN.g[i],tmp[i]=a[i]; int lim=pre(n<<1); NTT(g,lim,0);NTT(tmp,lim,0);NTT(s,lim,0); for(int i=0;i<lim;i++) s[i]=((ll)tmp[i]-g[i]+1+mdn)%mdn*s[i]%mdn; NTT(s,lim,1); for(int i=n;i<lim;i++) g[i]=tmp[i]=0; } void print(int n) { for(int i=0;i<n;i++) printf("%d ",s[i]); } }EXP; /** poly_div 通过系数翻转 f n次 g m次 f=g*h+r fR=x^nf(1/x) 所以全部翻转再左乘x^n 可以得到 x^nfR=x^mgR*x^(n-m)hR+x^(n-m+1)*x^(m-1)rR 其实就是 fR=gR*hR+x^(n-m+1)rR 于是我们可以在%x^(n-m+1)意义下先求逆得到hR 然后翻回去求r */ int main() { int n; n=read(); for(int i=0;i<n;i++) f[i]=read(); EXP.exp(f,n); EXP.print(n); return 0; }
（写了前三个 exp懒得调了发现还要清前面的ln啥的就扔在那看看吧QAQ）（多项式除法没写QAQ）
✔左偏树
//Love and Freedom. #include<cstdio> #include<cmath> #include<algorithm> #include<cstring> #define ll long long #define inf 20021225 #define N 100010 using namespace std; int read() { int f=1,s=0; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar(); return f*s; } struct node{int val,fa,son[2],dis; bool tag;}t[N]; int find(int x){return t[x].fa^x?t[x].fa=find(t[x].fa):x;} int merge(int x,int y) { if(!x||!y) return x|y; if(t[y].val<t[x].val||(t[y].val==t[x].val&&y<x)) swap(x,y); t[x].son[1]=merge(t[x].son[1],y); t[t[x].son[1]].fa=t[t[x].son[0]].fa=x; t[x].fa=x; if(t[t[x].son[1]].dis>t[t[x].son[0]].dis) swap(t[x].son[0],t[x].son[1]); t[x].dis=t[t[x].son[1]].dis+1; return x; } void pop(int x) { t[x].tag=1; printf("%d ",t[x].val); t[t[x].son[1]].fa=t[x].son[1]; t[t[x].son[0]].fa=t[x].son[0]; t[x].fa=merge(t[x].son[1],t[x].son[0]); } int n,m; int main() { n=read(); m=read(); int opt,x,y; for(int i=1;i<=n;i++) t[i].val=read(),t[i].fa=i; for(int i=1;i<=m;i++) { opt=read(); x=read(); if(opt==1) { y=read(); if(t[x].tag||t[y].tag) continue; x=find(x); y=find(y); if(x==y) continue; merge(x,y); } else { if(t[x].tag){printf("-1 "); continue;} x=find(x); pop(x); } } return 0; }
✔KD树
✔圆方树
✔FWT
/** OR FWT(A)=(FWT(A0),FWT(A0+A1)) IFWT(A)=(IFWT(A0),IFWT(A1-A0)) */ /** AND FWT(A)=(FWT(A0+A1),FWT(A1)) IFWT(A)=(IFWT(A0-A1),IFWT(A1)) */ /** XOR FWT(A)=(FWT(A0+A1),FWT(A0-A1)) IFWT(A)=(IFWT(A0+A1)/2,IFWT(A0-A1)/2) */ //Love and Freedom. #include<cstdio> #include<cmath> #include<algorithm> #include<cstring> #define ll long long #define inf 20021225 #define N 2000100 #define mdn 998244353 using namespace std; int read() { int s=0,f=1; char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();} while(ch<='9'&&ch>='0') s=s*10+ch-'0',ch=getchar(); return (s*f%mdn+mdn)%mdn; } int a[N],b[N],c[N]; int inv=499122177; void fwt(int *a,int top,int type) { for(int k=2,mid=1;k<=top;k<<=1,mid<<=1) for(int i=0;i<top;i+=k) for(int j=0;j<mid;j++) { int x=a[i+j],y=a[i+j+mid]; if(type==1) a[i+j]=x,a[i+j+mid]=(x+y)%mdn; else if(type==2) a[i+j]=(x+y)%mdn,a[i+j+mid]=y; else if(type==3) a[i+j]=(x+y)%mdn,a[i+j+mid]=(x-y+mdn)%mdn; else if(type==-1) a[i+j]=x,a[i+j+mid]=(y-x+mdn)%mdn; else if(type==-2) a[i+j]=(x-y+mdn)%mdn,a[i+j+mid]=y; else if(type==-3) a[i+j]=(ll)(x+y)%mdn*inv%mdn,a[i+mid+j]=((ll)(x-y)%mdn*inv%mdn+mdn)%mdn; } } int top; void query(int type) { fwt(a,top,type); fwt(b,top,type); for(int i=0;i<top;i++) c[i]=(ll)a[i]*b[i]%mdn; fwt(c,top,-type); fwt(a,top,-type); fwt(b,top,-type); for(int i=0;i<top;i++) printf("%d ",c[i]); printf(" "); } int main() { int n; scanf("%d",&n); top=1<<n; for(int i=0;i<top;i++) scanf("%d",&a[i]); for(int i=0;i<top;i++) scanf("%d",&b[i]); query(1); query(2); query(3); return 0; }
✔0/1分数规划
✔后缀自动机
//Love and Freedom. #include<cstdio> #include<cmath> #include<algorithm> #include<cstring> #define ll long long #define inf 20021225 #define N 1000100 using namespace std; struct node{int ch[26],fa,len,sz;}t[N*4]; struct edge{int to,lt;}e[N*4]; char ch[N]; int in[N*4],cnt,lt,rt,poi,ans,n; void add(int x,int y){e[++cnt].to=y;e[cnt].lt=in[x];in[x]=cnt;} int id(char c){return c-'a';} void insert(int c) { int p=lt,np=lt=++poi; t[np].len=t[p].len+1; t[np].sz=1; for(;p&&!t[p].ch[c];p=t[p].fa) t[p].ch[c]=np; if(!p){t[np].fa=rt; return;} int q=t[p].ch[c]; if(t[q].len==t[p].len+1){t[np].fa=q; return;} int nq=++poi; t[nq].fa=t[q].fa; t[q].fa=t[np].fa=nq; memcpy(t[nq].ch,t[q].ch,sizeof(t[nq].ch)); t[nq].len=t[p].len+1; for(;p&&t[p].ch[c]==q;p=t[p].fa) t[p].ch[c]=nq; } void build() { for(int i=2;i<=poi;i++) add(t[i].fa,i); } void dfs(int x) { for(int i=in[x];i;i=e[i].lt) dfs(e[i].to),t[x].sz+=t[e[i].to].sz; if(t[x].sz!=1) ans=max(ans,t[x].len*t[x].sz); } int main() { scanf("%s",ch+1); n=strlen(ch+1); rt=lt=poi=1; for(int i=1;i<=n;i++) insert(id(ch[i])); build(); dfs(1); printf("%d ",ans); return 0; }
✔线性规划
//Love and Freedom. #include<cstdio> #include<cmath> #include<algorithm> #include<cstring> #include<ctime> #define db long double #define ll long long #define inf 20021225 #define eps 1e-10 using namespace std; db a[51][51],ans[51]; int id[51],n,m; void pivot(int x,int y) { swap(id[n+x],id[y]); db w=1.0/a[x][y]; a[x][y]=1.0; for(int i=0;i<=n;i++) a[x][i]*=w; for(int i=0;i<=m;i++) { if(i==x || abs(a[i][y])<eps) continue; w=a[i][y]; a[i][y]=0.0; for(int j=0;j<=n;j++) a[i][j]-=a[x][j]*w; } } bool prework() { while(1) { int x=0,y=0; for(int i=1;i<=m;i++) if(a[i][0]<-eps && (!x||rand()&1)) x=i; if(!x) return true; for(int i=1;i<=n;i++) if(a[x][i]<-eps && (!y||rand()&1)) y=i; if(!y){printf("Infeasible ");return false;} pivot(x,y); } } bool simplex() { while(1) { int x=0,y=0; db mn=1e15; for(int i=1;i<=n;i++) if(a[0][i]>eps){y=i;break;} if(!y) return true; for(int i=1;i<=m;i++) if(a[i][y]>eps && a[i][0]/a[i][y]<mn) x=i,mn=a[i][0]/a[i][y]; if(!x){printf("Unbounded ");return false;} pivot(x,y); } } int main() { srand(time(0)); int t; scanf("%d%d%d",&n,&m,&t); for(int i=1;i<=n;i++) scanf("%Lf",&a[0][i]),id[i]=i; for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) scanf("%Lf",&a[i][j]); scanf("%Lf",&a[i][0]); } if(prework()&&simplex()) { printf("%.8Lf ",-a[0][0]); if(t) { for(int i=1;i<=m;i++) ans[id[n+i]]=a[i][0]; for(int i=1;i<=n;i++) printf("%.8Lf ",ans[i]); } } return 0; }
回文自动机
✔半平面交
✔旋转卡壳
✔欧拉回路
✔整体二分
✔可持久并查集
✔kruskal重构树
✔点分治/动态点分治
✔凸优化/斜率优化
上下界网络流
✔差分约束
✔LCT
//Love and Freedom. #include<cstdio> #include<cmath> #include<algorithm> #include<cstring> #define ll long long #define inf 20021225 #define N 300100 #define ls(x) t[x].son[0] #define rs(x) t[x].son[1] #define fa(x) t[x].fa #define isroot(x) (rs(fa(x))!=x && ls(fa(x))!=x) using namespace std; struct node{int fa,son[2],val,sum; bool rev;}t[N]; void pushup(int x){t[x].sum=t[ls(x)].sum^t[rs(x)].sum^t[x].val;} void pushdown(int x) { if(t[x].rev) { if(ls(x)) t[ls(x)].rev^=1; if(rs(x)) t[rs(x)].rev^=1; swap(ls(x),rs(x)); t[x].rev=0; } } void rotate(int x) { if(!x || isroot(x)) return; int f=fa(x),gf=fa(f); int k=rs(f)==x,p=k^1; if(!isroot(f)) t[gf].son[rs(gf)==f]=x; t[x].fa=gf; t[f].fa=x; if(t[x].son[p]) t[t[x].son[p]].fa=f; t[f].son[k]=t[x].son[p]; t[x].son[p]=f; pushup(f); pushup(x); } void push(int x){if(!isroot(x)) push(fa(x));pushdown(x);} void splay(int x) { push(x); while(!isroot(x)) { int f=fa(x),gf=fa(f); if(!isroot(f)) (rs(gf)==f)^(rs(f)==x)?rotate(x):rotate(f); rotate(x); } } void access(int x) { int y=0; do { splay(x); t[x].son[1]=y; pushup(x); y=x; x=t[x].fa; }while(x); } void makeroot(int x) { access(x); splay(x); t[x].rev=1; } int findroot(int x) { access(x); splay(x); while(ls(x)) x=ls(x); return x; } void link(int x,int y) { makeroot(x); if(findroot(y)==x) return; t[x].fa=y; } void cut(int x,int y) { makeroot(x); if(findroot(y)==x && t[x].fa==y && !t[x].son[1]) { t[x].fa=t[y].son[0]=0; pushup(y); } } void modify(int x,int val) { splay(x); t[x].val=val; pushup(x); } int query(int x,int y) { makeroot(x);access(y);splay(y);return t[y].sum; } int main() { int n,m,i,x,y,opt; scanf("%d%d",&n,&m); for(i=1;i<=n;i++) scanf("%d",&t[i].val); for(i=1;i<=m;i++) { scanf("%d%d%d",&opt,&x,&y); if(opt==0) printf("%d ",query(x,y)); if(opt==1) link(x,y); if(opt==2) cut(x,y); if(opt==3) modify(x,y); } return 0; }
莫比乌斯反演
积性函数相关
✔Polya
线段树合并
✔插头dp
✔虚树
✔CRT/EXCRT
//Love and Freedom. #include<cstdio> #include<cmath> #include<algorithm> #include<cstring> #define ll long long #define ldb long double #define inf 20021225 #define N 100010 using namespace std; ll ksc(ll a,ll b,ll md) { ll c=(a*b-(ll)((ldb)a/md*b+0.5)*md); return c<0?c+md:c; } ll exgcd(ll a,ll b,ll &x,ll &y) { if(!b){x=1;y=0;return a;} ll g=exgcd(b,a%b,x,y);// printf("QAQ"); ll k=x; x=y; y=k-a/b*y; return g; } ll p[N],w[N]; int n; ll excrt() { ll x=w[1],P=p[1],t,s; for(int i=2;i<=n;i++) { ll k=((w[i]-x)%p[i]+p[i])%p[i]; ll g=exgcd(P,p[i],t,s); ll bs=p[i]/g; if(k%g!=0) return -1; t=ksc(t,k/g,bs); x+=t*P; P*=bs; x=(x%P+P)%P; } return x; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%lld%lld",&p[i],&w[i]); printf("%lld ",excrt()); return 0; }