【洛谷 1102】A-B數對【HASH】

題目描述

出題是一件痛苦的事情！

相同的題目看多了也會有審美疲勞，于是我舍棄了大家所熟悉的 A + B P r o b l e m A+B Problem A+BProblem，改用 A − B A-B A−B 了哈哈！

好吧，題目是這樣的：給出一串數以及一個數字 C C C，要求計算出所有 A − B = C A−B=C A−B=C的數對的個數（不同位置的數字一樣的數對算不同的數對）。

輸入格式

輸入共兩行。

第一行，兩個整數 N , C N,C N,C。

第二行， N N N 個整數，作為要求處理的那串數。

輸出格式

一行，表示該串數中包含的滿足 A − B = C A−B=C A−B=C 的數對的個數。

輸入輸出樣例

輸入 #1

4 1

1 1 2 3

輸出

3

說明/提示

對于 75 75 75% 的資料， 1 ≤ N ≤ 20001 1≤N≤20001 1≤N≤20001

對于 100 100 100% 的資料， 1 ≤ N ≤ 2 × 1 0 5 1≤N≤2×10^5 1≤N≤2×105

保證所有輸入資料都在 32 32 32 位帶符号整數範圍内。

解題思路

就是将 A − B = C A−B=C A−B=C變成 A = B + C A=B+C A=B+C，把輸入的數都用哈希存起來，然後枚舉B+C，看有沒有出現過，然後累加。

代碼

#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
long long n,a[1000003],m=1000003,x,t,ans,c;
struct c
{
	long long x,y;
}bsy[1000003];
int h(long long x){  
	return x%m;
}
int locate(long long x){
	int k=h(x);
	int i=0;
	while(i<m&&bsy[(i+k)%m].x!=0&&bsy[(i+k)%m].x!=x)
		i++;
	return (i+k)%m;	 
}
int main(){
	scanf("%lld%lld",&n,&c);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		bsy[locate(a[i])].x=a[i];
		bsy[locate(a[i])].y++;
	}	
	for(int i=1;i<=n;i++)
	{
		if(bsy[locate(a[i]+c)].x)
			ans+=bsy[locate(a[i]+c)].y;
	}
	printf("%lld",ans); 
}