开局一行$srand$，得分全靠随机化。

A.kill

发现两个并不显然的性质：

1.选中的人和怪物一定是按顺序的。第一个人打所有被选中怪物的第一只，第二个人打第二只，$etc$。

2.最优方案打的怪物一定是一段连续的区间。（因为过去再反方向回来到任务点一定不优）

所以直接枚举第一个打哪只怪即可。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int read()

{

    int x=0,f=1;char ch=getchar();

    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}

    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();

    return x*f;

}

const int N=5005;

int p[N],q[N],n,m,s,vis[N];

ll ans=1e15;

int abss(int x)

{

    return x>0?x:-x;

}

ll cost(int i,int j)

{

    return 1LL*(1LL*abss(p[i]-q[j])+1LL*abss(s-q[j]));

}

int main()

{

    n=read();m=read();s=read();

    for(int i=1;i<=n;i++)

        p[i]=read();

    for(int i=1;i<=m;i++)

        q[i]=read();

    sort(p+1,p+n+1);sort(q+1,q+m+1);

    for(int i=1;i<=m;i++)

    {

        ll tmp=0;

        for(int j=1;j<=n;j++)

            tmp=max(tmp,cost(j,i+j-1));

        ans=min(ans,tmp);

    }

    cout<<ans<<endl;

    return 0;

}

B.beauty

直接考虑点对显然没有前途(当然可以像我一样结合随机化乱搞得到50分)，那么贪心地考虑每条边

令$size[x]$表示$x$的子树里关键点的个数，尽量让子树里和子树外的关键点配对

所以$x$到它父亲的这条边对答案作出的贡献就是$min(size[x],2*K-size[x])$。其实就是看最多能凑子树内外的多少个点对。

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+5,K=60005;

typedef long long ll;

int read()

{

    int x=0,f=1;char ch=getchar();

    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}

    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();

    return x*f;

}

int n,k,op,node[K];

int to[N<<1],head[N],nxt[N<<1],tot,size[N];

bool key[N];

ll ans;

void add(int x,int y)

{

    to[++tot]=y;

    nxt[tot]=head[x];

    head[x]=tot;

}

void dfs(int x,int f)

{

    size[x]+=key[x];

    for(int i=head[x];i;i=nxt[i])

    {

        int y=to[i];

        if(y==f)continue;

        dfs(y,x);

        size[x]+=size[y];

    }

    ans+=min(size[x],2*k-size[x]);

}

int main()

{

    n=read();k=read();op=read();

    for(int i=1;i<=(k<<1);i++)

        node[i]=read(),key[node[i]]=1;

    for(int i=1;i<n;i++)

    {

        int x=read(),y=read();

        add(x,y);add(y,x);

    }

    dfs(1,0);

    cout<<ans<<endl;

    return 0;

}

C.weight

先放官方题解：

首先图的某一棵最小生成树求出来,对于树边和非树边分类讨论。
对于一条非树边,我们至少要将它的权值调整到树上这两个端点对应路径边权最大值 -1 才可以,否则我们一定可以
不选这条边。显然,我们调整到这么大也足够了。
对于一条树边,我们关心的显然是两个端点对应的简单路径经过这条树边的那些边,我们最大的可能选择是那些边
中权值最小的边的权值 -1, (否则我们可以选那条最小边而不选这条树边),而我们如果将这条树边的边权调整成那
个值,它也一定还会在最小生成树中。
所以这道题我们可以写一个树链剖分来完成我们上面的各种操作。

然后……也就没什么了。边权化点权，不断插入非树边用树剖动态维护，树边和非树边分别统计答案。

调到吐血……

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

using namespace std;

int read()

{

    int x=0,f=1;char ch=getchar();

    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}

    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();

    return x*f;

}

const int N=7e4+5,M=1e5+5;

int n,m,op,maxx;

struct edge

{

    int s,t,w,id;

    friend bool operator < (edge x,edge y)

    {

        return x.w<y.w;

    }

}e[M];

int to[M<<1],head[N],nxt[M<<1],len[M<<1],tot,id[M<<1],chose[M];

int ans[M];

void add(int x,int y,int z,int i)

{

    to[++tot]=y;

    nxt[tot]=head[x];

    head[x]=tot;

    len[tot]=z;

    id[tot]=i;

}

int fa[N];

int findf(int x)

{

    if(x==fa[x])return x;

    return fa[x]=findf(fa[x]);

}

void kruskal()

{

    sort(e+1,e+m+1);

    for(int i=1;i<=n;i++)

        fa[i]=i;

    int t=0;

    for(int i=1;i<=m;i++)

    {

        int fx=findf(e[i].s),fy=findf(e[i].t);

        if(fx!=fy)

        {

            fa[fx]=fy;

            t++;chose[e[i].id]=1;

            add(e[i].s,e[i].t,e[i].w,e[i].id);

            add(e[i].t,e[i].s,e[i].w,e[i].id);

        }

        if(t==n-1)break;

    }

}

namespace tre

{

    int size[N],son[N],top[N],seg[N],rev[N],dep[N],fa[N],num[N],vl[N],idn[N];

    void dfs1(int x,int f)

    {

        size[x]=1;

        fa[x]=f;

        dep[x]=dep[f]+1;

        for(int i=head[x];i;i=nxt[i])

        {

            int y=to[i];

            if(y==f)continue;

            vl[y]=len[i];idn[y]=id[i];

            dfs1(y,x);

            size[x]+=size[y];

            if(size[y]>size[son[x]])son[x]=y;

        }

    }

    void dfs2(int x,int y)

    {

        top[x]=y;seg[x]=++seg[0];rev[seg[0]]=x;

        if(son[x])dfs2(son[x],y);

        for(int i=head[x];i;i=nxt[i])

        {

            int y=to[i];

            if(y==fa[x]||y==son[x])continue;

            dfs2(y,y);

        }

    }

    int lz[N<<2],val1[N<<2],val2[N<<2];

#define ls(k) (k)<<1

#define rs(k) (k)<<1|1

    void build(int k,int l,int r)

    {

        lz[k]=val2[k]=maxx+1;

        if(l==r)

        {

            val1[k]=vl[rev[l]];

            return ;

        }

        int mid=l+r>>1;

        build(ls(k),l,mid);

        build(rs(k),mid+1,r);

        val1[k]=max(val1[ls(k)],val1[rs(k)]);

    }

    void down(int k)

    {

        if(lz[k]==maxx+1)return ;

        val2[ls(k)]=min(val2[ls(k)],lz[k]);

        val2[rs(k)]=min(val2[rs(k)],lz[k]);

        lz[ls(k)]=min(lz[ls(k)],lz[k]);

        lz[rs(k)]=min(lz[rs(k)],lz[k]);

        lz[k]=maxx+1;

    }

    int query(int k,int l,int r,int L,int R)

    {

        if(L<=l&&R>=r)return val1[k];

        int mid=l+r>>1,res=0;

        if(L<=mid)res=max(res,query(ls(k),l,mid,L,R));

        if(R>mid)res=max(res,query(rs(k),mid+1,r,L,R));

        return res;

    }

    int query(int x,int y)

    {

        int fx=top[x],fy=top[y],res=0;

        while(fx!=fy)

        {

            if(dep[fx]<dep[fy])swap(fx,fy),swap(x,y);

            res=max(res,query(1,1,seg[0],seg[fx],seg[x]));

            x=fa[fx],fx=top[x];

        }

        if(dep[x]>dep[y])swap(x,y);

        if(seg[x]<seg[y])res=max(res,query(1,1,seg[0],seg[x]+1,seg[y]));

        return res;

    }

    void update(int k,int l,int r,int L,int R,int val)

    {

        if(L<=l&&R>=r)

        {

            val2[k]=min(val2[k],val);

            lz[k]=min(lz[k],val);

            return ;

        }

        down(k);

        int mid=l+r>>1;

        if(L<=mid)update(ls(k),l,mid,L,R,val);

        if(R>mid)update(rs(k),mid+1,r,L,R,val);

        val2[k]=min(val2[ls(k)],val2[rs(k)]);

    }

    void update(int x,int y,int val)

    {

        int fx=top[x],fy=top[y];

        while(fx!=fy)

        {

            if(dep[fx]<dep[fy])swap(fx,fy),swap(x,y);

            update(1,1,seg[0],seg[fx],seg[x],val);

            x=fa[fx],fx=top[x];

        }

        if(dep[x]>dep[y])swap(x,y);

        if(seg[x]<seg[y])update(1,1,seg[0],seg[x]+1,seg[y],val);

    }

    void get(int k,int l,int r)

    {

        if(l==r)

        {

            ans[idn[rev[l]]]=(val2[k]==maxx+1?-1:val2[k]-1);

            return ;

        }

        down(k);

        int mid=l+r>>1;

        get(ls(k),l,mid);

        get(rs(k),mid+1,r);

    }

    void Main()

    {

        dfs1(1,0);dfs2(1,1);

        build(1,1,seg[0]);

        for(int i=1;i<=m;i++)

        {

            if(chose[e[i].id])continue;

            ans[e[i].id]=query(e[i].s,e[i].t)-1;

            update(e[i].s,e[i].t,e[i].w);

        }

        get(1,1,seg[0]);

    }

}

int main()

{

    n=read();m=read();op=read();

    for(int i=1;i<=m;i++)

    {

        e[i].s=read(),e[i].t=read(),e[i].w=read();

        e[i].id=i;maxx=max(maxx,e[i].w);

    }

    kruskal();

    tre::Main();

    for(int i=1;i<=m;i++)

        printf("%d ",ans[i]);

    putchar('\n');

    return 0;

}

巴特西

[CSP-S模拟测试45]题解

A.kill

B.beauty

C.weight

最新文章

热门文章