P2757 [国家集训队]等差子序列

2018-09-18 16:36:09


这个题数据给的很小, $N<=10000$

暴力就是开一个桶记录每一个数的位置

枚举首项、公差,判断即可

这样就可以拿到 $45$ 分的好成绩

~~如果你常数够小的话可以得到 $50$ 或 $55$ ~~

讲一下 $100$ 分做法:

这是一个 $1$ 到 $n$ 的排列

用一个 $01$ 串来表示各个数字的出现情况

例如序列为 ${1,6,4,2,5,3}$ ,从前往后扫到 $2$ 的时候

$01$ 串长这样: ${110101}$

可以发现,如果以一个出现的数为中心,两边对称的地方有 $1$ ,则存在等差数列

用线段树或树状数组维护 $hash$ 值

从左往右扫,对于每一个 $a_i$ 查询它两边的 $hash$ 值是否相等

如果不相等,那么后面一定会有数补过来形成等差数列,输出 $Y$ 即可

所以区间查询单点修改,总复杂度 $O(nlogn)$

$CF452F$ 也是这个题,不过数据范围 $3e5$ 嘿嘿嘿

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define reg register
using namespace std;
typedef unsigned long long ll;
const int N=1e4+5,base=127;
int n,a[N];
ll pw[N],hs1[N<<2],hs2[N<<2];
inline int read()
{
    int x=0,w=1;
    char c=getchar();
    while (!isdigit(c)&&c!='-') c=getchar();
    if (c=='-') c=getchar(),w=-1;
    while (isdigit(c))
    {
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return x*w;
}
inline void pushup(int now,int l,int r)
{
    hs1[now]=(hs1[now<<1]*pw[r]+hs1[now<<1|1]);
    hs2[now]=(hs2[now<<1]+hs2[now<<1|1]*pw[l]);
}
void update(int l,int r,int now,int x)
{
    if (l==r){hs1[now]=hs2[now]=1; return;}
    int mid=(l+r)>>1;
    if (x<=mid) update(l,mid,now<<1,x);
    else update(mid+1,r,now<<1|1,x);
    pushup(now,mid-l+1,r-mid);
}
ll query1(int L,int R,int l,int r,int now)
{
    if (l>R||r<L) return 0;
    if (l>=L&&r<=R) return hs1[now];
    int mid=(l+r)>>1;
    if (mid>=R) return query1(L,R,l,mid,now<<1);
    if (mid<L) return query1(L,R,mid+1,r,now<<1|1);
    return (query1(L,mid,l,mid,now<<1)*pw[R-mid]+query1(mid+1,R,mid+1,r,now<<1|1));
}
ll query2(int L,int R,int l,int r,int now)
{
    if (l>R||r<L) return 0;
    if (l>=L&&r<=R) return hs2[now];
    int mid=(l+r)>>1;
    if (mid>=R) return query2(L,R,l,mid,now<<1);
    if (mid<L) return query2(L,R,mid+1,r,now<<1|1);
    return (query2(L,mid,l,mid,now<<1)+query2(mid+1,R,mid+1,r,now<<1|1)*pw[mid-L+1]);
}
int main()
{
    pw[0]=1;
    for (reg int i=1;i<=10000;i++) pw[i]=pw[i-1]*base;
    for (reg int T=read();T;T--)
    {
        memset(hs1,0,sizeof(hs1));
        memset(hs2,0,sizeof(hs2));
        n=read(); bool flag=0;
        for (reg int i=1;i<=n;a[i++]=read());
        if (n<3) {puts("N"); continue;}
        for (reg int i=1;i<=n;i++)
        {
            int len=min(a[i]-1,n-a[i]);
            if (query1(a[i]-len,a[i]-1,1,n,1)!=query2(a[i]+1,a[i]+len,1,n,1)){flag=1; break;}
            update(1,n,1,a[i]);
        }
        if (flag) puts("Y"); else puts("N");
    }
    return 0;
}