目录

 一：A-B 数对

题目背景

题目描述

输入格式

输出格式

输入输出样例

说明/提示

二：Hash 算法

 一：A-B 数对

题目背景

出题是一件痛苦的事情！

相同的题目看多了也会有审美疲劳，于是我舍弃了大家所熟悉的 A+B Problem，改用 A-B 了哈哈！

题目描述

给出一串正整数数列以及一个正整数 CC，要求计算出所有满足 A - B = CA−B=C 的数对的个数（不同位置的数字一样的数对算不同的数对）。

输入格式

输入共两行。

第一行，两个正整数 N,CN,C。

第二行，NN 个正整数，作为要求处理的那串数。

输出格式

一行，表示该串正整数中包含的满足 A - B = CA−B=C 的数对的个数。

输入输出样例

输入 #1复制

4 1
1 1 2 3

输出 #1复制

3

说明/提示

对于 75%75% 的数据，1 leq N leq 20001≤N≤2000。

对于 100%100% 的数据，1 leq N leq 2 times 10^51≤N≤2×105，0 leq a_i <2^{30}0≤ai​<230,1 leq C < 2^{30}1≤C<230。

2017/4/29 新添数据两组

题解：

开始我是直接暴力求解利用双层循环一个一个找

#include<bits/stdc++.h>
using namespace std;
int e[10009];
int main()
{
int a,b,c,d;
cin>>a>>b;
for(int i=0;i<a;i++)
{
cin>>e[i];
}
for(int i=0;i<a;i++)
{
for(int j=i+1;j<a;j++)
{
if(abs(e[i]-e[j])==b)
c++;
}
}
cout<<c;
}

结果时间超限。

看了一下标签，要用到二分法。

所以我让每一个值先变成B，然后二分找对应的A首次出现位置，看是否能找到。

如果找到A，那就二分找最后出现的位置，继而，求出A的个数，即数对的个数。

#include<bits/stdc++.h>
using namespace std;
long long a[1000009],n,c,cnt,st;
int main(){
cin>>n>>c;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+1+n);	//先排序
for(int i=1;i<n;i++)	//遍历每一个B
{
int l=i+1,r=n;	//寻找A第一次出现的位置，使得A-B=C
while(l<r) //因为是第一次出现，尽量往左，
{
int mid=l+r>>1;
if(a[mid]-a[i]>=c) r=mid;
else l=mid+1;
}
if(a[l]-a[i]==c) st=l; //能找到C就继续
else continue;
l=st-1,r=n;	//查找A最后出现的位置
while(l<r) //因为是最后一次出现，尽量往右，
{
int mid=l+r+1>>1;
if(a[mid]<=a[st]) l=mid;
else r=mid-1;
}
cnt+=l-st+1;	//最后出现的位置减首次出现的位置就是区间长度，即A的个数
}
cout<<cnt;
return 0;
}

二：Hash 算法

简单理解，就是一个加密过程，并且这个过程不可逆。

当我们原始输入信息发生任何变化，新的 Hash 值都应该出现很大变化。而且很难找到两段内容不同的明文，使得它们的 Hash 值一致。

而Hash 函数就是把一个大范围映射到一个小范围，目的往往是为了节省空间，使得数据容易保存，另外 Hash 函数也会应用于查找上。

常见的哈希有

1：进制哈希。核心便是给出一个固定进制base，将一个串的每一个元素看做一个进制位上的数字，所以这个串就可以看做一个base进制的数，那么这个数就是这个串的哈希值；则我们通过比对每个串的的哈希值，即可判断两个串是否相同

2：无错哈希。就是记录每一个已经诞生的哈希值，然后对于每一个新的哈希值，我们都可以来判断是否和已有的哈希值冲突，如果冲突，那么可以将这个新的哈希值不断加上一个大质数，直到不再冲突。

3：多重哈希。就是用不同的两种或多种方式哈希，然后分别比对每一种哈希值是否相同——显然是增加了空间和时间，但也确实增加了其正确性。

最后

以上就是大力芒果为你收集整理的2023/1/10 总结 一：A-B 数对二：Hash 算法的全部内容，希望文章能够帮你解决2023/1/10 总结 一：A-B 数对二：Hash 算法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。