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&&sum;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;
}
全部评论

相关推荐

05-29 09:02
门头沟学院 Java
点赞 评论 收藏
分享
05-09 13:22
门头沟学院 Java
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务