(未完待续:全部)
题目链接: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;
}
近期评论