求好元素
如果在一个由 \(N\) 个整数组成的数列 \(A_N\) 中，存在 \(A_m+A_n+A_p=A_i(i\leq m,n,p<i)\) （ \(m,n,p\) 可以相同）的话，就是一个“好元素”。
现在，有一个数列，要求求出这个数列中有多少个“好元素”。
题解
不妨设 \(m\leq n< i\) 。
如果直接求的话，是 \(n^3\) 的。
考虑进行优化。
- 移项一下： \(A_m+A_n=A_i-A_p\) 。
- 既然 \(m\leq n\) ，那么随着 \(m,n\) 的增加，\(A_i-A_p\) 的可取值集合是单调变大的。所以我们可以直接将所有 \(A_m+A_n\) 放入哈希表中。
- 发现：对于确定的 $ n$ ， \(i\in(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;
}