首页 > 代码库 > bzoj2850巧克力王国*
bzoj2850巧克力王国*
bzoj2850巧克力王国
题意：
n个巧克力，每个有牛奶含量，可可含量和美味值。m个人，每个有三个权值a，b，c，如果某个巧克力的牛奶含量*a+可可含量*b<c就可以接受。问每个人能接受的巧克力美味值之和。n，m≤50000。
题解：
对所有巧克力建kd树，树上节点除了维护子树横纵坐标最大最小值还要维护子树美味值之和。在查询时如果估价得出这个子树的牛奶含量最大值乘a+可可含量最大值*b小于c则整棵子树都能接受，否则只要该子树可能有机会存在可接受巧克力就遍历这棵子树。
代码：
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define inc(i,j,k) for(int i=j;i<=k;i++) 5 #define maxn 50010 6 #define ll long long 7 using namespace std; 8 9 inline ll read(){10 char ch=getchar(); ll f=1,x=0;11 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1; ch=getchar();}12 while(ch>=‘0‘&&ch<=‘9‘)x=x*10+ch-‘0‘,ch=getchar();13 return f*x;14 }15 int n,m,f,rt; ll ans;16 struct p{int pos[2],v; bool operator < (const p &a)const{return pos[f]<a.pos[f];}}ps[maxn];17 struct nd{p pos; int mx[2],mn[2],lc,rc; ll sm;}nds[maxn];18 bool check(int a,int b,ll c,ll d,ll e){return c*a+d*b<e;}19 void update(int x){20 inc(i,0,1){21 if(nds[x].lc)22 nds[x].mx[i]=max(nds[x].mx[i],nds[nds[x].lc].mx[i]),23 nds[x].mn[i]=min(nds[x].mn[i],nds[nds[x].lc].mn[i]);24 if(nds[x].rc)25 nds[x].mx[i]=max(nds[x].mx[i],nds[nds[x].rc].mx[i]),26 nds[x].mn[i]=min(nds[x].mn[i],nds[nds[x].rc].mn[i]);27 }28 if(nds[x].lc)nds[x].sm+=nds[nds[x].lc].sm;29 if(nds[x].rc)nds[x].sm+=nds[nds[x].rc].sm;30 }31 int build(int l,int r,int now){32 f=now; int mid=(l+r)>>1; nth_element(ps+l,ps+mid,ps+r+1);33 inc(i,0,1)nds[mid].mx[i]=nds[mid].mn[i]=ps[mid].pos[i]; nds[mid].sm=ps[mid].v; nds[mid].pos=ps[mid];34 if(l<mid)nds[mid].lc=build(l,mid-1,now^1); if(mid<r)nds[mid].rc=build(mid+1,r,now^1);35 update(mid); return mid;36 }37 int get(int x,ll a,ll b,ll c){38 int q=0;39 q+=check(nds[x].mx[0],nds[x].mx[1],a,b,c); q+=check(nds[x].mx[0],nds[x].mn[1],a,b,c);40 q+=check(nds[x].mn[0],nds[x].mx[1],a,b,c); q+=check(nds[x].mn[0],nds[x].mn[1],a,b,c);41 return q;42 }43 void query(int x,ll a,ll b,ll c){44 if(check(nds[x].pos.pos[0],nds[x].pos.pos[1],a,b,c))ans+=nds[x].pos.v; int dl=0,dr=0;45 if(nds[x].lc)dl=get(nds[x].lc,a,b,c); if(nds[x].rc)dr=get(nds[x].rc,a,b,c);46 if(dl==4)ans+=nds[nds[x].lc].sm;else if(dl)query(nds[x].lc,a,b,c);47 if(dr==4)ans+=nds[nds[x].rc].sm;else if(dr)query(nds[x].rc,a,b,c);48 }49 int main(){50 n=read(); m=read(); inc(i,1,n)ps[i].pos[0]=read(),ps[i].pos[1]=read(),ps[i].v=read(); rt=build(1,n,0);51 inc(i,1,m){52 ll x=read(),y=read(),z=read(); ans=0; query(rt,x,y,z); printf("%lld\n",ans);53 }54 return 0;55 }
20160906
bzoj2850巧克力王国*
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。