POJ 1840 Eqs 解方程式, 水题 难度:0

题目

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;
}
上一篇:windows nfs server for linux


下一篇:Java并发编程:Future接口、FutureTask类