题目描述DVD \texttt{DVD}DVD电影允许观众选择字幕语言。每种语言的字幕以文本文件形式存储每行一个字幕即屏幕上某一时刻显示的简短短语即使它在屏幕上占用了多行。所有语言的字幕文件行数相同但某些行可能为空表示缺少翻译。此外还有一个独立的时间码文件但本题中忽略。现在希望通过分析两个字幕文件自动构建简单的双语词典。规则如下若单词p pp在第一种语言文件中出现的行号集合为X XX单词e ee在第二种语言文件中出现的行号集合恰好也为X XX且∣ X ∣ ≥ 2 |X| \ge 2∣X∣≥2则p pp与e ee互为翻译。同一行内同一单词的多次出现只计一次。只考虑长度至少为3 33的单词。若同一语言中有多个单词的行号集合完全相同则将这些单词按字母序排列后用空格拼接作为该集合对应的词条。最终输出按第一种语言的词条字典序排列的翻译对格式为词条1/词条2。所有字母均转为小写。输入格式第一行包含一个整数T TT表示测试用例数。每个测试用例第一行为一个整数N NN0 N ≤ 1000 0 N \le 10000N≤1000表示每个字幕文件的行数。随后N NN行是第一种语言的字幕再N NN行是第二种语言的字幕。字幕内容为普通ASCII \texttt{ASCII}ASCII文本包含大小写字母和标点无变音符号。单词仅由字母和连字符-组成处理时不区分大小写。每行最多20 2020个单词每种语言的不同单词最多1000 10001000个单词长度不超过24 2424。输出格式对于每个测试用例输出若干行每行两个小写词条用/分隔。第一个词条为第一种语言的词条第二个为对应的翻译。输出按第一个词条的字典序排序。不同测试用例的输出之间用一个空行隔开。样例输入1 10 Quero um copo de cerveja, bem fresca. Nao temos cerveja, mas temos vinho. Nao obrigado, vinho nao quero. Tambem temos sumo de laranja natural. Esta bem, entao quero um sumo de laranja. Mais alguma coisa? Sim, um pastel de nata. Com certeza. Um sumo e um pastel. Sao quatro euros. Quatro euros!!! Mas isso e um roubo. Se acha que e um roubo, chame a policia. I want a glass of beer, very cool. We dont have beer, but we have wine. No thanks, I dont want wine. We also have natural orange juice. OK, then I want one orange juice. Anything else? Yes, a cream cake. Of course. One juice and one cake. Thats four euros. Four euros!!! That is a theft. If you think it is a theft, call the police.输出cerveja/beer euros quatro/euros four laranja/orange nao vinho/dont wine pastel/cake quero/want roubo/theft sumo/juice temos/have题目分析本题的核心任务是从两个平行文本中通过比较单词的出现行号集合自动发现翻译对。直接做法是分别处理两种语言的所有单词记录每个单词长度≥ 3 ≥ 3≥3出现的行号集合然后枚举所有可能的单词对若行号集合相同则配对。但需要注意同语言内多个单词可能共享同一个行号集合此时必须合并为一个词条因此正确的处理顺序是对每种语言先建立单词 → 行号集合的映射。过滤掉出现行数小于2 22的单词因为要求n ≥ 2 n \ge 2n≥2。反转映射按行号集合分组得到行号集合 → 单词列表。对每个列表内的单词排序并用空格拼接形成该集合对应的词条。最后比较两种语言得到的映射找出相同的行号集合输出对应的词条对。复杂度方面每种语言最多1000 10001000个不同单词每个单词的行号集合大小不超过N NN≤ 1000 ≤ 1000≤1000。若直接比较所有单词对则O ( 1000 2 ) O(1000^2)O(10002)的单词比较可行但内部集合比较可能较慢。使用std::setint作为键值通过红黑树比较总复杂度可控。本题的数据规模较小无需复杂的字符串匹配算法直接使用 STL 容器即可高效解决。解题思路单词提取与行号记录对每个字幕文件的每一行从左到右扫描字符。当遇到字母或连字符时将其累加到当前单词中并转为小写遇到其他字符如空格、标点时若当前单词非空且长度≥ 3 ≥ 3≥3则将其记录到该语言的unordered_mapstring, setint中行号为当前行号从1 11开始。注意同一行内同一单词只记录一次因此借助临时setstring去重。处理完一行后继续下一行。行号集合分组与合并遍历第一步得到的unordered_map对每个条目若其行号集合大小小于2 22忽略。否则以该行号集合为键将单词加入mapsetint, vectorstring中。由于std::set可作为std::map的键因为定义了操作可以直接比较行号集合是否相等。构建词条映射遍历上一步的分组对每个组内的单词列表进行排序字典序然后用空格拼接得到该行号集合对应的最终词条。存储到mapsetint, string中键为行号集合值为词条。两种语言分别处理得到groups1和groups2。配对与排序输出遍历groups1中的每个键值对查找groups2中是否存在相同的键。若存在则将(词条1, 词条2)存入一个vectorpairstring,string。最后对整个vector按第一个词条排序默认按字典序然后依次输出。测试用例之间用空行分隔注意第一个用例前不输出空行。正确性保证只保留出现行数≥ 2 ≥ 2≥2的单词符合题目要求。行号集合相同的单词被合并解决了歧义问题。最终配对条件是行号集合完全相等符合翻译判定规则。输出排序及小写转换均满足要求。复杂度分析每个单词插入unordered_map平均O ( 1 ) O(1)O(1)总单词数≤ 1000 ≤ 1000≤1000行数≤ 1000 ≤ 1000≤1000单词长度≤ 24 ≤ 24≤24因此扫描和插入的总时间复杂度为O ( N ⋅ L line ) O(N \cdot L_{\text{line}})O(N⋅Lline​)可视为常数。分组时mapsetint, vectorstring的插入复杂度为O ( log ⁡ M ) O(\log M)O(logM)其中M MM为不同行号集合的数量≤ 1000 ≤ 1000≤1000。最终配对时遍历groups1在groups2中查找复杂度O ( K log ⁡ M ) O(K \log M)O(KlogM)K KK为配对数量。总时间复杂度可认为是O ( N ⋅ W M log ⁡ M ) O(N \cdot W M \log M)O(N⋅WMlogM)空间复杂度O ( W ⋅ S ) O(W \cdot S)O(W⋅S)其中W WW为单词总数S SS为行号集合大小。代码实现// DVD Subtitles// UVa ID: 853// Verdict: Accepted// Submission Date: 2026-07-12// UVa Run Time: 0.000s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;// 处理一种语言的所有行生成 行号集合 - 词组 的映射voidprocessLines(intN,constvectorstringlines,mapsetint,stringgroups){unordered_mapstring,setintwordLines;// 单词 - 行号集合for(inti0;iN;i){conststringlinelines[i];setstringseen;// 当前行已出现的单词用于去重string word;for(charch:line){if(isalpha(ch)||ch-){// 单词字符字母或连字符word.push_back(tolower(ch));}else{if(!word.empty()){if(word.size()3seen.find(word)seen.end()){seen.insert(word);wordLines[word].insert(i1);// 行号从1开始}word.clear();}}}if(!word.empty()){// 处理行尾单词if(word.size()3seen.find(word)seen.end()){seen.insert(word);wordLines[word].insert(i1);}}}mapsetint,vectorstringgroupMap;// 行号集合 - 该集合的所有单词for(constautokv:wordLines)if(kv.second.size()2)// 只保留至少出现2行的单词groupMap[kv.second].push_back(kv.first);for(autokv:groupMap){sort(kv.second.begin(),kv.second.end());string combined;for(size_t j0;jkv.second.size();j){if(j0)combined ;combinedkv.second[j];}groups[kv.first]combined;// 生成最终词组}}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intT;cinT;boolfirstCasetrue;while(T--){intN;cinN;cin.ignore();// 跳过行末换行vectorstringlines1(N),lines2(N);for(inti0;iN;i)getline(cin,lines1[i]);for(inti0;iN;i)getline(cin,lines2[i]);mapsetint,stringgroups1,groups2;processLines(N,lines1,groups1);processLines(N,lines2,groups2);vectorpairstring,stringresult;// (L1词组, L2词组)for(constautokv:groups1){autoitgroups2.find(kv.first);if(it!groups2.end())result.emplace_back(kv.second,it-second);}sort(result.begin(),result.end());// 按L1词组排序if(!firstCase)cout\n;// 测试用例间空行firstCasefalse;for(constautop:result)coutp.first/p.second\n;}return0;}总结本题是一道经典的文本处理与集合映射问题关键在于行号集合作为等价关系的核心利用std::setint作为键值直接比较简化了匹配逻辑。分词与去重需注意同一行内同一单词只计一次且单词仅含字母和连字符。歧义合并同一集合内多个单词按字母序拼接保证了输出唯一性。容器选择unordered_map用于快速单词查重mapsetint, ...用于集合分组充分利用了 STL 的有序容器特性。本题数据范围较小采用朴素的逐行扫描和 STL 容器即可高效通过。掌握这种“行号集合”的抽象方法有助于处理类似的双语对齐或共现分析问题。