分类 解题报告 下的文章

PAT 航空公司VIP客户查询(哈希)解题报告


解题思路

题意不难,无非就是把身份证号哈希一下就可以计数了。于是我们可以把身份证号字符串的下标为 0, 5, 10, 15 位置上的字符 ASCII 码累加起来取余 10 当做哈希值的第一位,然后 1, 6, 11, 16 下标的累加和取余 10 当做哈希值的第二位,以此类推,就可以得到一个简单的哈希值。至于如何处理冲突,我这里使用了链地址法(基于 vector 实现),代码写起来比较简单。

如果不想自己写哈希的话,也可以用 map。不过本题如果直接用 string 的 map 是会超时的,但是神奇的是如果换用 long long 的 map 就不会超时哦!


PAT 基于词频的文件相似度(set)解题报告


解题思路

每个文件内的单词存放到单独的一个 set 中。询问时直接遍历其中一个 set(必须是 size 较小的那个,否则会超时在最后一个测试点),用 count() 查找另一个 set 中存不存在这个单词即可。做法类似 PAT 上另一道题目「集合相似度」(连示例输出都几乎是一样的)。


UVALive 6957 Hyacinth(DFS)解题报告


Also available: UVALive 6957, Kattis hyacinth, UESTC 1119

题意

在一个网络中给出 n 个节点,每个节点最多可以有两种频率,又给出 n-1 条边(题目保证形成树),要求每条边上的两个节点必须至少有一种频率相同,如果一种频率两个相连的节点所使用,那么这种频率就算做已使用的频率。要求使已使用频率的种数尽可能多,输出每个节点的频率。