题目链接

特殊城市

题目描述

Farmer John 有 N 座城市。每座城市都有一个全大写的名称和一个两字母的全大写州代码。

一对城市 (A, B) 被称为 "特殊城市对"，如果满足以下所有条件：

  1. 城市 A 的名称前两位字母 等于 城市 B 所在州的州代码。
  2. 城市 B 的名称前两位字母 等于 城市 A 所在州的州代码。
  3. 城市 A 和 城市 B 来自不同的州。

请计算共有多少对这样的特殊城市。

输入描述:

  • 第一行输入一个整数 N，表示城市数量。
  • 接下来 N 行，每行输入两个字符串：城市名称和所在州代码，用空格隔开。

输出描述:

  • 输出一个整数，表示特殊城市对的数量。

示例: 输入:

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

输出:

1

说明: (MIAMI, FL) 和 (FLINT, MI) 是一对特殊城市。

  • MIAMI 的前缀是 "MI"，是 FLINT 的州代码。
  • FLINT 的前缀是 "FL"，是 MIAMI 的州代码。
  • MIAMI 的州是 "FL"，FLINT 的州是 "MI"，两者不同。

解题思路

这是一个计数问题。直接遍历所有可能的城市对 () 会超时，因此我们需要一种更高效的方法来寻找和匹配。

核心思想： 我们可以将问题转化为：对于一个城市 A，其类型可以由 (名称前缀, 所在州) 定义，记为 (P_A, S_A)。我们想找的城市 B，其类型 (P_B, S_B) 必须满足：P_B = S_A 且 S_B = P_A。

这引导我们使用哈希表来预先统计每种 (前缀, 州) 类型的城市数量。

数据结构： 一个嵌套的哈希表是理想选择：Map<String, Map<String, Integer>>。

  • 外层键：城市的名称前缀（2个字母）。
  • 内层键：城市所在的州代码。
  • 值：具有此外层前缀和内层州代码的城市数量。

算法步骤:

  1. 计数：

    • 创建一个空的嵌套哈希表 counts。
    • 遍历输入的 N 个城市。对于每个城市（名称为 name, 州为 state）：
      • 提取名称的前两位作为前缀 prefix。
      • 在哈希表中增加对应条目的计数：counts[prefix][state]++。

  2. 匹配与计算：

    • 初始化一个长整型 total_pairs = 0 来存储结果。
    • 遍历 counts 哈希表中的每一个 (p1, s1) 类型及其数量 count1。
    • 对于每个 (p1, s1)，我们寻找其"配对"类型 (s1, p1)。
    • 关键条件：根据题目要求，两个城市必须来自不同州。对于 (p1, s1) 和 (s1, p1) 构成的配对，它们的州分别是 s1 和 p1。因此，只有在 p1 != s1 时，它们才能形成特殊城市对。
    • 如果 p1 == s1，则跳过。
    • 如果 p1 != s1，我们就在哈希表中查找配对类型 (s1, p1) 的数量，记为 count2。如果不存在，count2 为 0。
    • count1 个 (p1, s1) 类型的城市和 count2 个 (s1, p1) 类型的城市可以组成 count1 * count2 对。将这个乘积累加到 total_pairs。

  3. 修正重复计算：

    • 上述循环中，当我们处理 (p1, s1) 时计算了它与 (s1, p1) 的配对。之后当循环处理到 (s1, p1) 时，又会与 (p1, s1) 再计算一次。这样每对特殊城市都被计算了两次。
    • 因此，最终的结果需要将 total_pairs 除以 2。

代码

#include <iostream>
#include <string>
#include <vector>
#include <map>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    map<string, map<string, int>> counts;
    for (int i = 0; i < n; ++i) {
        string city, state;
        cin >> city >> state;
        counts[city.substr(0, 2)][state]++;
    }

    long long total_pairs = 0;
    for (auto const& [p1, inner_map] : counts) {
        for (auto const& [s1, count1] : inner_map) {
            // A 类型: (p1, s1)
            // 寻找 B 类型: (s1, p1)
            if (p1 == s1) {
                continue;
            }
            if (counts.count(s1) && counts.at(s1).count(p1)) {
                long long count2 = counts.at(s1).at(p1);
                total_pairs += (long long)count1 * count2;
            }
        }
    }

    cout << total_pairs / 2 << endl;

    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        Map<String, Map<String, Integer>> counts = new HashMap<>();
        for (int i = 0; i < n; i++) {
            String city = sc.next();
            String state = sc.next();
            String prefix = city.substring(0, 2);
            counts.computeIfAbsent(prefix, k -> new HashMap<>()).merge(state, 1, Integer::sum);
        }

        long totalPairs = 0;
        for (Map.Entry<String, Map<String, Integer>> entry1 : counts.entrySet()) {
            String p1 = entry1.getKey();
            for (Map.Entry<String, Integer> entry2 : entry1.getValue().entrySet()) {
                String s1 = entry2.getKey();
                int count1 = entry2.getValue();

                if (p1.equals(s1)) {
                    continue;
                }

                int count2 = counts.getOrDefault(s1, Collections.emptyMap()).getOrDefault(p1, 0);
                totalPairs += (long)count1 * count2;
            }
        }
        
        System.out.println(totalPairs / 2);
    }
}

from collections import defaultdict

n = int(input())

counts = defaultdict(lambda: defaultdict(int))
for _ in range(n):
    city, state = input().split()
    prefix = city[:2]
    counts[prefix][state] += 1

total_pairs = 0
for p1, inner_dict in counts.items():
    for s1, count1 in inner_dict.items():
        if p1 == s1:
            continue
        
        # 使用 .get(s1, {}) 来安全地访问可能不存在的内层字典
        count2 = counts.get(s1, {}).get(p1, 0)
        total_pairs += count1 * count2
        
print(total_pairs // 2)

算法及复杂度

  • 算法: 哈希表
  • 时间复杂度: ，其中 是所有输入字符串的总长度（用于读取和切片）， 是哈希表中唯一 (前缀, 州) 类型的数量。遍历哈希表进行计算的时间远小于读取输入的时间。复杂度主要由输入大小决定。
  • 空间复杂度: ，即存储所有唯一 (前缀, 州) 类型及其计数所需的空间。