首页 > 代码库 > POJ 1840 Eqs(哈希)
POJ 1840 Eqs(哈希)
题目地址:POJ 1840
sad。。。整个比赛期间一直以为是用什么定理或数学公式推导来做。。一直没仔细看。。结果最后5分钟的时候才看到每个元素的数据范围只是【-50,50】。。。算了。。就算看到了也做不出来。。因为会MLE,解决MLE需要把hash数组的定义类型定义成short。。。这我是不可能想出来的。。。。也没遗憾了。。
这题就是先求前两个for循环,将结果用hash数组存起来。再进行后面三个for循环,如果值为相反数的话,说明和为0.然后记录有多少个。
代码如下:
#include <iostream> #include <stdio.h> #include <string.h> #include <stdlib.h> #include <math.h> #include <ctype.h> #include <queue> #include <map> #include<algorithm> using namespace std; short _hash[25000001]; int main() { int a, b, c, d, e, i, j, k, m, n, s; while(scanf("%d%d%d%d%d",&a,&b,&c,&d,&e)!=EOF) { s=0; memset(_hash,0,sizeof(_hash)); m=25000000; for(i=-50;i<=50;i++) { if(!i) continue ; for(j=-50;j<=50;j++) { if(!j) continue ; n=i*i*i*a+j*j*j*b; n=-n; if(n<0) n+=m; _hash[n]++; } } for(i=-50;i<=50;i++) { if(!i) continue ; for(j=-50;j<=50;j++) { if(!j) continue ; for(k=-50;k<=50;k++) { if(!k) continue ; n=i*i*i*c+j*j*j*d+k*k*k*e; if(n<0) n+=m; if(_hash[n]) s+=_hash[n]; } } } printf("%d\n",s); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。