注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ1067][SCOI2007]降雨量  

2014-10-28 21:04:53|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1067: [SCOI2007]降雨量

被大姐吓着了……讨论了无数种情况……
然后交上去RE了~\(≧▽≦)/~
搞下来数据一看原来是ST表跪了._.
真的好长时间没写了
代码比较丑见谅
题解在代码下方

#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
int scan(){int i=0;scanf("%d",&i);return i;}
const int N = 5E4+10;
const int LOGN = 21;
int n,m,st[N][LOGN];
int year[N],data[N],two[50];
int ask(int l,int r){
if(l>r)return -1;
int k = log2(r-l+1);
return max(st[l][k],st[r-two[k]+1][k]);
}
int main(){
int i,j,a,b;
//freopen("6.in","r",stdin);
//freopen("NULL","w",stdout);
n = scan()+1;
//left edge
year[1] = -2e9+7;
data[1] = -2e9+7;
//right edge
year[n+1] = 2e9+7;
data[n+1] = 2e9+7;
//小心边界吃屎

for(i=2;i<=n;i++){
a = scan();b = scan();
year[i] = a;
st[i][0] = data[i] = b;
}
for(two[0]=1,i=1;i<=30;i++)two[i] = two[i-1]*2;
int lgn = log2(n+1)+1;
for(j=1;j<=lgn;j++)
for(i=1;i+two[j-1]<=(n+1);i++)
st[i][j] = max(st[i][j-1],st[i+two[j-1]][j-1]);
m = scan();
int l,r,tmp;


for(i=1;i<=m;i++){
a = scan();b = scan();
//输入不合法
if(a>b){printf("false\n");continue;}
//a==b
if(a==b){printf("true\n");continue;}
bool ok[3]={};
l = upper_bound(year+1,year+1+n,a) - year;
r = (lower_bound(year+1,year+1+n,b)- year) - 1;
if(year[l-1] == a)ok[0] = 1;
if(year[r+1] == b)ok[1] = 1;
//a~b都不存在
if(r<l && !(ok[0] && ok[1])){printf("maybe\n");continue;}
tmp = ask(l,r);
//a存在 & 中间的比a大
if(ok[0] && tmp >= data[l-1]){
printf("false\n");
continue;
}
//b存在 & 中间的比b大
if(ok[1] && tmp >= data[r+1]){
printf("false\n");
continue;
}
//有中间的但两边不存在
if((ok[0] || ok[1]) == 0){
printf("maybe\n");
continue;
}
//左右两边存在
if(ok[0] && ok[1]){
//不满足b<=a
if(data[r+1] > data[l-1]) printf("false\n");
//满足
else if(r-l+1 +2 == b-a+1)printf("true\n");
else printf("maybe\n");
continue;
}
//只有一边
printf("maybe\n");
}
return 0;
}


题解:
ST表+分类讨论
需要注意的情况:
1.某些部分/全部不存在 -> false or maybe
2.询问不合法(false),询问内容不存在但是两个值相等(true)
3.边界
具体看代码吧
-------------------------------------------------------------------------------------------------------------
然后是ST表模板。。话说这种东西也没人要吧

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=1E5+10;
const int LOGN = 21;
int n,m,st[N][LOGN],two[30];
int scan(){int i=0;scanf("%d",&i);return i;}
int ask(int l,int r){
int k = log2(r-l+1); //这里不+1
return max(st[l][k],st[r-two[k]+1][k]); //注意 "r-two[k]+1"
}
int main(){
int i,j;
n = scan();
for(i=1;i<=n;i++)st[i][0] = scan();
for(two[0]=1,i=1;i<=30;i++)two[i]=two[i-1]*2;

int lgn = log2(n)+1; //这里要+1
for(j=1;j<=lgn;j++)
for(i=1;i+two[j-1] <= n;i++) //注意结束条件
st[i][j] = max(st[i][j-1],st[i+two[j-1]][j-1]);
return 0;
}


  评论这张
 
阅读(21)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017