枚举 + 优化（4）—— 哈希表优化实例 2

例 3 四平方和展开目录

思路 1展开目录

枚举 abcd，判断 $a^2+b^2+c^2+d^2 == N$，分析规模

a：0 ~ sqrt(500000 / 4)
b：0 ~ sqrt(500000 / 3)
c：0 ~ sqrt(500000 / 2)
d：0 ~ sqrt(500000)

范围大约是 1000 ~ 2000，总枚举量 $10^{12}$，经验：1 秒 =$10^8$

思路 2展开目录

枚举 abc，判断 $N-a^2-b^2-c^2$ 是不是完全平方数，分析规模

a：0 ~ sqrt(500000 / 4)
b：0 ~ sqrt(500000 / 3)
c：0 ~ sqrt(500000 / 2)

总枚举量 $10^9$，依然超时

问题展开目录

只枚举 ab，那么余下 $R=N-a^2-b^2$，能否快速求出 $c^2+d^2=R$ 的解？（或者快速判断无解）

例如：N=5，当前枚举量 a=b=0, 能不能快速求出解 c=1，d=2。这里哈希表就派上用场了，我们可以预先求出 $R=c^2+d^2$ 的解，用一个 unordered_map<int ,int> f 来保存一个 R 对应的 c

比如 f [5]=1，表示 R=5 的解是 c=1，d=2 可以由 R 和 c 算出来；如果我们能求出 f [0]，f [1],...,f [5000000] 的值，那么我们就可以查哈希表用 O (1) 的复杂度找到 $R=c^2+d^2$ 的解

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    unordered_map<int,int> f;
    //打表记录c的值
    for(int c = 0;c * c <= n;c++)
        for(int d = c;c * c + d * d <= n;d++)
            if(f.find(c * c + d * d) == f.end())
                f[c * c + d * d] = c;
    //枚举a，b的值
    for(int a = 0;a * a <= n / 4;a++)
    {
        for(int b = 0;a * a + b * b <= n / 2;b++)
        {
            //查表
            if(f.find(n - a * a - b * b) != f.end())
            {
                int c = f[n - a * a - b * b];
                int d = int(sqrt(n - a * a - b * b) + 1e-3);
                cout << a << " " << b << " " << c << " " << d << endl;
                return 0;
            }
        }
    }
    return 0;
}

例 4 题目链接：hihocoder1505展开目录

思路展开目录

首先预处理两袋金币数目和是某个值 X 一共有多少种选法。把预处理的结果存在哈希表里，记作 cnt2 [X]，表示选出 2 袋金币和是 X 有几种选法。然后只枚举 i 和 j，也就是给小 Hi 的两袋金币，通过查哈希表得到小 Ho 的两袋金币一共有多少种选法。但是存在一个小问题，一袋金币不能既给小 Hi 又给小 Ho。假设现在有 5 枚金币，有几种选法能选出总数是 3 枚的 2 袋金币呢？
从上图我们可以看到一共 6 种选法。现在假设我给小 Hi 的金币是第 1 袋和第 3 袋，那么这时给小 Ho 的 2 袋金币的选法，上面 6 种并不是都成立，因为第 1 袋和第 3 袋已经分给小 Hi 了，所以 (1,3)(1,4)(1,5)(2,3) 这四种组合都不能选，只剩下 2 种组合可选

我们仔细观察，包含第 1 袋的选法数目等于有几个袋子的金币与第 3 袋一样；同理，包含第 3 袋的选法数目等于有几个袋子的金币与第 1 袋一样。于是我们需要多预处理一个结果：cnt1 [X] 表示包含 X 枚金币的袋子数量

有了 cnt2 和 cnt1，我们就可以进行计算了，当我们枚举分给小 Hi 的袋子是 i=1 和 j=3 时，分给小 Ho 的选法一共有：cnt2[A[i]+A[j]]-cnt1[A[i]]-cnt1[A[j]]+1，这里 + 1 是因为 (1,3) 这个组合被减了两次，另外，这个式子还有个特例，就是当 A[i]=A[j] 时，cnt2[A[i]+A[j]]-cnt1[A[i]]-cnt1[A[j]]+3

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,a[1000];
    unordered_map<int,int> cnt1,cnt2;
    long long ans = 0;
    cin >> n;
    for(int i = 0;i < n;i++)
    {
        cin >> a[i];
        cnt1[a[i]]++;
    }
    for(int i = 0;i < n;i++)
        for(int j = i + 1;j < n;j++)
            cnt2[a[i] + a[j]]++;
    for(int i = 0;i < n;i++)
    {
        for(int j = i + 1;j < n;j++)
        {
            if(a[i] != a[j])
                ans += cnt2[a[i] + a[j]] - cnt1[a[i]] - cnt1[a[j]] + 1;
            else
                ans += cnt2[a[i] + a[j]] - cnt1[a[i]] - cnt1[a[j]] + 3;
        }
    }
    cout<<ans;
    return 0;
}

第一次作业展开目录

先说说的思路，当时看到这题有点懵，可能还是对哈希算法掌握的不够，怎么都想不到用哈希的方法去做，索性先写了个 $O (N^2)$ 的两重循环，想着这几天学的优化，都是减少循环层数，总共就两层，再减也只能减一层，然后我就去找规律（此处省略 1 万字......），最后找到了规律，用一个 map 保存一对二元组的差，f [X] 的值表示有多少个差为 X 的二元组

#include <iostream>
#include <unordered_map>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    long long n,a,b,min = 100001,max = -100000;
    long long ans = 0;
    unordered_map<long long,long long> f;
    cin >> n;
    for(int i = 0;i < n;i++)
    {
        cin >> a >> b;
        long long temp = a - b;
        if(f.find(-temp) != f.end())
            ans += f[-temp];
        f[temp]++;
    } 
    cout<<ans;
    return 0;
}