题目描述

Bob Roberts 负责在不同语言之间进行文档翻译。他的上司提供了成对的翻译文件：一个文件包含某种语言的短语，另一个文件包含这些短语翻译成另一种语言的结果。然而，某个下属擅自将所有文件的内容按字母顺序排序，导致短语与其翻译之间的对应关系丢失。幸运的是，由于这些列表非常全面，原始翻译可以从排序后的列表中重新构建。Bob 发现，当所有短语都由两个单词组成时，这种情况通常成立。

输入格式：

• 输入包含多个输入集。
• 每个输入集以一个正整数 n ≤ 250 开头，表示每种语言中两单词短语的数量。
• 随后是 2n 行：前 n 行是第一种语言的短语（按字母顺序排列），后 n 行是第二种语言的短语（按字母顺序排列）。
• 单词仅包含大小写字母。
• 每个输入集最多涉及 25 个不同的单词。
• 对于任何一种语言，没有任何单词作为短语的第一个单词出现超过 10 次，同样也没有任何单词作为短语的最后一个单词出现超过 10 次。
• 最后一个输入集之后是一行仅包含 0，表示输入结束。

输出格式：

• 对于每个输入集，输出以下形式的行：word1/word2，其中 word1 是第一种语言的单词，word2 是 word1 在第二种语言中的翻译。
• 输出行应按第一种语言的单词排序，且每个第一种语言的单词只出现一次。
• 不同输入集的输出之间用一个空行分隔。

解题思路

1. 问题分析

我们需要从两组已排序的短语列表中恢复单词之间的对应关系。关键在于利用短语的结构（两单词组成）和排序后的唯一性约束来推断单词的翻译。

2. 关键观察

• 每个短语由两个单词组成，且列表已按字母顺序排序。
• 由于列表非常全面，可以通过短语的“共同部分”推断单词的翻译。
• 例如：
  • 如果 pleve 出现在多个短语中（如 pleve dourm 和 pleve zym），而对应的翻译是 bus stop 和 school bus，则可以推断 pleve 对应 bus。
  • 类似地，dourm 和 stop 是唯一对应的，因为 bus stop 中 stop 是第二个单词。

3. 算法设计

• 构建单词频率表：
  • 统计每种语言中每个单词作为第一个单词和第二个单词出现的频率。
  • 例如，pleve 作为第一个单词出现了 2 次，bus 作为第一个单词出现了 2 次。
• 匹配唯一对应关系：
  • 如果一个单词在第一种语言中作为第一个单词出现的次数等于某个单词在第二种语言中作为第一个单词出现的次数，则可以尝试匹配。
  • 类似地处理第二个单词。
• 逐步消解：
  • 从唯一确定的单词开始（如出现次数最少的单词），逐步推导其他单词的翻译。
  • 使用类似拓扑排序的方法，每次处理一个已确定的单词，更新其他单词的可能性。

4. 实现步骤

1. 读取输入数据，分离两种语言的短语列表。
2. 统计每种语言中每个单词作为第一个和第二个单词的出现次数。
3. 构建单词之间的可能对应关系。
4. 通过唯一性约束逐步确定单词的翻译。
5. 输出结果，按第一种语言的单词排序。

5. 示例解析

以示例输入为例：

4
arlo zym
flub pleve
pleve dourm
pleve zym
bus seat
bus stop
hot seat
school bus

• 第一种语言的短语：
  • arlo zym
  • flub pleve
  • pleve dourm
  • pleve zym
• 第二种语言的短语：
  • bus seat
  • bus stop
  • hot seat
  • school bus

统计单词出现次数：

• 第一种语言：
  • 第一个单词：arlo(1), flub(1), pleve(2)
  • 第二个单词：zym(2), pleve(1), dourm(1)
• 第二种语言：
  • 第一个单词：bus(2), hot(1), school(1)
  • 第二个单词：seat(2), stop(1), bus(1)

匹配过程：

1. flub 和 school 都作为第一个单词出现 1 次，可以匹配。
2. dourm 和 stop 都作为第二个单词出现 1 次，可以匹配。
3. pleve 作为第一个单词出现 2 次，bus 也出现 2 次，可以匹配。
4. 剩下的单词可以逐步推导。

代码实现

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

using namespace std;

struct Phrase {
	string a;
	string b;
};

int main() {
	int n;
	bool first_case = true;
	
	while (cin >> n && n != 0) {
		if (!first_case) {
			cout << endl; // 不同测试用例间输出空行
		}
		first_case = false;
		
		vector<Phrase> lang1(n), lang2(n);
		map<string, pair<int, int>> cnt1, cnt2;
		set<string> words1, words2;
		
		// 读取并统计语言1
		for (int i = 0; i < n; ++i) {
			string a, b;
			cin >> a >> b;
			lang1[i] = {a, b};
			cnt1[a].first++;    // 作为首单词的次数
			cnt1[b].second++;   // 作为尾单词的次数
			words1.insert(a);
			words1.insert(b);
		}
		
		// 读取并统计语言2
		for (int i = 0; i < n; ++i) {
			string a, b;
			cin >> a >> b;
			lang2[i] = {a, b};
			cnt2[a].first++;
			cnt2[b].second++;
			words2.insert(a);
			words2.insert(b);
		}
		
		// 构建映射字典
		map<string, string> dict;
		for (const auto& w1 : words1) {
			auto& c1 = cnt1[w1];
			for (const auto& w2 : words2) {
				if (cnt2[w2] == c1) {
					dict[w1] = w2;
					break; // 题目保证唯一解，找到即可停止
				}
			}
		}
		
		// 转换并排序结果
		vector<pair<string, string>> res;
		for (const auto& w : words1) {
			res.emplace_back(w, dict[w]);
		}
		sort(res.begin(), res.end());
		
		// 输出结果
		for (const auto& p : res) {
			cout << p.first << "/" << p.second << endl;
		}
	}
	
	return 0;
}

进一步思考

1. 如何处理更长的短语？
   • 如果短语由多个单词组成，可能需要更复杂的匹配算法（如基于统计或机器学习的方法）。
2. 单词歧义问题：
   • 如果一个单词在两种语言中有多个可能的翻译，可能需要上下文或其他约束来解决。
3. 优化算法：
   • 可以使用图论中的二分图匹配或最大流算法来优化单词匹配过程。

总结

本题的关键在于利用短语的结构和单词出现的频率约束，通过逐步消解的方法恢复单词之间的对应关系。实现时需要注意处理输入输出的格式和边界条件。