首页 > 代码库 > [HZOJ10420]计算

[HZOJ10420]计算

2024-11-27 15:49:39   203人阅读

[HZOJ10420]计算

题目

给定一个数列，第i个位置包含两个数ai，bi

每次询问给出x，y

求数列ai*x+bi*y的最大值

输入所有数为自然数，在int范围内

INPUT

第一行为n，m。n为数列长度,m为询问个数。

接下来n行，每行两个数，代表ai，bi

接下来m行，每行两个数，代表x，y

OUTPUT

共m行，每行输出一个答案

SAMPLE

INPUT

3 3

1 5

9 0

9 1

4 4

1 1

3 4

OUTPUT

40

10

31

解题报告

首道估值线段树留念

首先，我们看题目，输入所有数据为自然数，自然数意味着不会有负数，那么，我们就可以确定，$a$和$b$越大，答案也就可能越大

剩下的就是如何找到准确的最大值了

我们可以用线段树处理出来每个区间的最大的$a$和$b$，然后，对于每一个询问，我们在线段树中进行搜索，我们可以用这个区间最大的$a$和$b$来限制搜索的范围，具体做法：

对于每一次搜索，我们先瞎XX搜到某一个子节点（一般来说是第一个子节点，根据线段树的实现而定），获得一个准确的$ans$值，然后，我们在搜索的时候，假如获得的该区间最大的$a$和$b$所计算出来的函数值都没有当前的$ans$大，我们可以直接舍弃该区间，这样下去，我们得到的$ans$值一定是越来越大的，然后可以舍弃的区间也就越来越多，从而比$O(n)$枚举每一个$a$和$b$更快，更加优秀。最终也可以得到最优解

实现基本上就是线段树+$DFS$：

技术分享
 1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 using namespace std; 5 inline int read(){ 6     int sum(0); 7     char ch(getchar()); 8     for(;ch<‘0‘||ch>‘9‘;ch=getchar()); 9     for(;ch>=‘0‘&&ch<=‘9‘;sum=sum*10+(ch^48),ch=getchar());10     return sum;11 }12 typedef long long L;13 struct node{14     int l,r;15     L maxa,maxb;16     node *lch,*rch;17     node():l(0),r(0),maxa(0),maxb(0),lch(NULL),rch(NULL){}18 }a[400005],*root;19 int n,m,cnt;20 inline void pushup(node *rt){21     rt->maxa=max(rt->lch->maxa,rt->rch->maxa);22     rt->maxb=max(rt->lch->maxb,rt->rch->maxb);23 }24 inline void build(int l,int r,node *rt){25     rt->l=l,rt->r=r;26     if(l==r){27         rt->maxa=read(),rt->maxb=read();28         return;29     }30     rt->lch=&a[++cnt],rt->rch=&a[++cnt];31     int mid((l+r)>>1);32     build(l,mid,rt->lch);33     build(mid+1,r,rt->rch);34     pushup(rt);35 }36 inline L query_a(int l,int r,node *rt){37     if(l<=rt->l&&rt->r<=r)38         return rt->maxa;39     int mid((rt->l+rt->r)>>1);40     L ret(-0x7fffffff);41     if(l<=mid)42         ret=max(ret,query_a(l,r,rt->lch));43     if(mid<r)44         ret=max(ret,query_a(l,r,rt->rch));45     return ret;46 }47 inline L query_b(int l,int r,node *rt){48     if(l<=rt->l&&rt->r<=r)49         return rt->maxb;50     int mid((rt->l+rt->r)>>1);51     L ret(-0x7fffffff);52     if(l<=mid)53         ret=max(ret,query_b(l,r,rt->lch));54     if(mid<r)55         ret=max(ret,query_b(l,r,rt->rch));56     return ret;57 }58 L ans;59 inline void dfs(L x,L y,node *rt){60     if(rt->l==rt->r){61         ans=max(ans,x*(rt->maxa)+y*(rt->maxb));62         return;63     }64     L ans1(x*(rt->lch->maxa)+y*(rt->lch->maxb)),ans2(x*(rt->rch->maxa)+y*(rt->rch->maxb));65     if(ans1>ans)66         dfs(x,y,rt->lch);67     if(ans2>ans)68         dfs(x,y,rt->rch);69 }70 int main(){71     n=read(),m=read();72     root=&a[++cnt];73     build(1,n,root);74     for(int i=1;i<=m;++i){75         L x(read()),y(read());76         ans=-0x7fffffff;77         dfs(x,y,root);78         printf("%lld\n",ans);79     }80 }
View Code

 

[HZOJ10420]计算


联系
我们