poj1840Eqs（哈希判重)

题目链接：

思路：

这道题是一个简单的hash的应用，假设直接暴力的话肯定承受不了5重for循环，所以比赛的时候我先到分成两组。可是后来用到了很多数组，然后想到数字太大，还先到stl判重，

后来搞出来还是在本地跑的非常慢。就放弃了。

。后来看到题解，不得不说太牛了。我的思路是对的，首先把方程分成左右两边，然后分别暴力，由于计算结果的上限可能达到

505050502=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:

a1x1³+ a2x2³+ a3x3³+ a4x4³+ a5x5³=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

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;

}

巴特西

poj1840Eqs（哈希判重)

题目链接：

思路：

题目：

代码：

最新文章

热门文章