题目
http://poj.org/problem?id=1840
题意
给
与数组a[5]，其中-50<=a[i]<=50，0<=i<5，求有多少组不同的x[5]，使得a[0] *
pow(x[0], 3) + a[1] * pow(x[1], 3) + a[2] * pow(x[2], 3) + a[3] *
pow(x[3], 3) + a[4] * pow(x[4], 3)==0
其中x[i]满足-50<=x[i]<=50，0<=i<5
思路
该等式明显可以转化为a[0] * pow(x[0], 3) + a[1] * pow(x[1], 3) + a[2] * pow(x[2], 3) == -(a[3] * pow(x[3], 3) + a[4] * pow(x[4], 3))
所以很自然可以想到，可以先列举并存储等式右边的值及对应组数(状态数约为50 * 50 * 50 * 50 * 4，约为2e7)，再列举左边的所有可能，状态数为100 * 100 * 100，即可知道总组数。
但原题目的空间限制使得开50 * 50 * 50 * 50 * 4个int型状态数组不可取，故此处改用short数组。
不过因为等式右边的值在[-50 * 50 * 50 * 50 * 2, +50 * 50 * 50 * 50 * 2]上非常稀疏，故可以使用二分查找或者哈希查找来减少空间复杂度。
感想
下次提交前应当先算清空间复杂度，而不是直接改。
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <sstream>
using namespace std;
typedef long long ll;
const int maxn = 5;
const int base = 50 * 50 * 50 * 50 * 2;
const int maxm = base * 2;
int a[maxn];
short s34[maxm]; int solve(){
int cnt = 0;
for(int x3 = -50;x3 <= 50;x3++){
if(x3 == 0)continue;
int s3 = a[3] * x3 * x3 * x3;
for(int x4 = -50;x4 <= 50;x4++){
if(x4 == 0)continue;
int s4 = a[4] * x4 * x4 * x4;
s34[s3 + s4 + base]++;
}
}
for(int x0 = -50;x0 <= 50;x0++){
if(x0 == 0)continue;
int s0 = a[0] * x0 * x0 * x0;
for(int x1 = -50;x1 <= 50;x1++){
if(x1 == 0)continue;
int s1 = a[1] * x1 * x1 * x1;
for(int x2 = -50;x2 <= 50;x2++){
if(x2 == 0)continue;
int s2 = a[2] * x2 * x2 * x2;
int sum = s0 + s1 + s2;
if (base - sum >= 0 && base - sum < maxm){
cnt += s34[base - sum];
}
}
}
}
return cnt;
} int main(){
#ifdef LOCAL
freopen("input.txt","r",stdin);
#endif // LOCAL
for(int i = 0;i < maxn;i++)scanf("%d", a + i);
printf("%d\n", solve());
return 0;
}