首页 > 代码库 > 1152 - 4 Values whose Sum is 0(好用的hash标记，多重循环简单化)

1152 - 4 Values whose Sum is 0(好用的hash标记，多重循环简单化)

2024-07-16 01:57:10   224人阅读

不得不说这个题就是炫酷啊！

首先说一说思路吧，是这么想的：

1.弄四重循环，爆破，明显会超时。

2.为了处理多重循环，就枚举a+b+c，只需要在d中找到a+b+c的相反数即可，超时

3.枚举a+b，只需要在c+d中找到a+b的相反数即可，TMD超时！

4.循环只能优化到这个程度了，再优化就得用哈希表直接调用了。


这个题的哈希表也是新的知识，由于本题a+b的值可能很大很大，所以以前的哈希表检索不好用了（因为数组开不了那么大），多亏高神的Blog，学了一招，哈哈，下面是搬运的内容：

对于一个无法用数组来标记的数 可以用hash来标记

比如  100这个数 如果 我们在后面判断他是否出现过 可以在前面 用数组 vis[100]  = 1； 这样表示出现过。

但是 对于超大的数 10000000000这样的， 数组就无能为力了。 这时候就上hash了

 struct Hash_map
{
    static const int mask=0x7fffff;
    int p[8388608],q[8388608];
    void clear()
    {
        for(int i=0; i<=mask; ++i)
            q[i]=0;
    }
    int& operator [](int k)
    {
        int i;
        for(i=k&mask; q[i]&&p[i]!=k; i=(i+1)&mask);
        p[i]=k;
        return q[i];
    }
}hash;

这是一个hash 结构体  在结构体内 对 [] 进行了重载， 则可以直接用  hash[10000000000] ++； 就标记成功了。
在查询的时候 直接可以  int  x = hash[10000000000] ;  即可 很方便吧 哈哈 也就是说 这个 hash 直接实现了对 特别大的数的标记。

#include<stdio.h>
#include<iostream>
#include<map>
#include<vector>
using namespace std;
struct Hash_map
{
    static const int mask=0x7fffff;
    int p[8388608],q[8388608];
    void clear()  //初始化为0
    {
        for(int i=0; i<=mask; ++i)
            q[i]=0;
    }
    int& operator [](int k)  //重载“[]”
    {
        int i;
        for(i=k&mask; q[i]&&p[i]!=k; i=(i+1)&mask);
            p[i]=k;
        return q[i];
    }
}hash;
int main()
{
    int n,kase = 0;
    cin>>n;
    while(n--)
    {
        if(kase) printf("\n");
        vector<int> v1,v2,v3,v4,v5,v6;
        int m,ji = 0;
        cin>>m;
        while(m--)  //输入数据到不定长数组中
        {
            int temp;
            cin>>temp;
            v1.push_back(temp);
            cin>>temp;
            v2.push_back(temp);
            cin>>temp;
            v3.push_back(temp);
            cin>>temp;
            v4.push_back(temp);
        }
        int len1 = v1.size(),len2 = v2.size(),len3 = v3.size(),len4 = v4.size();
        hash.clear();
        for(int i = 0;i < len1;i++)
            for(int j = 0;j < len2;j++)
                hash[v1[i] + v2[j]]++;
        for(int i = 0;i < len3;i++)
            for(int j = 0;j < len4;j++)
                ji += hash[-v3[i] -v4[j]];  //这里是坑啊，由于每个a+b不一定只能是一种，可能a和b的值不同，但a+b的值相同有好几组，在这WA了好几次，TMD
        printf("%d\n",ji);
        kase = 1;
    }
    return 0;
}



联系
我们