题解 洛谷P2814 家谱
March 16, 2018
STL大法好!
(看到楼下的大佬们都没有用我这个方法,我就来脱碳甲醛一下辣~~)
以上都是废话
我所说的这个方法,具体思路是这样的:
- 最首先,基础的并查集大家应该都会,如果不会的话可以看代码或者出门右转P3367并查集模板
- 然后,STL中的Map可以直接方便地解决字符串哈希的问题
- 但是,每次都用一遍Map似乎显得有些不优美,似乎有些慢的说
- 所以,我们需要引进两个数组,一个Num和一个Names
- Num是一个Map,它的作用就是Num[“A”]表示名为A的人的编号
- 于是,Names就是反过来的Num,Name[i]表示编号为i的人的名字
- 总体而言,不仅加快了速度,还方便了调试