统一将单词转为小写后分别去重，再用集合查询交集并由容斥公式得到并集。
OJ: shumeng
题目 ID: CSP202403B
难度:入门
标签:字符串集合哈希表
日期: 2026-07-31 16:21
形式化题目
给定两篇文章的单词序列，忽略英文字母大小写差异后分别得到去重集合
求两个值：
：同时出现在两篇文章中的不同单词数； ：两篇文章一共包含的不同单词数。
思路
问题本质是集合的求交与求并，难点只在于“同一个单词”的判定规则：The、the、THE 应视为同一个单词。
大小写归一化
读入单词时先把所有大写字母转换成小写，再插入集合。归一化必须在插入集合之前完成，否则同一个单词会因写法不同被当成多个元素。
求交与求并
- 交集：遍历集合
，统计其中也出现在集合 里的单词个数。 - 并集：直接由容斥公式得到
用哈希集合存储，插入与查询都是均摊
代码
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-07-31 16:21
* update_at: 2026-08-17 22:39
*/
#include <bits/stdc++.h>
using namespace std;
// 把单词统一成小写：忽略大小写差异后才能把同一个单词去重
string normalize(const string &word) {
string result = word;
for (int i = 0; i < (int)result.size(); i++) {
if ('A' <= result[i] && result[i] <= 'Z') result[i] += 'a' - 'A';
}
return result;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
// 哈希集合保存两篇文章各自去重后的单词，平均 O(1) 插入与查询
unordered_set<string> set_a, set_b;
string word;
for (int i = 0; i < n; i++) {
cin >> word;
set_a.insert(normalize(word));
}
for (int i = 0; i < m; i++) {
cin >> word;
set_b.insert(normalize(word));
}
// 交集大小：统计同时在两篇文章集合中出现的单词数
int intersection = 0;
for (unordered_set<string>::const_iterator it = set_a.begin(); it != set_a.end(); ++it) {
if (set_b.count(*it)) intersection++;
}
// 并集大小由容斥公式得到：|A ∪ B| = |A| + |B| - |A ∩ B|
cout << intersection << '\n';
cout << set_a.size() + set_b.size() - intersection << '\n';
return 0;
}复杂度
设两篇文章总单词数为
- 时间：每个单词做一次大小写转换与集合插入，加上一次遍历求交集，哈希集合均摊
操作，总时间复杂度 。 - 空间：两个集合共保存
个不同单词，空间复杂度 。
总结
集合统计题要先把“同一个元素”的判定规则想清楚。本题的要点是大写归一化必须在去重前完成，随后交集与并集分别通过集合查询和容斥公式一步求出，用哈希集合即可高效处理大输入。