问题求解III-HW11 题解
Problem A: 字符串匹配
- 给定一个字符串池，有 $q$ 查询，每次查询提供一个字符串，问该字符串是否在字符串池中。
- 字符串池中字符串数目和 $q$ 同阶，$q\leq 10^5$，所有字符串长度不超过 16。
解法1: 内置数据结构
对于 C++ 而言，使用红黑树实现的 set<string> 或哈希实现的 unordered_set<string> 都可以轻松完成本题。
解法2: 哈希
参考 讲义 中的讲解。注意本题可能需要使用讲义最后提到的双哈希才能通过。
解法3: 字典树
这是一道字典树的模板题，参考 讲义 中的讲解。
Problem B: 顶点覆盖
- 给定一张图 $G(V, E)$，求图的一个尽可能小的顶点覆盖 (即所有边都至少有一个端点在选中的点集中)，你的答案只要不超过最优解的 2 倍即可。
- $|V|\leq 2000, |E|\leq 20000$。
近似比为 2 的顶点覆盖近似算法非常简单：只需要在原图中任取一个极大匹配，然后将匹配边的端点全部选中即可。具体细节和证明见教材。