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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【BZOJ1067】【SCOI2007】【降雨量】  

2014-03-24 14:31:30|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
   题目大意:
   给乃一些年份的降雨量,然后每次一个询问X Y,询问X+1~Y-1年内的降雨量是否严格小于Y,且Y不大于X。如果X+1~Y-1年有的年的数据未知,输出maybe。
   感觉乱搞就可以了??咱们可以把这些年份处理成一个个连通块,只有询问在连通块里面的或者跨越连通块且中间有一个大于Y或者Y大于X或者XY中有一个不知道才能不输出maybe,然后对于询问区间最大一个RMQ的ST即可。
   然后具体的讨论可以去看 huzecong神犇
   感觉这道题比较考语文水平...
   实际交的时候在讨论的时候把一个变量u在中途赋成另一个值了,教训...以后一个变量只作为一个用途!!
==============================

program bzoj1067;
const maxn=50010;
var year,rain:array[0..maxn]of longint;
    x,y:array[0..maxn]of longint;
    f:array[0..maxn,0..16]of longint;
    n,m:longint;

function max(a,b:longint):longint;
begin
  if a>b then exit(a) else exit(b);
end;

function ask(l,r:longint):longint;
var j:longint;
begin
  if r<l then exit(-1);
  j:=trunc(ln(r-l+1)/ln(2));
  exit(max(f[l][j],f[r-(1<<j)+1][j]));
end;

procedure prepare;
var i,j:longint;
begin
  for j:=1 to trunc(ln(n)/ln(2)) do
    for i:=1 to n-1<<j+1 do
      f[i][j]:=max(f[i][j-1],f[i+1<<(j-1)][j-1]);
end;

function find(x:longint):longint;
var l,r,mid:longint;
begin
  l:=1;r:=n;
  while l<r do
   begin
     mid:=(l+r)shr 1;
     if year[mid]=x then exit(mid);
     if year[mid]<x then l:=mid+1
                    else r:=mid-1;
   end;
  exit(l);
end;

procedure init;
var i,u,v,j,k:longint;
begin
  read(n);
  for i:=1 to n do
   read(year[i],rain[i]);
  for i:=1 to n do
    f[i][0]:=rain[i];
  prepare;
  read(m);
  for i:=1 to m do
   begin
     read(u,v);
     if u>v then
      begin
        writeln('false');
        continue;
      end;
     j:=find(u);
     k:=find(v);
     if (year[j]=u)and(year[k]=v) then
      if (v-u=k-j) then
       if (rain[j]>=rain[k]) then
        if ask(j+1,k-1)<rain[k] then
         begin
          writeln('true');
          continue;
         end;
     if (year[j]<>u)and(year[k]<>v)then
      begin
        writeln('maybe');
        continue;
      end;
     if (year[j]<>u)or(year[k]<>v) then
      begin
        while (year[j]>u)and(j<>0) do dec(j);
        while (year[k]<v)and(k<=n) do inc(k);
        if year[j]<>u then v:=k
                      else v:=j;
        u:=ask(j+1,k-1); 
        if u<rain[v] then writeln('maybe')
                     else writeln('false');
        continue;
      end;
     if (k-j<>v-u) then
      if (rain[j]>=rain[k]) then
       begin
         u:=ask(j+1,k-1);
         if u<rain[k] then writeln('maybe')
                      else writeln('false');
         continue;
       end;
     writeln('false');
   end;
end;

begin
  init;
end.





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

历史上的今天

评论

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

页脚

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