【bzoj2809】 Apio2012

http://www.lydsy.com/JudgeOnline/problem.php?id=2809 (题目链接)

题意

　　给出一棵树，每个节点有两个权值${c}$，${L}$，分别代表花费和领导力，在树中找到一个点${i}$，并且找到这个点子树中的一些点组成一个集合，使得集合中的所有点的${c}$之和不超过${M}$，且${L[i]*集合中元素个数和}$最大。

Solution

　　听说这道题正解是可并堆，可是并不会做，我们考虑换一种方法。正好最近才学了莫队算法，于是脑洞大开，似乎找到了方法——莫队＋分块，是不是很神。

　　首先，我们将树上节点按dfs序排序，得到一串序列${S}$，将子树询问转换为在${S}$上的区间询问，总共${n}$棵子树，所以也就只有${n}$个询问，可以承受。

　　然后我们发现，对于单一节点来说，“使得集合中的所有点的${c}$之和不超过${M}$，且${Li*集合中元素个数和最大}$”可以贪心，也就是尽量选取${c}$小的节点加入集合。于是我们想到了对权值${c}$离散化后进行分块（注意是权值${c}$而不是序列${S}$），对于无修改区间查询用莫队进行转移，权值分块的修改是${O(1)}$的，查询是${O(\sqrt{n})}$的，复杂度仍是${O(n*\sqrt{n})}$。

　　接下来就是细节问题。我们先dfs一遍求出dfs序以及区间之后对区间排序（以左端点所在块作为第一关键字，右端点作为第二关键字），之后对树上的节点按照${C}$的大小排序，求出${C}$的值域记录在${ma[]}$数组中，并用${p}$数组记录离散化后当前节点的编号。对${C}$的值域建块。

　　如何插入，删除和询问呢？对于插入和删除，我们用一个数组${b[x]}$来记录在${C}$为${x}$的节点有几个在当前询问中，用${cnts[x]}$来记录${x}$所在的块中有几个节点在当前询问中，用${sumv[x]}$来记录${x}$所在的块中当前的所有${C}$的和。

　　有了这三个数组询问就很好做了。

　　记得我在糖果公园里面写过：莫队中的分块只是用来保证复杂度，而这里把dfs序抠出来在变成序列上的莫队不是复杂度不对吗？其实不是这样的，糖果公园那道题查询的是树上路径，而这里查询的是子树，两者不是一个东西，这两种询问的范围也不一样。所以这里直接将dfs序抠出来是可以的。

细节

　　注意莫队的块与权值分块的区别，别搞混了。

代码

// bzoj2120

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<vector>

#define MOD 1000000007

#define inf 2147483640

#define LL long long

#define free(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout);

using namespace std;

inline LL getint() {

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

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

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

    return x*f;

}

const int maxn=100010;

struct edge {int next,to;}e[maxn<<2];

struct interval {int l,r,id,L;}t[maxn];

struct data {int dfn,c,l;}a[maxn];

int n,m,M,cnt,mo_block,chunk_block;

int L[maxn],head[maxn],cnts[maxn],pos[maxn],sumv[maxn],b[maxn],ma[maxn],p[maxn];

void insert(int u,int v) {

    e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;

}

void dfs(int u) {

    t[u].l=a[u].dfn=++cnt;

    for (int i=head[u];i;i=e[i].next) dfs(e[i].to);

    t[u].r=cnt;t[u].id=u;t[u].L=a[u].l;

}

bool ccmp(data a,data b) {

    return a.c<b.c;

}

bool poscmp(interval a,interval b) {

    return pos[a.l]==pos[b.l]?a.r<b.r:pos[a.l]<pos[b.l];

}

void Mo_build() {

    mo_block=(int)sqrt(n);

    for (int i=1;i<=n;i++) pos[i]=(i-1)/mo_block+1;

}

void chunk_build() {

    chunk_block=(int)sqrt(cnt);

    m=(cnt%chunk_block>0) ? cnt/chunk_block+1 : cnt/chunk_block;

    for (int i=1;i<=cnt;i++) pos[i]=(i-1)/chunk_block+1;

    for (int i=1;i<=m;i++) L[i]=(i-1)*chunk_block+1;

}

void update(int x,int val) {

    b[x]+=val;

    cnts[pos[x]]+=val;

    sumv[pos[x]]+=(LL)val*ma[x];

}

int query() {

    LL tot=0;int ans=0;

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

        tot+=sumv[i];ans+=cnts[i];

        if (tot>M) {

            tot-=sumv[i];ans-=cnts[i];

            for (int j=L[i];;j++) {

                tot+=(LL)ma[j]*b[j];

                ans+=b[j];

                if (tot>M) return ans-(int)(tot-M)/ma[j]-((tot-M)%ma[j]!=0);

            }

        }

    }

    return ans;

}

int main() {

    scanf("%d%d",&n,&M);

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

        int x;

        scanf("%d%d%d",&x,&a[i].c,&a[i].l);

        insert(x,i);

    }

    cnt=0;

    dfs(e[head[0]].to);

    Mo_build();

    sort(t+1,t+1+n,poscmp);

    for (int i=1;i<=n;i++) pos[i]=0;

    sort(a+1,a+1+n,ccmp);

    cnt=0;ma[p[a[1].dfn]=++cnt]=a[1].c;

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

        if (a[i].c!=a[i-1].c) cnt++;

        ma[p[a[i].dfn]=cnt]=a[i].c;

    }

    LL ans=0;

    chunk_build();

    for (int l=1,r=0,i=1;i<=n;i++) {

        for (;r<t[i].r;r++) update(p[r+1],1);

        for (;r>t[i].r;r--) update(p[r],-1);

        for (;l<t[i].l;l++) update(p[l],-1);

        for (;l>t[i].l;l--) update(p[l-1],1);

        ans=max(ans,(LL)query()*t[i].L);

    }

    printf("%lld\n",ans);

    return 0;

}

UPD 2017.1.9

Solution

　　可并堆。

　　对于每个节点建立一个大根堆，如果堆中所有元素之和大于M，那么pop堆顶。每次dfs合并当前节点的堆与儿子节点的堆。

代码

// bzoj2809

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<ctime>

#define LL long long

#define inf 1<<30

#define Pi acos(-1.0)

#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);

using namespace std;

const int maxn=100010;

struct edge {int to,next;}e[maxn];

struct heap {int val,l,r;}q[maxn];

int head[maxn],cnt,sz,m,n;

int size[maxn],C[maxn],rt[maxn];

LL L[maxn],sum[maxn],ans;

void link(int u,int v) {

	e[++cnt]=(edge){v,head[u]};head[u]=cnt;

}

int merge(int x,int y) {

	if (x==0 || y==0) return x+y;

	if (q[x].val<q[y].val) swap(x,y);

	q[x].r=merge(q[x].r,y);

	swap(q[x].l,q[x].r);

	return x;

}

int pop(int x) {

	return merge(q[x].l,q[x].r);

}

void dfs(int x) {

	rt[x]=++sz;size[x]=1;

	q[sz].val=sum[x]=C[x];

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

		dfs(e[i].to);

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

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

		rt[x]=merge(rt[x],rt[e[i].to]);

	}

	while (sum[x]>m) {

		sum[x]-=q[rt[x]].val;

		rt[x]=pop(rt[x]);

		size[x]--;

	}

	ans=max(ans,size[x]*L[x]);

}

int main() {

	scanf("%d%d",&n,&m);

	for (int x,i=1;i<=n;i++) {

		scanf("%d",&x);

		link(x,i);

		scanf("%d%lld",&C[i],&L[i]);

	}

	dfs(1);

	printf("%lld",ans);

    return 0;

}

巴特西

【bzoj2809】 Apio2012—dispatching

题意

Solution

细节

代码

Solution

代码

最新文章

热门文章