• 周三. 6月 29th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

[BZOJ 2124]等差子序列

admin

11月 28, 2021

[BZOJ 2124]等差子序列

题目

给一个1到N的排列{Ai},询问是否存在(3<=plen),使得Ap1,Ap2,Ap3,…ApLen是一个等差序列。

INPUT

输入的第一行包含一个整数T,表示组数。下接T组数据,每组第一行一个整数N,每组第二行为一个1到N的排列,数字两两之间用空格隔开。

OUTPUT

对于每组数据,如果存在一个等差子序列,则输出一行“Y”,否则输出一行“N”。

SAMPLE

INPUT

2

3

1 3 2

3

3 2 1

OUTPUT

N

Y

解题报告

神题神思路= =

我们用$01$串代表某个值是否出现过,然后$hash$

对于每次出现的$a[i]$,我们找出向左与向右最长相等长度的$01$串的$hash$值,

判断一下是否相等,如果相等,说明$a[i]-x$与$a[i]+x$在$a[i]$的同侧,就不可能出现长度为$3$的等差数列

线段树瞎$XX$维护一下就好了

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 using namespace std;
 5 inline int read(){
 6     int sum(0);
 7     char ch(getchar());
 8     for(;ch<'0'||ch>'9';ch=getchar());
 9     for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
10     return sum;
11 }
12 typedef long long L;
13 const int p=3;
14 const int mod=1000000007;
15 L xp[10005];
16 L has1[40005],has2[40005];
17 int a[10005];
18 inline void pushup(int i,int len){
19     int tmp(len>>1);
20     has1[i]=(has1[i<<1]*xp[tmp]+has1[i<<1|1])%mod;
21     has2[i]=(has2[i<<1|1]*xp[len-tmp]+has2[i<<1])%mod;
22 }
23 inline void update(int pos,int l,int r,int i){
24     if(l==r){
25         has1[i]=has2[i]=1;
26         return;
27     }
28     int mid((l+r)>>1);
29     if(pos<=mid)
30         update(pos,l,mid,i<<1);
31     else
32         update(pos,mid+1,r,i<<1|1);
33     pushup(i,r-l+1);
34 }
35 inline L query1(int ll,int rr,int l,int r,int i){
36     if(ll>rr)
37         return 0;
38     if(ll==l&&r==rr)
39         return has1[i];
40     int mid((l+r)>>1);
41     if(rr<=mid)
42         return query1(ll,rr,l,mid,i<<1);
43     if(ll>mid)
44         return query1(ll,rr,mid+1,r,i<<1|1);
45     return (query1(ll,mid,l,mid,i<<1)*xp[rr-mid]+query1(mid+1,rr,mid+1,r,i<<1|1))%mod;
46 }
47 inline L query2(int ll,int rr,int l,int r,int i){
48     if(ll>rr)
49         return 0;
50     if(ll==l&&r==rr)
51         return has2[i];
52     int mid((l+r)>>1);
53     if(rr<=mid)
54         return query2(ll,rr,l,mid,i<<1);
55     if(ll>mid)
56         return query2(ll,rr,mid+1,r,i<<1|1);
57     return (query2(ll,mid,l,mid,i<<1)+query2(mid+1,rr,mid+1,r,i<<1|1)*xp[mid-ll+1])%mod;
58 }
59 int main(){
60     int T(read());
61     xp[0]=1;
62     for(int i=1;i<=10000;++i)
63         xp[i]=xp[i-1]*p%mod;
64     while(T--){
65         memset(has1,0,sizeof(has1));
66         memset(has2,0,sizeof(has2));
67         int n(read());
68         for(int i=1;i<=n;++i)
69             a[i]=read();
70         bool flag(false);
71         for(int i=1;i<=n;++i){
72             int len(min(a[i]-1,n-a[i]));
73             L tp1(query1(a[i]-len,a[i]-1,1,n,1)),tp2(query2(a[i]+1,a[i]+len,1,n,1));
74             if(tp1^tp2){
75                 flag=true;
76                 break;
77             }
78             update(a[i],1,n,1);
79         }
80         if(flag)
81             puts("Y");
82         else
83             puts("N");
84     }
85 }

View Code

发表评论

您的电子邮箱地址不会被公开。