首页 > 代码库 > poj1840（Eps）

poj1840（Eps）

2024-07-13 20:13:22   220人阅读

题目地址: Eps

 

题目大意;

     a1x13+ a2x23+ a3x33+ a4x43+ a5x53=0   求有多少个解，范围是[-50,50].注意（x！=0）。

解题思路：

    O（n^5）超时。 可以转换方程式  a1x13+ a2x23=-（a3x33+ a4x43+ a5x53） 时间复杂度降低到O（n^3）。

    同时也要注意MTL。由于计算左右两边的数相等，所以只需开2*（50*50*50*50）即可，又因为是从-50开始的，所以存在负数。须再数组乘以2 .利用简单的哈希先将左边的总和hash数组存储起来，然后再计算右边的式子，看自否与左边的相等。当右边的式子小于零和大于2*MM的话不存在解，应该continue。如果相等就用cnt+=hash[sum].  不能cnt++。因为我们不能保证函数的映射为 1对1 映射，更多的是存在 多对1映射。

例如当 a1=a2时，x1=m  ,  x2= n我们得到了sum，但x1=n  ,  x2= m时我们也会得到sum，但是我们说这两个是不同的解，这就是 多对1 的情况了，如果单纯记录sum是否出现过，则会使得 解的个数 减少。

 

代码；

 1 #include <algorithm> 2 #include <iostream> 3 #include <sstream> 4 #include <cstdlib> 5 #include <cstring> 6 #include <cstdio> 7 #include <string> 8 #include <bitset> 9 #include <vector>10 #include <queue>11 #include <stack>12 #include <cmath>13 #include <list>14 #include <map>15 #include <set>16 using namespace std;17 /***************************************/18 #define ll long long19 #define int64 __int6420 /***************************************/21 const int INF = 0x7f7f7f7f;22 const double eps = 1e-8;23 const double PIE=acos(-1.0);24 const int dx[]= {0,-1,0,1};25 const int dy[]= {1,0,-1,0};26 const int fx[]= {-1,-1,-1,0,0,1,1,1};27 const int fy[]= {-1,0,1,-1,1,-1,0,1};28 /***************************************/29 void openfile()30 {31     freopen("data.in","rb",stdin);32     freopen("data.out","wb",stdout);33 }34 /**********************华丽丽的分割线,以上为模板部分*****************/35 const int M=6250000;36 const int MM=12500000;37 short hash[4*M+1];38 int sum;39 int main()40 {41     int a,b,c,d,e;42     memset(hash,0,sizeof(hash));43     scanf("%d%d%d%d%d",&a,&b,&c,&d,&e);44     int i,j,k;45     for(i=-50; i<=50; i++)46     {47         if (i==0)48            continue;49         for(j=-50; j<=50; j++)50             {51                if (j==0)52                     continue;53                 sum=MM+a*i*i*i+b*j*j*j;54                 hash[sum]++;55             }56     }57     int cnt=0;58     for(k=-50; k<=50; k++)59     {60         if (k==0)61             continue;62         for(i=-50; i<=50; i++)63         {64             if (i==0)65                 continue;66             for(j=-50; j<=50; j++)67             {68                 if (j==0)69                     continue;70                 sum=MM-c*k*k*k+d*i*i*i+e*j*j*j;71                 //    sum=-sum;72                 if (sum<0||sum>2*MM)73                     continue;74                 if (hash[sum])75                 {76                     cnt+=hash[sum];77                 }78         }79             }80     }81     printf("%d\n",cnt);82     return 0;83 }
View Code


联系
我们