題目大意：

有以下等式：a1*x13+a2*x23+a3*x33+a4*x43+a5*x53=0.x1,x2,x3,x4,x5都就在區(qū)間[-50,50]之間的整數(shù)，且x1,x2,x3,x4,x5都不等于0.問：給定a1,a2,a3,a4,a5的情況下，x1,x2,x3,x4,x5共有多少種可能的取值？

解題思路：

這道題想了很久，以為是簡單的暴力枚舉呢。。。。然后怎么想都覺得要超時。之后經(jīng)人提醒，可以把前兩項(xiàng)的結(jié)果映射到一個數(shù)組里，然后用后三項(xiàng)遍歷查找，然后用暴力寫了，內(nèi)存幾乎爆掉。。。。

然后知道最好的方法是hash，用了之后發(fā)現(xiàn)有點(diǎn)bug。就是當(dāng)數(shù)據(jù)全是0的時候，hash表中只有0這一條鏈，這樣在查找的時候需要100*100*100*100*100=100億次，鐵定要超時，因?yàn)槲业某绦蚺芰?4s。。。Orz

之后想到一個方法，可以用一個數(shù)組記錄每個數(shù)字出現(xiàn)的次數(shù)，只要這個數(shù)字出現(xiàn)后，只需要count+=這個數(shù)字出現(xiàn)的次數(shù)就可以了。就可以解決這個問題了。

#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]) //記錄重復(fù){if(x == Key[i]){Same[i]++;return true;}}return false; }template<class T> inline void Hash<T>::push(int x) {if(pre(x) == true) //出現(xiàn)過,Same記錄return ;else //沒出現(xiàn)過{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; }

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的POJ-1840 Eqs Hash的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。