首页 > 代码库 > 1067: [SCOI2007]降雨量
1067: [SCOI2007]降雨量
1067: [SCOI2007]降雨量
Time Limit: 1 Sec Memory Limit: 162 MBSubmit: 2148 Solved: 554
[Submit][Status]
Description
我们常常会说这样的话：“X年是自Y年以来降雨量最多的”。它的含义是X年的降雨量不超过Y年，且对于任意Y＜Z＜X，Z年的降雨量严格小于X年。例如2002，2003，2004和2005年的降雨量分别为4920，5901，2832和3890，则可以说“2005年是自2003年以来最多的”，但不能说“2005年是自2002年以来最多的”由于有些年份的降雨量未知，有的说法是可能正确也可以不正确的。
Input
输入仅一行包含一个正整数n，为已知的数据。以下n行每行两个整数yi和ri，为年份和降雨量，按照年份从小到大排列，即yi＜yi+1。下一行包含一个正整数m，为询问的次数。以下m行每行包含两个数Y和X，即询问“X年是自Y年以来降雨量最多的。”这句话是必真、必假还是“有可能”。
Output
对于每一个询问，输出true，false或者maybe。
Sample Input
2002 4920
2003 5901
2004 2832
2005 3890
2007 5609
2008 3024
5
2002 2005
2003 2005
2002 2007
2003 2007
2005 2008
Sample Output
true
false
maybe
false
HINT
100%的数据满足：1<=n<=50000, 1<=m<=10000, -10^9<=yi<=10^9, 1<=ri<=10^9
Source
POJ 2637 WorstWeather Ever
题解：逗比的我果然还是选了个要人命的题目额。。。TT。。。害得我纠结了2个小时。。。好了思路——其实核心部件就是个球区间最大值（可以选择RMQ或者线段树，但是还是建议RMQ,因为线段树O(logn)的复杂度伤不起啊，别忘了时限为1s），接下来就是各种坑爹的WA——原因很简单也很不简单——这道题虽然true的情况只有一种很明显，但是maybe有N多情况！！！要命啊！！！简直改到发疯。。。接下来引用hzwer神犇的话，我自己改来改去也讲不太清楚了，不过大概意思就是这样（hzwer的题解传送门）：
需要考虑很多情况。比如第x年到第y年
如果y<x，不知道有没这种情况，应该是false吧
true的情况需要满足
x与y的值都已知且y值<x值且x+1到y-1都已知并且都小于y值
maybe满足
1.x值y值均未知
2.已知x值未知y值并且x+1到y-1都已知并且都小于y值
3.已知y值未知x值并且x+1到y-1都已知并且都小于x值
4.x为年份最大一年，y>x
5.y为年份最小一年，x<y
6.x，y均已知且y<x并且x+1到y-1有未知并且都小于x值
其它都是false
大概这样。。。
这种题一遍AC的是神
***调了几个小时
1 var //HansBug的萌萌哒code 2 c,b:array[0..100010]of longint; 3 x,y:array[0..100010]of longint; 4 f:array[0..100010,0..20]of longint; 5 i,j,k,n,m,x0,y0:longint; 6 function max(a,b:longint):longint; 7 begin 8 if a>b then exit(a) else exit(b); 9 end;10 function cal(l,r:longint):longint;11 var 12 j:longint;13 begin14 if r<l then exit(-1);15 j:=trunc(ln(r-l+1)/ln(2));16 exit(max(f[l][j],f[r-(1 shl j)+1][j]));17 end;18 procedure built;19 var 20 i,j:longint;21 begin22 for j:=1 to trunc(ln(n)/ln(2)) do23 for i:=1 to n-1 shl j+1 do24 f[i][j]:=max(f[i][j-1],f[i+1 shl (j-1)][j-1]);25 end;26 function find(x:longint):longint;27 var 28 l,r,mid:longint;29 begin30 l:=1;r:=n;31 while l<r do32 begin33 mid:=(l+r)shr 1;34 if c[mid]=x then exit(mid);35 if c[mid]<x then l:=mid+1 else r:=mid-1;36 end;37 exit(l);38 end;39 begin40 read(n);41 for i:=1 to n do42 read(c[i],b[i]);43 for i:=1 to n do44 f[i][0]:=b[i];45 built;46 read(m);47 for i:=1 to m do48 begin49 read(x0,y0);50 if x0>y0 then51 begin52 writeln(‘false‘);53 continue;54 end;55 j:=find(x0);56 k:=find(y0);57 if (c[j]=x0)and(c[k]=y0) then58 if (y0-x0=k-j) then59 if (b[j]>=b[k]) then60 if cal(j+1,k-1)<b[k] then61 begin62 writeln(‘true‘);63 continue;64 end;65 if (c[j]<>x0)and(c[k]<>y0)then66 begin67 writeln(‘maybe‘);68 continue;69 end;70 if (c[j]<>x0)or(c[k]<>y0) then71 begin72 while (c[j]>x0)and(j<>0) do dec(j);73 while (c[k]<y0)and(k<=n) do inc(k);74 if c[j]<>x0 then y0:=k else y0:=j;75 x0:=cal(j+1,k-1); 76 if x0<b[y0] then writeln(‘maybe‘) else writeln(‘false‘);77 continue;78 end;79 if (k-j<>y0-x0) then80 if (b[j]>=b[k]) then81 begin82 x0:=cal(j+1,k-1);83 if x0<b[k] then writeln(‘maybe‘) else writeln(‘false‘);84 continue;85 end;86 writeln(‘false‘);87 end;88 end.
1067: [SCOI2007]降雨量