本文主要是介绍hdu1496(用hash思想统计数目),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
作为一个刚学hash的孩子,感觉这道题目很不错,灵活的运用的数组的下标。
解题步骤:如果用常规方法解,那么时间复杂度为O(n^4),肯定会超时,然后参考了网上的解题方法,将等式分成两个部分,a*x1^2+b*x2^2和c*x3^2+d*x4^2,
各自作为数组的下标,如果两部分相加为0,则满足等式;
代码如下:
#include<iostream>
#include<algorithm>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<time.h>
#include<math.h>#define eps 1e-9
#define N 500005*2
#define P system("pause")
using namespace std;
int hash1[N],hash2[N];int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);ccint a,b,c,d;int i,j;while(scanf("%d%d%d%d",&a,&b,&c,&d)!=EOF){if((a>0&&b>0&&c>0&&d>0)||(a<0&&b<0&&c<0&&d<0)){printf("0\n");continue;}memset(hash1,0,sizeof(hash1));memset(hash2,0,sizeof(hash2));for(i=1;i<=100;i++)for(j=1;j<=100;j++){int k=i*i*a+j*j*b;if(k>=0) hash1[k]++;else hash2[-k]++; } int count=0;for(i=1;i<=100;i++)for(j=1;j<=100;j++){int k=i*i*c+j*j*d;if(k>0) count+=hash2[k];else count+=hash1[-k]; }printf("%d\n",16*count); } // P; return 0;
}
这篇关于hdu1496(用hash思想统计数目)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!