代码鉴赏,[福州培训2010]文件夹计数(字符串树)

题目地址:

http://d1kt.cn/course/mod/programming/view.php?id=2876

AC代码:

  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <vector>
  4. #include <string>
  5. #include <cstring>
  6. #include <iostream>
  7. #include <algorithm>
  8. using namespace std;
  9. class Node
  10. {
  11. public:string name;
  12. vector<Node*> child;
  13. }; typedef Node* pNode;
  14. int Ans=0,N;
  15. string str;
  16. vector<string> names;
  17.  
  18. inline pNode NewNode()
  19. {
  20. pNode tmp=new Node;
  21. tmp->name.clear();
  22. tmp->child.clear();
  23. return tmp;
  24. }
  25. pNode Root=NewNode();
  26.  
  27. void dfs(pNode pnt,unsigned int deep)
  28. {
  29. if(deep==names.size()) return;
  30. string nname=names[deep]; bool find=false;
  31. for(unsigned int i=0;i<pnt->child.size();i++)
  32. {
  33. if( (pnt->child[i])->name!=nname) continue;
  34. find=true; dfs(pnt->child[i],deep+1); break;
  35. }
  36. if(find) return; Ans++;
  37. pNode tmp=NewNode(); tmp->name=nname;
  38. pnt->child.push_back(tmp); dfs(tmp,deep+1);
  39. }
  40.  
  41. int main()
  42. {
  43. freopen("folder.in","r",stdin);
  44. freopen("folder.out","w",stdout);
  45. cin>>N; int len; string tname;
  46. for(int i=1;i<=N;i++)
  47. {
  48. str.clear(); names.clear();
  49. cin>>str; str.push_back(str[0]);
  50. len=str.length(); tname.clear();
  51. for(int j=1;j<len;j++)
  52. {
  53. if(str[j]==str[0])
  54. {
  55. names.push_back(tname);
  56. tname.clear(); continue;
  57. }
  58. tname.push_back(str[j]);
  59. }
  60. dfs(Root,0);
  61. cout<<Ans<<endl;
  62. }
  63. return 0;
  64. }
最后修改: 2013年05月1日 星期三 11:44