JZOJ_7.18C组第一题 好元素

本文主要是介绍JZOJ_7.18C组第一题 好元素，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意

给出一个序列，如果满足$ai+aj+ak=al(i,j,k<l)(i,j,k可以相同)$，那么$al$就是一个好元素，求出这个序列里一共有多少个好元素。

思路

hash判重。我们可以让$ai+aj+ak=al$移项变成$ai+aj=al-ak$，然后我们就可以用$n^{2}$的方法来做了。每次把$ai+aj$扔到hash表，然后查询$al-ak$是否存在，累加答案。

代码

#include<cstdio>
#include<cstring>
#define MAXN 25000003
#define hash(x) (x%MAXN+MAXN)%MAXN//负数要特殊判断
#define push(x) h[find(x)]=x;
using namespace std;
int n,a[5001],h[MAXN],ans;
inline int find(int x)
{int f=hash(x);while (h[f]!=2139062143&&h[f]!=x) f=(f+1)%MAXN;return f;
}
inline bool check(int x)
{int f=find(x);return h[f]==x;
}
int main()
{memset(h,0x7f,sizeof(h));//因为0要特殊判断scanf("%d",&n);for (int i=1;i<=n;i++){scanf("%d",&a[i]);for (int j=1;j<i;j++) push(a[i-1]+a[j]);//扔a[i]+a[j]for (int j=1;j<i;j++)if (check(a[i]-a[j]))//查询a[l]-a[k]{ans++;break;}}printf("%d",ans);
}

这篇关于JZOJ_7.18C组第一题 好元素的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---