HomeWork1
程序员文章站
2022-04-16 09:54:31
HomeWork1 a)项目描述 原文链接 最近公共祖先问题。对于100%的数据,满足N<=10^5,M<=10^5, 且数据中所有涉及的人物中不存在两个名字相同的人(即姓名唯一的确定了一个人),所有询问中出现过的名字均在之前所描述的N对父子关系中出现过,第一个出现的名字所确定的人是其他所有人的公共 ......
HomeWork1
a)项目描述
原文链接
最近公共祖先问题。对于100%的数据,满足N<=10^5,M<=10^5, 且数据中所有涉及的人物中不存在两个名字相同的人(即姓名唯一的确定了一个人),所有询问中出现过的名字均在之前所描述的N对父子关系中出现过,第一个出现的名字所确定的人是其他所有人的公共祖先。
b) 错误描述
项目完成后,对于输入的样例数据无论如何都得不出正确的结果。再确认思路无误后,进行了大量的错误排查,仍无法定位错误所在地。由于数据量巨大,当时没有现成的输入数据,无法通过常规的方式进行debug,当时只能仔细思考,推导代码的走势。
c) 错误解决
由于该项目是用来解决大数据量的问题,在数据结构方面进行了大量的优化,其中最明显的地方就是对于数入数据的重排。利用vector来存大量的输入数据,数据和数据下标组成一个数据元,当时在数据遍历时并没有将数据元作为一个基本单位,而是将数据作为基本单位(见第74行代码),导致遍历时访问了错误的数据,最终导致了错误的结果。修正后上传至系统,得出了正确的结果。这种十分常见的细节错误让我留下了深刻的印象。
d)源代码
1 #include <iostream> 2 #include <vector> 3 #include <map> 4 #include <memory.h> 5 6 using namespace std; 7 8 int far[100010],represent[100010],true_num,int_far,int_son,int_name1,int_name2,state[100010]; 9 map <string, int> name_str_int; 10 string name_int_str[100010]; 11 vector<int> son[100010],left_next[100010]; 12 int input[100010]; 13 14 int GetNum(string); 15 int dfs(int); 16 int Represent(int); 17 18 int main() 19 { 20 cin.sync_with_stdio(0); 21 cin.tie(0); 22 23 int N,M; 24 string Father_i,Son_i,Name1_i,Name2_i; 25 26 name_str_int.clear(); 27 true_num=0; 28 memset(state,0,sizeof(state)); 29 for(int i=1; i<100010; i++) 30 represent[i]=i; 31 32 cin>>N; 33 while(N--) 34 { 35 cin>>Father_i>>Son_i; 36 int_far=GetNum(Father_i); 37 int_son=GetNum(Son_i); 38 son[int_far].push_back(int_son); 39 far[int_son]=int_far; 40 } 41 42 cin>>M; 43 for(int i=1; i<=M; i++) 44 { 45 cin>>Name1_i>>Name2_i; 46 int_name1=name_str_int.at(Name1_i); 47 int_name2=name_str_int.at(Name2_i); 48 if(int_name1==int_name2) 49 input[i]=int_name1; 50 else 51 { 52 left_next[int_name1].push_back(int_name2); 53 left_next[int_name1].push_back(i); 54 } 55 } 56 dfs(1); 57 for(int i=1; i<=M; i++) 58 cout<<name_int_str[input[i]]<<endl; 59 60 } 61 62 int Represent(int number) 63 { 64 while(number!=represent[number]) 65 number=represent[number]; 66 return number; 67 } 68 69 int dfs(int cur_node) 70 { 71 //cout<<"-->"<<name_int_str[cur_node]; 72 state[cur_node]=1; 73 74 for(int i=0; i<left_next[cur_node].size(); i=i+2) 75 { 76 if(state[left_next[cur_node][i]]) 77 { 78 input[left_next[cur_node][i+1]]=Represent(left_next[cur_node][i]); 79 } 80 else 81 { 82 left_next[left_next[cur_node][i]].push_back(cur_node); 83 left_next[left_next[cur_node][i]].push_back(left_next[cur_node][i+1]); 84 } 85 } 86 87 for(int i=0; i<son[cur_node].size(); i++) 88 dfs(son[cur_node][i]); 89 90 represent[cur_node]=far[cur_node]; 91 //state[cur_node]=2; 92 } 93 94 int GetNum(string name) 95 { 96 if(!name_str_int.count(name)) 97 { 98 name_int_str[++true_num]=name; 99 name_str_int.insert(pair<string, int> (name, true_num)); 100 return true_num; 101 } 102 return name_str_int.at(name); 103 }
上一篇: 使用Python的package机制如何简化utils包设计详解
下一篇: 常用算法