解题报告:SPOJ4580 ABCDEF
程序员文章站
2022-05-12 10:58:44
...
参考代码
#include <bits/stdc++.h>
using namespace std;
const long long MAXN = 105,MOD = 19260817,BASE = 900000007LL;
struct Hash
{
int key,nxt;
long long cnt;
}table[MOD + 5]; //数组开大些,作者暂时不清楚这个数组要开多大。
long long ans;
int n,e;
int seq[MAXN],head[MOD + 5];
namespace HashTable
{
void getHash(long long value)
{
value += BASE;
int m = value % MOD;
for (int i = head[m];i;i = table[i].nxt)
{
if (table[i].key == value)
{
table[i].cnt++;
return;
}
}
table[++e].key = value;
table[e].nxt = head[m];
table[e].cnt = 1;
head[m] = e;
}
int queryHash(long long value)
{
value += BASE;
int m = value % MOD;
for (int i = head[m];i;i = table[i].nxt)
{
if (table[i].key == value) return table[i].cnt;
}
return 0;
}
}
using namespace HashTable;
void init()
{
scanf("%d",&n);
for (int i = 1;i <= n;++i) scanf("%d",&seq[i]);
}
void work()
{
for (int a = 1;a <= n;++a)
for (int b = 1;b <= n;++b)
for (int c = 1;c <= n;++c)
getHash(seq[a] * seq[b] + seq[c]);
for (int d = 1;d <= n;++d)
for (int e = 1;e <= n;++e)
for (int f = 1;f <= n;++f)
if (seq[d] != 0)
ans += queryHash((seq[e] + seq[f]) * seq[d]);
printf("%lld",ans);
}
int main()
{
init();
work();
return 0;
}
分析
- 哈希表
最暴力的,直接枚举,可以有40分。
由于除法会有误差,即使是开double也是如此。考虑移项,结果判断条件为,从而避免误差。
思路是先枚举等式左边所有可能值,由于30000*30000=9亿,不可能开一个这样的数组保存每种答案出现了多少次,考虑建立哈希表(作者使用的是开链表)。
哈希完成后,枚举等式右边所有可能值,若该值已经被计算过,则可以在哈希表中找到这个值在等式左边被计算出了多少次,累加答案即可。
BASE
要足够大,否则可能出现value += BASE
为负,导致取模后值为负,最终数组下标为负,导致段错误。
注意判断d == 0
的情况。
若有谬误,敬请斧正。
上一篇: 找出数组中最大(小)的十个数
下一篇: 3sum解法一
推荐阅读
-
【解题报告】洛谷 P2571 [SCOI2010]传送带
-
11.1NOIP模拟赛解题报告
-
Ural 1090. In the Army Now 解题报告
-
[leetcode] 306. Additive Number 解题报告
-
2019.3.14解题报告&补题报告
-
HDU GCC(HDU 3123)解题报告
-
LeetCode 1020. Number of Enclaves 解题报告(python)
-
LeetCode 1254. Number of Closed Islands解题报告(python)
-
PTAL1-009 N个数求和解题报告---GCD & LCM
-
LeetCode 解题报告-92. 反转链表 II