[APIO2012]

来自FallDream的博客，未经允许，请勿转载，谢谢。

---------------------------------------------------

A.dispatching 派遣

上次hzwer出了这道题所以做过了，搬一下以前的博文。

给定一棵n个点的树和一个费用m，每个点有一个忍者，派遣它的费用是ci，它的领导力是li。你要选择一个点作为领导，并且在它的子树中(包括它)选出尽可能多的点，满足费用不超过m且选出的点的数量*领导的领导力最大。n<=100000 m,c,l<=10^9

题解：这道题很多做法吧..首先费用少的肯定先选，我们每次肯定是从费用小的开始选，所以题目可以转换为求所有点的子树中最多能选几个点。

做法1：平衡树/优先队列+启发式合并

把费用装进一个平衡树/优先队列里面，然后启发式合并，合并次数是nlogn，总复杂度nlog^2n

我的做法：树剖那样子标号，满足子树的dfs序连续，然后主席树，复杂度是nlogn

#include<iostream>

#include<cstdio>

#include<queue>

#define MN 100000

#define MM 5000000

#define INF 2000000000

#define ll long long

using namespace std;

inline int read()

{

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

    while(ch < '' || ch > ''){ if(ch == '-') f = -;  ch = getchar();}

    while(ch >= '' && ch <= ''){x = x *  + ch - '';ch = getchar();}

    return x * f;

}

int n,dfn=,cnt=,mx[MN+],size[MN+],nl[MN+],nr[MN+],head[MN+],id[MN+],rt[MN+];

ll c[MN+],l[MN+],ans=,m;

struct edge{

    int to,next;

}e[MN+];

struct TREE{

    int l,r,size;ll x;

}T[MM+];

void ins(int f,int t)

{

    e[++cnt]=(edge){t,head[f]};head[f]=cnt;

}

void dfs1(int x)

{

    size[x]=;mx[x]=;int maxn=;

    for(int i=head[x];i;i=e[i].next)

    {

        dfs1(e[i].to);

        size[x]+=size[e[i].to];

        if(size[e[i].to]>maxn){maxn=size[e[i].to];mx[x]=e[i].to;}

    }

}

void dfs2(int x)

{

    nl[x]=++dfn;id[dfn]=x;

    if(mx[x]) dfs2(mx[x]);

    for(int i=head[x];i;i=e[i].next)

        if(e[i].to!=mx[x])

            dfs2(e[i].to);

    nr[x]=dfn;

}

void ins(int x,int nx,ll c)

{

    T[nx].size=T[x].size+;T[nx].x=T[x].x+c;

    ll l=,r=INF,mid;

    while(l<r)

    {

        mid=l+r>>;

        if(c<=mid)

        {

            T[nx].r=T[x].r;T[nx].l=++cnt;

            r=mid;nx=T[nx].l;x=T[x].l;

        }

        else

        {

            T[nx].l=T[x].l;T[nx].r=++cnt;

            l=mid+;nx=T[nx].r;x=T[x].r;

        }

        T[nx].size=T[x].size+;T[nx].x=T[x].x+c;

    }

}

int query(int x,int nx,ll cc)

{

    ll l=,r=INF,mid,num=;

    while(l<r)

    {

        mid=l+r>>;

        if(T[T[nx].l].x-T[T[x].l].x<=cc)

        {

            cc-=T[T[nx].l].x-T[T[x].l].x;

            num+=T[T[nx].l].size-T[T[x].l].size;

            x=T[x].r;nx=T[nx].r;l=mid+;

        }

        else

        {

            x=T[x].l;nx=T[nx].l;

            r=mid;

        }

    }

    if(T[nx].size-T[x].size>)

    {

        int x=cc/((T[nx].x-T[x].x)/(T[nx].size-T[x].size));

        num+=x;

    }

    return num;

}

main()

{

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

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

    {

        int fa=read();c[i]=read();l[i]=read();

        if(fa) ins(fa,i);

    }

    dfs1();dfs2();cnt=;

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

        ins(rt[i-],rt[i]=++cnt,c[id[i]]);

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

        ans=max(ans,l[i]*1LL*query(rt[nl[i]-],rt[nr[i]],m));

    cout<<ans;

    return ;

}

B.guard守卫

有n个草丛(#滑稽）,里面有K个盖伦忍者，有m个条信息，表示一段区间内有没有盖伦忍者，你要求出一定有盖伦忍者的草丛。 $n,m,k\leqslant 10^{5}$

一开始我看到这道题就写了一个线段树+大判断，挂了3个点，想了好久才发现忍者数量可能会超过的情况没判。

讲讲正解：先删掉没用的，然后剩下的如果是K个，就直接输出，否则我们重新标号之后，排序，删除无用区间，这样满足信息的左右坐标都递增。很显然，对每段区间选择放在最右边的点是最优的。用F[i]表示前i个区间放在最右的节点至少放几个，g[i]表示后... 然后对每个区间，如果它长度为一，直接输出，否则我们认为放在第二右边是次优的，二分出不能覆盖第二右的节点的区间范围，假设是1..a 和b..m，那么判断f[a]+g[b]+1如果大于K，说明这个最右的节点必须放，否则会超过K个。

#include<iostream>

#include<cstdio>

#include<algorithm>

#define MN 100000

using namespace std;

inline int read()

{

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

    while(ch < '' || ch > ''){ if(ch == '-') f = -;  ch = getchar();}

    while(ch >= '' && ch <= ''){x = x *  + ch - '';ch = getchar();}

    return x * f;

}

struct TREE{int l,r,val,x;}T[MN*+];

struct ques{int l,r;

    bool operator <(const ques&y)const{return l==y.l?r>y.r:l<y.l;}

}q[MN+],s[MN+];

int n,K,m,cnt=,f[MN+],g[MN+],nl[MN+],nr[MN+],cn=,id[MN+];

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

{

    if((T[x].l=l)==(T[x].r=r)) {T[x].x=;return;}

    int mid=l+r>>;

    build(x<<,l,mid);

    build(x<<|,mid+,r);

    T[x].x=T[x<<].x+T[x<<|].x;

}

void modify(int x,int l,int r)

{

    if(T[x].val)return;

    if(T[x].l==l&&T[x].r==r)

    {

        T[x].val=;T[x].x=;

        return;

    }

    int mid=T[x].l+T[x].r>>;

    if(r<=mid) modify(x<<,l,r);

    else if(l>mid) modify(x<<|,l,r);

    else {modify(x<<,l,mid);modify(x<<|,mid+,r);}

    T[x].x=T[x<<].x+T[x<<|].x;

}

int query(int x,int k)

{

    if(T[x].val)return ;

    if(T[x].l==T[x].r)return T[x].x;

    int mid=T[x].l+T[x].r>>;

    return k<=mid?query(x<<,k):query(x<<|,k);

}

int get(int x,int l,int r)

{

    int ans=;

    for(int mid=l+r>>;l<=r;mid=l+r>>)

        if(s[mid].r<x) ans=mid,l=mid+;

        else r=mid-;

    return f[ans];

}

int get2(int x,int l,int r)

{

    int ans=;

    for(int mid=l+r>>;l<=r;mid=l+r>>)

        if(s[mid].l>x) ans=mid,r=mid-;

        else l=mid+;

    return g[ans];

}

int main()

{

    n=read();K=read();m=read();

    build(,,n);

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

    {

        int l=read(),r=read(),x=read();

        if(!x) modify(,l,r);

        else q[++cnt]=(ques){l,r};

    }

    if(T[].x==K)

    {

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

            if(query(,i)==)

                printf("%d\n",i);

        return ;

    }

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

        if(query(,i)==)

            nl[i]=++cn,id[cn]=i;

    for(int i=n;i;i--)

        nr[i]=(nl[i]?nl[i]:nr[i+]);

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

        nl[i]=(nl[i]?nl[i]:nl[i-]);

    for(int i=;i<=cnt;i++)

        q[i].l=nr[q[i].l],q[i].r=nl[q[i].r];

    sort(q+,q+cnt+);int j=;

    for(int i=;i<=cnt;i++)

    {

        while(j&&q[i].r<=s[j].r)--j;

        s[++j]=q[i];

    }

    for(int i=,mx=;i<=j;i++)

        if(s[i].l>mx) {mx=s[i].r;f[i]=f[i-]+;}

        else f[i]=f[i-];

    for(int k=j,mn=n+;k;k--)

        if(s[k].r<mn) {mn=s[k].l;g[k]=g[k+]+;}

        else g[k]=g[k+];

    bool flag=;

    for(int i=;i<=j;i++)

    {

        if(f[i]!=f[i-]+) continue;

        if(s[i].l==s[i].r) {flag=;printf("%d\n",id[s[i].l]);continue;}

        int lt=get(s[i].r-,,i-),rt=get2(s[i].r-,i+,j);

        if(lt+rt+>K) printf("%d\n",id[s[i].r]),flag=;

    }

    if(!flag) puts("-1");

    return ;

}

C.苦无

大概就是乱排序每种情况考虑一下，然后堆搞一搞，最后矩形面积并。

傻逼大码农，本来打算码的，现在代码已经被我删了.

巴特西

[APIO2012]

最新文章

热门文章