首页 > 代码库 > POJ1840___Eqs(哈希表)
POJ1840___Eqs(哈希表)
本文出自svitter的blog
——怒草哈希表!
题意
Consider equations having the following form: a1x13+ a2x23+ a3x33+ a4x43+ a5x53=0 The coefficients are given integers from the interval [-50,50]. It is consider a solution a system (x1, x2, x3, x4, x5) that verifies the equation, xi∈[-50,50], xi != 0, any i∈{1,2,3,4,5}.
Determine how many solutions satisfy the given equation.
a1~a5,x1~x5分别在[-50~50]取值,x1~x5均不为0,求一共有多少组解。
输入输出分析
写在这里记录一下, 如果动态开辟空间就不用while(~scanf)这种形式了,可能MLE或者回收错误。
Sample Input
37 29 41 43 47
Sample Output
654
算法数据结构分析
把i**3的值求出来打表存,因为肯定要遍历用到无数次。为了简化计算将0点定在坐标为50的地方。
计算出前两组乘积的和存到哈希表中,然后在计算后面三组值取相反数看是否相等。
注意找到数不要立刻break,因为这一个数可以由多组不同的组合求出,所以属于一种答案。
AC代码
//author: svtter // #include <iostream> #include <stdio.h> #include <string.h> #include <vector> #include <map> #include <algorithm> #include <queue> #include <cmath> #define INF 0xffffff #define lln long long #ifdef ONLINE_JUDGE #define FOI(file) 0 #define FOW(file) 0 #else #define FOI(file) freopen(file,"r",stdin); #define FOW(file) freopen(file,"w",stdout); #endif using namespace std; struct hashnode { int v; hashnode *next; }; int a[5]; int hash[101]; //先前取值3533 #define M 3533 int i, j, k; int res; hashnode * Hash[M+5]; void BuildList() { for(i = -50; i < 0; i++) { hash[i+50] = i*i*i; hash[50-i] = -hash[i+50]; } } void BuildHash() { int hashkey; hashnode * tmp; for(i = 0; i <= 100; i++) { if(i == 50) continue; for(j = 0; j <= 100; j++) { if(j == 50) continue; res = a[0]*hash[i] + a[1]*hash[j]; hashkey = (res > 0 ? res : -res) % M; tmp = new hashnode; tmp->v = res; tmp->next = Hash[hashkey]; Hash[hashkey] = tmp; } } } int main() { //FOI("input"); //FOW("output"); //write your programme here BuildList(); int ans = 0; int hashkey; hashnode *ph; scanf("%d%d%d%d%d", &a[0], &a[1], &a[2], &a[3], &a[4]); ans = 0; BuildHash(); for(i = 0; i <= 100; i++) { if(i == 50) continue; for(j = 0; j <= 100; j++) { if(j == 50) continue; for(k = 0; k <= 100; k++) { if(k == 50) continue; res = a[2]*hash[i] + a[3]*hash[j] + a[4]*hash[k]; res = -res; hashkey = (res > 0 ? res : -res) % M; ph = Hash[hashkey]; // while(ph != NULL) { //可能有多组数据 if(ph->v == res) ans++; ph = ph->next; } } } } printf("%d\n", ans); return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。