HomeWork1

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

新老客户大回馈,云服务器低至5折

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 }

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:ccf--20140303--命令行选项

下一篇:LNK1123: 转换到 COFF 期间失败: 文件无效或损坏