Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 2148 Solved: 554
我们常常会说这样的话:“X年是自Y年以来降雨量最多的”。它的含义是X年的降雨量不超过Y年,且对于任意Y<Z<X,Z年的降雨量严格小于X年。例如2002,2003,2004和2005年的降雨量分别为4920,5901,2832和3890,则可以说“2005年是自2003年以来最多的”,但不能说“2005年是自2002年以来最多的”由于有些年份的降雨量未知,有的说法是可能正确也可以不正确的。
输入仅一行包含一个正整数n,为已知的数据。以下n行每行两个整数yi和ri,为年份和降雨量,按照年份从小到大排列,即yi<yi+1。下一行包含一个正整数m,为询问的次数。以下m行每行包含两个数Y和X,即询问“X年是自Y年以来降雨量最多的。”这句话是必真、必假还是“有可能”。
对于每一个询问,输出true,false或者maybe。
6 2002 4920 2003 5901 2004 2832 2005 3890 2007 5609 2008 3024 5 2002 2005 2003 2005 2002 2007 2003 2007 2005 2008
false true false maybe false
100%的数据满足:1<=n<=50000, 1<=m<=10000, -10^9<=yi<=10^9, 1<=ri<=10^9
题解:逗比的我果然还是选了个要人命的题目额。。。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 begin
14 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 begin
22 for j:=1 to trunc(ln(n)/ln(2)) do
23 for i:=1 to n-1 shl j+1 do
24 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 begin
30 l:=1;r:=n;
31 while l<r do
32 begin
33 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 begin
40 read(n);
41 for i:=1 to n do
42 read(c[i],b[i]);
43 for i:=1 to n do
44 f[i][0]:=b[i];
45 built;
46 read(m);
47 for i:=1 to m do
48 begin
49 read(x0,y0);
50 if x0>y0 then
51 begin
52 writeln('false');
53 continue;
54 end;
55 j:=find(x0);
56 k:=find(y0);
57 if (c[j]=x0)and(c[k]=y0) then
58 if (y0-x0=k-j) then
59 if (b[j]>=b[k]) then
60 if cal(j+1,k-1)<b[k] then
61 begin
62 writeln('true');
63 continue;
64 end;
65 if (c[j]<>x0)and(c[k]<>y0)then
66 begin
67 writeln('maybe');
68 continue;
69 end;
70 if (c[j]<>x0)or(c[k]<>y0) then
71 begin
72 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) then
80 if (b[j]>=b[k]) then
81 begin
82 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.