洛谷题解 P2757 【[国家集训队]等差子序列】

洛谷题解 P2757 【[国家集训队]等差子序列】

先看代码再解释

#include <bits/stdc++.h>
using namespace std;
int p[10001];int n;
int l[1000001];
bool find()
{
    register int i,j,N=n-1;
    for(i=1;i<N;++i)
    {
        l[p[i]]=-1e9;
        for(j=i+1;j<n;++j)
            if(p[j]+p[j]-p[i]>0&&l[p[j]+p[j]-p[i]]>j) return 1;
    }   
    return 0;
}
inline int read()
{
    char o=getchar();
    int a=0,l=1;
    while(o<'0'||o>'9') {if(o=='-') l=-1;o=getchar();}
    while(o>='0'&&o<='9') {a=a*10+o-'0';o=getchar();} 
    return a;
}
int main()
{
    register int t,i;
    t=read();
    while(t--)
    {
        n=read();
        memset(l,-1e9,sizeof(l));
        for(i=1;i<=n;i++)
        {
            p[i]=read();
            l[p[i]]=i;
        } 
        if(n<3) {putchar('N');putchar('\n');continue;}
        if(find()) putchar('Y');
        else putchar('N');
        putchar('\n');
    }
}

考试时我用了map代替桶结果超时
经过20次的测试后终于知道桶的大小了
这个题解卡评测机是卡的过的
因为题目是说只要三个以上的就可以称为等差数列了所以只要找三个数为等差数列并满足i1<i2<i3便可以