本文主要是介绍整数Hash散列总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
方法：
step1 :线性探测
step2 散列
当 h(k)位置已经存储有元素的时候，依次探查(h(k)+i) mod S, i=1,2,3…，直到找到空的存储单元为止。其中，S为 数组长度。
HDU 1496 a*x1^2+b*x2^2+c*x3^2+d*x4^2=0 。 x在 [-100,100] 解的个数
const int MaxN = 30000 ;
bool used[MaxN] ;struct Hash{int val ;int count ;
} ;
Hash HashTable[MaxN] ;int searchHash(int n){int x = n ;while(x < 0) x += MaxN ;while(x >= MaxN) x -= MaxN ;while(used[x] && HashTable[x].val != n){x++ ;if(x >=MaxN) x -= MaxN ;}return x ;
}void insertTable(int n){int id = searchHash(n) ;HashTable[id].val = n ;used[id] = 1 ;HashTable[id].count++ ;
}int main(){int a , b , c , d , i , j , ans , id ;while(scanf("%d%d%d%d" ,&a , &b ,&c ,&d) != EOF){if(a > 0 && b > 0 && c > 0 && d > 0){puts("0") ; continue ;}if(a < 0 && b < 0 && c < 0 && d < 0){puts("0") ; continue ;}memset(used , 0 , sizeof(used)) ;memset(HashTable , 0 , sizeof(HashTable)) ;ans = 0 ;for(i = 1 ; i <= 100 ; i++)for(j = 1 ; j <= 100 ; j++)insertTable(a*i*i + b*j*j) ;for(i = 1 ; i <= 100 ; i++){for(j = 1 ; j <= 100 ; j++){id = searchHash(- c*i*i - d*j*j) ;ans += HashTable[id].count ;}}printf("%d\n" , ans*16) ;}return 0 ;
}
POJ 1186 k1*x1^p1 + k2*x2^p2 + ...+kn*xn^pn = 0 , n <=6 , 1 <=x <= 150 方程的个数
const int MaxN = 4000000 ;
bool used[MaxN] ;struct Hash{int val ;int count ;
};
Hash HashTable[MaxN] ;int searchHash(int n){int x = n ;while(x < 0) x += MaxN ;while(x >= MaxN) x -= MaxN ;while(used[x] && HashTable[x].val != n){if(++x >= MaxN) x -= MaxN ;}HashTable[x].val = n ;return x ;
}void insertTable(int n){int id = searchHash(n) ;HashTable[id].count++ ;used[id] = 1 ;
}int Pow(int x , int y){int ans = 1 ;for(; y ; y >>= 1 , x *= x){if(y&1) ans *= x ;}return ans ;
}int N , M , k[7] , p[7] , mid , ans ;void GaoLeft(int id , int sum){if(id == mid){insertTable(sum) ;return ;}for(int i = 1 ; i <= M ; i++)GaoLeft(id+1 , sum + k[id] * Pow(i , p[id])) ;
}void GaoRight(int id , int sum){if(id == N){int s = -sum ;ans += HashTable[searchHash(s)].count ;return ;}for(int i = 1 ; i <= M ; i++)GaoRight(id+1 , sum + k[id] * Pow(i , p[id])) ;
}int main(){int i ;scanf("%d%d" ,&N , &M) ;memset(HashTable , 0 , sizeof(HashTable)) ;for(i = 0 ; i < N ; i++) scanf("%d%d" ,&k[i] , &p[i]) ;mid = N>>1 ;ans = 0 ;GaoLeft(0 , 0) ;GaoRight(mid , 0) ;printf("%d\n" , ans) ;return 0 ;
}zoj2672 N数，求其子数列为等差数列，且最长并输出。
struct Hash{static const int mask = 0x7fff ;int p[32768] , q[32768] ; //做p->q的映射map<p , q>void clear(){memset(q , -1 , sizeof(q)) ;}int & operator[] (int k){ //注意这个引用int i = k & mask ;while(q[i] != -1 && p[i] != k) i = (i+1) & mask ;p[i] = k ;return q[i] ;}
};int n , x[3003] ;
short dp[3003][3003] ;void dfs(int k , int a , int b){if(k == 2){printf("%d %d" , a , b) ;return ;}dfs(k-1 , b-a , a) ;printf(" %d" , b) ;
}int main(){int i , j , ans , L , R , k ;while(scanf("%d" ,&n) != EOF){for(i = 1 ; i <= n ; i++) scanf("%d" ,&x[i]) ;Hash h ;h.clear() ;for(i = 1 ; i <= n ; i++)for(j = i+1 ; j <= n ; j++)dp[i][j] = 2 ;ans = 1 ;for(i = 1 ; i <= n ; i++){for(j = i+1 ; j <= n ; j++){k = h[ x[j] - x[i] ] ;if(k != -1)dp[i][j] = dp[k][i] + 1 ;if(ans < dp[i][j]){ans = dp[i][j] ;L = i ;R = j ;}}h[ x[i] ] = i ;}printf("%d\n" , ans) ;if(ans == 1) printf("%d\n" , x[1]) ;else{dfs(ans , x[L] , x[R]) ;puts("") ;}}return 0 ;
}
这篇关于整数Hash散列总结的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
