【洛谷1184题解析】用C++高效解决地点匹配问题（附代码与解题思路）

一、题目解读

洛谷1184题要求处理一组地点列表与行程记录，统计其中匹配的天数。题目难点在于高效处理带有空格的字符串输入，以及快速判断每日行程是否在高手可去地点集合中。需要兼顾输入格式解析与算法效率。

二、解题思路

1. 哈希集合优化匹配：使用C++的unordered_set存储高手能去的地点，利用其O(1)平均查找时间提升效率。

2. 逐行输入处理：通过getline()读取包含空格的地点和行程，避免因空格导致输入错误。

3. 计数统计：遍历每日行程，在哈希集中查找匹配项，累计匹配天数。

三、解题步骤解析

1. 初始化与输入：

    禁用同步流提升输入速度（ios::sync_with_stdio(false)）。

    读取n和m（地点数量与行程天数）。

    cin.ignore()清除第一行换行符，确保后续getline正确读取。

2. 存储高手可去地点：

    循环n次，逐行读取地点并插入unordered_set。

3. 匹配统计：

    循环m次，对每日行程进行查找，若存在于集合则计数+1。

4. 输出结果：直接输出匹配天数。

四、代码与注释

#include <iostream>
#include <unordered_set>
#include <string>
using namespace std;

int main() {
    ios::sync_with_stdio(false); // 禁用同步流加速输入
    cin.tie(nullptr);           // 解除cin与cout绑定

    int n, m;                  // 地点数量n与行程天数m
    cin >> n >> m;
    cin.ignore();              // 清除第一行换行符

    unordered_set<string> available; // 存储高手可去地点

    // 读取高手能去的地点（支持空格）
    for(int i = 0; i < n; ++i) {
        string place;
        getline(cin, place); // 按行读取
        available.insert(place); // 插入哈希集合
    }

    int count = 0;             // 匹配天数计数器

    // 遍历每日行程并统计匹配
    for(int i = 0; i < m; ++i) {
        string place;
        getline(cin, place);   // 读取行程地点
        if(available.find(place)!= available.end()) { // 哈希查找匹配
            ++count;
        }
    }

    cout << count << endl;     // 输出结果
    return 0;
}

五、总结

本解法通过哈希集合将地点匹配时间复杂度降至O(1)，有效应对大规模数据。注意输入时的格式处理（如清除换行符）和unordered_set的应用，是解决此类字符串匹配问题的典型思路。可进一步优化空间复杂度或结合其他数据结构应对变体题目。