hdu 1496 Equations（技巧hash）

 

题意，给你a,b,c,d这4个数的值，然后问a*x1^2 + b*x2^2 +  c*x3^2 + d*x4^2 = 0

的（x1,x2,x3,x4）解一共有多少种？   初看这题，想直接4次循环找，但是这样绝对超时，所以就用了hash这种方法来解决，很巧妙！分开两部分求和，若两部分的和是0，则就加上那么多种，最后乘以16。这样就能从n^4变成2*n^2，速度快了很多很多！！！ 两层循环最多只可能产生10000个不同的结果,开200W的数组将会浪费很多初始化的时间,所以开小数组+处理冲突会比较好 链接：http://acm.hdu.edu.cn/showproblem.php?pid=1496 代码： #include <bits/stdc++.h>using namespace std;const int maxn=1e6+10; int f1[maxn],f2[maxn]; int a,b,c,d;int main() {while(cin>>a>>b>>c>>d){if((a>0&&b>0&&c>0&&d>0)||(a<0&&b<0&&c<0&&d<0)){cout<<"0"<<endl;continue;}memset(f1,0,sizeof(f1));memset(f2,0,sizeof(f2));int i,j;for(i=1;i<=100;i++){for(j=1;j<=100;j++){int k=a*i*i+b*j*j;if(k>=0) f1[k]++;else f2[-k]++;}}int sum=0;for(i=1;i<=100;i++){for(j=1;j<=100;j++){int k=c*i*i+d*j*j;if(k>0) sum+=f2[k];else sum+=f1[-k];}}cout<<16*sum<<endl;}return 0; }

 

转载于:https://www.cnblogs.com/Fy1999/p/9355319.html

总结

以上是生活随笔为你收集整理的hdu 1496 Equations（技巧hash）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。