欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

解题报告: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;
}

分析

  • 哈希表

最暴力的,直接O(n6)O(n^6)枚举,可以有40分。

由于除法会有误差,即使是开double也是如此。考虑移项,结果判断条件为ab+c=(e+f)da*b+c=(e+f)*d,从而避免误差。

思路是先枚举等式左边所有可能值,由于30000*30000=9亿,不可能开一个这样的数组保存每种答案出现了多少次,考虑建立哈希表(作者使用的是开链表)。

哈希完成后,枚举等式右边所有可能值,若该值已经被计算过,则可以在哈希表中找到这个值在等式左边被计算出了多少次,累加答案即可。

BASE要足够大,否则可能出现value += BASE为负,导致取模后值为负,最终数组下标为负,导致段错误。

注意判断d == 0的情况。

若有谬误,敬请斧正。

相关标签: 哈希表