2020.10.27模拟赛 NK Contest 1074
T1
第一问是瓶颈路,Kruscal或Prim可以解决
在第一问的基础上,跑一边Dij即可
#include <bits/stdc++.h> #define ri register int #define ll long long using namespace std; const ll Maxn=5e5; const ll Maxm=1e6; struct Edge { ll x,y,t,w; }e[Maxm+5]; struct Path { ll u,dis; }; priority_queue<Path>q; ll lt[Maxn+5],nt[2*Maxm+5],ed[2*Maxm+5],val[2*Maxm+5][2],dis[Maxn+5],mark[Maxn+5],father[Maxn+5],n,m,a,b,cnt; ll read() { char c=getchar(); ll k=1,ret=0; while(c<48||c>57) { if(c=='-')k=-1; c=getchar(); } while(c>=48&&c<=57) { ret=(ret<<1)+(ret<<3)+(c^48); c=getchar(); } return ret*k; } bool cmp(Edge a,Edge b) { return a.t<b.t; } bool operator<(Path a,Path b) { return a.dis>b.dis; } void addedge(ll x,ll y,ll t,ll w) { ed[++cnt]=y;nt[cnt]=lt[x];lt[x]=cnt; val[cnt][0]=t;val[cnt][1]=w; } ll getfather(ll v) { if(father[v]==v)return v; else { father[v]=getfather(father[v]); return father[v]; } } void merge(ll x,ll y) { ll fx=getfather(x),fy=getfather(y); if(fx!=fy)father[fy]=fx; } void init() { for(ri i=1;i<=n;i++)dis[i]=5e17; dis[a]=0; Path t; t.u=a;t.dis=0; q.push(t); } void dij() { while(!q.empty()) { Path t=q.top();q.pop(); if(mark[t.u])continue; mark[t.u]=1; for(ri i=lt[t.u];i;i=nt[i]) { ll v=ed[i],l=val[i][0]*val[i][1]; if(dis[v]>dis[t.u]+l) { dis[v]=dis[t.u]+l; Path p; p.u=v;p.dis=dis[v]; q.push(p); } } } } ll kruscal() { sort(e+1,e+m+1,cmp); for(ri i=1;i<=n;i++)father[i]=i; ll ret; for(ri i=1;i<=m&&getfather(a)!=getfather(b);i++) { ll x=e[i].x,y=e[i].y,z=e[i].t; ret=z; merge(x,y); } return ret; } int main() { n=read(),m=read(); for(ri i=1;i<=m;i++)e[i].x=read(),e[i].y=read(),e[i].t=read(),e[i].w=read(); a=read(),b=read(); int ans=kruscal(); for(ri i=1;i<=m;i++) if(e[i].t<=ans) { addedge(e[i].x,e[i].y,e[i].t,e[i].w); addedge(e[i].y,e[i].x,e[i].t,e[i].w); } init(); dij(); printf("%lld %lld\n",ans,dis[b]); return 0; }
T2
有一个结论:
只要每个连通块有偶数个节点,就能生成度数为奇数的森林。
为什么呢?
对于每个连通块,随便DFS出一棵生成树,自底向上考虑每条边是否保留。
如果一个节点已经和偶数个儿子相连,则保留自己到父亲的边,否则删除自己到父亲的边。
这样构造可以保证除了根节点以外,每个节点度数都是奇数。
又因为每个连通块节点数是偶数, 总度数等于边数*2,所以根节点的度数也是奇数。
回到原题,如果n是奇数直接无解。
接下来将边按长度递增排序,像Kruscal一样合并,直到所有连通块都有偶数个节点,则用过的最后一
条边就是长度最大的边。
然后对每个连通块分别DFS确定哪些边保留。
mlogm复杂度
#include <bits/stdc++.h> #define ri register int #define ll long long #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) using namespace std; const int Maxn=2e5; const int Maxm=5e5; struct Edge { int x,y,z,id; }e[Maxm+5]; char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf; int lt[Maxn+5],nt[2*Maxn+5],ed[2*Maxn+5],id[2*Maxn+5],father[Maxn+5],size[Maxn+5],visit[Maxn+5],mark[Maxm+5],n,m,cnt,sum; int read() { char c=getchar(); int k=1,ret=0; while(c<48||c>57) { if(c=='-')k=-1; c=getchar(); } while(c>=48&&c<=57) { ret=(ret<<1)+(ret<<3)+(c^48); c=getchar(); } return ret*k; } bool cmp(Edge a,Edge b) { return a.z<b.z; } void addedge(int x,int y,int z) { ed[++cnt]=y;nt[cnt]=lt[x];lt[x]=cnt; id[cnt]=z; } int getfather(int v) { if(father[v]==v)return v; else { int f=getfather(father[v]); size[v]=size[f]; father[v]=f; return f; } } void merge(int x,int y) { int fx=getfather(x),fy=getfather(y); if(fx!=fy) { if(size[fx]<size[fy])swap(fx,fy); father[fy]=fx; if(size[fy]%2&&size[fx]%2)sum-=2; size[fx]+=size[fy]; } } int kruscal() { sum=n; sort(e+1,e+m+1,cmp); for(ri i=1;i<=n;i++)father[i]=i,size[i]=1; int ret=-1; for(ri i=1;i<=m&∑i++) { int x=e[i].x,y=e[i].y,z=e[i].z; if(getfather(x)!=getfather(y)) { merge(x,y); addedge(x,y,e[i].id); addedge(y,x,e[i].id); if(sum==0)ret=e[i].z; } } return ret; } void dfs(int u,int fa,int edge) { visit[u]=1; int node=0; for(ri i=lt[u];i;i=nt[i]) if(!visit[ed[i]]) { dfs(ed[i],u,i); if(mark[id[i]])++node; } if(node%2==0)mark[id[edge]]=1; } int main() { n=read(),m=read(); for(ri i=1;i<=m;i++) { e[i].x=read(),e[i].y=read(),e[i].z=read(); e[i].id=i; } int t=kruscal(); printf("%d\n",t); if(t==-1)return 0; for(ri i=1;i<=n;i++) if(!visit[i])dfs(i,0,0); for(ri i=1;i<=m;i++)putchar(mark[i]+48); fwrite(obuf,O-obuf,1,stdout); return 0; }
T3
一定是在最小生成树上做操作,所以先建出Kruscal重构树
所以两个实节点的lca的权值即为最长边
考虑合并/查询
对于一个新建的虚节点,我们考虑启发式查询,方法是:对于一个size较小的子树中的每个节点,查另一个子树中满足此节点c的限制条件的点的个数,再乘以u的权值
注意到,我们每次查询的实际上是一个二维数点,满足dfs序在查询子树中且c在限制条件的区间中
所以把操作存下来,离散化之后用树状数组可以解决
时间复杂度nlognlogn,空间复杂度n*logn
#include <bits/stdc++.h> #define ri register int #define ll long long #define mid (((l)+(r))>>1) #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) using namespace std; const int Maxn=2e5; const int Maxm=5e5; const int Lgc=19; struct Edge { int x,y,z; }e[Maxm+5]; struct Question { int lc,rc,lx,rx,v,x; }qt[2*Maxn*Lgc+5]; struct Point { int x,y; }point[Maxn+5]; char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf; ll ans,val[2*Maxn+5]; int c[Maxn+5],father[2*Maxn+5],rk[2*Maxn+5],size[2*Maxn+5],lson[2*Maxn+5],rson[2*Maxn+5],lsh[3*Maxn+5],query[Maxn+5][2],in[2*Maxn+5],out[2*Maxn+5],tree[3*Maxn+5],n,m,l,now,cntq,visittime,cnt; inline int read() { register char c=getchar(); int k=1,ret=0; while(c<48||c>57) { if(c=='-')k=-1; c=getchar(); } while(c>=48&&c<=57) { ret=ret*10+(c^48); c=getchar(); } return ret*k; } void solve(int u) { in[u]=++visittime;rk[visittime]=u; int p=lson[u],q=rson[u]; if(p)solve(p); if(q)solve(q); out[u]=visittime; if(p&&q) { if(out[p]-in[p]+1<out[q]-in[q]+1) { for(ri i=in[p];i<=out[p];i++) if(rk[i]<=n) { qt[++cntq]=(Question){query[rk[i]][0],query[rk[i]][1],in[q],out[q],val[u],out[q]}; } } else { for(ri i=in[q];i<=out[q];i++) if(rk[i]<=n) { qt[++cntq]=(Question){query[rk[i]][0],query[rk[i]][1],in[p],out[p],val[u],out[p]}; } } } } inline int getfather(int v) { if(father[v]==v)return v; else { father[v]=getfather(father[v]); size[v]=size[father[v]]; return father[v]; } } inline void merge(int x,int y) { if(size[y]>size[y])swap(x,y); father[y]=x;size[x]+=size[y]; } bool cmp1(Edge a,Edge b) { return a.z<b.z; } void kruscal() { now=n; sort(e+1,e+m+1,cmp1); for(ri i=1;i<=2*n;i++)father[i]=i,size[i]=1; int cnt=0; for(ri i=1;i<=m&&cnt<n-1;i++) { int x=getfather(e[i].x),y=getfather(e[i].y),z=e[i].z; if(x!=y) { ++cnt;++now; lson[now]=x;rson[now]=y; merge(now,x);merge(now,y); val[now]=z; } } } void discre() { for(ri i=1;i<=n;i++) { lsh[i*2-1]=c[i]-l; lsh[i*2]=l==0?c[i]:c[i]+l-1; } for(ri i=2*n+1;i<=3*n;i++)lsh[i]=c[i-2*n]; sort(lsh+1,lsh+3*n+1); cnt=unique(lsh+1,lsh+3*n+1)-lsh-1; for(ri i=1;i<=n;i++) { query[i][0]=lower_bound(lsh+1,lsh+cnt+1,c[i]-l)-lsh; query[i][1]=lower_bound(lsh+1,lsh+cnt+1,c[i]+l-1)-lsh; c[i]=lower_bound(lsh+1,lsh+cnt+1,c[i])-lsh; } } inline void add(register int x,int d) { for(;x<=cnt;x+=x&(-x))tree[x]+=d; } inline int getsum(register int x) { register int ret=0; for(;x>=1;x-=x&(-x))ret+=tree[x]; return ret; } bool cmp2(const Question &a,const Question &b) { return a.x<b.x; } bool cmp3(const Point &a,const Point &b) { return a.x<b.x; } signed main() { n=read(),m=read(),l=read(); for(ri i=1;i<=n;i++)c[i]=read(); for(ri i=1;i<=m;i++)e[i].x=read(),e[i].y=read(),e[i].z=read(); kruscal(); discre(); solve(now); for(ri i=1;i<=cntq;i++) { qt[i+cntq]=qt[i]; qt[i+cntq].v=-qt[i].v; qt[i+cntq].x=qt[i].lx-1; } sort(qt+1,qt+cntq*2+1,cmp2); for(ri i=1;i<=n;i++)point[i].x=in[i],point[i].y=c[i]; sort(point+1,point+n+1,cmp3); int t=1;ll ans=0; for(ri i=1;i<=cntq*2;i++) { while(point[t].x<=qt[i].x&&t<=n)add(point[t].y,1),++t; ans+=1ll*qt[i].v*(t-getsum(qt[i].rc)+getsum(qt[i].lc)-1); } printf("%lld\n",ans); fwrite(obuf,O-obuf,1,stdout); return 0; }
另一种写法是线段树合并,即对c建立权值线段树,但常数特别大,我只卡到了60分
#include <bits/stdc++.h> #define ri register int #define ll long long #define mid (((l)+(r))>>1) #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) using namespace std; const int Maxn=2e5; const int Maxm=5e5; const int Lgc=19; struct Edge { int x,y,z; }e[Maxm+5]; vector<int>node[2*Maxn+5]; char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf; ll ans; int val[2*Maxn+5],c[Maxn+5],father[2*Maxn+5],size[2*Maxn+5],lson[2*Maxn+5],rson[2*Maxn+5],lsh[3*Maxn+5],query[Maxn+5][2],n,m,l,now,maxc,minc=1e9+1; inline int read() { char c=getchar(); int k=1,ret=0; while(c<48||c>57) { if(c=='-')k=-1; c=getchar(); } while(c>=48&&c<=57) { ret=ret*10+(c^48); c=getchar(); } return ret*k; } //----- ll v[3*Maxn*Lgc]; int ls[3*Maxn*Lgc],rs[3*Maxn*Lgc],rt[2*Maxn+5],tot; inline void change(int &p,int l,int r,int k,int d) { if(!p)p=++tot; if(l==r) { v[p]+=d; return ; } if(k<=mid)change(ls[p],l,mid,k,d); else change(rs[p],mid+1,r,k,d); v[p]=v[ls[p]]+v[rs[p]]; } inline ll getsum(int &p,int l,int r,int a,int b) { if(a>b)return 0; if(p==0)return 0; if(a<=l&&r<=b)return v[p]; ll ret=0; if(a<=mid)ret+=getsum(ls[p],l,mid,a,b); if(b>mid)ret+=getsum(rs[p],mid+1,r,a,b); return ret; } inline void merge_tree(int &x,int y,int l,int r) { if(!x||!y) { x|=y; return ; } if(l==r) { v[x]+=v[y]; return ; } merge_tree(ls[x],ls[y],l,mid); merge_tree(rs[x],rs[y],mid+1,r); v[x]=v[ls[x]]+v[rs[x]]; } //----- //----- inline void solve(int u) { int p=lson[u],q=rson[u]; if(p)solve(p); if(q)solve(q); if(u<=n) { node[u].push_back(u); rt[u]=++tot;change(rt[u],minc,maxc,c[u],1); } else if(p&&q) { if(node[p].size()<node[q].size()) { for(ri i=0;i<(int)node[p].size();i++) { ans+=1LL*val[u]*(node[q].size()-getsum(rt[q],minc,maxc,query[node[p][i]][0],query[node[p][i]][1])); } node[u].swap(node[q]);node[u].insert(node[u].end(),node[p].begin(),node[p].end()); } else { for(ri i=0;i<(int)node[q].size();i++) { ans+=1LL*val[u]*(node[p].size()-getsum(rt[p],minc,maxc,query[node[q][i]][0],query[node[q][i]][1])); } node[u].swap(node[p]);node[u].insert(node[u].end(),node[q].begin(),node[q].end()); } rt[u]=rt[p]; merge_tree(rt[p],rt[q],minc,maxc); } if(p)vector<int>().swap(node[p]); if(q)vector<int>().swap(node[q]); } //----- //----- inline int getfather(int v) { if(father[v]==v)return v; else { father[v]=getfather(father[v]); size[v]=size[father[v]]; return father[v]; } } inline void merge(int x,int y) { if(size[y]>size[y])swap(x,y); father[y]=x;size[x]+=size[y]; } //----- //----- inline bool cmp(Edge a,Edge b) { return a.z<b.z; } inline void kruscal() { now=n; sort(e+1,e+m+1,cmp); for(ri i=1;i<=2*n;i++)father[i]=i,size[i]=1; int cnt=0; for(ri i=1;i<=m&&cnt<n-1;i++) { int x=getfather(e[i].x),y=getfather(e[i].y),z=e[i].z; if(x!=y) { ++cnt;++now; lson[now]=x;rson[now]=y; merge(now,x);merge(now,y); val[now]=z; } } } //----- inline void discre() { for(ri i=1;i<=n;i++) { lsh[i*2-1]=c[i]-l+1; lsh[i*2]=c[i]+l-1; } for(ri i=2*n+1;i<=3*n;i++)lsh[i]=c[i-2*n]; lsh[3*n+1]=minc;lsh[3*n+2]=maxc; sort(lsh+1,lsh+3*n+3); int cnt=unique(lsh+1,lsh+3*n+3)-lsh-1; for(ri i=1;i<=n;i++) { query[i][0]=lower_bound(lsh+1,lsh+cnt+1,c[i]-l+1)-lsh; query[i][1]=lower_bound(lsh+1,lsh+cnt+1,c[i]+l-1)-lsh; c[i]=lower_bound(lsh+1,lsh+cnt+1,c[i])-lsh; } minc=lower_bound(lsh+1,lsh+cnt+1,minc)-lsh; maxc=lower_bound(lsh+1,lsh+cnt+1,maxc)-lsh; } signed main() { n=read(),m=read(),l=read(); for(ri i=1;i<=n;i++) { c[i]=read(); maxc=max(maxc,c[i]); minc=min(minc,c[i]); } for(ri i=1;i<=m;i++)e[i].x=read(),e[i].y=read(),e[i].z=read(); kruscal(); discre(); solve(now); printf("%lld\n",ans); fwrite(obuf,O-obuf,1,stdout); return 0; }
T4
重心的f肯定是最小的,所以排序
较大的f肯定是叶节点,size为1,根据f[son[i]]=f[i]+n-2*size[son[i]]可以求出i的父亲,如果没有这个值直接无解
如此可以求出每个节点的父亲
最后还要dfs检查一遍,看建出来的树dp出来的值和f一不一样
#include <bits/stdc++.h> #define pb push_back #define ri register int #define ll long long #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) using namespace std; const ll Maxn=1e5; map<ll,ll>q; vector<ll>node[Maxn+5]; char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf; ll f[Maxn+5],g[Maxn+5],a[Maxn+5],mark[Maxn+5],size[Maxn+5],father[Maxn+5],sum[Maxn+5],n; ll read() { char c=getchar(); ll k=1,ret=0; while(c<48||c>57) { if(c=='-')k=-1; c=getchar(); } while(c>=48&&c<=57) { ret=(ret<<1)+(ret<<3)+(c^48); c=getchar(); } return ret*k; } void dfs1(ll u,ll fa) { sum[u]=1; for(ri i=0;i<(int)node[u].size();i++) if(node[u][i]!=fa) { dfs1(node[u][i],u); sum[u]+=sum[node[u][i]]; g[u]+=g[node[u][i]]+sum[node[u][i]]; } } void dfs2(ll u,ll fa) { for(ri i=0;i<(int)node[u].size();i++) if(node[u][i]!=fa) { g[node[u][i]]=g[u]+n-2*sum[node[u][i]]; dfs2(node[u][i],u); } } int main() { scanf("%lld",&n); for(ri i=1;i<=n;i++) { scanf("%lld",&f[i]);a[i]=f[i]; q[f[i]]=i;size[i]=1; } sort(f+1,f+n+1); for(ri i=n;i>=2;i--) { ll p=lower_bound(f+1,f+i,f[i]+2*size[q[f[i]]]-n)-f; father[q[f[i]]]=q[f[p]];size[q[f[p]]]+=size[q[f[i]]]; if(f[p]!=f[i]+2*size[q[f[i]]]-n)return !printf("-1\n"); } for(ri i=1;i<=n;i++)node[father[i]].pb(i); dfs1(q[f[1]],0); dfs2(q[f[1]],0); for(ri i=1;i<=n;i++) if(a[i]!=g[i])return !printf("-1\n"); for(ri i=1;i<=n;i++) if(father[i])printf("%lld %lld\n",i,father[i]); fwrite(obuf,O-obuf,1,stdout); return 0; }