《洛谷深入浅出基础篇》——P3405 citis and state ——哈希表
上链接:P3405 [USACO16DEC] Cities and States S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
https://www.luogu.com.cn/problem/P3405
上题干:
题目描述
Farmer John 有若干头奶牛。为了训练奶牛们的智力,Farmer John 在谷仓的墙上放了一张美国地图。地图上表明了每个城市及其所在州的代码(前两位大写字母)。
由于奶牛在谷仓里花了很多时间看这张地图,他们开始注意到一些奇怪的关系。例如,FLINT 的前两个字母就是 MIAMI 所在的
FL州,MIAMI 的前两个字母则是 FLINT 所在的MI州。
确切地说,对于两个城市,它们的前两个字母互为对方所在州的名称。我们称两个城市是一个一对「特殊」的城市,如果他们具有上面的特性,并且来自不同的省。对于总共 N 座城市,奶牛想知道有多少对「特殊」的城市存在。请帮助他们解决这个有趣的地理难题!
输入格式
输入共 N+1 行。
第一行一个正整数 N,表示地图上的城市的个数。
接下来 N 行,每行两个字符串,分别表示一个城市的名称(2∼102∼10 个大写字母)和所在州的代码(22 个大写字母)。同一个州内不会有两个同名的城市。输出格式
输出共一行一个整数,代表特殊的城市对数。
输入输出样例
输入 #1复制
6 MIAMI FL DALLAS TX FLINT MI CLEMSON SC BOSTON MA ORLANDO FL输出 #1复制
1说明/提示
数据规模与约定
对于 100%100% 的数据1≤N≤2×10^5,城市名称长度不超过 10。
这道题其中思路很简单,我们只要把每一个城市的名称的前两个字符,以及它的代号,分别存储在结构体里面,然后再遍历一遍找出所有的特殊字符就可以了。
但是,
有个问题,在我们进行上面的操作,会发现复杂度是O(n^2)的,显然无法通过本题。
所以我们必须减少无效的遍历次数。
那这样的话,我们就必须给所有的数据定义某个性质,并且使得每对特殊城市之间都满足这个性质,从而进行精确查找。
也就是说,我们只要给每个数据定义某个性质,然后只需要遍历一次,每次查询这个性质是否在之前出现过,如果出现过,第二次出现的时候,答案就++,说明多了一对,这样的特殊城市。
那么怎么定义这个性质才能只让特殊城市之间相同,
我们可以观察到,一对特殊城市,MI FA ————FA MI
只要把其中一个反过来,那么这两个标记就相同了。我们可以利用哈希表
给每个数据都定义一个独一无二的哈希值,这个哈希值就是我们所说的性质。
然后只要把代号和城市名字的前俩个字符反过来查询就可以了;
上代码:
using namespace std;
const int N = 2e5 + 10;
const int base = 27;
#define mod 1007
typedef long long LL;
int ans;
bool times = 1;
struct city {string city, id;
};
city a[N];int fn[mod][mod];int main()
{int n;cin >> n;int ans = 0;for (int i = 1; i <= n; i++){int hash1 = 0, hash2 = 0;cin >> a[i].city >> a[i].id;string t = a[i].city.substr(0, 2);for(int j=0;j<t.size();j++)hash1 = (hash1*base+a[i].city[j]) % mod;for (int j = 0; j < a[i].id.size(); j++)hash2 = (hash2 * base + a[i].id[j]) % mod;if (hash1 != hash2){fn[hash1][hash2]++;ans += fn[hash2][hash1];}}cout << ans;
}
相关文章:
《洛谷深入浅出基础篇》——P3405 citis and state ——哈希表
上链接:P3405 [USACO16DEC] Cities and States S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)https://www.luogu.com.cn/problem/P3405 上题干: 题目描述 Farmer John 有若干头奶牛。为了训练奶牛们的智力,Farmer John 在谷仓的墙上放了一…...
在QGIS中加载显示3DTiles数据
“我们最近有机会在QGIS 3.34中实现一个非常令人兴奋的功能–能够以“Cesium 3D Tiles”格式加载和查看3D内容!” ——QGIS官方的 宣传介绍。 体验一下,感觉就是如芒刺背、如坐针毡、如鲠在喉。 除非我电脑硬件有问题,要么QGIS的3Dtiles是真…...
HBase学习笔记(3)—— HBase整合Phoenix
目录 Phoenix Shell 操作 Phoenix JDBC 操作 Phoenix 二级索引 HBase整合Phoenix Phoenix 简介 Phoenix 是 HBase 的开源 SQL 皮肤。可以使用标准 JDBC API 代替 HBase 客户端 API来创建表,插入数据和查询 HBase 数据 使用Phoenix的优点 在 Client 和 HBase …...
CentOS 7上生成HTTPS证书
在CentOS 7上生成HTTPS证书,可以使用OpenSSL工具。以下是在CentOS 7上生成自签名HTTPS证书的步骤: 安装OpenSSL: sudo yum install openssl生成证书和私钥: openssl req -x509 -nodes -days 365 -newkey rsa:2048 -keyout ssl.…...
解决React遍历每次渲染多个根元素导致无法为元素赋值key的问题
遍历时,存在多个根标签,如果使用<></>无法正确赋值key,代码如下: function App() {const list [{ id:1, name:"小明" },{ id:2, name:"小田" },{ id:3, name:"小王" }]const listCon…...
2023年软件安装管家目录最新
软件目录 ①【电脑办公】电脑系统(直接安装)Win7Win8Win10OfficeOffice激活office2003office2007office2010office2013office2016office2019office365office2021wps2021Projectproject2007project2010project2016project2019project2013project2021Visio…...
mac苹果笔记本应用程序在哪?有什么快捷方式吗?
苹果笔记本电脑一直以来都被广泛使用,而苹果的操作系统 macOS 也非常受欢迎。一台好的笔记本电脑不仅仅依赖于硬件配置,还需要丰富多样的应用程序来满足用户的需求。苹果笔记本应用程序在哪,不少mac新手用户会有这个疑问。在这篇文章中&#…...
py 循环打开多个页面
在Python中,你可以使用selenium库来循环打开多个页面并进行场控。Selenium是一个用于网页自动化测试的工具,它能够模拟用户与网页交互的操作,如点击、输入等。 以下是一个基本的示例代码,演示如何使用Selenium循环打开多个页面并…...
AD教程 (十八)导入常见报错解决办法(unkonw pin及绿色报错等)
AD教程 (十八)导入常见报错解决办法(unkonw pin及绿色报错等) 常见报错解决办法 绿色报错 可以先按TM,复位错位标识绿色报错原因一般是由于规则冲突的原因,和规则冲突就会报错 点击工具,设计…...
ubuntu22.04下hadoop3.3.6+hbase2.5.6+phoenix5.1.3开发环境搭建
一、涉及软件包资源清单 1、java 这里使用的是openjdk 2、hadoop-3.3.6.tar.gz 3、hbase-2.5.6-hadoop3-bin.tar.gz 4、phoenix-hbase-2.5-5.13-bin.tar.gz 5、apache-zookeeper-3.8.3-bin.tar.gz 6、openssl-3.0.12.tar.gz 二、安装 1、操作系统环境准备 换源 sudo vim /et…...
【随手记】python语言的else语句在for、while等循环语句中的运用
在Python中,else语句可以与if语句一起使用,用于处理条件不成立时的情况。但是,else语句也可以与循环结构(如for循环、while循环)一起使用,用于处理循环正常结束时的情况,即循环没有被break语句中…...
RK3568 + YT 9215交换机芯片,MAC TO MAC 调试记录
前言 原来的方案是rk3568 gmac 直接接phy,phy 接 switch 芯片,只是把交换芯片当交换用,驱动方面基本不用开发,但是要做vlan 那么必须涉及交换芯片的开发。 选择裕太微有两个方面的原因:1.国产化替代2.可获得原厂技术支持3.目前已经完成 两个gmac 口交换芯片的配置,实现v…...
Flutter笔记:桌面端应用多窗口管理方案
Flutter笔记 桌面端应用多窗口管理方案 作者:李俊才 (jcLee95):https://blog.csdn.net/qq_28550263 邮箱 :291148484163.com 本文地址:https://blog.csdn.net/qq_28550263/article/details/134468587 【简介…...
demo(三)eurekaribbonhystrix----服务降级熔断
一、介绍: 1、雪崩: 多个微服务之间调用的时候,假如微服务A调用微服务B和微服务C,微服务B和微服务C又调用其他的微服务,这就是所谓的"扇出"。如果扇出的链路上某个微服务的调用响应的时间过长或者不可用&am…...
相机突然断电,保存的DAT视频文件如何修复
3-7 本文主要解决因相机突然断电导致拍摄的视频文件损坏的问题。 在平常使用相机拍摄视频,比如用单反相机、无人机拍摄视频的时候,如果电池突然断电,或者突然炸机了,就非常有可能会得到一个损坏的视频文件,比如会产生…...
【数据结构与算法篇】顺序栈的C++实现
如何用C实现一个顺序栈 数据结构 -- 栈的简介顺序栈 - 结构体的定义顺序栈的初始化顺序栈的销毁入栈出栈获取栈顶元素判断顺序栈是否为空返回顺序栈中元素的个数 数据结构 – 栈的简介 栈是插入和删除遵循先进后出原则的一种容器。 也是一种线性表对象存放在栈, 可以…...
阿里云ESSD云盘、高效云盘和SSD云盘介绍和IOPS性能参数表
阿里云服务器系统盘或数据盘支持多种云盘类型,如高效云盘、ESSD Entry云盘、SSD云盘、ESSD云盘、ESSD PL-X云盘及ESSD AutoPL云盘等,阿里云服务器网aliyunfuwuqi.com详细介绍不同云盘说明及单盘容量、最大/最小IOPS、最大/最小吞吐量、单路随机写平均时延…...
VSG-001
VulkanSceneGraph (VSG), is a modern, cross platform, high performance scene graph library built upon Vulkan VSG 是一个基于vulkan的现代的、跨平台的高性能场景管理库 VSg特性: 使用C17作为c规范编码,支持 CppCoreGuidelines支持 FOSS Best P…...
Smart Tomcat的使用
文章目录 Smart Tomcat的作用Smart Tomcat的安装Smart Tomcat的配置Smart Tomcat的启动 Smart Tomcat的作用 我们知道使用Servlet来完成一个项目一共需要七个步骤,即创建maven项目、添加依赖、创建目录结构、编写代码、打包程序、部署程序、验证程序。这样的确是完…...
vue3 TS数据处理常见错误分析:列表变为对象的错误如何处理
注意点1: return 语句无法跳出foreach()循环;return语句可以跳出For()循环。 注意点2:预防 [ ]变为object 后端前端之间传值如果为空的时候,数组会被变成空对象,如何解决呢? 描述:父传子 att…...
挑战杯推荐项目
“人工智能”创意赛 - 智能艺术创作助手:借助大模型技术,开发能根据用户输入的主题、风格等要求,生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用,帮助艺术家和创意爱好者激发创意、提高创作效率。 - 个性化梦境…...
Oracle查询表空间大小
1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...
Objective-C常用命名规范总结
【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名(Class Name)2.协议名(Protocol Name)3.方法名(Method Name)4.属性名(Property Name)5.局部变量/实例变量(Local / Instance Variables&…...
Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)
引言:为什么 Eureka 依然是存量系统的核心? 尽管 Nacos 等新注册中心崛起,但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制,是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...
css的定位(position)详解:相对定位 绝对定位 固定定位
在 CSS 中,元素的定位通过 position 属性控制,共有 5 种定位模式:static(静态定位)、relative(相对定位)、absolute(绝对定位)、fixed(固定定位)和…...
Linux-07 ubuntu 的 chrome 启动不了
文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了,报错如下四、启动不了,解决如下 总结 问题原因 在应用中可以看到chrome,但是打不开(说明:原来的ubuntu系统出问题了,这个是备用的硬盘&a…...
Mysql8 忘记密码重置,以及问题解决
1.使用免密登录 找到配置MySQL文件,我的文件路径是/etc/mysql/my.cnf,有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...
BLEU评分:机器翻译质量评估的黄金标准
BLEU评分:机器翻译质量评估的黄金标准 1. 引言 在自然语言处理(NLP)领域,衡量一个机器翻译模型的性能至关重要。BLEU (Bilingual Evaluation Understudy) 作为一种自动化评估指标,自2002年由IBM的Kishore Papineni等人提出以来,…...
掌握 HTTP 请求:理解 cURL GET 语法
cURL 是一个强大的命令行工具,用于发送 HTTP 请求和与 Web 服务器交互。在 Web 开发和测试中,cURL 经常用于发送 GET 请求来获取服务器资源。本文将详细介绍 cURL GET 请求的语法和使用方法。 一、cURL 基本概念 cURL 是 "Client URL" 的缩写…...
基于开源AI智能名片链动2 + 1模式S2B2C商城小程序的沉浸式体验营销研究
摘要:在消费市场竞争日益激烈的当下,传统体验营销方式存在诸多局限。本文聚焦开源AI智能名片链动2 1模式S2B2C商城小程序,探讨其在沉浸式体验营销中的应用。通过对比传统品鉴、工厂参观等初级体验方式,分析沉浸式体验的优势与价值…...
