?

題意，給你a,b,c,d這4個數(shù)的值，然后問a*x1^2 + b*x2^2 +? c*x3^2 + d*x4^2 = 0

的（x1,x2,x3,x4）解一共有多少種？ ? 初看這題，想直接4次循環(huán)找，但是這樣絕對超時，所以就用了hash這種方法來解決，很巧妙！分開兩部分求和，若兩部分的和是0，則就加上那么多種，最后乘以16。這樣就能從n^4變成2*n^2，速度快了很多很多！！！ 兩層循環(huán)最多只可能產(chǎn)生10000個不同的結(jié)果,開200W的數(shù)組將會浪費很多初始化的時間,所以開小數(shù)組+處理沖突會比較好 鏈接：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; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Fy1999/p/9355319.html

總結(jié)

以上是生活随笔為你收集整理的hdu 1496 Equations（技巧hash）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。