首页 > 代码库 > poj1840Eqs（哈希判重)

poj1840Eqs（哈希判重)

2024-07-18 12:28:48   218人阅读

题目链接：

传送门

思路：

这道题是一个简单的hash的应用，如果直接暴力的话肯定承受不了5重for循环，所以比赛的时候我先到分成两组，但是后来用到了许多数组，然后想到数字太大，还先到stl判重，
后来搞出来还是在本地跑的很慢，就放弃了。。后来看到题解，不得不说太牛了，我的思路是对的，首先把方程分成左右两边，然后分别暴力，因为计算结果的上限可能达到
50*50*50*50*2=1250000,所以取值范围为-12500000--12500000,所以为了避免冲突，应该将hash数组开到2*1250000+1，为什么加1呢，是因为如果出现-12500000那么加上25000000，那么值为12500000，那么就与正的12500000冲突了。。还有最开始先算的3重循环，还是过了，说明这个题目的数据非常水。。。那么最后这个题目就解决了。。。。还有一个小常识65536KB 差不多能开int型数组1677w左右，所以应该用short型数组。。那么就可以开到25000000了。。。。

题目：

Eqs
Time Limit: 5000MS Memory Limit: 65536K
Total Submissions: 12220 Accepted: 5968

Description

Consider equations having the following form: 
a1x13+ a2x23+ a3x33+ a4x43+ a5x53=0 
The coefficients are given integers from the interval [-50,50]. 
It is consider a solution a system (x1, x2, x3, x4, x5) that verifies the equation, xi∈[-50,50], xi != 0, any i∈{1,2,3,4,5}. 

Determine how many solutions satisfy the given equation. 

Input

The only line of input contains the 5 coefficients a1, a2, a3, a4, a5, separated by blanks.

Output

The output will contain on the first line the number of the solutions for the given equation.

Sample Input

37 29 41 43 47

Sample Output

654

Source

Romania OI 2002

代码：

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;

const int maxn=25000000+10;
short hash[maxn];

int a1,a2,a3,a4,a5;


int main()
{
    int ans,temp;
    while(~scanf("%d%d%d%d%d",&a1,&a2,&a3,&a4,&a5))
    {
        ans=0;
        memset(hash,0,sizeof(hash));
        for(int i=-50;i<=50;i++)
            for(int j=-50;j<=50;j++)
                  {
                    if(i==0||j==0)  continue;
                    temp=(a1*i*i*i+a2*j*j*j)*(-1);
                    if(temp<0)
                        temp=temp+maxn;
                    hash[temp]++;
                  }
        for(int i=-50;i<=50;i++)
            for(int j=-50;j<=50;j++)
                for(int k=-50;k<=50;k++)
            {
               if(i==0||j==0||k==0)  continue;
               temp=a3*i*i*i+a4*j*j*j+a5*k*k*k;
               if(temp<0)
                  temp=temp+maxn;
               if(hash[temp])
                  ans=ans+hash[temp];
            }
        printf("%d\n",ans);
    }
    return 0;
}




联系
我们