STL大法好!

(看到楼下的大佬们都没有用我这个方法,我就来脱碳甲醛一下辣~~)


以上都是废话

我所说的这个方法,具体思路是这样的:

  • 最首先,基础的并查集大家应该都会,如果不会的话可以看代码或者出门右转P3367并查集模板
  • 然后,STL中的Map可以直接方便地解决字符串哈希的问题
  • 但是,每次都用一遍Map似乎显得有些不优美,似乎有些慢的说
  • 所以,我们需要引进两个数组,一个Num和一个Names
  • Num是一个Map,它的作用就是Num[“A”]表示名为A的人的编号
  • 于是,Names就是反过来的Num,Name[i]表示编号为i的人的名字
  • 总体而言,不仅加快了速度,还方便了调试

上代码~~


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<bits/stdc++.h> // 万能头文件 

using namespace std;

int f[50100]; // 并查集,f[i]表示编号为i的人的祖先(可能是之一)
map <string, int> Num; // 前面已经解释过了
string Names[50100]; // 同上
map <string, bool> Used; // 表示这个人有没有被加进Num数组里面

int Find(int x){ // 找到编号为x的人最早的祖先(并查集的东西)
if(f[x] == x) return x;
int next = Find(f[x]);
f[x] = next; // 路径压缩
return next;
}

void Link(int Fa, int Son){ // 将两个人连起来(把Son加到Fa的族谱下方)
f[Son] = f[Find(Fa)];
}

int main(){
string Name; // 当前这组父子关系中儿子的名字
string Fa; // Fa ♂乐♂器 (划掉)其实是表示当前这组父子关系中父亲的名字
char Type = 'A'; // 顾名思义,当前读入指令的种类
int Cur = 0; // 当前编号编到第几个
int Fanum; // 表示当前这组父子关系中父亲的编号
while(Type != '$'){
Type = getchar();
switch(Type){
case '#':{
cin >> Fa;
if(!Used[Fa]){ // 如果这人第一次出现,给他编个号
Used[Fa] = true;
Num[Fa] = ++Cur;
Names[Cur] = Fa;
}
if(f[Num[Fa]] == 0) // 如果他没有祖先,将他的祖先定义为他自己
f[Cur] = Cur;
Fanum = f[Num[Fa]];
break;
}
case '+':{
cin >> Name;
if(!Used[Name]){ // 如果这个人是第一次出现,给他编个号
Used[Name] = true;
Num[Name] = ++Cur;
Names[Cur] = Name;
}
if(f[Num[Name]] == 0) // 如果他没有祖先,将他的祖先定义为他自己
f[Num[Name]] = Cur;
Link(Fanum, Num[Name]); // 设定:他是他爸爸的儿子
break;
}
case '?':{ // 问询操作:输出Name和Name最早的祖先
cin >> Name;
cout << Name << " " << Names[Find(Num[Name])]<< endl;
break;
}
default:break;
}
}
return 0;
}

 评论