求好元素
如果在一个由 (N) 个整数组成的数列 (A_N) 中，存在 (A_m+A_n+A_p=A_i(ileq m,n,p<i)) （ (m,n,p) 可以相同）的话，就是一个“好元素”。
现在，有一个数列，要求求出这个数列中有多少个“好元素”。
题解
不妨设 (mleq n< i) 。
如果直接求的话，是 (n^3) 的。
考虑进行优化。
- 移项一下： (A_m+A_n=A_i-A_p) 。
- 既然 (mleq n) ，那么随着 (m,n) 的增加，(A_i-A_p) 的可取值集合是单调变大的。所以我们可以直接将所有 (A_m+A_n) 放入哈希表中。
- 发现：对于确定的 $ n$ ， (iin(n,N]) ，而集合单调变大，则 (i) 是可以仅取 (n+1) 的。
复杂度 (O(n^2)).
代码
#include <bits/stdc++.h>
#define fo(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std;
const int INF = 0x3f3f3f3f,N = 5e3+5;
typedef long long ll;
typedef unsigned long long ull;
inline ll read(){
ll ret=0;char ch=' ',c=getchar();
while(!(c>='0'&&c<='9'))ch=c,c=getchar();
while(c>='0'&&c<='9')ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
return ch=='-'?-ret:ret;
}
int n;
ll a[N];
const ll HT = 1e6+5 , Hmod = 1e6;
struct HashTable{int to,nxt;}e[N*N];
int head[HT],ecnt = -1 , ncnt;
ll nd[N*N];
inline void insert(ll x){
x += 1e9;
ll u = x % Hmod;
nd[++ncnt] = x;
e[++ecnt] = (HashTable){ncnt,head[u]} , head[u] = ecnt;
}
bool find(ll x){
x += 1e9;
for(int i = head[x%Hmod] ; ~i ; i = e[i].nxt)
if(nd[e[i].to] == x) return true;
return false;
}
int ans;
signed main(){
memset(head,-1,sizeof(head));
n = read();
for(int i = 1 ; i <= n ; i ++) a[i] = read();
for(int i = 1 ; i < n ; i ++){
for(int j = 1 ; j <= i ; j ++)
insert(a[i]+a[j]);
for(int j = 1 ; j <= i ; j ++)
if(find(a[i+1]-a[j])) {ans ++; break;}
}
printf("%d",ans);
return 0;
}