HDU 杭电 1496 （Hash求解）

小咪咪 2024-02-17 18:53 49阅读 0赞

看到这题首先想到的是四重for循环，肯定超时，但还是很想试一下，结果和预期一样；然后就换成三重循环，结果还是超时；最后就换成 hash求解（第一次接触）两重循环。由题意可得a\*x1\*x1+b\*x2\*x2=-(c\*x3\*x3+d\*x4\*x4)才满足条件，hash数组至少开200W （因为50 \* 100 \*100+50 \*100 \*100=100W）.

如果有兴趣了解hash可以访问

[http://wenku.baidu.com/link?url=DZyBKou-bE2kVUit-\_HXsq3oBqV7doaaS7Cpy\_c-qp9URedeO9QVpQf442V\_cqr6ISDZOsPmv\_mDGOdzZXM6fborImRmpKw8D2Pt9MkzZ2a&qq-pf-to=pcqq.discussion][http_wenku.baidu.com_link_url_DZyBKou-bE2kVUit-_HXsq3oBqV7doaaS7Cpy_c-qp9URedeO9QVpQf442V_cqr6ISDZOsPmv_mDGOdzZXM6fborImRmpKw8D2Pt9MkzZ2a_qq-pf-to_pcqq.discussion]

1.  \#include<cstdio>
2.  \#include<cstring>
3.  const int maxn=2000000+10;
4.  int hash\[maxn\];
5.  int t\[100+5\]; //用于储存i=1~100 ,i\*i的值
6.  int main()\{ 
7.   int a,b,c,d;
8.   for(int i=1;i<=100;i++)t\[i\]=i\*i;
9.   while(scanf("%d%d%d%d",&a,&b,&c,&d)==4)\{ 
10.  if(a>0 && b>0 &&c>0 && d>0 ||a<0 &&b<0 &&c<0 &&d<0)printf("0\\n"); //全小于0 或全大于0 输出0
11.  else \{ 
12.  int count=0;
13.  memset(hash,0,sizeof(hash));
14.  for(int i=1;i<=100;i++)
15.  for(int j=1;j<=100;j++)
16.  hash\[1000000+a\*t\[i\]+b\*t\[j\]\]++;
17.   
    
18.  for(int i=1;i<=100;i++)
19.  for(int j=1;j<=100;j++)
20.  count+=hash\[1000000-(c\*t\[i\]+d\*t\[j\])\];
21.  printf("%d\\n",16\*count); //因为每个xi都有两个值（正，负），所以共有2的4次方16倍
22.  \}
23.  \}
24.  return 0;
25. \}

[http_wenku.baidu.com_link_url_DZyBKou-bE2kVUit-_HXsq3oBqV7doaaS7Cpy_c-qp9URedeO9QVpQf442V_cqr6ISDZOsPmv_mDGOdzZXM6fborImRmpKw8D2Pt9MkzZ2a_qq-pf-to_pcqq.discussion]: http://wenku.baidu.com/link?url=DZyBKou-bE2kVUit-_HXsq3oBqV7doaaS7Cpy_c-qp9URedeO9QVpQf442V_cqr6ISDZOsPmv_mDGOdzZXM6fborImRmpKw8D2Pt9MkzZ2a&qq-pf-to=pcqq.discussion