首页 > 代码库 > BZOJ2124: 等差子序列
BZOJ2124: 等差子序列
2124: 等差子序列
Time Limit: 3 Sec Memory Limit: 259 MBSubmit: 365 Solved: 151
[Submit][Status]
Description
给一个1到N的排列{Ai}，询问是否存在1<=p1=3），使得Ap1,Ap2,Ap3,…ApLen是一个等差序列。
Input
输入的第一行包含一个整数T，表示组数。下接T组数据，每组第一行一个整数N，每组第二行为一个1到N的排列，数字两两之间用空格隔开。
Output
对于每组数据，如果存在一个等差子序列，则输出一行“Y”，否则输出一行“N”。
Sample Input
2
3
1 3 2
3
3 2 1
3
1 3 2
3
3 2 1
Sample Output
N
Y
Y
HINT
对于100%的数据，N<=10000，T<=7
Source
题解：
这题的思路比较巧妙
从左到右扫描，维护01序列，表示到当前这个点，每个值是否出现过
当且仅当 这个点向左和向右不论扩展多长，01序列都相同时，才表示这个点不会作为等差中项（a[i]-x,a[i]+x的出现情况相同，说明都未出现或都已出现）
判断两个字符串是否相等可以用hash
然后就变成单点修改，区间查询了---线段树
代码：
1 {$inline on} 2 const base=3;p=100000007;maxn=10000+10; 3 type node=record 4 l,r,mid,s:longint; 5 v1,v2:int64 6 end; 7 var t:array[0..6*maxn] of node; 8 a:array[0..maxn] of longint; 9 b:array[0..maxn] of int64;10 i,n,x,y,cs:longint;11 xx,yy:longint;12 function min(x,y:longint):longint;inline;13 begin14 if x<y then exit(x) else exit(y);15 end;16 17 procedure build(k,x,y:longint);inline;18 begin19 with t[k] do20 begin21 l:=x;r:=y;mid:=(l+r)>>1;s:=r-l+1;v1:=0;v2:=0;22 if l=r then exit;23 build(k<<1,l,mid);24 build(k<<1+1,mid+1,r);25 end;26 end;27 procedure change(k,x,y:longint);inline;28 begin29 with t[k] do30 begin31 if l=r then32 begin33 v1:=y;v2:=y;;exit;34 end;35 if x<=mid then change(k<<1,x,y)36 else change(k<<1+1,x,y);37 v1:=(t[k<<1].v1*b[t[k<<1+1].s]+t[k<<1+1].v1) mod p;38 v2:=(t[k<<1+1].v2*b[t[k<<1].s]+t[k<<1].v2) mod p;39 end;40 end;41 function query1(k,x,y:longint):int64;inline;42 begin43 with t[k] do44 begin45 if (l=x) and (r=y) then exit(v1);46 if y<=mid then exit(query1(k<<1,x,y))47 else if x>mid then exit(query1(k<<1+1,x,y))48 else exit(((query1(k<<1,x,mid)*b[(y-mid)]+query1(k<<1+1,mid+1,y))) mod p);49 end;50 end;51 function query2(k,x,y:longint):int64;inline;52 begin53 with t[k] do54 begin55 if (l=x) and (r=y) then exit(v2);56 if y<=mid then exit(query2(k<<1,x,y))57 else if x>mid then exit(query2(k<<1+1,x,y))58 else exit(((query2(k<<1+1,mid+1,y)*b[(mid-x+1)]+query2(k<<1,x,mid))) mod p);59 end;60 end;61 procedure init;62 begin63 readln(n);64 for i:=1 to n do read(a[i]);readln;65 build(1,1,n);66 end;67 function check:boolean;inline;68 begin69 if n<=2 then exit(false);70 for i:=1 to n do71 begin72 x:=a[i];73 y:=min(n-a[i],a[i]-1);74 if (a[i]<>1) and (a[i]<>n) then75 begin76 xx:=query1(1,x-y,x-1);yy:=query2(1,x+1,x+y);77 if xx<>yy then exit(true);78 end;79 change(1,a[i],1);80 end;81 exit(false);82 end;83 begin84 assign(input,‘input.txt‘);assign(output,‘output.txt‘);85 reset(input);rewrite(output);86 readln(cs);87 b[1]:=base;88 for i:=2 to maxn do b[i]:=b[i-1]*base mod p;89 while cs>0 do90 begin91 dec(cs);92 init;93 if check then writeln(‘Y‘) else writeln(‘N‘);94 end;95 close(input);close(output);96 end.97
（吐槽：wikioi数据真心弱？在wikioi上1A，结果在bzoj上就WA了，把数据类型改了改就A了。。。）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。