（未完待续：全部）

题目链接：JZOJ 3508。

题目

题目描述

小 A 一直认为，如果在一个由 $N$ 个整数组成的数列 $\{ A _ {n} \}$ 中，存在 $A _ m+A _ n+A _ p=A _ i(1\leq m,n,p\leq i-1)$（ $m,n,p$ 可以相同）的话，$A _ i$ 就是一个“好元素”。现在，小 A 有一个数列，他想知道这个数列中有多少个“好元素”，请你帮帮他。

输入格式

第一行只有一个正整数 $N$ ，意义如上。
第二行包含 $N$ 个整数，表示数列 $\{A _ n\}$。

输出格式

输出一个整数，表示这个数列中“好元素”的个数。

样例输入输出

#1

• Input:

2
1 3

• Output:

1

#2

• Input:

6
1 2 3 5 7 10

• Output:

4

#3

• Input:

3
-1 2 0

• Output:

1

数据范围

对于 $10\%$ 的数据 $1\leq N\leq 10$；
对于 $40\%$ 的数据 $1\leq N\leq 500,-10^5\leq A _ i\leq 10^5$；
对于 $70\%$ 的数据 $1\leq N\leq 5000,-10^6\leq A _ i\leq 10^6$；
对于 $100\%$ 的数据 $1\leq N\leq 5000,-10^9\leq A _ i\leq 10^9$。

时空限制

$$2\text{s}/256\text{MiB}$$
本题有部分分做法（10分、40分、70分、100分（AC）），详情请见下一页。

题解

解法 A （直接模拟）

思路

采用渐进时间复杂度为 $\Theta(n^4)$ 的模拟算法。

代码

没写。

解法 B

思路

代码

解法 C

思路

代码

解法 D

#include<cstdio>
#define INF 2147483647
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
    register bool flag=false;
    register char ch=getchar();
    register int res=0;
    while(ch<'0'||'9'<ch){if(ch=='-')flag=true;ch=getchar();}
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return flag?-res:res;
}
const int MAXN=5000+5;
struct Hash{
    #define MAXSIZE 25000005
    int h[MAXSIZE];
    void Init(void){
        register int i;
        for(i=0;i<MAXSIZE;++i)
            h[i]=INF;
        return;
    }
    int find(int x){
        register int f=(x%MAXSIZE+MAXSIZE)%MAXSIZE;
        while(h[f]!=INF&&h[f]!=x)
            f=(f+1)%MAXSIZE;
        return f;
    }
    bool check(int x){
        return h[find(x)]==x;
    }
    void push(int x){
        h[find(x)]=x;
        return;
    }
    #undef MAXSIZE
};
int n,a[MAXN];
Hash H;
int main(void){
    //freopen("good.in","r",stdin);
    //freopen("good.out","w",stdout);
    register int i,j,ans=0;
    n=read();
    //scanf("%d",&n);
    H.Init();
    for(i=1;i<=n;++i){
        a[i]=read();
        //scanf("%d",&a[i]);
        for(j=1;j<i;++j)
            H.push(a[i-1]+a[j]);
        for(j=1;j<i;++j)
            if(H.check(a[i]-a[j])){
                ++ans;
                break;
            }
    }
    printf("%d\n",ans);
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}