hash算法的意义在于提供了一种快速存取数据的方法,
它用一种算法建立键值与真实值之间的对应关系,
(每一个真实值只能有一个键值,但是一个键值可以对应多个真实值),
这样可以快速在数组等条件中里面存取数据.
把任意长度的输入(又叫做预映射, pre-image),通过散列算法,变换成固定长度的输出,该输出就是散列值。
这种转换是一种压缩映射,也就是,
*散列值的空间通常远小于输入的空间,
*不同的输入可能会散列成相同的输出,
*而不可能从散列值来唯一的确定输入值。
简单的说就是一种将任意内容的输入转换成相同长度输出的方式.
几个用hash的简单题:
HDU1280给n个小于1e6的正数,输出最小的m个数;
解决方法:开1e6的数组,将n个数作为下标存到数组里,A[N]++;输出。
HDU1496 给一个多项式:ax1^2+bx2^2+cx3^2+dx4^2=0 -50<=a~d<=50 -100<=xi<=100
输入:abcd
输出:共有多少种解决方案。
分成两块,一块正数,一块负数。正数不会超过100*100*50*2负数同理,开这么大的数组,下标代表值,O(1)的访问数据。
#include <bits/stdc++.h> using namespace std; int res[105]; const int maxn = 100*100*50*2+10; int pos[maxn],neg[maxn]; int len=sizeof(pos); int main() { for(int i=1;i<=100;i++) res[i]=i*i; int a,b,c,d; while(scanf("%d%d%d%d",&a,&b,&c,&d)!=EOF) { if(a>0 && b>0 && c>0 && d>0||a<0 && b<0 && c<0 && d<0) { printf("0 "); continue; } memset(pos,0,len); memset(neg,0,len); for(int i=1;i<=100;i++) { for(int j=1;j<=100;j++) { int x=a*res[i]+b*res[j]; if(x>=0) pos[x]++; else neg[-x]++; } } int sum=0; for(int i=1;i<=100;i++) { for(int j=1;j<=100;j++) { int x=c*res[i]+d*res[j]; if(x>0) sum+=neg[x]; else sum+=pos[-x]; } } printf("%d ",sum<<4); } return 0; }