枚举+优化(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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏黑泽君的专栏

Java语言中:float数据类型在内存中是怎么存储的?

============================================================================= ja...

20310
来自专栏SeanCheney的专栏

《Pandas Cookbook》第05章 布尔索引1. 计算布尔值统计信息2. 构建多个布尔条件3. 用布尔索引过滤4. 用标签索引代替布尔索引5. 用唯一和有序索引选取6. 观察股价7. 翻译SQ

第01章 Pandas基础 第02章 DataFrame运算 第03章 数据分析入门 第04章 选取数据子集 第05章 布尔索引 第06章 索引对齐 ...

21220
来自专栏Java帮帮-微信公众号-技术文章全总结

Java案例-数组随机数

五四青年节,是为纪念1919年5月4日爆发的五四运动而设立的。它来源于中国一九一九年反帝爱国的。1939年,陕甘宁边区西北青年救国联合会规定5月4日为中国青年节...

40180
来自专栏java初学

top K 问题

489160
来自专栏二进制文集

LeetCode 004 Median of Two Sorted Arrays 详细分析

题目链接:https://leetcode.com/problems/median-of-two-sorted-arrays/

11910
来自专栏GIS讲堂

geotools等值线生成

前文中,提到了等值面的生成,后面有人经常会问等值线的生成,本文在前文的基础上做了一点修改,完成了等值线的geotools生成。

35450
来自专栏数据结构与算法

字符串hash入门

简单介绍一下字符串hash 相信大家对于hash都不陌生 hash算法广泛应用于计算机的各类领域,像什么md5,文件效验,磁力链接 等等都会用到hash算法 在...

72750
来自专栏软件开发

C语言 经典编程100题

一、题目 【程序1】 题目:有1、2、3、4个数字,能组成多少个互不相同且无重复数字的三位数?都是多少? ===========================...

2.7K80
来自专栏前端说吧

JS-用js的for循环实现九九乘法表以及其他算数题等

55060
来自专栏数据小魔方

让执着成为一种习惯——仿网易数独玫瑰气泡图

没有难学的技艺,只有不够辛勤的付出! 今天这篇文章推送仿的的是网易数独的一幅信息图,内容呈现的是全球各国人民对于养老所持的态度,数据来源于Pew Reserch...

42550

扫码关注云+社区

领取腾讯云代金券