《洛谷深入浅出基础篇》——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…...
DockerHub与私有镜像仓库在容器化中的应用与管理
哈喽,大家好,我是左手python! Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库,用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...
Admin.Net中的消息通信SignalR解释
定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...
STM32+rt-thread判断是否联网
一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...
为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?
在建筑行业,项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升,传统的管理模式已经难以满足现代工程的需求。过去,许多企业依赖手工记录、口头沟通和分散的信息管理,导致效率低下、成本失控、风险频发。例如&#…...
【解密LSTM、GRU如何解决传统RNN梯度消失问题】
解密LSTM与GRU:如何让RNN变得更聪明? 在深度学习的世界里,循环神经网络(RNN)以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而,传统RNN存在的一个严重问题——梯度消失&#…...
均衡后的SNRSINR
本文主要摘自参考文献中的前两篇,相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程,其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt 根发送天线, n r n_r nr 根接收天线的 MIMO 系…...
【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习
禁止商业或二改转载,仅供自学使用,侵权必究,如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...
听写流程自动化实践,轻量级教育辅助
随着智能教育工具的发展,越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式,也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建,…...
【Redis】笔记|第8节|大厂高并发缓存架构实战与优化
缓存架构 代码结构 代码详情 功能点: 多级缓存,先查本地缓存,再查Redis,最后才查数据库热点数据重建逻辑使用分布式锁,二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...
day36-多路IO复用
一、基本概念 (服务器多客户端模型) 定义:单线程或单进程同时监测若干个文件描述符是否可以执行IO操作的能力 作用:应用程序通常需要处理来自多条事件流中的事件,比如我现在用的电脑,需要同时处理键盘鼠标…...
