-
个人简介
-std=c++11 -O2 -Wl,--stack=123456789
代码
剪贴板:
/* (x-y)(x^2+y^2+xy) (x-y)((x-y)^2+3xy) a=x-y,b=xy a(a^2+3b) (x-y)^2=x^2+y^2-2xy; (x+y)^2=x^2+y^2+2xy; */
weq是机房J霸!!!
代码模板
【模板】单源最短路径(标准版)
#include<bits/stdc++.h> using namespace std; const int N=1e5+114; int n,m,dis[N],s; struct node { int x,z; }; struct nod { int x,z; }; vector<nod> adj[N]; bool operator <(node x,node y){return x.z>y.z;} bool flag[N]; void dij() { priority_queue<node> q; q.push({s,0}); memset(flag,0,sizeof flag); memset(dis,0x3f,sizeof dis); dis[s]=0; while(!q.empty()) { node t=q.top(); q.pop(); if(flag[t.x])continue; flag[t.x]=1; for(auto it:adj[t.x]) { if(dis[it.x]>dis[t.x]+it.z) { dis[it.x]=dis[t.x]+it.z; if(!flag[it.x])q.push({it.x,dis[it.x]}); } } } } int main() { // freopen("P4779_1.in","r",stdin); // freopen("P4779__1.out","w",stdout); cin>>n>>m>>s; for(int i=1;i<=m;i++) { int x,y,z; cin>>x>>y>>z; adj[x].push_back({y,z}); } dij(); for(int i=1;i<=n;i++)cout<<dis[i]<<' '; return 0; }
双hash
#include<bits/stdc++.h> using namespace std; #define maxn 1000005 typedef long long ll; typedef long double ld; int mod1,base1,power1[maxn],h1[maxn]; int mod2,base2,power2[maxn],h2[maxn]; int n,m; char s[maxn]; inline int read() { int x=0,f=1; char ch=getchar(); for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1; for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; return x*f; } void build1() { for (int i=1;i<=n;i++) h1[i]=1ll*h1[i-1]*base1%mod1+s[i]-'a'; power1[0]=1; for (int i=1;i<=n;i++) power1[i]=1ll*power1[i-1]*base1%mod1; } bool check1(int l1,int r1,int l2,int r2) { int len=r1-l1+1; int h11=((h1[r1]-1ll*h1[l1-1]*power1[len]%mod1)+mod1)%mod1; int h21=((h1[r2]-1ll*h1[l2-1]*power1[len]%mod1)+mod1)%mod1; return h11==h21; } void build2() { for (int i=1;i<=n;i++) h2[i]=1ll*h2[i-1]*base2%mod2+s[i]-'a'; power2[0]=1; for (int i=1;i<=n;i++) power2[i]=1ll*power2[i-1]*base2%mod2; } bool check2(int l1,int r1,int l2,int r2) { int len=r1-l1+1; int h12=((h2[r1]-1ll*h2[l1-1]*power2[len]%mod2)+mod2)%mod2; int h22=((h2[r2]-1ll*h2[l2-1]*power2[len]%mod2)+mod2)%mod2; return h12==h22; } int main() { mod1=998244353,mod2=666623333; base1=233,base2=431; scanf("%s",s+1); n=strlen(s+1); build1(),build2(); int id=0; for (int T=read();T;T--) { ++id; int l1=read(),r1=read(),l2=read(),r2=read(); if (r1-l1+1!=r2-l2+1) { puts("No"); continue; } puts((check1(l1,r1,l2,r2)&&check2(l1,r1,l2,r2))?"Yes":"No"); } return 0; }
可持久化线段树(主席树)
#include<bits/stdc++.h> #define int long long #define debug(a) cout<<#a<<':'<<a<<endl; using namespace std; const int N=100114,M=32; int n,m,a[N],sum[N*M],lc[N*M],rc[N*M],cnt,b[N],rt[N],p; void build(int &k,int l,int r) { k=++cnt; sum[k]=0; if(l==r)return; int mid=l+r>>1; build(lc[k],l,mid); build(rc[k],mid+1,r); } int jia(int k,int l,int r) { int xin=++cnt; lc[xin]=lc[k],rc[xin]=rc[k],sum[xin]=sum[k]+1; if(l==r)return xin; int mid=l+r>>1; if(p<=mid)lc[xin]=jia(lc[k],l,mid); else rc[xin]=jia(rc[k],mid+1,r); return xin; } int xunwen(int u,int v,int l,int r,int k) { int x=sum[lc[v]]-sum[lc[u]]; if(l==r)return l; int mid=l+r>>1; if(k<=x)return xunwen(lc[u],lc[v],l,mid,k); else return xunwen(rc[u],rc[v],mid+1,r,k-x); } signed main() { cin>>n>>m; for(int i=1;i<=n;i++)cin>>a[i],b[i]=a[i]; sort(b+1,b+1+n); int q=unique(b+1,b+1+n)-b-1; build(rt[0],1,q); for(int i=1;i<=n;i++) { p=lower_bound(b+1,b+1+q,a[i])-b; rt[i]=jia(rt[i-1],1,q); } while(m--) { int x,y,z; cin>>x>>y>>z; cout<<b[xunwen(rt[x-1],rt[y],1,q,z)]<<endl; } return 0; }
C(n,m)的求法
暴力
int C(int n,int m) { int ans=1; for(int i=n-m+1;i<=n;i++)ans*=i; int sum=1; for(int i=m;i>=1;i--)sum*=i; ans/=sum; return ans; }
优化
int C(int n,int m) { int ans=1; int t=n; int b=1; for(int i=1;i<=m;i++) { ans=ans*t/b; t--;b++; } return ans; }
超快速
int qpow(int a,int b,int p) { int res=1; while(b) { if(b&1) res=(a*res)%p; a*=a; a%=p; b>>=1; } return res; } void ff() { fac[0]=1; for(int i=1;i<=100000;i++)fac[i]=fac[i-1]*i%mod; } int C(int n,int m) { return (fac[n]*qpow(fac[n-m],mod-2,mod)%mod*qpow(fac[m],mod-2,mod)%mod)%mod; }
快速幂
int qpow(int a,int b,int p) { int res=1; while(b) { if(b&1) res=(a*res)%p; a*=a; a%=p; b>>=1; } return res; } ((qpow(m,n+1,mod)-1+mod)%mod*qpow(m-1,mod-2,mod)%mod-1+mod)%mod//等比数列求和公式
扩欧
扩欧 void ojld(int a,int b) { if(b==0) { jx=1,jy=0; return; } ojld(b,a%b); int tx=jx; jx=jy; jy=tx-a/b*jy; }
鼠据生成:
#include<bits/stdc++.h> using namespace std; char a[10]; int top; void ddd(int x) { top=0; a[top]='c'; a[++top]='c'; string s=""; while(x) { s+=(x%10)+'0'; x/=10; } reverse(s.begin(),s.end()); for(int i=0;i<s.size();i++) { a[++top]=s[i]; } a[++top]='.'; a[++top]='o'; a[++top]='u'; a[++top]='t'; } int main() { for(int i=1;i<=800;i++) { freopen("c1.out","r",stdin); ddd(i); freopen(a,"w",stdout); for(int j=1;j<=800;j++) { int x; cin>>x; if(i==j) { cout<<x<<endl; break; } } fclose(stdin); fclose(stdout); } return 0; }
tarjan
//tarjan #include<bits/stdc++.h> typedef long long ll; //#define int long long using namespace std; const int N=1e5+114; int n,m,dfn[N],low[N],tot,ans; vector<int> adj[N],what[N]; stack<int> st; int flag[N]; void tarjan(int u) { dfn[u]=low[u]=++tot; st.push(u); for(auto it : adj[u]) { if(!dfn[it]) { tarjan(it); low[u]=min(low[u],low[it]); } else if(!flag[it]) { low[u]=min(low[u],dfn[it]); } } if(dfn[u]==low[u]) { ans++; flag[u]=ans; what[ans].push_back(u); while(st.top()!=u) { flag[st.top()]=ans; what[ans].push_back(st.top()); st.pop(); } st.pop(); } } int main() { cin>>n>>m; for(int i=1;i<=m;i++) { int x,y; cin>>x>>y; adj[x].push_back(y); } for(int i=1;i<=n;i++) { if(!dfn[i]) { tarjan(i); } } int ab=0; for(int i=1;i<=ans;i++) { if(what[i].size()>1)ab++; } cout<<ab; return 0; } //求割点 //tarjan #include<bits/stdc++.h> typedef long long ll; #define int long long using namespace std; //A const int N=1e5+114; int n,m,dfn[N],low[N],tot,ans,sbsb,hi; vector<int> adj[N],what[N]; set<int> anss; stack<int> st; int flag[N]; void tarjan(int u,int fa) { dfn[u]=low[u]=++tot; st.push(u);int son=0; for(auto it : adj[u]) { if(!dfn[it]) { son++; tarjan(it,u); low[u]=min(low[u],low[it]); if(low[it]>=dfn[u] && it!=fa && hi!=u && !(anss.count(u))) { sbsb++; anss.insert(u); } } else { low[u]=min(low[u],dfn[it]); } } if(hi==u && son>=2) { sbsb++; anss.insert(u); } } signed main() { cin>>n>>m; for(int i=1;i<=m;i++) { int x,y; cin>>x>>y; adj[x].push_back(y); adj[y].push_back(x); } for(int i=1;i<=n;i++) { if(!dfn[i]) { hi=i; tarjan(i,0); } } cout<<sbsb<<endl; for(auto it: anss) { cout<<it<<' '; } return 0; } //求割边(有重边时) #include<bits/stdc++.h> using namespace std; const int N=30114; int n,m; vector<int> adj[N]; int low[N],dfn[N],flag[N],tot,idx; void tarjan(int u,int fa) { bool sb=0; low[u]=dfn[u]=++idx; for(auto it:adj[u]) { if(!dfn[it]) { tarjan(it,u); low[u]=min(low[u],low[it]); if(low[it]>dfn[u]) { tot++; flag[it]=1; } } else { if(it!=fa || sb) { low[u]=min(low[u],dfn[it]); } else sb=1; } } } int main() { while(cin>>n>>m && !(n==0 && m==0)) { for(int i=1;i<=m;i++) { int x,y; cin>>x>>y; adj[x].push_back(y); adj[y].push_back(x); } tarjan(1,-1); cout<<tot<<endl; for(int i=1;i<=n;i++)adj[i].clear(); memset(low,0,sizeof low); memset(dfn,0,sizeof dfn); tot=0; } return 0; } //边双连通分量(可以用上面的代码改一下) #include<bits/stdc++.h> #define inf 0x3f3f3f3f using namespace std; int n,m,dfn[2000010],low[2000010],bel[2000010],ecc; int shijian; stack<int> st; vector<int> adj[4000001]; int head[2000001],ans=1; struct node { int nxt,v; }e[4000001]; bool flag[4000001]; int jj; void add(int x,int y) { e[++ans].v=y; e[ans].nxt=head[x]; head[x]=ans; } void tarjan(int u,int edg) { st.push(u); dfn[u]=low[u]=++shijian; for(int i=head[u];i!=-1;i=e[i].nxt) { int t=e[i].v; if(!dfn[t]) { tarjan(t,i); low[u]=min(low[u],low[t]); if(low[t]>dfn[u]) { flag[i]=flag[i^1]=1; } } else if(i!=(edg^1))//所以不要走到他的父亲节点去了,解释在下面 { low[u]=min(low[u],dfn[t]); } } } void dfs(int u) { bel[u]=ecc; adj[ecc].push_back(u); for(int i=head[u];i!=-1;i=e[i].nxt) { int t=e[i].v; if(bel[t] || flag[i])continue; dfs(t); } } int main() { //freopen("name.in","r",stdin); //freopen("name.out","w",stdout); cin>>n>>m; memset(head,-1,sizeof(head)); for(int i=1;i<=m;i++) { //✔✘▓※ int x,y; cin>>x>>y;//解释 add(x,y);//如果ans=3 add(y,x);//那么这一行执行完后ans=4 //他们是相对的 } for(int i=1;i<=n;i++) { if(!dfn[i])tarjan(i,0); } for(int i=1;i<=n;i++) { if(!bel[i]) { ecc++; dfs(i); } } cout<<ecc<<endl; for(int i=1;i<=ecc;i++) { cout<<adj[i].size(); for(int j=0;j<adj[i].size();j++)cout<<" "<<adj[i][j]; cout<<endl; } return 0; } //点双连通分量 #include<bits/stdc++.h> #define inf 0x3f3f3f3f using namespace std; int n,m,dfn[500010],low[500010],bel[500010],abab; int shijian; stack<int> st; vector<int> ans[1000001]; vector<int> adj[500010]; bool flag[1000001],vis[1000001]; int jj; void tarjan(int u,int fa) { st.push(u); dfn[u]=low[u]=++shijian; if(fa==0 && adj[u].size()==0) { ans[++abab].push_back(u); return; } for(int i=0;i<adj[u].size();i++) { int t=adj[u][i]; if(!dfn[t]) { tarjan(t,u); low[u]=min(low[u],low[t]); if(low[t]>=dfn[u]) { abab++; while(st.top()!=t) { ans[abab].push_back(st.top()); st.pop(); } ans[abab].push_back(t); st.pop(); ans[abab].push_back(u); } } else if(t!=fa) { low[u]=min(low[u],dfn[t]); } } } int main() { //freopen("name.in","r",stdin); //freopen("name.out","w",stdout); cin>>n>>m;//K for(int i=1;i<=m;i++) { //✔✘▓※ int x,y; cin>>x>>y; if(x == y) continue; adj[x].push_back(y); adj[y].push_back(x); } for(int i=1;i<=n;i++) { if(!dfn[i])tarjan(i,0); while(!st.empty())st.pop(); } cout<<abab<<endl; for(int i=1;i<=abab;i++) { cout<<ans[i].size(); for(int j=0;j<ans[i].size();j++)cout<<" "<<ans[i][j]; cout<<endl; } return 0; }
树的重心
//树的重心 #include<bits/stdc++.h> using namespace std; const int N=20114; int n; vector<int> adj[N]; int siz[N],msz[N]; void dfs(int u,int fa) { siz[u]=1; for(auto it : adj[u]) { if(it==fa)continue; dfs(it,u); siz[u]+=siz[it]; msz[u]=max(msz[u],siz[it]); } msz[u]=max(msz[u],n-siz[u]); } int main() { cin>>n; for(int i=1;i<n;i++) { int x,y; cin>>x>>y; adj[x].push_back(y); adj[y].push_back(x); } dfs(1,0); bool flag=0; for(int i=1;i<=n;i++) { if(msz[i]<=n/2) { flag=1; cout<<i<<endl; } } if(!flag)cout<<"NONE"; return 0; }
树状数组
#include<bits/stdc++.h> #define int long long using namespace std; int n,a[1000001],ans,t[1000001],number[1000001]; int lowbit(int x) { return x & -x; } void add(int x,int y) { for(;x<=n;x+=lowbit(x))t[x]+=y; } int ask(int x) { int sum=0; for(;x;x-=lowbit(x))sum+=t[x]; return sum; } signed main() { cin>>n; for(int i=1;i<=n;i++)cin>>a[i],a[i]++; for(int i=1;i<=n;i++) { ans+=a[i]-ask(a[i])-1; add(a[i],1); } cout<<ans<<endl; for(int i=1;i<n;i++) { ans-=ask(a[i])-1; ans+=n-ask(a[i]); cout<<ans<<endl; } return 0; }
离散化
#include<bits/stdc++.h>//I #define inf 0x3f3f3f3f using namespace std; int n,b[100001],maxn; int l[100001],r[100001],g[300001],cnt; int main() { cin>>n; for(int i=1;i<=n;i++) { cin>>l[i]>>r[i];g[++cnt]=l[i],g[++cnt]=r[i]; } sort(g+1,g+1+cnt); for(int i=1;i<=n;i++) { int lll=lower_bound(g+1,g+1+cnt,l[i])-g; int rrr=lower_bound(g+1,g+1+cnt,r[i])-g; b[lll]++; b[rrr+1]--; } int maxnn=0; for(int i=1;i<=cnt;i++)b[i]+=b[i-1],maxnn=max(maxnn,b[i]); cout<<maxnn<<endl; return 0; }
二维差分
#include<bits/stdc++.h> #define inf 0x3f3f3f3f using namespace std; int n,k,b[3001][3001],a[3001][3001]; int main() { cin>>n; while(n--) { int l,r,ll,rr; cin>>l>>ll>>r>>rr; if(ll<l)swap(l,ll); if(rr<r)swap(r,rr); l++,r++; b[l][r]++; b[l][rr+1]--; b[ll+1][r]--; b[ll+1][rr+1]++; } int c=0; for(int i=1;i<=100;i++) { for(int j=1;j<=100;j++) { a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+b[i][j]; if(a[i][j]>=1)c++; } } cout<<c; return 0; }
线段树
//线段树 //我现在的模板 #include<bits/stdc++.h> #define int long long #define debug(a) cout<<#a<<':'<<a<<endl; using namespace std; const int N=100005; int n,k,a[N],maxn,minn; struct { int mx,mn; }tr[N*4]; void build(int num,int l,int r) { if(l==r) { tr[num]={a[l],a[r]}; return; } int mid=l+r>>1; build(num*2,l,mid); build(num*2+1,mid+1,r); tr[num].mx=max(tr[num*2].mx,tr[num*2+1].mx); tr[num].mn=min(tr[num*2].mn,tr[num*2+1].mn); } void qunwen(int num,int l,int r,int x,int y) { if(x<=l && r<=y) { maxn=max(maxn,tr[num].mx); minn=min(minn,tr[num].mn); return; } int mid=l+r>>1; if(mid>=x)qunwen(num*2,l,mid,x,y); if(mid<y)qunwen(num*2+1,mid+1,r,x,y); } signed main() { cin>>n>>k; for(int i=1;i<=n;i++)cin>>a[i]; build(1,1,n); for(int i=k;i<=n;i++) { maxn=-1e9,minn=1e9; qunwen(1,1,n,i-k+1,i); cout<<maxn<<' '<<minn<<endl; } return 0; } //以前的模板 #include <bits/stdc++.h> #define lson k << 1 #define rson k << 1 | 1 #define inf 0x3f3f3f3f using namespace std; typedef long long ll; const int maxn = 5e5 + 5; int a[maxn], n, m; struct node { // 线段树的结点 int l,r; ll val; } tree[maxn << 2]; void build(int k, int l, int r) { // 建树 tree[k].l=l,tree[k].r=r; if(l==r)tree[k].val=a[l]; else { int mid=l+r>>1; build(lson,l,mid); build(rson,mid+1,r); tree[k].val=tree[lson].val+tree[rson].val; } } void update(int k, int id, int val) { // a[id] += val if(tree[k].l==tree[k].r && tree[k].l==id) { tree[k].val=a[id]+val; a[id]+=val; return; } int mid=tree[k].l+tree[k].r>>1; if(id<=mid)update(lson,id,val); else update(rson,id,val); tree[k].val=tree[lson].val+tree[rson].val; } ll query(int k, int l, int r) { // 查询 a[l...r] 的区间和 int tl=tree[k].l,tr=tree[k].r; if(tl>=l && tr<=r)return tree[k].val; int mid=tl+tr>>1; ll ans=0; if(mid>=l)ans=ans+query(lson,l,r); if(mid+1<=r)ans=ans+query(rson,l,r); return ans; } int main() { cin>>n>>m; for(int i = 1; i <= n; ++i) cin>>a[i]; // 初始化建树 build(1,1,n); while(m--) { int op, x, y; cin>>op>>x>>y; if(op == 1) { update(1, x, y); } else { cout<<query(1, x, y)<<'\n'; } } return 0; } //加lazy #include <bits/stdc++.h> #define lson k << 1 #define rson k << 1 | 1 using namespace std; typedef long long ll; const int maxn = 1e5 + 5; ll a[maxn], n, m; struct node {//O int l, r; ll sum, lazy; // lazy 惰性标记 } tree[maxn << 2]; void build(int k, int l, int r) { // 建树 tree[k].l=l,tree[k].r=r; tree[k].lazy=0; if(l==r)tree[k].sum=a[l]; else { int mid=l+r>>1; build(lson,l,mid); build(rson,mid+1,r); tree[k].sum=tree[lson].sum+tree[rson].sum; } } void pushdown(int k) { // 将 k 的 lazy 标记下传 if(tree[k].lazy) { tree[lson].sum+=tree[k].lazy*(tree[lson].r-tree[lson].l+1); tree[rson].sum+=tree[k].lazy*(tree[rson].r-tree[rson].l+1); tree[lson].lazy+=tree[k].lazy; tree[rson].lazy+=tree[k].lazy; tree[k].lazy=0; } } void update(int k, int l, int r, int val) { // a[l...r] += val int tl=tree[k].l,tr=tree[k].r; if(l<=tl && tr<=r) { tree[k].sum+=val*(tr-tl+1); //他是一个区间啊 tree[k].lazy+=val; return; } pushdown(k); int mid=tree[k].l+tree[k].r>>1; if(mid>=l)update(lson,l,r,val); if(mid+1<=r)update(rson,l,r,val); tree[k].sum=tree[lson].sum+tree[rson].sum; } ll query(int k, int l, int r) { // 查询 a[l...r] 的和 int tl=tree[k].l,tr=tree[k].r; if(tl>=l && tr<=r)return tree[k].sum; pushdown(k); int mid=tl+tr>>1; ll ans=0; if(mid>=l)ans=ans+query(lson,l,r); if(mid+1<=r)ans=ans+query(rson,l,r); return ans; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin>>n>>m; for(int i = 1; i <= n; ++i) cin>>a[i]; build(1, 1, n); while(m--) { int op, x, y, val; cin>>op>>x>>y; if(op == 1) { cin>>val; update(1, x, y, val); } else { cout<<query(1, x, y)<<'\n'; } } return 0; }
严格次小生成树
//严格次小生成树 #include<bits/stdc++.h> #define int long long #define inf 0x3f3f3f3f3f3f3f using namespace std; const int N=1e6+114,M=3e6+114; int n,m,fa[N]; struct node { int x,z; }; vector<node> adj[N]; struct nod { int x,y,z; }edge[M]; bool cmp(nod x,nod y) { return x.z<y.z; } int dep[N],tiao[N][51],fir[N][51],sec[N][51]; bool flag[N]; void dfs(int u,int fa,int de) { dep[u]=de; for(auto it:adj[u]) { if(it.x==fa)continue; tiao[it.x][0]=u; fir[it.x][0]=it.z; sec[it.x][0]=-inf; dfs(it.x,u,de+1); } } int lca(int xx,int yy) { if(dep[xx]<dep[yy])swap(xx,yy); for(int i=50;i>=0;i--) { if(dep[tiao[xx][i]]>=dep[yy]) { xx=tiao[xx][i]; } } if(xx==yy)return xx; for(int i=50;i>=0;i--) { if(tiao[xx][i]!=tiao[yy][i]) { xx=tiao[xx][i]; yy=tiao[yy][i]; } } return tiao[xx][0]; } int find(int x) { if(fa[x]==x)return fa[x]; return fa[x]=find(fa[x]); } int qunwen(int x,int y,int cost) { int ret=0; for(int i=50;i>=0;i--) { if(dep[tiao[x][i]]>=dep[y]) { if(cost==fir[x][i])ret=max(ret,sec[x][i]); else ret=max(ret,fir[x][i]); x=tiao[x][i]; } } return ret; } signed main() { cin>>n>>m; for(int i=1;i<=n;i++)fa[i]=i; for(int i=1;i<=m;i++) { int x,y,z; cin>>x>>y>>z; edge[i]={x,y,z}; } sort(edge+1,edge+1+m,cmp); int sum=0,ans=0; for(int i=1;i<=m;i++) { int x=edge[i].x,y=edge[i].y; int xx=find(x),yy=find(y); if(xx==yy)continue; adj[x].push_back({y,edge[i].z}); adj[y].push_back({x,edge[i].z}); ans++; sum+=edge[i].z; fa[xx]=yy; flag[i]=1; if(ans==n-1)break; } dfs(1,0,0); for(int j=1;j<=50;j++) { for(int i=1;i<=n;i++) { tiao[i][j]=tiao[tiao[i][j-1]][j-1]; int temp[4]={fir[i][j-1],sec[i][j-1],fir[tiao[i][j-1]][j-1],sec[tiao[i][j-1]][j-1]}; sort(temp,temp+4); fir[i][j]=temp[3]; sec[i][j]=temp[2]; if(fir[i][j]==sec[i][j])sec[i][j]=temp[1]; } } ans=inf; for(int i=1;i<=m;i++) { if(!flag[i]) { int x=edge[i].x; int y=edge[i].y; int lcaa=lca(x,y); int tttt=max(qunwen(x,lcaa,edge[i].z),qunwen(y,lcaa,edge[i].z)); ans=min(ans,sum+edge[i].z-tttt); } } cout<<ans; return 0; }
CSP-S2019树的重心
CSP2019树的重心 #include<bits/stdc++.h> #define int long long using namespace std; const int N=3e5+114; int T,son[N][2],siz[N],tiao[N][31],ans; vector<int> adj[N]; int n; void rrr(int u) { tiao[u][0]=son[u][0]; for(int i=1;i<=20;i++) { tiao[u][i]=tiao[tiao[u][i-1]][i-1]; } } void dfs(int u,int fa) { siz[u]=1; for(auto it: adj[u]) { if(it==fa)continue; dfs(it,u); siz[u]+=siz[it]; if(siz[it]>siz[son[u][0]]) { son[u][1]=son[u][0]; son[u][0]=it; } else if(siz[it]>siz[son[u][1]]) son[u][1]=it; } rrr(u); } void find(int u) { int t=u; for(int i=20;i>=0;i--) { if(siz[tiao[u][i]]>siz[t]/2) u=tiao[u][i]; } ans+=u; if(siz[t]%2==0) { u=tiao[u][0]; if(2*siz[u]==siz[t]) { ans+=u; } } } void run(int u,int fa) { int t1=son[u][0],t2=siz[u]; for(auto v:adj[u]) { if(v==fa)continue; if(v==t1) { son[u][0]=siz[son[u][1]]>n-t2?son[u][1]:fa; } else son[u][0]=siz[t1]>n-t2?t1:fa; siz[u]=n-siz[v]; rrr(u); find(u); find(v); run(v,u); } son[u][0]=t1; siz[u]=t2; rrr(u); } signed main() { cin>>T; while(T--) { memset(son,0,sizeof son); memset(siz,0,sizeof siz); memset(tiao,0,sizeof tiao); ans=0; cin>>n; for(int i=1;i<n;i++) { int x,y; cin>>x>>y; adj[x].push_back(y); adj[y].push_back(x); } dfs(1,0); run(1,0); cout<<ans<<endl; for(int i=1;i<=n;i++)adj[i].clear(); } return 0; }
树链剖分
#include<bits/stdc++.h> #define int long long using namespace std; int n,m,root; const int N=500005; vector<int> adj[N]; int dep[N],fa[N],son[N],top[N],siz[N]; void dfs1(int x) { siz[x]=1; for(auto it:adj[x]) { if(it==fa[x])continue; fa[it]=x; dep[it]=dep[x]+1; dfs1(it); if(siz[son[x]]<siz[it])son[x]=it; siz[x]+=siz[it]; } } void dfs2(int x) { if(!son[x])return; top[son[x]]=top[x]; dfs2(son[x]); for(auto it:adj[x]) { if(fa[x]==it || it==son[x])continue; top[it]=it; dfs2(it); } } int lca(int x,int y) { while(top[x]!=top[y]) { if(dep[top[x]]<dep[top[y]])swap(x,y); x=fa[top[x]]; } return dep[x]<dep[y]?x:y; } signed main() { cin>>n>>m>>root; for(int i=1;i<n;i++) { int x,y; cin>>x>>y; adj[x].push_back(y); adj[y].push_back(x); } dep[root]=1; dfs1(root); top[root]=root; dfs2(root); while(m--) { int x,y; cin>>x>>y; printf("%d\n",lca(x,y)); } return 0; }
同余最短路&&跳楼机
#include<bits/stdc++.h> #define int long long using namespace std; const int N=1e5+114; int h,x,y,z,dis[N],s; struct node { int x,z; }; struct nod { int x,z; }; vector<nod> adj[N]; bool operator <(node x,node y){return x.z>y.z;} bool flag[N]; void dij() { priority_queue<node> q; q.push({s,0}); memset(flag,0,sizeof flag); memset(dis,0x3f,sizeof dis); dis[s]=0; while(!q.empty()) { node t=q.top(); q.pop(); if(flag[t.x])continue; flag[t.x]=1; for(auto it:adj[t.x]) { if(dis[it.x]>dis[t.x]+it.z) { dis[it.x]=dis[t.x]+it.z; if(!flag[it.x])q.push({it.x,dis[it.x]}); } } } } signed main() { cin>>h>>x>>y>>z; if(x==1 || y==1 || z==1) { cout<<h<<endl; return 0; } h--; for(int i=0;i<x;i++) { adj[i].push_back({(i+y)%x,y}); adj[i].push_back({(i+z)%x,z}); } s=0; dij(); int sum=0; for(int i=0;i<=x-1;i++) if(h>=dis[i])sum+=(h-dis[i])/x+1; cout<<sum<<endl; return 0; } //不开long long见祖宗
圆方树
#include<bits/stdc++.h> using namespace std; const int N=2000001,M=700001; int n,m,dfn[M],low[M],abab; int shijian; stack<int> st; vector<int> ans[N]; vector<int> adj[M]; int top[N],son[N],dep[N],siz[N],fa[N]; void add_ans(int u,int v) { ans[u].push_back(v); ans[v].push_back(u); } void tarjan(int u) { st.push(u); dfn[u]=low[u]=++shijian; for(int i=0;i<adj[u].size();i++) { int t=adj[u][i]; if(!dfn[t]) { tarjan(t); low[u]=min(low[u],low[t]); if(low[t]==dfn[u]) { abab++; add_ans(u,abab); while(st.top()!=t) { add_ans(st.top(),abab); st.pop(); } add_ans(t,abab); st.pop(); } } else low[u]=min(low[u],dfn[t]); } } void dfs1(int u,int f) { dep[u]=dep[f]+1; fa[u]=f; siz[u]=1; for(auto v:ans[u]) { if(v==f)continue; dfs1(v,u); siz[u]+=siz[v]; if(siz[son[u]]<siz[v])son[u]=v; } } void dfs2(int u,int tp) { top[u]=tp; if(!son[u])return; dfs2(son[u],tp); for(auto v:ans[u]) if(v!=fa[u] && v!=son[u]) dfs2(v,v); } int lca(int x,int y) { while (top[x]!=top[y]) { if(dep[top[x]]<dep[top[y]])swap(x,y); x=fa[top[x]]; } if(dep[x]<dep[y])return x; return y; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); // freopen("P4320_2.in","r",stdin); // freopen("ssssssssssss.out","w",stdout); cin>>n>>m; for(int i=1;i<=m;i++) { int x,y; cin>>x>>y; adj[x].push_back(y); adj[y].push_back(x); } abab=n; tarjan(1); dfs1(1,0); dfs2(1,1); int q; cin>>q; while(q--) { int x,y; cin>>x>>y; cout<<((dep[x]+dep[y]-dep[lca(x,y)]*2)>>1)+1<<endl; } return 0; } /* 5 5 1 2 1 3 1 4 3 4 4 5 1 4 3 */
支配树
没环
#include<bits/stdc++.h> using namespace std; #define int long long const int N=65540; int n,in[N],dep[N];//拓扑序 vector<int> adj[N],fan[N],shu[N]; int tiao[N][25],siz[N]; int lca(int x,int y) { if(dep[x]<dep[y])swap(x,y); for(int i=20;i>=0;i--) { if(dep[tiao[x][i]]>=dep[y]) { x=tiao[x][i]; } } if(x==y) return x; for(int i=20;i>=0;i--) { if(tiao[x][i]!=tiao[y][i]) { x=tiao[x][i]; y=tiao[y][i]; } } return tiao[x][0]; } void topu112(int s) { queue<int> q; q.push(s); while(!q.empty()) { int t=q.front(); q.pop(); for(auto it:adj[t]) { if(fan[it].size()<2 && !tiao[it][0]) { shu[t].push_back(it); tiao[it][0]=t; for(int i=1;i<=20;i++) { tiao[it][i]=tiao[tiao[it][i-1]][i-1]; } dep[it]=dep[t]+1; } else if(!tiao[it][0]) { int t=fan[it][0],tt=fan[it][1]; int anss=lca(t,tt); for(int i=2;i<fan[it].size();i++) { anss=lca(anss,fan[it][i]); } shu[anss].push_back(it); tiao[it][0]=anss; for(int i=1;i<=20;i++) { tiao[it][i]=tiao[tiao[it][i-1]][i-1]; } dep[it]=dep[anss]+1; } in[it]--; if(!in[it])q.push(it); } } } void dfs(int u) { siz[u]=1; for(auto it:shu[u]) { dfs(it); siz[u]+=siz[it]; } } signed main() { cin>>n; for(int i=1;i<=n;i++) { int ssss; cin>>ssss; while(ssss!=0) { adj[ssss].push_back(i); fan[i].push_back(ssss); in[i]++; cin>>ssss; } } for(int i=1;i<=n;i++) { if(!in[i]) { adj[0].push_back(i); fan[i].push_back(0); in[i]++; } } topu112(0); dfs(0); for(int i=1;i<=n;i++) { cout<<siz[i]-1<<endl; } return 0; }
LCA
int lca(int x,int y) { if(dep[x]<dep[y])swap(x,y); for(int i=20;i>=0;i--) { if(dep[tiao[x][i]]>=dep[y]) { x=tiao[x][i]; } } if(x==y) return x; for(int i=20;i>=0;i--) { if(tiao[x][i]!=tiao[y][i]) { x=tiao[x][i]; y=tiao[y][i]; } } return tiao[x][0]; }
二叉树前、中、后序遍历:
#include <bits/stdc++.h> using namespace std; int n; vector<int> adj[1000001]; void xian(int x) { cout<<x<<' '; if(adj[x][0]!=0)xian(adj[x][0]); if(adj[x][1]!=0)xian(adj[x][1]); } void zhong(int x) { if(adj[x][0]!=0)zhong(adj[x][0]); cout<<x<<' '; if(adj[x][1]!=0)zhong(adj[x][1]); } void hou(int x) { if(adj[x][0]!=0)hou(adj[x][0]); if(adj[x][1]!=0)hou(adj[x][1]); cout<<x<<' '; } int main() { // freopen("filename.in", "r", stdin); // freopen("filename.out", "w", stdout); cin>>n; for(int i=1;i<=n;i++) { int x,y; cin>>x>>y; adj[i].push_back(x); adj[i].push_back(y); } xian(1); cout<<endl; zhong(1); cout<<endl; hou(1); cout<<endl; return 0; }
dij:
struct nod { int x,z; }; bool operator <(nod xx,nod yy) { return xx.z>yy.z; } vector<nod> adj[200100]; int dis[1000001]; bool flag[1000001]; void sb(int s) { priority_queue<nod> q; q.push({s,0}); memset(dis,0x7f,sizeof(dis)); dis[s]=0; while(!q.empty()) { nod t=q.top(); q.pop(); // cout<<t.x<<endl; if(flag[t.x]) continue; flag[t.x]=true; for(int i=0;i<adj[t.x].size();i++) { nod tt=adj[t.x][i]; if(!flag[tt.x]&&dis[tt.x]>t.z+tt.z) { dis[tt.x]=t.z+tt.z; q.push({tt.x,dis[tt.x]}); } } } }
floyd:
for(int k=1;k<=n;k++) { for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(i!=j && j!=k && i!=k) { c[i][j]=min(c[i][j],c[i][k]+c[k][j]); } } } }
快读:
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();return x*f;}
线性筛
void init(int n){ memset(v,0,sizeof(v)); int tot=0; for(int i=2;i<=n;i++){ if(!v[i]){ p[++tot]=i; } for(int k=1;k<=tot;k++){ if(i*p[k]>n) break; v[i*p[k]]=1; if(i%p[k]==0) break; } } }
-
通过的题目
-
最近活动
-
最近编写的题解
This person is lazy and didn't write any solutions. -
Stat
-
Rating
题目标签
- 系统测试
- 1