poj1840 Eqs
IAmL
posted @ 2009年3月30日 06:46
in 解题报告
with tags
poj1840 Eqs解题报告
, 2894 阅读
本题第一眼看上去可以回溯，而我也写了回溯，然后毫无悬念的tle……主要是状态数太多……
之后看discuss，发现居然要用hash做（只能怪自己水，没看出来（T_T））。个人感觉和判重差不多，就是先在hash里面存a1x1^3 + a2x2^3的值。之后再计算-(a3x3^3 + a4x4^3 + a5x5^3)，看是否已经出现再hash表之中，如果出现，就表示a1x1^3 + a2x2^3 ＝ -(a3x3^3 + a4x4^3 + a5x5^3)，那当然就是指a1x1^3 + a2x2^3 + a3x3^3 + a4x4^3 + a5x5^3 ＝ 0。这题用hash还要注意一个地方，就是可能出现不同的x1， x2的值得到同一个结果a1x1^3 + a2x2^3。所以要记录同一个关键字出现次数。
另外，这题还要考虑关键字重复之后的转移方法。
后记：
1.计算出-50到50的立方数后，把它存在一个数组中，之后枚举的时候就可以省去重复的计算～
2.当然，这题暴力的用map也能过……不过自己写hash比map快了10倍……
＝＝＝＝＝＝＝华丽的分割线＝＝＝＝＝＝＝＝＝
#include <iostream>
#include <cmath>
using namespace std;
#define N 55457 //prim
struct hash
{
int key, count;
}h[N];
int main()
{
int i, j, k, a[5], pow[101], ori1, ori2, tmp, p;
__int64 sum = 0;
//预处理，把-50到50的立方求出来
for (i = -50; i <= 50; i++) pow[i + 50] = i * i * i;
for (i = 0; i < 5; i++) cin >> a[i];
for (i = -50; i <= 50; i++)
{
if (i == 0) continue;
ori1 = pow[i + 50] * a[0];
for (j = -50; j <= 50; j++)
{
if (j == 0) continue;
ori2 = a[1] * pow[50 + j] + ori1;
p = abs(ori2) % N;
while (h[p].count && h[p].key != ori2) p = (p + 1) % N;
if (!h[p].count)
{
h[p].key = ori2;
h[p].count++;
}
else h[p].count++;
}
}
for (i = -50; i <= 50; i++)
{
if (i == 0) continue;
ori1 = a[2] * pow[i + 50];
for (j = -50; j <= 50; j++)
{
if (j == 0) continue;
ori2 = a[3] * pow[j + 50] + ori1;
for (k = -50; k <= 50; k++)
{
if (k == 0) continue;
tmp = ori2 + pow[50 + k] * a[4];
tmp = -tmp;
p = abs(tmp) % N;
while (h[p].count && h[p].key != tmp) p = (p + 1) % N;
sum += h[p].count;
}
}
}
printf("%ld\n", sum);
return 0;
}
#include <cmath>
using namespace std;
#define N 55457 //prim
struct hash
{
int key, count;
}h[N];
int main()
{
int i, j, k, a[5], pow[101], ori1, ori2, tmp, p;
__int64 sum = 0;
//预处理，把-50到50的立方求出来
for (i = -50; i <= 50; i++) pow[i + 50] = i * i * i;
for (i = 0; i < 5; i++) cin >> a[i];
for (i = -50; i <= 50; i++)
{
if (i == 0) continue;
ori1 = pow[i + 50] * a[0];
for (j = -50; j <= 50; j++)
{
if (j == 0) continue;
ori2 = a[1] * pow[50 + j] + ori1;
p = abs(ori2) % N;
while (h[p].count && h[p].key != ori2) p = (p + 1) % N;
if (!h[p].count)
{
h[p].key = ori2;
h[p].count++;
}
else h[p].count++;
}
}
for (i = -50; i <= 50; i++)
{
if (i == 0) continue;
ori1 = a[2] * pow[i + 50];
for (j = -50; j <= 50; j++)
{
if (j == 0) continue;
ori2 = a[3] * pow[j + 50] + ori1;
for (k = -50; k <= 50; k++)
{
if (k == 0) continue;
tmp = ori2 + pow[50 + k] * a[4];
tmp = -tmp;
p = abs(tmp) % N;
while (h[p].count && h[p].key != tmp) p = (p + 1) % N;
sum += h[p].count;
}
}
}
printf("%ld\n", sum);
return 0;
}
评论 (0)