[COGS 1086][福州培训2010]文件夹计数 AC_Code

folder.cpp

/*
*Problem : COGS 1086
*Contest : 福州NOIP2010培训
*Author  : YeefanZhu
*Address : http://cojs.tk/cogs/problem/problem.php?pid=1086
*/
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
class Node
{
	public:string name;
	vector<Node*> child;
}; typedef Node* pNode;
int Ans=0,N;
string str;
vector<string> names;

inline pNode NewNode()
{
	pNode tmp=new Node;
	tmp->name.clear();
	tmp->child.clear();
	return tmp;
}
pNode Root=NewNode();

void dfs(pNode pnt,unsigned int deep)
{
	if(deep==names.size()) return;
	string nname=names[deep]; bool find=false;
	for(unsigned int i=0;i<pnt->child.size();i++)
	{
		if( (pnt->child[i])->name!=nname) continue;
		find=true; dfs(pnt->child[i],deep+1); break;
	}
	if(find) return; Ans++;
	pNode tmp=NewNode(); tmp->name=nname;
	pnt->child.push_back(tmp); dfs(tmp,deep+1);
}

int main()
{
	freopen("folder.in","r",stdin);
	freopen("folder.out","w",stdout);
	cin>>N; int len; string tname;
	for(int i=1;i<=N;i++)
	{
		str.clear(); names.clear();
		cin>>str; str.push_back(str[0]);
		len=str.length(); tname.clear();
		for(int j=1;j<len;j++)
		{
			if(str[j]==str[0])
			{
				names.push_back(tname);
				tname.clear(); continue;
			}
			tname.push_back(str[j]);
		}
		dfs(Root,0);
		cout<<Ans<<endl;
	}
	return 0;
}

第一次寫這麼複雜的字符串樹。。用了STL的string和vector。。閱讀起來比較費勁