首页 > > 程序设计 > C/C++ >

HomeWork1

2018-06-17 21:03:55来源：未知阅读 ()

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 }