对拍（详见注释）
1 #include<stdio.h> 2 #include<windows.h> 3 using namespace std; 4 int main() 5 { 6 int n=100000; 7 while(n--) 8 { 9 system("data.exe>data.in");//运行data.exe导入data.in 10 system("myCode.exe<data.in>myCode.out");//用data.in的数据运行待测程序导入out文件 11 system("correctCode.exe<data.in>correctCode.out");//用data.in的数据运行对拍程序导入out文件 12 if(system("fc myCode.out correctCode.out")) break;//比较输出结果 13 } 14 system("pause"); 15 return 0; 16 }
负环
（spfa中一个点被松弛（放入队列中）n次，一定有负环）
1 #include<bits/stdc++.h> 2 #define I inline 3 using namespace std; 4 using namespace std; 5 const int N=2010; 6 const int M=3010; 7 I int read() 8 { 9 int x=0,f=1;char ch=getchar(); 10 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 11 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 12 return x*f; 13 } 14 15 struct node 16 { 17 int nxt,to,dis; 18 }g[M<<1]; 19 int head[N],tot; 20 int T,n,m; 21 int dist[N],cnt[N]; 22 bool vis[N]; 23 24 I void addedge(int u,int v,int dis) 25 { 26 g[++tot].nxt=head[u]; 27 g[tot].to=v; 28 g[tot].dis=dis; 29 head[u]=tot; 30 } 31 32 I bool spfa() 33 { 34 memset(vis,0,sizeof(vis)); 35 memset(cnt,0,sizeof(cnt)); 36 memset(dist,127,sizeof(dist)); 37 queue<int>q;q.push(1);vis[1]=0;dist[1]=0; 38 while(q.size()) 39 { 40 int u=q.front();q.pop();vis[u]=0; 41 for(int i=head[u];i;i=g[i].nxt) 42 { 43 int v=g[i].to; 44 if(dist[v]>dist[u]+g[i].dis) 45 { 46 cnt[v]=cnt[u]+1; 47 if(cnt[v]>n)return 1; 48 dist[v]=dist[u]+g[i].dis; 49 if(!vis[v])vis[v]=1,q.push(v); 50 } 51 } 52 } 53 return 0; 54 } 55 56 57 int main() 58 { 59 T=read(); 60 while(T--) 61 { 62 n=read();m=read();tot=0; 63 memset(head,0,sizeof(head)); 64 for(int i=1;i<=m;i++) 65 { 66 int x=read(),y=read(),z=read(); 67 if(z<0)addedge(x,y,z); 68 else addedge(y,x,z),addedge(x,y,z); 69 } 70 if(spfa())puts("YE5"); 71 else puts("N0"); 72 } 73 }
缩点
（tarjan+toposort+dp基操）
1 #include<bits/stdc++.h> 2 #define I inline 3 using namespace std; 4 using namespace std; 5 const int N=1e4+10; 6 const int M=1e5+10; 7 I int read() 8 { 9 int x=0,f=1;char ch=getchar(); 10 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 11 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 12 return x*f; 13 } 14 int n,m; 15 int val[N]; 16 vector<int>g[N],e[N]; 17 int dfn[N],low[N],sta[N],col[N],color,ind,top; 18 int p[N],in[N],dp[N],ans; 19 20 I void tarjan(int u) 21 { 22 low[u]=dfn[u]=++ind; 23 sta[++top]=u; 24 for(int i=0;i<g[u].size();i++) 25 { 26 int v=g[u][i]; 27 if(!dfn[v])tarjan(v),low[u]=min(low[u],low[v]); 28 else if(!col[v])low[u]=min(low[u],dfn[v]); 29 } 30 if(low[u]==dfn[u]) 31 { 32 color++; 33 while(sta[top]!=u) 34 { 35 col[sta[top]]=color; 36 p[color]+=val[sta[top]]; 37 top--; 38 }top--;col[u]=color; 39 p[color]+=val[u]; 40 } 41 } 42 43 I void topo() 44 { 45 queue<int>q; 46 for(int i=1;i<=color;i++) 47 { 48 if(!in[i])q.push(i),dp[i]=p[i]; 49 } 50 while(!q.empty()) 51 { 52 int u=q.front();q.pop();ans=max(ans,dp[u]); 53 for(int i=0;i<e[u].size();i++) 54 { 55 int v=e[u][i]; 56 in[v]--;dp[v]=max(dp[v],dp[u]+p[v]); 57 if(!in[v])q.push(v); 58 } 59 } 60 cout<<ans; 61 } 62 63 int main() 64 { 65 n=read();m=read();for(int i=1;i<=n;i++)val[i]=read(); 66 for(int i=1;i<=m;i++) 67 { 68 int x=read(),y=read(); 69 g[x].push_back(y); 70 } 71 for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i); 72 for(int u=1;u<=n;u++) 73 for(int i=0;i<g[u].size();i++) 74 { 75 int v=g[u][i]; 76 if(col[v]!=col[u]) 77 { 78 e[col[u]].push_back(col[v]); 79 in[col[v]]++; 80 } 81 } 82 topo(); 83 }
ST表
（注意边界是$l+2^{k}-1$，询问的时候右边区间从$r-2^{k}+1$开始，即找一个x使$x+x^{k}-1=r$
1 #include<bits/stdc++.h> 2 #define I inline 3 using namespace std; 4 using namespace std; 5 const int N=1e5+10; 6 const int M=1e6+10; 7 I int read() 8 { 9 int x=0,f=1;char ch=getchar(); 10 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 11 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 12 return x*f; 13 } 14 int n,m; 15 int f[N][25]; 16 17 I void ST() 18 { 19 for(int j=1;(1<<j)-1<=n;j++) 20 for(int i=1;i+(1<<j)-1<=n;i++) 21 f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]); 22 } 23 24 I int query(int l,int r) 25 { 26 int k=log2(r-l+1); 27 return max(f[l][k],f[r-(1<<k)+1][k]); 28 } 29 30 int main() 31 { 32 n=read();m=read();for(int i=1;i<=n;i++)f[i][0]=read(); 33 ST(); 34 while(m--) 35 { 36 int l=read(),r=read(); 37 printf("%d ",query(l,r)); 38 } 39 }
动态DP
（NOIP2018毒瘤，求树上最大带权独立集，树形DP之后，先把dp值放到数组里，全部是虚边（每个点一棵splay根），修改用$max$矩阵乘法和LCT维护，注意一下pushup的时候矩阵乘法的和深度的关系，按照$ls(x)*x*rs(x)$的顺序乘）
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #include<algorithm> 5 #define I inline 6 #define R register 7 #define ls(x) ch[x][0] 8 #define rs(x) ch[x][1] 9 using namespace std; 10 typedef long long LL; 11 const int N=500010; 12 const int inf=(1<<31)-1; 13 14 I int read() 15 { 16 int x=0,f=1;char ch=getchar(); 17 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 18 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 19 return x*f; 20 } 21 22 int n,m; 23 struct node 24 { 25 int nxt,to; 26 }g[N<<1]; 27 int head[N],cnt; 28 29 int a[N],f[N],ch[N][2]; 30 LL dp[N][2]; 31 32 struct matrix 33 { 34 LL p[2][2]; 35 matrix(){p[0][0]=p[0][1]=p[1][0]=p[1][1]=-inf;}//新定义的矩阵乘初始化 36 }s[N],si[N];//s为整棵splay（实链）上点的矩阵乘积 37 //si为x的虚子树的矩阵乘积（包括自己） 38 39 I matrix operator * (const matrix &a,const matrix &b) 40 { 41 matrix c; 42 for(int i=0;i<=1;i++) 43 for(int k=0;k<=1;k++) 44 for(int j=0;j<=1;j++) 45 c.p[i][j]=max(c.p[i][j],a.p[i][k]+b.p[k][j]); 46 return c; 47 } 48 49 I void dfs(R int u)//刚开始全部是虚边，所以不区分虚实子树 50 { 51 dp[u][1]=a[u]; 52 for(int i=head[u];i;i=g[i].nxt) 53 { 54 int v=g[i].to; 55 if(v==f[u])continue; 56 f[v]=u;dfs(v); 57 dp[u][0]+=max(dp[v][0],dp[v][1]); 58 dp[u][1]+=dp[v][0]; 59 } 60 si[u].p[0][0]=si[u].p[0][1]=dp[u][0]; 61 si[u].p[1][0]=dp[u][1]; 62 s[u]=si[u];//开始s和si都一样 63 } 64 65 I void pushup(R int x) 66 { 67 s[x]=si[x];//考虑推出的矩阵式子，其实就是 68 //虚子树*dep小于dep[x]的和dep>dep[x]的实链上的，就是整棵树的贡献 69 if(ls(x))s[x]=s[ls(x)]*s[x]; 70 if(rs(x))s[x]=s[x]*s[rs(x)]; 71 } 72 //一下为LCT板子，不需要link也不要cut也不要makeroot 73 I bool nroot(int x) 74 { 75 return ls(f[x])==x||rs(f[x])==x; 76 } 77 78 I void rotate(R int x) 79 { 80 int y=f[x],z=f[y],k=(rs(y)==x),w=ch[x][!k]; 81 if(nroot(y))ch[z][rs(z)==y]=x;ch[x][!k]=y;ch[y][k]=w; 82 if(w)f[w]=y;f[x]=z;f[y]=x;pushup(y);pushup(x); 83 } 84 85 I void splay(R int x) 86 { 87 while(nroot(x)) 88 { 89 int y=f[x],z=f[y]; 90 if(nroot(y))rotate((ls(y)==x)^(ls(z)==y)?x:y); 91 rotate(x); 92 } 93 } 94 //这其实就是维护虚子树信息的access写法 95 I void access(R int x) 96 { 97 for(int y=0;x;x=f[y=x]) 98 { 99 splay(x); 100 if(rs(x))//实变虚，加到虚树中 101 { 102 si[x].p[0][0]+=max(s[rs(x)].p[0][0],s[rs(x)].p[1][0]); 103 si[x].p[1][0]+=s[rs(x)].p[0][0]; 104 } 105 rs(x)=y; 106 if(rs(x))//虚变实，从虚树中减去 107 { 108 si[x].p[0][0]-=max(s[rs(x)].p[0][0],s[rs(x)].p[1][0]); 109 si[x].p[1][0]-=s[rs(x)].p[0][0]; 110 }si[x].p[0][1]=si[x].p[0][0]; 111 pushup(x);//别忘了更新 112 } 113 } 114 115 I void modify(int x,int y)//很显然的修改函数 116 { 117 access(x);splay(x); 118 si[x].p[1][0]-=a[x]-y;//转到splay的根上，照着dp方程直接修改即可 119 a[x]=y;pushup(x); 120 } 121 122 I void addedge(int u,int v) 123 { 124 g[++cnt].nxt=head[u]; 125 g[cnt].to=v;head[u]=cnt; 126 } 127 128 int main() 129 { 130 n=read();m=read(); 131 for(int i=1;i<=n;i++)a[i]=read(); 132 for(int i=1;i<n;i++) 133 { 134 int x=read(),y=read(); 135 addedge(x,y);addedge(y,x); 136 } 137 dfs(1); 138 while(m--) 139 { 140 int x=read(),y=read(); 141 modify(x,y);splay(1);//选一个点为根输出答案 142 printf("%lld ",max(s[1].p[0][0],s[1].p[1][0])); 143 } 144 }
线性求逆元
（记住就行了，从$p=k*i+r≡0(mod p)$开始推，乘一个$i^{-1}$和$r^{-1}$即可
1 #include<bits/stdc++.h> 2 #define I inline 3 using namespace std; 4 using namespace std; 5 const int N=3e6+10; 6 I int read() 7 { 8 int x=0,f=1;char ch=getchar(); 9 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 10 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 11 return x*f; 12 } 13 int n; 14 int p,inv[N]; 15 16 int main() 17 { 18 n=read();p=read(); 19 inv[1]=1; 20 for(int i=2;i<=n;i++) 21 inv[i]=1LL*(p-p/i)*(inv[p%i])%p; 22 for(int i=1;i<=n;i++)printf("%d ",inv[i]); 23 }
康拓展开
（就是给你一个$1-n$的排列，问你按字典序是$1-n$全排列的第几个（注意是否从$0$开始计算）$ans=(1+)sumlimits_{i=1}^na_i*(n-i)!$
1 #include<bits/stdc++.h> 2 #define lowbit(x) (x&-x) 3 #define I inline 4 using namespace std; 5 using namespace std; 6 const int N=1000010; 7 const int p=998244353; 8 I int read() 9 { 10 int x=0,f=1;char ch=getchar(); 11 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 12 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 13 return x*f; 14 } 15 int n,a[N],ans; 16 int bit[N],fac[N]; 17 18 I void add(int pos,int val) 19 { 20 while(pos<=n)bit[pos]+=val,pos+=lowbit(pos); 21 } 22 I int query(int pos) 23 { 24 int res=0; 25 while(pos)res+=bit[pos],pos-=lowbit(pos); 26 return res; 27 } 28 29 int main() 30 { 31 n=read();for(int i=1;i<=n;i++)a[i]=read(); 32 fac[0]=1; 33 for(int i=1;i<=n;i++)add(i,1),fac[i]=1LL*i*fac[i-1]%p; 34 for(int i=1;i<=n;i++) 35 { 36 int k=query(a[i])-1; 37 ans=(ans+1LL*k*fac[n-i]%p)%p; 38 add(a[i],-1); 39 } 40 cout<<ans+1; 41 }
线段树1
没啥可说的
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 using namespace std; 5 #define smid ((l+r)>>1) 6 #define lch (now<<1) 7 #define rch ((now<<1)|1) 8 #define maxn 100005 9 #define maxlen maxn*4 10 #define root 1 11 struct Sgt 12 {long long num,pls;}sgt[maxlen]; 13 int n,m; 14 long long a[maxn]; 15 void update(int now) 16 { 17 sgt[now].num=sgt[lch].num+sgt[rch].num; 18 } 19 void pushdown(int now,int l,int r) 20 { 21 if(sgt[now].pls) 22 { 23 sgt[lch].pls+=sgt[now].pls; 24 sgt[lch].num+=(smid-l+1)*sgt[now].pls; 25 sgt[rch].num+=(r-(smid+1)+1)*sgt[now].pls; 26 sgt[rch].pls+=sgt[now].pls; 27 sgt[now].pls=0; 28 } 29 } 30 void build_sgt(int now,int l,int r) 31 { 32 if(l==r) 33 { 34 sgt[now].num=a[l];return ; 35 } 36 build_sgt(lch,l,smid); 37 build_sgt(rch,smid+1,r); 38 update(now); 39 } 40 void plus_sgt(int now,int l,int r,int x,int y,long long val) 41 { 42 if(l==x&&r==y) 43 { 44 sgt[now].num+=(y-x+1)*val; 45 sgt[now].pls+=val; 46 return ; 47 } 48 pushdown(now,l,r); 49 if(y<=smid) 50 { 51 plus_sgt(lch,l,smid,x,y,val); 52 } 53 else if(x>smid) 54 { 55 plus_sgt(rch,smid+1,r,x,y,val); 56 } 57 else 58 { 59 plus_sgt(lch,l,smid,x,smid,val); 60 plus_sgt(rch,smid+1,r,smid+1,y,val); 61 } 62 update(now); 63 } 64 long long qry_sgt(int now,int l,int r,int x,int y) 65 { 66 if(l==x&&r==y) 67 { 68 return sgt[now].num; 69 } 70 pushdown(now,l,r); 71 if(y<=smid) 72 return qry_sgt(lch,l,smid,x,y); 73 else if(x>smid) 74 return qry_sgt(rch,smid+1,r,x,y); 75 else 76 return qry_sgt(lch,l,smid,x,smid)+qry_sgt(rch,smid+1,r,smid+1,y); 77 } 78 int main() 79 { 80 cin>>n>>m; 81 for(int i=1;i<=n;i++) 82 { 83 scanf("%lld",&a[i]); 84 } 85 build_sgt(root,1,n); 86 for(int i=1;i<=m;i++) 87 { 88 int cid; 89 scanf("%d",&cid); 90 if(cid==1) 91 { 92 int x,y; 93 long long k; 94 scanf("%d%d%lld",&x,&y,&k); 95 plus_sgt(root,1,n,x,y,k); 96 } 97 if(cid==2) 98 { 99 int x,y; 100 scanf("%d%d",&x,&y); 101 printf("%lld ",qry_sgt(root,1,n,x,y)); 102 } 103 } 104 }
线段树2
注意下放标记的顺序即可，当然线段树的板子不止于此
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #define root 1 #define lch now*2 #define rch now*2+1 #define smid (l+r)/2 using namespace std; typedef long long LL; const int maxn=100005; int n,m,p; struct node { LL pls,mul,sum; }sgt[maxn*4]; LL a[maxn]; void update(int now) { sgt[now].sum=(sgt[lch].sum+sgt[rch].sum)%p; } void pushdown(int now,int l,int r) { sgt[lch].pls=(sgt[lch].pls*sgt[now].mul%p+sgt[now].pls)%p; sgt[rch].pls=(sgt[rch].pls*sgt[now].mul%p+sgt[now].pls)%p; sgt[lch].mul=(sgt[lch].mul*sgt[now].mul)%p; sgt[rch].mul=(sgt[rch].mul*sgt[now].mul)%p; sgt[lch].sum=(sgt[now].pls*(smid-l+1)%p+sgt[lch].sum*sgt[now].mul%p)%p; sgt[rch].sum=(sgt[now].pls*(r-smid)%p+sgt[rch].sum*sgt[now].mul%p)%p; sgt[now].pls=0; sgt[now].mul=1; } void build_sgt(int now,int l,int r) { sgt[now].pls=0; sgt[now].mul=1; if(l==r) { sgt[now].sum=a[l]; return; } build_sgt(lch,l,smid); build_sgt(rch,smid+1,r); update(now); } void plus_sgt(int now,int l,int r,int x,int y,LL val) { if(l==x&&r==y) { sgt[now].pls=(sgt[now].pls+val)%p; sgt[now].sum=(sgt[now].sum+(r-l+1)%p*val%p)%p; return; } pushdown(now,l,r); if(y<=smid) plus_sgt(lch,l,smid,x,y,val); else if(x>smid) plus_sgt(rch,smid+1,r,x,y,val); else { plus_sgt(lch,l,smid,x,smid,val); plus_sgt(rch,smid+1,r,smid+1,y,val); } update(now); } void multipy_sgt(int now,int l,int r,int x,int y,LL val) { if(l==x&&r==y) { sgt[now].sum=sgt[now].sum*val%p; sgt[now].mul=sgt[now].mul*val%p; sgt[now].pls=sgt[now].pls*val%p; return; } pushdown(now,l,r); if(y<=smid) multipy_sgt(lch,l,smid,x,y,val); else if(x>smid) multipy_sgt(rch,smid+1,r,x,y,val); else { multipy_sgt(lch,l,smid,x,smid,val); multipy_sgt(rch,smid+1,r,smid+1,y,val); } update(now); } LL query_sgt(int now,int l,int r,int x,int y) { if(x==l&&r==y) return sgt[now].sum; pushdown(now,l,r); if(y<=smid) return query_sgt(lch,l,smid,x,y)%p; else if(x>smid) return query_sgt(rch,smid+1,r,x,y)%p; else { return (query_sgt(lch,l,smid,x,smid)%p+ query_sgt(rch,smid+1,r,smid+1,y)%p)%p; } } int main() { scanf("%d%d%d",&n,&m,&p); for(int i=1;i<=n;i++)scanf("%lld",&a[i]); build_sgt(root,1,n); while(m--) { int cid; scanf("%d",&cid); if(cid==1) { int x,y; LL k; scanf("%d%d%lld",&x,&y,&k); multipy_sgt(root,1,n,x,y,k); } if(cid==2) { int x,y; LL k; scanf("%d%d%lld",&x,&y,&k); plus_sgt(root,1,n,x,y,k); } if(cid==3) { int x,y; scanf("%d%d",&x,&y); printf("%lld ",query_sgt(root,1,n,x,y)%p); } } }
2-SAT
加边的时候多注意就行，至于构造方案，，，考的不多，主要是不太理解为什么取拓扑序大的就行了
1 #include<bits/stdc++.h> 2 #define I inline 3 using namespace std; 4 const int N=2000010; 5 I int read() 6 { 7 int x=0,f=1;char ch=getchar(); 8 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 9 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 10 return x*f; 11 } 12 vector<int>g[N]; 13 int n,m; 14 I void add(int u,int v){g[u].push_back(v);} 15 int dfn[N],low[N],sta[N],col[N],color,ind,top; 16 17 I void tarjan(int u) 18 { 19 low[u]=dfn[u]=++ind;sta[++top]=u; 20 for(int i=0;i<g[u].size();i++) 21 { 22 int v=g[u][i]; 23 if(!dfn[v])tarjan(v),low[u]=min(low[u],low[v]); 24 else if(!col[v])low[u]=min(low[u],dfn[v]); 25 } 26 if(low[u]==dfn[u]) 27 { 28 color++; 29 while(sta[top]!=u) 30 { 31 col[sta[top]]=color; 32 top--; 33 }top--;col[u]=color; 34 } 35 } 36 37 I bool chk() 38 { 39 for(int i=1;i<=n;i++) 40 if(col[i]==col[i+n])return 0; 41 return 1; 42 } 43 44 int main() 45 { 46 n=read();m=read(); 47 for(int i=1;i<=m;i++) 48 { 49 int a=read(),b=read(),c=read(),d=read(); 50 if(b&&d)add(a,c+n),add(c,a+n); 51 if(!b&&d)add(a+n,c+n),add(c,a); 52 if(b&&!d)add(a,c),add(c+n,a+n); 53 if(!b&&!d)add(a+n,c),add(c+n,a); 54 } 55 for(int i=1;i<=(n<<1);i++)if(!dfn[i])tarjan(i); 56 if(chk()) 57 { 58 puts("POSSIBLE"); 59 for(int i=1;i<=n;i++) 60 { 61 printf("%d ",col[i]>col[i+n]); 62 } 63 return 0; 64 } 65 cout<<"IMPOSSIBLE"; 66 return 0; 67 }
三分
求单峰函数极值
1 #include<bits/stdc++.h> 2 using namespace std; 3 const double eps=1e-8; 4 int n; 5 double a[20],l,r; 6 7 double val(double x) 8 { 9 double res=0;int v=0; 10 for(int i=n+1;i>=1;i--)res+=a[++v]*pow(x,i-1); 11 return res; 12 } 13 14 int main() 15 { 16 cin>>n>>l>>r; 17 for(int i=1;i<=n+1;i++)cin>>a[i]; 18 while(r-l>eps) 19 { 20 double m1=l+(r-l)/3.0,m2=r-(r-l)/3.0; 21 if(val(m1)-val(m2)>eps)r=m2; 22 else l=m1; 23 } 24 printf("%.5lf",l); 25 }
割点
判断$low[v]>=dfn[u]$
1 #include<bits/stdc++.h> 2 #define I inline 3 using namespace std; 4 const int N=20010; 5 const int M=100010; 6 I int read() 7 { 8 int x=0,f=1;char ch=getchar(); 9 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 10 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 11 return x*f; 12 } 13 14 int n,m; 15 vector<int>g[N]; 16 bool cut[N]; 17 int ans; 18 int dfn[N],low[N],ind; 19 20 I void tarjan(int u,int rt) 21 { 22 int ch=0; 23 low[u]=dfn[u]=++ind; 24 for(int i=0;i<g[u].size();i++) 25 { 26 int v=g[u][i]; 27 if(!dfn[v]) 28 { 29 tarjan(v,rt); 30 low[u]=min(low[u],low[v]); 31 if(u!=rt&&low[v]>=dfn[u])cut[u]=1; 32 if(u==rt)ch++; 33 } 34 low[u]=min(low[u],dfn[v]); 35 } 36 if(ch>=2&&u==rt)cut[u]=1; 37 } 38 39 int main() 40 { 41 n=read();m=read(); 42 for(int i=1;i<=m;i++) 43 { 44 int x=read(),y=read(); 45 g[x].push_back(y); 46 g[y].push_back(x); 47 } 48 for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i,i); 49 for(int i=1;i<=n;i++)if(cut[i])ans++; 50 cout<<ans<<endl; 51 for(int i=1;i<=n;i++)if(cut[i])printf("%d ",i); 52 }
树链剖分
挑战30min打出树剖板子成功
1 #include<bits/stdc++.h> 2 #define I inline 3 #define ls (now<<1) 4 #define rs (now<<1|1) 5 #define smid (l+r>>1) 6 using namespace std; 7 const int N=1e5+10; 8 I int read() 9 { 10 int x=0,f=1;char ch=getchar(); 11 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 12 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 13 return x*f; 14 } 15 struct segment 16 { 17 int sum,pls; 18 }sgt[N<<2]; 19 int n,m,rt,p; 20 vector<int>g[N]; 21 int a[N]; 22 int dep[N],f[N],rk[N],id[N],ind,top[N],son[N],sz[N]; 23 24 I void dfs1(int u) 25 { 26 dep[u]=dep[f[u]]+1; 27 sz[u]=1; 28 for(int i=0;i<g[u].size();i++) 29 { 30 int v=g[u][i]; 31 if(v==f[u])continue; 32 f[v]=u;dfs1(v); 33 sz[u]+=sz[v]; 34 if(sz[v]>sz[son[u]])son[u]=v; 35 } 36 } 37 38 I void dfs2(int u,int tp) 39 { 40 top[u]=tp; 41 rk[++ind]=u; 42 id[u]=ind; 43 if(son[u])dfs2(son[u],tp); 44 for(int i=0;i<g[u].size();i++) 45 { 46 int v=g[u][i]; 47 if(v==f[u]||v==son[u])continue; 48 dfs2(v,v); 49 } 50 } 51 52 I void pushup(int now) 53 { 54 sgt[now].sum=sgt[ls].sum+sgt[rs].sum; 55 } 56 57 I void pushdown(int now,int l,int r) 58 { 59 if(!sgt[now].pls)return; 60 sgt[ls].pls=(sgt[ls].pls+sgt[now].pls)%p; 61 sgt[rs].pls=(sgt[rs].pls+sgt[now].pls)%p; 62 sgt[ls].sum=(sgt[ls].sum+1LL*(smid-l+1)*sgt[now].pls%p)%p; 63 sgt[rs].sum=(sgt[rs].sum+1LL*(r-smid)*sgt[now].pls%p)%p; 64 sgt[now].pls=0; 65 } 66 67 I void bt(int now,int l,int r) 68 { 69 if(l==r){sgt[now].sum=a[rk[l]];return ;} 70 bt(ls,l,smid);bt(rs,smid+1,r); 71 pushup(now); 72 } 73 74 I void modify(int now,int l,int r,int x,int y,int k) 75 { 76 if(x<=l&&r<=y) 77 { 78 sgt[now].sum=(sgt[now].sum+1LL*(r-l+1)*k%p)%p; 79 sgt[now].pls=(sgt[now].pls+k)%p; 80 return ; 81 } 82 pushdown(now,l,r); 83 if(x<=smid)modify(ls,l,smid,x,y,k); 84 if(smid<y)modify(rs,smid+1,r,x,y,k); 85 pushup(now); 86 } 87 88 I int query(int now,int l,int r,int x,int y) 89 { 90 if(x<=l&&r<=y)return sgt[now].sum; 91 pushdown(now,l,r); 92 int res=0; 93 if(x<=smid)res=(res+query(ls,l,smid,x,y))%p; 94 if(smid<y)res=(res+query(rs,smid+1,r,x,y))%p; 95 return res; 96 } 97 98 I void change_range(int x,int y,int z) 99 { 100 while(top[x]!=top[y]) 101 { 102 if(dep[top[x]]<dep[top[y]])swap(x,y); 103 modify(1,1,n,id[top[x]],id[x],z); 104 x=f[top[x]]; 105 } 106 if(dep[x]<dep[y])swap(x,y); 107 modify(1,1,n,id[y],id[x],z); 108 } 109 110 I int query_range(int x,int y) 111 { 112 int res=0; 113 while(top[x]!=top[y]) 114 { 115 if(dep[top[x]]<dep[top[y]])swap(x,y); 116 res=(res+query(1,1,n,id[top[x]],id[x]))%p; 117 x=f[top[x]]; 118 } 119 if(dep[x]<dep[y])swap(x,y); 120 res=(res+query(1,1,n,id[y],id[x]))%p; 121 return res; 122 } 123 124 I void change_tree(int x,int z) 125 { 126 modify(1,1,n,id[x],id[x]+sz[x]-1,z); 127 } 128 129 I int query_tree(int x) 130 { 131 return query(1,1,n,id[x],id[x]+sz[x]-1); 132 } 133 134 int main() 135 { 136 n=read();m=read();rt=read();p=read(); 137 for(int i=1;i<=n;i++)a[i]=read(); 138 for(int i=1;i<n;i++) 139 { 140 int x=read(),y=read(); 141 g[x].push_back(y); 142 g[y].push_back(x); 143 } 144 dfs1(rt); 145 dfs2(rt,rt); 146 bt(1,1,n); 147 while(m--) 148 { 149 int cid=read(); 150 if(cid==1) 151 { 152 int x=read(),y=read(),z=read(); 153 change_range(x,y,z); 154 } 155 if(cid==2) 156 { 157 int x=read(),y=read(); 158 printf("%d ",query_range(x,y)%p); 159 } 160 if(cid==3) 161 { 162 int x=read(),z=read(); 163 change_tree(x,z); 164 } 165 if(cid==4) 166 { 167 int x=read(); 168 printf("%d ",query_tree(x))%p; 169 } 170 } 171 }
树状数组1
没啥可说的
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 using namespace std; 5 #define lowbit(pos) ((pos)&(-pos)) 6 #define maxn 500005 7 int tarr[maxn]; 8 int n,m; 9 void addtarr(int pos,int k) 10 { 11 while(pos<maxn) 12 { 13 tarr[pos]+=k; 14 pos+=lowbit(pos); 15 } 16 } 17 int qrytarr(int pos) 18 { 19 int res=0; 20 while(pos) 21 { 22 res+=tarr[pos]; 23 pos-=lowbit(pos); 24 } 25 return res; 26 } 27 int main() 28 { 29 scanf("%d%d",&n,&m); 30 for(int i=1;i<=n;i++) 31 {int p;scanf("%d",&p);addtarr(i,p);} 32 for(int i=1;i<=m;i++) 33 { 34 int cid; 35 int x; 36 scanf("%d",&cid); 37 if(cid==1) 38 { 39 int x,k; 40 scanf("%d%d",&x,&k); 41 addtarr(x,k); 42 } 43 else 44 { 45 int j,y; 46 scanf("%d%d",&j,&y); 47 printf("%d ",qrytarr(y)-qrytarr(j-1)); 48 } 49 } 50 }
树状数组2
差分一下就行了
1 #include<cstdio> 2 #include<algorithm> 3 #include<iostream> 4 using namespace std; 5 #define maxn 500005 6 #define lowbit(x) (x)&(-x) 7 int tarr[maxn]; 8 int n,m; 9 int in[maxn]; 10 void addtarr(int pos,int v) 11 { 12 while(pos<=maxn) 13 { 14 tarr[pos]+=v; 15 pos+=lowbit(pos);} 16 } 17 int qrytarr(int pos) 18 { 19 int res=0; 20 while(pos) 21 { 22 res+=tarr[pos]; 23 pos-=lowbit(pos);} 24 return res; 25 } 26 int main() 27 { 28 scanf("%d%d",&n,&m); 29 for(int i=1;i<=n;i++) 30 { 31 int x; 32 scanf("%d",&in[i]);} 33 for(int i=1;i<=n;i++) 34 {addtarr(i,in[i]-in[i-1]);} 35 //for(int s=1;s<=n;s++) 36 //{cout<<tarr[s]<<" ";} 37 //cout<<endl; 38 for(int i=1;i<=m;i++) 39 { 40 int cid; 41 scanf("%d",&cid); 42 if(cid==1) 43 {int x,y,k; 44 scanf("%d%d%d",&x,&y,&k); 45 addtarr(x,k); 46 addtarr(y+1,-k); 47 } 48 if(cid==2) 49 { 50 int x; 51 scanf("%d",&x); 52 printf("%d ",qrytarr(x)); 53 } 54 } 55 }
普通平衡树（fhq Treap）
记得画图模拟split和merge，merge时按照rank，split时按照val
1 #include<bits/stdc++.h> 2 #define ls(x) ch[x][0] 3 #define rs(x) ch[x][1] 4 #define I inline 5 using namespace std; 6 const int N=100010; 7 I int read() 8 { 9 int x=0,f=1;char ch=getchar(); 10 while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} 11 while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();} 12 return x*f; 13 } 14 15 int ch[N][2],rnk[N],val[N],sz[N],root,x,y,z,cnt; 16 int n; 17 18 I void pushup(int now) 19 { 20 sz[now]=sz[ls(now)]+sz[rs(now)]+1; 21 } 22 23 I void split(int now,int k,int &x,int &y) 24 { 25 if(!now)x=y=0; 26 else 27 { 28 if(val[now]<=k)x=now,split(rs(now),k,rs(now),y); 29 else y=now,split(ls(now),k,x,ls(now)); 30 pushup(now); 31 } 32 } 33 34 I int merge(int x,int y) 35 { 36 if(!x||!y)return x+y; 37 if(rnk[x]<rnk[y]){rs(x)=merge(rs(x),y);pushup(x);return x;} 38 else{ls(y)=merge(x,ls(y));pushup(y);return y;} 39 } 40 41 I int kth(int now,int k) 42 { 43 while(1) 44 { 45 if(k<=sz[ls(now)])now=ls(now); 46 else if(k==sz[ls(now)]+1)return now; 47 else k-=sz[ls(now)]+1,now=rs(now); 48 } 49 } 50 51 I int new_node(int x) 52 { 53 cnt++;sz[cnt]=1; 54 val[cnt]=x;rnk[cnt]=rand(); 55 return cnt; 56 } 57 58 I void insert(int k) 59 { 60 split(root,k,x,y); 61 root=merge(merge(x,new_node(k)),y); 62 } 63 64 I void del(int k) 65 { 66 split(root,k,x,z); 67 split(x,k-1,x,y); 68 y=merge(ls(y),rs(y)); 69 root=merge(merge(x,y),z); 70 } 71 72 I int getrank(int k) 73 { 74 split(root,k-1,x,y); 75 printf("%d ",sz[x]+1); 76 root=merge(x,y); 77 } 78 79 I int get_pre(int k) 80 { 81 split(root,k-1,x,y); 82 printf("%d ",val[kth(x,sz[x])]); 83 root=merge(x,y); 84 } 85 86 I int get_nxt(int k) 87 { 88 split(root,k,x,y); 89 printf("%d ",val[kth(y,1)]); 90 root=merge(x,y); 91 } 92 93 int main() 94 { 95 srand(time(0)); 96 n=read(); 97 while(n--) 98 { 99 int op=read(),k=read(); 100 if(op==1)insert(k); 101 if(op==2)del(k); 102 if(op==3)getrank(k); 103 if(op==4)printf("%d ",val[kth(root,k)]); 104 if(op==5)get_pre(k); 105 if(op==6)get_nxt(k); 106 } 107 }
矩阵快速幂
记得精度，重载比较美观，记得单位矩阵
1 #include<bits/stdc++.h> 2 #define ls(x) ch[x][0] 3 #define rs(x) ch[x][1] 4 #define I inline 5 using namespace std; 6 const int N=110; 7 const int p=1e9+7; 8 typedef long long LL; 9 struct mat 10 { 11 LL p[N][N]; 12 }base,ans,a; 13 14 int n; 15 LL k; 16 17 mat operator * (mat a,mat b) 18 { 19 mat c; 20 for(int i=1;i<=n;i++) 21 for(int j=1;j<=n;j++) 22 c.p[i][j]=0; 23 24 for(int i=1;i<=n;i++) 25 for(int k=1;k<=n;k++) 26 for(int j=1;j<=n;j++) 27 c.p[i][j]=(c.p[i][j]%p+a.p[i][k]*b.p[k][j]%p)%p; 28 return c; 29 } 30 31 mat qpow(mat a,LL k) 32 { 33 for(int i=1;i<=n;i++)base.p[i][i]=1; 34 while(k) 35 { 36 if(k&1LL)base=base*a; 37 a=a*a;k>>=1LL; 38 } 39 return base; 40 } 41 42 int main() 43 { 44 cin>>n>>k; 45 for(int i=1;i<=n;i++) 46 for(int j=1;j<=n;j++) 47 cin>>a.p[i][j]; 48 ans=qpow(a,k); 49 for(int i=1;i<=n;i++) 50 { 51 for(int j=1;j<=n;j++) 52 printf("%lld ",ans.p[i][j]%p); 53 printf(" "); 54 } 55 }
卢卡斯定理
模数p小的情况下用于求组合数。
公式 $C_m^n=C_{m/p}^{n/p}*C_{mmod p}^{nmod p}$
模运算直接算，除法运算递归即可。
1 #include<bits/stdc++.h> 2 #define I inline 3 using namespace std; 4 const int N=1e5+10; 5 I int read() 6 { 7 int x=0,f=1;char ch=getchar(); 8 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 9 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 10 return x*f; 11 } 12 int T,fac[N]; 13 14 I int ksm(int a,int b,int p) 15 { 16 int res=1; 17 while(b) 18 { 19 if(b&1)res=1LL*res*a%p; 20 a=1LL*a*a%p; 21 b>>=1; 22 } 23 return res; 24 } 25 26 I int C(int n,int m,int p) 27 { 28 if(n<m)return 0; 29 return 1LL*fac[n]*ksm(fac[m],p-2,p)%p*1LL*ksm(fac[n-m],p-2,p)%p; 30 } 31 32 I int Lucas(int n,int m,int p) 33 { 34 return !m?1:1LL*C(n%p,m%p,p)*Lucas(n/p,m/p,p)%p; 35 } 36 37 int main() 38 { 39 T=read(); 40 while(T--) 41 { 42 int n=read(),m=read(),p=read(); 43 fac[0]=1;for(int i=1;i<=p;i++)fac[i]=1LL*fac[i-1]*i%p; 44 printf("%d ",Lucas(n+m,m,p)); 45 } 46 }
线性筛素数
背掉，关键在于$imod prime[j]=0$时$i*prime[j]$可以被一个更小的质数和一个更大的合数表示
1 #include<bits/stdc++.h> 2 #define I inline 3 using namespace std; 4 const int N=10000010; 5 int prime[N],cnt; 6 bool not_prime[N]; 7 int n,m; 8 9 I void pre() 10 { 11 not_prime[0]=not_prime[1]=1; 12 for(int i=2;i<=n;i++) 13 { 14 if(!not_prime[i])prime[++cnt]=i; 15 for(int j=1;j<=cnt&&prime[j]*i<=n;j++) 16 { 17 not_prime[prime[j]*i]=1; 18 if(i%prime[j]==0)break; 19 } 20 } 21 } 22 int main() 23 { 24 cin>>n>>m; 25 pre(); 26 while(m--) 27 { 28 int x;scanf("%d",&x); 29 if(not_prime[x])puts("No"); 30 else puts("Yes"); 31 } 32 }
矩阵加速递推
注意细节，可以用初始矩阵开始乘，也可以用单位矩阵开始乘
1 #include<bits/stdc++.h> 2 #define I inline 3 using namespace std; 4 typedef long long LL; 5 const int p=1e9+7; 6 I int read() 7 { 8 int x=0,f=1;char ch=getchar(); 9 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 10 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 11 return x*f; 12 } 13 struct mat 14 { 15 LL p[5][5]; 16 }base,ans; 17 int T; 18 19 I mat operator * (mat a,mat b) 20 { 21 mat c;memset(c.p,0,sizeof(c.p)); 22 for(int i=1;i<=3;i++) 23 for(int k=1;k<=3;k++) 24 for(int j=1;j<=3;j++) 25 c.p[i][j]=(c.p[i][j]%p+a.p[i][k]*b.p[k][j]%p)%p; 26 return c; 27 } 28 29 void mat_ksm(int k) 30 { 31 memset(base.p,0,sizeof(base.p)); 32 memset(ans.p,0,sizeof(ans.p)); 33 base.p[1][1]=base.p[2][1]=base.p[1][3]=base.p[3][2]=1; 34 ans.p[1][1]=ans.p[2][1]=ans.p[3][1]=1; 35 while(k) 36 { 37 if(k&1)ans=ans*base; 38 base=base*base; 39 k>>=1; 40 } 41 } 42 43 int main() 44 { 45 T=read(); 46 while(T--) 47 { 48 int n=read(); 49 if(n<=3)puts("1"); 50 else 51 { 52 mat_ksm(n-1); 53 printf("%lld ",ans.p[1][1]); 54 } 55 } 56 }
有理数取余（大数除法模运算）
$$cequivfrac{a}{b}pmod p$$
$$b*cequiv apmod p$$
$$b*(a*inv[b])equiv apmod p$$
$$b_{mod p}*a_{mod p}*inv[b]_{mod p}equiv a_{mod p}pmod p$$
$$c=a_{mod p}*inv[b]_{mod p}$$
求一下逆元就好了，这里因为有angry的情况，根据exgcd的成立条件特判即可。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstdio> 4 #include<cstring> 5 #define LL long long 6 using namespace std; 7 const LL p=19260817; 8 LL a,b; 9 LL x,y; 10 inline LL read() 11 { 12 LL x=0,f=1; 13 char ch=getchar(); 14 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 15 while(ch>='0'&&ch<='9') 16 { 17 x=(x*10%p+(ch-'0')%p)%p;ch=getchar(); 18 } 19 return (x*f)%p; 20 } 21 LL exgcd(LL a,LL b,LL &x,LL &y) 22 { 23 if(b==0) 24 { 25 x=1;y=0; 26 return a; 27 } 28 LL k=exgcd(b,a%b,x,y); 29 LL t=x; 30 x=y; 31 y=t-(a/b)*y; 32 return k; 33 } 34 int main() 35 { 36 a=read(); 37 b=read(); 38 LL r=exgcd(b,p,x,y); 39 if(r!=1){cout<<"Angry!";return 0;} 40 x=(x%p+p)%p; 41 cout<<(x%p*a%p)%p; 42 return 0; 43 }
二分图匹配
注意判vis，找当前点增光路的时候如果有环（之前被dfs的点又被找了一次）直接跳过
1 #include<bits/stdc++.h> 2 #define I inline 3 using namespace std; 4 const int N=1010; 5 I int read() 6 { 7 int x=0,f=1;char ch=getchar(); 8 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 9 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 10 return x*f; 11 } 12 int g[N][N]; 13 int n,m,e; 14 int ans,match[N]; 15 bool vis[N]; 16 17 I bool dfs(int u) 18 { 19 for(int v=1;v<=m;v++) 20 { 21 if(!vis[v]&&g[u][v]) 22 { 23 vis[v]=1; 24 if(!match[v]||dfs(match[v])) 25 { 26 match[v]=u;return 1; 27 } 28 } 29 }return 0; 30 } 31 32 int main() 33 { 34 n=read();m=read();e=read(); 35 for(int i=1;i<=e;i++) 36 { 37 int x=read(),y=read(); 38 if(x<=n&&y<=m)g[x][y]=1; 39 } 40 for(int i=1;i<=n;i++) 41 { 42 memset(vis,0,sizeof(vis)); 43 ans+=dfs(i); 44 } 45 cout<<ans; 46 }
树上公共祖先（树剖求LCA）
1 #include<bits/stdc++.h> 2 #define I inline 3 using namespace std; 4 const int N=500010; 5 I int read() 6 { 7 int x=0,f=1;char ch=getchar(); 8 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 9 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 10 return x*f; 11 } 12 vector<int>g[N]; 13 int n,m,rt; 14 int dep[N],son[N],sz[N],top[N],f[N]; 15 16 I void dfs1(int u) 17 { 18 dep[u]=dep[f[u]]+1; 19 sz[u]=1; 20 for(int i=0;i<g[u].size();i++) 21 { 22 int v=g[u][i]; 23 if(v==f[u])continue; 24 f[v]=u;dfs1(v); 25 sz[u]+=sz[v]; 26 if(sz[v]>sz[son[u]])son[u]=v; 27 } 28 } 29 30 I void dfs2(int u,int tp) 31 { 32 top[u]=tp;if(son[u])dfs2(son[u],tp); 33 for(int i=0;i<g[u].size();i++) 34 { 35 int v=g[u][i]; 36 if(v==f[u]||v==son[u])continue; 37 dfs2(v,v); 38 } 39 } 40 41 I int LCA(int x,int y) 42 { 43 while(top[x]!=top[y]) 44 { 45 if(dep[top[x]]<dep[top[y]])swap(x,y); 46 x=f[top[x]]; 47 } 48 if(dep[x]<dep[y])swap(x,y); 49 return y; 50 } 51 52 53 int main() 54 { 55 n=read();m=read();rt=read(); 56 for(int i=1;i<n;i++) 57 { 58 int x=read(),y=read(); 59 g[x].push_back(y); 60 g[y].push_back(x); 61 } 62 dfs1(rt);dfs2(rt,rt); 63 while(m--) 64 { 65 int x=read(),y=read(); 66 printf("%d ",LCA(x,y)); 67 } 68 }
快速幂
不说什么。。。
1 #include<bits/stdc++.h> 2 #define I inline 3 using namespace std; 4 I int read() 5 { 6 int x=0,f=1;char ch=getchar(); 7 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 8 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 9 return x*f; 10 } 11 int b,k,p; 12 13 I int ksm(int b,int k,int p) 14 { 15 int res=1; 16 while(k) 17 { 18 if(k&1)res=1LL*res*b%p; 19 b=1LL*b*b%p;k>>=1; 20 } 21 return res%p; 22 } 23 24 int main() 25 { 26 b=read();k=read();p=read(); 27 printf("%d^%d mod %d=%d",b,k,p,ksm(b,k,p)); 28 }
字符串匹配（KMP）
注意细节，预处理的时候从第2个开始更新，匹配串要和$i$之前的自我匹配，$while里的j>0$容易忘
1 #include<bits/stdc++.h> 2 #define I inline 3 using namespace std; 4 const int N=1000010; 5 char a[N],b[N]; 6 int n,m,nxt[N]; 7 I void pre() 8 { 9 int j=0;nxt[1]=0; 10 for(int i=1;i<m;i++) 11 { 12 while(j&&b[j+1]!=b[i+1])j=nxt[j]; 13 if(b[j+1]==b[i+1])j++;nxt[i+1]=j; 14 } 15 } 16 17 I void kmp() 18 { 19 int j=0; 20 for(int i=0;i<n;i++) 21 { 22 while(j&&b[j+1]!=a[i+1])j=nxt[j]; 23 if(b[j+1]==a[i+1])j++; 24 if(j==m)printf("%d ",i-m+2),j=nxt[j]; 25 } 26 } 27 28 int main() 29 { 30 cin>>a+1>>b+1; 31 n=strlen(a+1);m=strlen(b+1); 32 pre();kmp(); 33 for(int i=1;i<=m;i++)printf("%d ",nxt[i]); 34 }
最小费用最大流（EK）
EK，把bfs换成spfa就行了
1 #include<bits/stdc++.h> 2 #define I inline 3 using namespace std; 4 const int N=5010; 5 const int M=50010; 6 const int inf=2147483647; 7 I int read() 8 { 9 int x=0,f=1;char ch=getchar(); 10 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 11 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 12 return x*f; 13 } 14 struct node 15 { 16 int nxt,to,w,f; 17 }g[M<<1]; 18 struct PRE 19 { 20 int id,u; 21 }pre[N]; 22 int dist[N]; 23 bool vis[N]; 24 int head[N],cnt=1; 25 int n,m,s,t; 26 int cost; 27 I void addedge(int u,int v,int w,int f) 28 { 29 g[++cnt].nxt=head[u]; 30 g[cnt].to=v; 31 g[cnt].w=w; 32 g[cnt].f=f; 33 head[u]=cnt; 34 } 35 36 I bool spfa() 37 { 38 for(int i=1;i<=n;i++)dist[i]=inf; 39 memset(vis,0,sizeof(vis)); 40 memset(pre,-1,sizeof(pre)); 41 queue<int>q;q.push(s);dist[s]=0; 42 while(!q.empty()) 43 { 44 int u=q.front();q.pop();vis[u]=0; 45 for(int i=head[u];i;i=g[i].nxt) 46 { 47 int v=g[i].to,f=g[i].f,w=g[i].w; 48 if(w&&dist[v]>dist[u]+f) 49 { 50 dist[v]=dist[u]+f; 51 pre[v].u=u;pre[v].id=i; 52 if(!vis[v])q.push(v),vis[v]=1; 53 } 54 } 55 } 56 return dist[t]!=inf; 57 } 58 59 I int EK() 60 { 61 int maxflow=0; 62 while(spfa()) 63 { 64 int mi=inf; 65 for(int i=t;i!=s;i=pre[i].u)mi=min(mi,g[pre[i].id].w); 66 for(int i=t;i!=s;i=pre[i].u)g[pre[i].id].w-=mi,g[pre[i].id^1].w+=mi; 67 maxflow+=mi;cost+=mi*dist[t]; 68 } 69 return maxflow; 70 } 71 72 int main() 73 { 74 n=read();m=read();s=read();t=read(); 75 for(int i=1;i<=m;i++) 76 { 77 int x=read(),y=read(),w=read(),f=read(); 78 addedge(x,y,w,f);addedge(y,x,0,-f); 79 } 80 printf("%d ",EK());printf("%d",cost); 81 }
单源最短路径(dijkstra)
关于spfa，
它死了
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=200010; 4 struct node 5 { 6 int pos,dis; 7 bool operator < (const node &x)const 8 { 9 return dis>x.dis; 10 } 11 }; 12 priority_queue<node>q; 13 struct edge 14 { 15 int next,to,dis; 16 }g[N]; 17 int head[N],cnt; 18 int n,m,s; 19 20 inline void addedge(int u,int v,int dis) 21 { 22 g[++cnt].next=head[u]; 23 g[cnt].to=v; 24 g[cnt].dis=dis; 25 head[u]=cnt; 26 } 27 28 bool vis[maxn]; 29 int dis[maxn]; 30 31 void dijkstra(int x) 32 { 33 for(int i=1;i<=n;i++) 34 { 35 dis[i]=2147483647;vis[i]=0; 36 } 37 q.push((node){x,0}); 38 dis[x]=0; 39 while(!q.empty()) 40 { 41 int u=q.top().pos;q.pop(); 42 if(vis[u])continue; 43 vis[u]=1; 44 for(int i=head[u];i;i=g[i].next) 45 { 46 int v=g[i].to; 47 if(dis[v]>dis[u]+g[i].dis) 48 { 49 dis[v]=dis[u]+g[i].dis; 50 if(!vis[v]) 51 { 52 q.push((node){v,dis[v]}); 53 } 54 } 55 } 56 } 57 } 58 int main() 59 { 60 scanf("%d%d%d",&n,&m,&s); 61 for(int i=1;i<=m;i++) 62 { 63 int x,y,z; 64 scanf("%d%d%d",&x,&y,&z); 65 addedge(x,y,z); 66 } 67 dijkstra(s); 68 for(int i=1;i<=n;i++) 69 { 70 cout<<dis[i]<<" "; 71 } 72 }
静态区间第k小（主席树）
自我感觉主席树写的挺美观qwq，注意时间关系，离散化下标，前缀和和线段树二分思想
1 #include<bits/stdc++.h> 2 #define smid (l+r>>1) 3 #define I inline 4 using namespace std; 5 const int N=2e5+10; 6 I int read() 7 { 8 int x=0,f=1;char ch=getchar(); 9 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 10 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 11 return x*f; 12 } 13 int sum[N<<5],ls[N<<5],rs[N<<5],T[N],cnt; 14 int n,m,d,a[N],b[N]; 15 16 I void bt(int &now,int l,int r) 17 { 18 now=++cnt;if(l==r)return; 19 bt(ls[now],l,smid);bt(rs[now],smid+1,r); 20 } 21 22 I void modify(int &now,int pre,int l,int r,int pos) 23 { 24 now=++cnt;sum[now]=sum[pre]+1;ls[now]=ls[pre];rs[now]=rs[pre]; 25 if(l==r)return; 26 if(pos<=smid)modify(ls[now],ls[pre],l,smid,pos); 27 else modify(rs[now],rs[pre],smid+1,r,pos); 28 } 29 30 I int query(int now,int pre,int l,int r,int k) 31 { 32 if(l==r)return b[l]; 33 int s=sum[ls[now]]-sum[ls[pre]]; 34 if(s>=k)return query(ls[now],ls[pre],l,smid,k); 35 else return query(rs[now],rs[pre],smid+1,r,k-s); 36 } 37 38 int main() 39 { 40 n=read();m=read(); 41 for(int i=1;i<=n;i++)a[i]=read(),b[i]=a[i]; 42 sort(b+1,b+1+n);d=unique(b+1,b+1+n)-b-1; 43 bt(T[0],1,d); 44 for(int i=1;i<=n;i++) 45 { 46 int x=lower_bound(b+1,b+1+d,a[i])-b; 47 modify(T[i],T[i-1],1,d,x); 48 } 49 while(m--) 50 { 51 int l=read(),r=read(),k=read(); 52 printf("%d ",query(T[r],T[l-1],1,d,k)); 53 } 54 }
左偏树
不太可能会考，不用$dsu$的版本很好写，如果加了$dsu$，注意一下$pop时f[ls[x]]=f[rs[x]]=f[x]=merge(ls[x],rs[x])$，因为并查集可能有多个儿子，并不是二叉树，所以要把其他儿子的根通过x也变成新的merge(ls[x],rs[x])（画个菊花图模拟一下就好啦）
1 #include<bits/stdc++.h> 2 #define I inline 3 using namespace std; 4 const int N=100010; 5 I int read() 6 { 7 int x=0,f=1;char ch=getchar(); 8 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 9 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 10 return x*f; 11 } 12 int n,m; 13 int f[N],val[N],ls[N],rs[N],dist[N]; 14 15 I int getf(int x){return x==f[x]?x:f[x]=getf(f[x]);} 16 17 I int merge(int x,int y) 18 { 19 if(!x||!y)return x+y; 20 if(val[x]>val[y]||(val[x]==val[y]&&x>y))swap(x,y); 21 rs[x]=merge(rs[x],y); 22 f[rs[x]]=x; 23 if(dist[ls[x]]<dist[rs[x]])swap(ls[x],rs[x]); 24 dist[x]=dist[rs[x]]+1; 25 return x; 26 } 27 28 I void pop(int x) 29 { 30 val[x]=-1;f[ls[x]]=f[rs[x]]=f[x]=merge(ls[x],rs[x]); 31 } 32 33 int main() 34 { 35 n=read();m=read();for(int i=1;i<=n;i++)val[i]=read(); 36 dist[0]=-1;for(int i=1;i<=n;i++)f[i]=i; 37 while(m--) 38 { 39 int cid=read(); 40 if(cid==1) 41 { 42 int x=read(),y=read(); 43 int r1=getf(x),r2=getf(y); 44 if(val[x]==-1||val[y]==-1)continue; 45 if(r1==r2)continue; 46 f[r1]=f[r2]=merge(r1,r2); 47 } 48 if(cid==2) 49 { 50 int x=read(); 51 if(val[x]==-1){puts("-1");continue;} 52 int r=getf(x);printf("%d ",val[r]); 53 pop(r); 54 } 55 } 56 }
LCT
注意画图模拟，，，顺序：$access->splay->rotate->nroot->pushup->pushdown->reverse->makeroot->link->split->cut$
注意修改点权时，要把点移动到splay的根，这样没有影响
1 #include<bits/stdc++.h> 2 #define ls(x) ch[x][0] 3 #define rs(x) ch[x][1] 4 #define I inline 5 using namespace std; 6 const int N=100010; 7 I int read() 8 { 9 int x=0,f=1;char ch=getchar(); 10 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 11 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 12 return x*f; 13 } 14 int n,m; 15 int val[N],sum[N],ch[N][2],f[N],sta[N]; 16 bool rev[N]; 17 18 I void pushup(int x){sum[x]=val[x]^sum[ls(x)]^sum[rs(x)];} 19 20 I bool nroot(int x){return ls(f[x])==x||rs(f[x])==x;} 21 22 I void reverse(int x){rev[x]^=1;swap(ls(x),rs(x));} 23 24 I void pushdown(int x) 25 { 26 if(!rev[x])return; 27 if(ls(x))reverse(ls(x)); 28 if(rs(x))reverse(rs(x)); 29 rev[x]=0; 30 } 31 32 I void rotate(int x) 33 { 34 int y=f[x],z=f[y],k=rs(y)==x,w=ch[x][!k]; 35 if(nroot(y))ch[z][rs(z)==y]=x;ch[x][!k]=y;ch[y][k]=w; 36 if(w)f[w]=y;f[x]=z;f[y]=x;pushup(y); 37 } 38 39 I void splay(int x) 40 { 41 int y=x,z=1;sta[z]=y; 42 while(nroot(y))sta[++z]=y=f[y]; 43 while(z)pushdown(sta[z--]); 44 while(nroot(x)) 45 { 46 y=f[x];z=f[y]; 47 if(nroot(y))rotate((ls(y)==x)^(ls(z)==y)?x:y); 48 rotate(x); 49 }pushup(x); 50 } 51 52 I void access(int x) 53 { 54 for(int y=0;x;y=x,x=f[x]) 55 splay(x),rs(x)=y,pushup(x); 56 } 57 58 I int findroot(int x) 59 { 60 access(x);splay(x); 61 while(ls(x))pushdown(x),x=ls(x); 62 splay(x); 63 return x; 64 } 65 66 I void makeroot(int x){access(x);splay(x);reverse(x);} 67 68 I void link(int x,int y){makeroot(x);if(findroot(y)!=x)f[x]=y;} 69 70 I void split(int x,int y){makeroot(x);access(y);splay(y);} 71 72 I void cut(int x,int y) 73 { 74 makeroot(x); 75 if(findroot(y)==x&&f[y]==x&&!ls(y))f[y]=rs(x)=0,pushup(x); 76 } 77 78 int main() 79 { 80 n=read();m=read();for(int i=1;i<=n;i++)val[i]=read(); 81 while(m--) 82 { 83 int op=read(),x=read(),y=read(); 84 if(op==0)split(x,y),printf("%d ",sum[y]); 85 if(op==1)link(x,y); 86 if(op==2)cut(x,y); 87 if(op==3)splay(x),val[x]=y; 88 } 89 }
欧拉路径（欧拉图的遍历)
从$degree$为奇数的点开始（由欧拉路径性质），每次遍历出边中序号字典序最小的点（题目要求），并把这条双向边删掉，用$stack$存一下即可
1 #include <cstdio> 2 #include <algorithm> 3 #include <iostream> 4 #include <stack> 5 using namespace std; 6 const int maxn = 1031; 7 int G[maxn][maxn],du[maxn]; 8 int n,m; 9 stack<int>S; 10 void dfs(int u) 11 { 12 for(int v=1;v<=n;v++) 13 if(G[u][v]) 14 { 15 G[u][v]--; 16 G[v][u]--; 17 dfs(v); 18 } 19 S.push(u); 20 } 21 int main(){ 22 23 cin>>m; 24 int u,v; 25 for(int i=1;i<=m;i++){ 26 cin>>u>>v; 27 n=max(n,u); 28 n=max(n,v); 29 G[u][v]++; 30 G[v][u]++; 31 du[u]++; 32 du[v]++; 33 } 34 int s=1; 35 for(int i=1;i<=n;i++) 36 if(du[i]%2==1) 37 { 38 s=i; 39 break; 40 } 41 dfs(s); 42 while(!S.empty()) 43 { 44 cout<<S.top()<<endl; 45 S.pop(); 46 } 47 return 0; 48 }
三维偏序（CDQ分治)
考虑两个排好序的序列合并，前面的对后面的做贡献
1 #include<bits/stdc++.h> 2 #define I inline 3 #define lowbit(x) (x&-x) 4 using namespace std; 5 const int N=100010; 6 I int read() 7 { 8 int x=0,f=1;char ch=getchar(); 9 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 10 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 11 return x*f; 12 } 13 14 struct node 15 { 16 int a,b,c,f,w; 17 }q[N],t[N]; 18 int ans[N]; 19 int n,m; 20 int bit[N<<1]; 21 22 I void add(int pos,int val) 23 { 24 while(pos<=m)bit[pos]+=val,pos+=lowbit(pos); 25 } 26 I int query(int pos) 27 { 28 int res=0; 29 while(pos)res+=bit[pos],pos-=lowbit(pos); 30 return res; 31 } 32 33 I bool cmp(node a,node b) 34 { 35 return a.a==b.a?(a.b==b.b?a.c<b.c:a.b<b.b):a.a<b.a; 36 } 37 38 I void cdq(int l,int r) 39 { 40 if(l==r)return; 41 int mid=(l+r>>1); 42 cdq(l,mid);cdq(mid+1,r); 43 int i=l,j=mid+1,k=l; 44 while(i<=mid&&j<=r) 45 { 46 if(q[i].b<=q[j].b)add(q[i].c,q[i].w),t[k++]=q[i++]; 47 else q[j].f+=query(q[j].c),t[k++]=q[j++]; 48 } 49 while(i<=mid)add(q[i].c,q[i].w),t[k++]=q[i++]; 50 while(j<=r)q[j].f+=query(q[j].c),t[k++]=q[j++]; 51 for(i=l;i<=mid;i++)add(q[i].c,-q[i].w); 52 for(i=l;i<=r;i++)q[i]=t[i]; 53 } 54 55 int main() 56 { 57 n=read();m=read(); 58 for(int i=1;i<=n;i++) 59 { 60 q[i].a=read();q[i].b=read();q[i].c=read();q[i].w=1; 61 } 62 sort(q+1,q+1+n,cmp); 63 int cnt=1; 64 for(int i=2;i<=n;i++) 65 { 66 if(q[cnt].a==q[i].a&&q[cnt].b==q[i].b&&q[cnt].c==q[i].c)q[cnt].w++; 67 else q[++cnt]=q[i]; 68 } 69 cdq(1,cnt); 70 for(int i=1;i<=cnt;i++)ans[q[i].f+q[i].w-1]+=q[i].w; 71 for(int i=0;i<n;i++)printf("%d ",ans[i]); 72 }
单调栈求最大子矩阵
维护$pre[i][j]表示(i,j)$向上最远的没被占领的地方，用一个递增单调栈维护每列的高h和往左最远的不小于它高度的列，加入$h$时，若$h$比栈顶小，则计算，并更新往左的最远列，否则入栈。
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 using namespace std; 6 const int N=2010; 7 struct node 8 { 9 int h,x; 10 }s[N]; 11 int a[N][N]; 12 int n,m; 13 int ans; 14 int pre[N][N]; 15 16 int main() 17 { 18 scanf("%d%d",&n,&m); 19 for(int i=1;i<=n;i++) 20 for(int j=1;j<=m;j++) 21 { 22 char x; 23 cin>>x; 24 if(x=='F') 25 { 26 pre[i][j]=pre[i-1][j]+1; 27 } 28 } 29 for(int i=1;i<=n;i++) 30 { 31 int top=0; 32 for(int j=1;j<=m+1;j++) 33 { 34 int xx=j; 35 while(pre[i][j]<=s[top].h&&top) 36 { 37 if(s[top].h)ans=max(ans,s[top].h*(j-s[top].x)); 38 xx=s[top].x; 39 top--; 40 } 41 top++; 42 s[top].h=pre[i][j];s[top].x=xx; 43 } 44 }cout<<ans*3; 45 }
高精度
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=20010; 4 char tmp[N]; 5 struct bigint 6 { 7 int num[N]; 8 int l; 9 }x,y,z; 10 11 bigint operator + (bigint a,bigint b) 12 { 13 bigint c;c.l=1; 14 int x=0; 15 while(c.l<=a.l||c.l<=b.l) 16 { 17 c.num[c.l]=a.num[c.l]+b.num[c.l]+x;//Õý³£¼Ó 18 x=c.num[c.l]/10;c.num[c.l]%=10;//½øλ 19 c.l++; 20 } 21 c.num[c.l]=x;//×îºóһλ½øµô£¨²»¹ÜÓÐûÓнø£© 22 if(c.num[c.l]==0)c.l--;//È¥0 23 return c; 24 } 25 26 bigint operator - (bigint a,bigint b) 27 { 28 if(a.l<b.l)swap(a,b),cout<<"-";//¸ºÊý 29 for(int i=1;i<=a.l;i++) 30 { 31 a.num[i]=a.num[i]-b.num[i];//Õý³£¼õ 32 if(a.num[i]<0)a.num[i]+=10,a.num[i+1]--;//½èλ 33 } 34 while(a.num[a.l]==0&&a.l>1)a.l--;//È¥0 35 return a; 36 } 37 38 bigint operator * (bigint a,bigint b) 39 { 40 bigint c;c.l=a.l+b.l; 41 for(int i=1;i<=a.l;i++) 42 for(int j=1;j<=b.l;j++) 43 c.num[i+j-1]+=a.num[i]*b.num[j]; 44 for(int i=1;i<c.l;i++)if(c.num[i]>9)c.num[i+1]+=c.num[i]/10,c.num[i]%=10; 45 while(!c.num[c.l]&&c.l>1)c.l--; 46 return c; 47 } 48 49 inline void print(bigint x) 50 { 51 for(int i=x.l;i>=1;i--) 52 cout<<x.num[i]; 53 } 54 55 int main() 56 { 57 //Õý¶Á×Ö·û£¬·´×ªÊý×飬´ÓµÍλ¿ªÊ¼´¦Àí 58 cin>>tmp;x.l=strlen(tmp);for(int i=0;i<x.l;i++)x.num[x.l-i]=tmp[i]-'0'; 59 cin>>tmp;y.l=strlen(tmp);for(int i=0;i<y.l;i++)y.num[y.l-i]=tmp[i]-'0'; 60 //z=x+y;print(z); 61 //z=x-y;print(z); 62 z=x*y;print(z); 63 }
最长上升（不上升）子序列(nlogn)
d数组为满足的合法序列，用贪心的思路对于使len相等的多个元素，以最小（大）的结尾一定是最优的
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=100010; 4 int a[N],d1[N],d2[N],n; 5 int len1,len2; 6 7 int main() 8 { 9 while(cin>>a[++n]);n--; 10 d1[1]=a[1];d2[1]=a[1]; 11 len1=len2=1; 12 for(int i=2;i<=n;i++) 13 { 14 if(d1[len1]>=a[i])d1[++len1]=a[i]; 15 else 16 { 17 int tmp=upper_bound(d1+1,d1+1+len1,a[i],greater<int>())-d1; 18 d1[tmp]=a[i]; 19 } 20 if(d2[len2]<a[i])d2[++len2]=a[i]; 21 else 22 { 23 int tmp=lower_bound(d2+1,d2+1+len2,a[i])-d2; 24 d2[tmp]=a[i]; 25 } 26 } 27 cout<<len1<<endl<<len2; 28 }
最长公共子序列（nlogn)
考虑LIS为一个数列和{1,2,3...n}的LCS，那么我们也可以把LCS转化为LIS，具体做法：用$b$中的$a[i],a[j]$的相对位置来重新定义$a[i]和a[j]$的大小关系。这样我们维护m[b[i]]=i的一个映射，如果$m[a[i]]<m[a[j]]$那么我们认为$“a[i]<a[j]”$。
1 #include<bits/stdc++.h> 2 #define I inline 3 using namespace std; 4 const int N=100010; 5 typedef long long ll; 6 const int inf=2147483647; 7 I int read() 8 { 9 int x=0,f=1;char ch=getchar(); 10 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 11 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 12 return x*f; 13 } 14 15 int n,a[N],b[N],m[N],f[N],ans; 16 17 int main() 18 { 19 n=read(); 20 for(int i=1;i<=n;i++)a[i]=read(),f[i]=inf; 21 for(int i=1;i<=n;i++)b[i]=read(),m[b[i]]=i; 22 f[1]=a[1];ans=1; 23 for(int i=2;i<=n;i++) 24 { 25 if(m[a[i]]>f[ans]){f[++ans]=m[a[i]];continue;} 26 int tmp=lower_bound(f+1,f+1+ans,m[a[i]])-f; 27 f[tmp]=m[a[i]]; 28 } 29 cout<<ans; 30 }
字典树求异或最大值
1 void insert(int x) 2 { 3 int u=1; 4 for(int i=(1<<30);i;i>>=1) 5 { 6 bool c=(i&x)?1:0; 7 if(!ch[u][c])ch[u][c]=++cnt; 8 u=ch[u][c]; 9 } 10 } 11 12 int query(int x) 13 { 14 int u=1,res=0; 15 for(int i=(1<<30);i;i>>=1) 16 { 17 bool c=(i&x)?0:1; 18 if(ch[u][c])res+=i,u=ch[u][c]; 19 else u=ch[u][!c]; 20 }return res; 21 }