POJ-1840 Eqs Hash

题目大意：

有以下等式：a1*x13+a2*x23+a3*x33+a4*x43+a5*x53=0.x1,x2,x3,x4,x5都就在区间[-50,50]之间的整数，且x1,x2,x3,x4,x5都不等于0.问：给定a1,a2,a3,a4,a5的情况下，x1,x2,x3,x4,x5共有多少种可能的取值？

解题思路：

这道题想了很久，以为是简单的暴力枚举呢。。。。然后怎么想都觉得要超时。之后经人提醒，可以把前两项的结果映射到一个数组里，然后用后三项遍历查找，然后用暴力写了，内存几乎爆掉。。。。

然后知道最好的方法是hash，用了之后发现有点bug。就是当数据全是0的时候，hash表中只有0这一条链，这样在查找的时候需要100*100*100*100*100=100亿次，铁定要超时，因为我的程序跑了64s。。。Orz

之后想到一个方法，可以用一个数组记录每个数字出现的次数，只要这个数字出现后，只需要count+=这个数字出现的次数就可以了。就可以解决这个问题了。

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<ctime> #include<cmath> #include<string> using namespace std;#define N 12350 #define MAX 12345 #define MAXSUM 12500000 #define CLR(arr, what) memset(arr, what, sizeof(arr))template<class T> class Hash { private:int Key[N], Head[N], Next[N], Same[N];int top; public:int count;void search( int x);void push(int x);bool pre(int x);void clear(); };template<class T> inline void Hash<T>::clear() {top = 0;count = 0;CLR(Head, -1);CLR(Next, -1);CLR(Same, 0); }template<class T> inline bool Hash<T>::pre(int x) {int temp;temp = abs(x) % MAX;for(int i = Head[temp]; i != -1; i = Next[i]) //记录重复{if(x == Key[i]){Same[i]++;return true;}}return false; }template<class T> inline void Hash<T>::push(int x) {if(pre(x) == true) //出现过,Same记录return ;else //没出现过{int temp;temp = abs(x) % MAX;Key[top] = x;Next[top] = Head[temp];Head[temp] = top;Same[top] = 1;top++;} }template<class T> inline void Hash<T>::search(int x) {int temp;temp = abs(x) % MAX;for(int i = Head[temp]; i != -1; i = Next[i]){if(x == -Key[i])count += Same[i];} } Hash<int> h;int main() {int T;int a, b, c, d, e;int temp;scanf("%d", &T);while(T--){h.clear();scanf("%d%d%d%d%d", &a, &b, &c, &d, &e);for(int i = -50; i <= 50; ++i){for(int j = -50; j <= 50; ++j){if(i == 0 || j == 0)continue;temp = a * i * i * i + b * j * j * j;h.push(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 = c * i * i * i + d * j * j * j + e * k * k * k;if(temp > MAXSUM || temp < -MAXSUM)continue;h.search(temp);}}}printf("%d\n", h.count);}return 0; }

《新程序员》：云原生和全面数字化实践50位技术专家共同创作，文字、视频、音频交互阅读

总结

以上是生活随笔为你收集整理的POJ-1840 Eqs Hash的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。