枚举+优化（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^，<font color = red>经验：1秒=10^8^</font>
思路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一共有多少种选法。把预处理的结果存在哈希表里，记作<font color = red>cnt2[X]，表示选出2袋金币和是X有几种选法</font>。然后只枚举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袋一样。于是我们需要多预处理一个结果：<font color = red>cnt1[X]表示包含X枚金币的袋子数量。</font> 有了cnt2和cnt1，我们就可以进行计算了，当我们枚举分给小Hi的袋子是i=1和j=3时，分给小Ho的选法一共有：<font color = red>cnt2[A[i]+A[j]]-cnt1[A[i]]-cnt1[A[j]]+1</font>，这里+1是因为(1,3)这个组合被减了两次，另外，这个式子还有个特例，就是<font color = red>当A[i]=A[j]时，cnt2[A[i]+A[j]]-cnt1[A[i]]-cnt1[A[j]]+3</font>
#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保存一对二元组的差，<font color = red >f[X]的值表示有多少个差为X的二元组</font>
#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;
}腾讯云开发者
