hdu 1823 Luck and Love
2018-06-17 21:49:25来源:未知 阅读 ()
Luck and Love
Time Limit : 10000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 21 Accepted Submission(s) : 11
而是我在你面前
可你却不知道我爱你
―― 张小娴
前段日子,枫冰叶子给Wiskey做了个征婚启事,聘礼达到500万哦,天哪,可是天文数字了啊,不知多少MM蜂拥而至,顿时万人空巷,连扫地的大妈都来凑热闹来了。―_―|||
由于人数太多,Wiskey实在忙不过来,就把统计的事情全交给了枫冰叶子,自己跑回家休息去了。这可够枫冰叶子忙的了,他要处理的有两类事情,一是得接受MM的报名,二是要帮Wiskey查找符合要求的MM中缘分最高值。
这道题目被称为入门二维线段树。。
不好做的地方就是,开始没有想到这会是二维,建线段树必分区间。一开始想的就是从哪个量下手来分。
此处以身高为一维,活泼度为二维。
#include <iostream> #include <cstdio> #include <algorithm> #include<vector> #include<cstring> using namespace std; struct nod { int l,r; double maxv; }; struct node { int l,r; nod str[2050<<2]; }tr[2050<<2]; void subbuild(int ll,int rr,int n,int sn) { tr[n].str[sn].l=ll; tr[n].str[sn].r=rr; tr[n].str[sn].maxv=-1; if(ll==rr) return; int m=(ll+rr)>>1; subbuild(ll,m,n,sn<<1); subbuild(m+1,rr,n,sn<<1|1); } void build(int l,int r,int ll,int rr,int n) { tr[n].l=l; tr[n].r=r; subbuild(ll,rr,n,1); if(l==r) return; int m=(l+r)>>1; build(l,m,ll,rr,n<<1); build(m+1,r,ll,rr,n<<1|1); } void updata(int ho,double yu,int n,int sn) //subtree { int l=tr[n].str[sn].l; int r=tr[n].str[sn].r; if(l==r){ tr[n].str[sn].maxv=max(yu,tr[n].str[sn].maxv); return; } int m=(l+r)>>1; if(ho<=m) updata(ho,yu,n,sn<<1); else updata(ho,yu,n,sn<<1|1); tr[n].str[sn].maxv=max(tr[n].str[sn<<1].maxv,tr[n].str[sn<<1|1].maxv); } void up(int hi,int ho,double yu,int n) { int l=tr[n].l; int r=tr[n].r; updata(ho,yu,n,1); if(l==r) return; int m=(l+r)>>1; if(hi<=m) up(hi,ho,yu,n<<1); else up(hi,ho,yu,n<<1|1); } double querysub(int ll,int rr,int n,int sn) { int l=tr[n].str[sn].l; int r=tr[n].str[sn].r; if(l==ll&&r==rr){ return tr[n].str[sn].maxv; } int m=(l+r)>>1; double res=-1.0; if(ll<=m) res=max(res,querysub(ll,min(m,rr),n,sn<<1)); if(rr>m) res=max(res,querysub(max(ll,m+1),rr,n,sn<<1|1)); return res; } double query(int l,int r,int ll,int rr,int n) { if(tr[n].l==l&&tr[n].r==r){ return querysub(ll,rr,n,1); } int m=(tr[n].l+tr[n].r)>>1; double res=-1.0; if(l<=m){ res=max(res,query(l,min(m,r),ll,rr,n<<1)); } if(r>m){ res=max(res,query(max(l,m+1),r,ll,rr,n<<1|1)); } return res; } int main() { int t; while(scanf("%d",&t),t) { build(100,200,0,1000,1); while(t--) { char x[2]; scanf("%s",x); int h1,h2; double ho1,ho2,yu; if(x[0]=='I'){ scanf("%d%lf%lf",&h1,&ho1,&yu); up(h1,(int)(ho1*10),yu,1); } else{ scanf("%d%d%lf%lf",&h1,&h2,&ho1,&ho2); if(h1>h2) swap(h1,h2); if(ho1>ho2) swap(ho1,ho2); double res=query(h1,h2,(int)(ho1*10),(int)(ho2*10),1); if(res<0) puts("-1"); else printf("%.1lf\n",res); } } } }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- HDU-2955-Robberies(0-1背包) 2020-03-30
- hdu1455 拼木棍(经典dfs) 2020-02-29
- anniversary party_hdu1520 2020-02-16
- hdu1062 text reverse 2020-01-27
- hdu4841 2020-01-26
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash