首页 > 其他分享 >[USACO16DEC] Cities and States S

[USACO16DEC] Cities and States S

时间:2024-08-26 19:37:37浏览次数:9  
标签:10 两个 map int 城市 States mp Cities USACO16DEC

[USACO16DEC] Cities and States S

题目描述

Farmer John 有若干头奶牛。为了训练奶牛们的智力,Farmer John 在谷仓的墙上放了一张美国地图。地图上表明了每个城市及其所在州的代码(前两位大写字母)。

由于奶牛在谷仓里花了很多时间看这张地图,他们开始注意到一些奇怪的关系。例如,FLINT 的前两个字母就是 MIAMI 所在的 FL 州,MIAMI 的前两个字母则是 FLINT 所在的 MI 州。
确切地说,对于两个城市,它们的前两个字母互为对方所在州的名称。

我们称两个城市是一个一对「特殊」的城市,如果他们具有上面的特性,并且来自不同的州。对于总共 $N$ 座城市,奶牛想知道有多少对「特殊」的城市存在。请帮助他们解决这个有趣的地理难题!

输入格式

输入共 $N + 1$ 行。

第一行一个正整数 $N$,表示地图上的城市的个数。
接下来 $N$ 行,每行两个字符串,分别表示一个城市的名称($2 \sim 10$ 个大写字母)和所在州的代码($2$ 个大写字母)。同一个州内不会有两个同名的城市。

输出格式

输出共一行一个整数,代表特殊的城市对数。

样例 #1

样例输入 #1

6
MIAMI FL
DALLAS TX
FLINT MI
CLEMSON SC
BOSTON MA
ORLANDO FL

样例输出 #1

1

提示

数据规模与约定

对于 $100%$ 的数据,$1 \leq N \leq 2 \times 10 ^ 5$,城市名称长度不超过 $10$。


算法1

(字符串哈希 + map)

由题意可知

(1)一对「特殊」的城市:对于两个城市,它们的前两个字母互为对方所在州的名称

(2)同一个州内不会有两个同名的城市

整体思路

1.把州和城市的前两位分别提出来进行hash,映射到26进制的一个整数

2.对于给定的字符串(a,b),找出对应的(b,a),利用map实现

3.特判: a != b; 两个城市不能所在同一个州

欠缺的知识:map 的二维数组

C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
int n;
map<int,int> mp [N];
string a,b;
int ans;

int main(){
	cin >> n;
	while(n--){
		cin >> a >> b;
	    int A = (a[0]-'0') * 26 + (a[1] - '0');
	    int B = (b[0]-'0') * 26 + (b[1] - '0');
		ans += mp[B][A];
	    if(A == B)  //一个州不能有两个同名城市
		{
			ans -= mp[A][B];
     	} 
	    mp[A][B]++;
	}
	cout << ans ;
	return 0;
}

标签:10,两个,map,int,城市,States,mp,Cities,USACO16DEC
From: https://www.cnblogs.com/ltphy-/p/18381511

相关文章

  • 发现这个有趣的问题Dynamic Planning Approach for Radio Tower Placement in Cities
    在ByteLand中,沿轴有n(≤105)个城市,第i个城市位于(A₁,0)(对于1≤i≤n,A≤10°)。在ByteLand,有一家制造无线电塔的电信公司。每个塔的覆盖半径为d,即,当且仅当x-y≤d时,(y,0)处的塔可覆盖(2,0)处的城市。提示:1.目标解决方案基于动态规划,2.问题陈述本身包含有关......
  • GGR273Smart Cities Bike Sharing Locations
    GGR273Lab1:SmartCities–BikeSharingLocationsLab 1:Analyzing BicyclingParking Locations inToronto(15%)Due:July 19th 2024@ 11:59 pm ESTthroughtheQuizzestabSubmitthrough Lab 1and answerquestionsandsubmitfile(.jpeg ofyour......
  • VINS-Fusion源码逐行解析:updateLatestStates()函数与slideWindow()
    初始化并优化位姿后,接下来做的事是将这些位姿更新给上一帧,我们来看下updateLatestStates()源码:voidEstimator::updateLatestStates(){//锁定mPropagate,确保对最新状态的更新是线程安全的mPropagate.lock();//更新最新的时间戳,等于当前帧的时间戳加上时间延......
  • CF613D Kingdom and its Cities
    CF613DKingdomanditsCities虚树优化dp考虑无解的情况,若有两个重要城市相邻,那么无解。对于有解的情况,朴素的如何求解最少占领的城市数?考虑从叶子节点开始向上贪心,假如当前\(u\)节点为关键点,那么对于它的子树\(v\),若它的关键点能到\(v\),就要和他断开。如果\(u\)节点不......
  • 【漏洞复现】用友NC-Cloud PMCloudDriveProjectStateServlet接口存在JNDI注入漏洞
    阅读须知花果山的技术文章仅供参考,此文所提供的信息只为网络安全人员对自己所负责的网站、服务器等(包括但不限于)进行检测或维护参考,未经授权请勿利用文章中的技术资料对任何计算机系统进行入侵操作。利用此文所提供的信息而造成的直接或间接后果和损失,均由使用者本人负责。本......
  • CF1922C Closest Cities 题解
    解题思路贪心,能走距离最短的城市就一定走。分别考虑\(x>y\)和\(x<y\)的情况,两种情况分别是从后向前转移和从前往后转移,分别预处理一个前缀和和后缀和即可。AC代码#include<stdio.h>#include<stdlib.h>#include<valarray>#defineN100005#definelllonglongintn......
  • 六、多态样式@stateStyles
    @Styles和Extend仅仅应用于静态页面的样式复用,stateStyles可以依据组件的内部状态的不同,快速设置不同样式。@stateStyles是属性方法,可以根据UI内部状态来设置样式,类似于css伪类,但语法不同,ArkUI提供以下四种状态:focused:获焦态normal:正常态pressed:按压态disabled:不可用态impo......
  • Linux: CPU C-states
    0.OverviewTherearevariouspowermodesoftheCPUwhicharedeterminedbasedontheircurrentusageandarecollectivelycalled“C-states”or“C-modes.”WithCPUC-states,theCPUcanentertheidlestatustooptimizeenergyconsumption.TheCPUhas......
  • Ways China’s Cities Can Drive Equitable and Sustainable Urbanization
    Thefive-yearplanrepresentsanopportunitynotjusttoadvanceclimategoals,buttocreatebettercitiesasurbanizationcontinues.HerearefivewaysChina’sFive-YearPlancanhelpsteerthenationtowardachievingajusttransitionandgreenurbaniz......
  • 'ddlCities' has a SelectedValue which is invalid because it does not exist in th
    this.ddlCities.DataSource=GetAll_List();this.ddlCities.DataTextField="Name";this.ddlCities.DataValueField="Id";this.ddlCities.DataBind();错误:'ddlCities'hasaSelectedValuewhichisinvalidbecauseitdoe......