C++题解 P2288 家谱(gen)

C++题解 P2288 家谱(gen)

原题：2288.家谱(gen)FHD_WOLF 于2025-02-12

---

思路

这题如果没有字符串处理，就是一道ez的并查集板子题。

所以这题的难点在于：字符串处理。

如果我们能有一个f(x)表示字符串x对应的编号f(x)，再有一个g(x)表示编号为x的字符串，在每次输入后调下f(x)，merge一下，询问的时候g(根节点)，就能做出来了。

map时间复杂度高，我在这里介绍一下hash的解法。

普通hash函数直接完成了f(x)函数的功能，
接下来我们令names[hash(name)]=name，
以后询问的时候直接names[getroot(hash(name)]，
这题就做完了。

Hash是什么？

你可以将一个大字符串看成一个T进制位的整数，而每个字母都有它对应的值。

习惯上，我们直接使用每个字母的ASCII作为它代表的值。

计算的时候，你的结果需要%一个MOD。

1. int hash(char str[]) //str的字符串部分从str[1]开始
2. {
3. int i, l = strlen(str + 1), ret = 0;
4. for (i = 1; i <= l; i++) ret = ((ret * T + MOD) % MOD + str[i] - '0' + MOD) % MOD;
5. return (ret + MOD) % MOD;
6. } //这里的实现可以手算模拟一下

参考大常数代码

#include <cstdio>
#include <cstring>const int MOD = 1000007, T = 12346; //定义hash的MOD和T
int fa[MOD]; //并查集
char names[MOD][7]; //names用来实现从字符串查到编号的功能int get(int x)
{
if (fa[x] != x) fa[x] = get(fa[x]);
return fa[x];
} //你的get_root写法跟这个不一样没关系QwQint hash(char str[])
{
int i, l = strlen(str + 1), ret = 0;
for (i = 1; i <= l; i++) ret = ((ret * T + MOD) % MOD + str[i] - '0' + MOD) % MOD;
return (ret + MOD) % MOD;
}int main()
{
char ch = getchar(), name[7];
int i, lastfa = -1, nowhash, t;
//lastfa是上次读入的父亲节点（字符串编号），也就是带'#'的节点
for (i = 1; i <= MOD; i++) fa[i] = i; //并查集初始化，这道题里也说的过去，如果没有父亲节点，最早祖先就是自己
while (ch != '$')
{
for (i = 1; i <= 6; i++) name[i] = getchar(); //读入名字
nowhash = hash(name); //令nowhash=当前名字的hash值（编号），为了防止以后的重复调用hash()
for (i = 1; i <= 6; i++) names[nowhash][i] = name[i]; //令names[hash(name)]=name
if (ch == '#') lastfa = nowhash; //更新lastfa
else if (ch == '+') fa[get(nowhash)] = get(lastfa); //使此节点的最早祖先为它父亲的最早祖先，相当于合并它所在集合与父亲节点所在集合，所有节点的最早祖先统一
else if (ch == '?')
{
for (i = 1; i <= 6; i++) putchar(name[i]); //先输出本人的名字
putchar(' '); //一个空格
for (i = 1; i <= 6; i++) putchar(names[get(nowhash)][i]); //最早祖先的名字
putchar('\n'); //一个换行符
}
ch = getchar();
while (ch == '\r' || ch == '\n' || ch == EOF) ch = getchar(); //这里是去除不必要的字符防止getchar()出现混乱，读入下一个需求的类型
}
return 0;
}