首页 > 其他 > 详细

【YBTOJ】【哈希表】求好元素

时间:2021-09-24 01:13:38      阅读:25      评论:0      收藏:0      [点我收藏+]

求好元素

如果在一个由 \(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;
}

【YBTOJ】【哈希表】求好元素

原文:https://www.cnblogs.com/Shinomiya/p/15306101.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!