「题解」好元素 good

(未完待续:全部)

题目链接: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;
}