刚拿到这道题时，想到的肯定是暴力枚举啊。肯定超时。想到了立方乘系数，如果再枚举的话，还是会超时的。。无语。。
最后看了看了结题报告。。果然霸气。。。思维还是不够灵活是。。
将式子a1*x1^3 +a2*x2^3 + a3 * x3^3 + a4 * x4^3 + a5 * x5^3 = 0;转化成 a1*x1^3 +a2*x2^3 + a3 * x3^3 = - a4 * x4^3 - a5 * x5^3
两边相等，将左边的数利用hash建立映射，然后枚举右边的数和利用hash查找。。。
开散列：
挂链 891ms
View Code #include#include #include #include #define maxn 107 #define N 9997 using namespace std; struct node { int num; node *next; }*tagp[N],H[99999997]; int pos; int pw[maxn]; int main() { int i,j,k,p; int a1,a2,a3,a4,a5; for (i = 0; i < 101; ++i) { pw[i] = (i - 50)*(i - 50)*(i - 50); } while (~scanf("%d%d%d%d%d",&a1,&a2,&a3,&a4,&a5)) { pos = 0; memset(tagp,0,sizeof(tagp)); for (i = 0; i < 101; ++i) { if (i == 50) continue; for (j = 0; j < 101; ++j) { if (j == 50) continue; for (k = 0; k < 101; ++k) { if (k == 50) continue; int tmp = a1*pw[i] + a2*pw[j] + a3*pw[k]; p = tmp%N; if (p < 0) p = -p; node *t = &H[pos++]; t->num = tmp; t->next = tagp[p]; tagp[p] = t; } } } int count = 0; for (i = 0; i < 101; ++i) { if (i == 50) continue; for (j = 0; j < 101; ++j) { if (j == 50) continue; int tmp = -a4*pw[i] - a5*pw[j]; p = tmp%N; if (p < 0) p = -p; node *q; for (q = tagp[p]; q != NULL; q = q->next) { if (q->num == tmp) count++; } } } printf("%d\n",count); } return 0; }
vector 2610MS
View Code #include#include #include #include #include #define maxn 107 #define N 9997 using namespace std; int pw[maxn]; vector hash[N]; int main() { int i,j,k,p; int a1,a2,a3,a4,a5; for (i = 0; i < 101; ++i) { pw[i] = (i - 50)*(i - 50)*(i - 50); } while (~scanf("%d%d%d%d%d",&a1,&a2,&a3,&a4,&a5)) { for (i = 0; i < N; ++i) hash[i].clear(); for (i = 0; i < 101; ++i) { if (i == 50) continue; for (j = 0; j < 101; ++j) { if (j == 50) continue; for (k = 0; k < 101; ++k) { if (k == 50) continue; int tmp = a1*pw[i] + a2*pw[j] + a3*pw[k]; p = tmp%N; if (p < 0) p = -p; hash[p].push_back(tmp); } } } int count = 0; for (i = 0; i < 101; ++i) { if (i == 50) continue; for (j = 0; j < 101; ++j) { if (j == 50) continue; int tmp = -a4*pw[i] - a5*pw[j]; p = tmp%N; if (p < 0) p = -p; for (k = 0; k < hash[p].size(); ++k) { if (hash[p][k] == tmp) count++; } } } printf("%d\n",count); } return 0; }