0.8poj1840(排序||哈希)

http://poj.org/problem?id=1840

Eqs

Time Limit: 5000MS	Memory Limit: 65536K
Total Submissions: 8859	Accepted: 4377

Description

Consider equations having the following form:

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

題意：解方程。

一開始暴力果斷tle。。。時間有估計錯了。還以為5S,,100*100*100*100*100可以過。1ms大約可以執行1000條語句，那麼5000ms最多執行500W次每個變量都有100種可能值，那麼暴力枚舉，5層循環，就是要執行100^5=100E次，等着TLE吧。。。。

這題可以用哈希，傳說中的哈希啊，老是聽大牛們說怎麼怎麼好，我當時看到哈希直接跳過發現太難了 。

出處神姐：

要AC這題，就要對方程做一個變形

即先枚舉x1和x2的組合，把所有出現過的 左值 記錄打表，然後再枚舉x3 x4 x5的組合得到的右值，如果某個右值等于已經出現的左值，那麼我們就得到了一個解

時間複雜度從 O(n^5)降低到 O(n^2+n^3)，大約執行100W次

我們先定義一個映射數組hash[]，初始化為0

對于方程左邊，當x1=m , x2= n時得到sum，則把用hash[]記錄sum : hash[sum]++，表示sum這個值出現了1次

之是以是記錄“次數”，而不是記錄“是否已出現”，

是因為我們不能保證函數的映射為 1對1 映射，更多的是存在 多對1映射。

例如當 a1=a2時，x1=m , x2= n我們得到了sum，但x1=n , x2= m時我們也會得到sum，但是我們說這兩個是不同的解，這就是 多對1 的情況了，如果單純記錄sum是否出現過，則會使得解的個數減少。

其次，為了使得 搜尋sum是否出現 的操作為o(1)，我們把sum作為下标，那麼hash數組的上界就取決于a1 a2 x1 x2的組合，四個量的極端值均為50

是以上界為 50*50^3+50*50^3=12500000，由于sum也可能為負數，是以我們對hash[]的上界進行擴充，擴充到25000000，當sum<0時，我們令sum+=25000000存儲到hash[]

由于數組很大，必須使用全局定義

同時由于數組很大，用int定義必然會MLE，是以要用char或者short定義數組，推薦short。

Accepted

53780K

579MS

C++

#include<iostream>

using namespace std;

#define MAX 31250000

short hash[MAX*2+100];//hash[sum]表示值等于sum的的解的個數(多對1映射) 

int main()

{

 int i,j,k;

 int count=0;

 int ans=0;

 int a,b,c,d,e;

 while(cin>>a>>b>>c>>d>>e)

 {

  for(i=-50;i<=50;i++)

  {

   for(j=-50;j<=50;j++)

   {

    for(k=-50;k<=50;k++)

    {

     if(i!=0&&j!=0&&k!=0)

     {

      ans=a*i*i*i+b*j*j*j+c*k*k*k;

      hash[MAX+ans]++;//有可能是負的！！

     }

    }

   }

  }

  for(i=-50;i<=50;i++)

  {

   for(j=-50;j<=50;j++)

   {

    if(i!=0&&j!=0)

    {

      ans=-(d*i*i*i+e*j*j*j);

      count+=hash[MAX+ans];

      //ans=(d*i*i*i+e*j*j*j);(也可以改為下面的形式)

      //if(hash[MAX-ans]==hash[MAX+ans])

      //count+=hash[MAX+ans];

    }

   }

  }

  cout<<count<<endl;

 }

 return 0;

}