Time Limit: 1 second
Memory Limit: 128 MB
【问题描述】
可以用路径来描述文件夹，路径为一个包含若干部分的字符串，之间用’/’分隔。每部分均为一个文件夹的名称，且表示这个文件夹的父文件夹为前一部分描述的文件夹。
例如：/home/fj/summer表示根目录下有一个名称为home的文件夹，这个home文件夹下有一个名称fj的文件夹，这个名称为fj的文件夹下有。
每个路径的第1个字符总是’/’，且不会出现两个连续的’/’，最后一个字符不会是’/’。而所有文件夹仅包含数字和字母。
现在先给出N个路径，一开始除了根目录不存在任何文件夹，在每给出一个路径后，对于第i个路径，你需要输出的是若要让第1个路径到第i
个路径存在，最少需要新建多少个文件夹。
【输入格式】
输入文件第1行为一个正整数N。 接下来N行，每行为一个描述路径的字符串，长度均不超过100。【输出格式】
输出应包含N行，每行1个正整数，第i行输出若要使第1个路径到第i个路径存在，最少需要新建多少个文件夹。
【数据规模】
对于所有数据，N<=1000。 对于部分数据，有N<=20； 对于部分数据，有N<=200； 对于部分数据，有对于所有路径最多存在两个’/’（包含第1个字符）。
Sample Input1
2 /home/fj/summer /home/fj/123
Sample Output1
3 4
Sample Input2
4 /a /a/b /a/c /b/b
Sample Output2
1 2 3 5
Sample Input3
3 /chicken /chicken/egg /chicken
Sample Output3
1 2 2【题解】
这就是一道字典树的题。
只要往根节点往下走。然后走完一个文件夹就记录这个节点是终点。之后如果同样到达这个节点。则不用新建文件夹。否则要新建文件夹。
然后会出现最后一个字符也是/的情况。且这个时候要再新建一个文件夹。
用数组模拟链表。然后数组要开到20万左右。
【代码】
#include <cstdio>
#include <iostream>
#include <string>
using namespace std;
struct node//用数组来模拟链表 直接用指针会爆炸
{
bool haved_end;
int next[39];
};
int root = 1,tot = 1;
node tree[200000]; //数组来模拟链表
int n,num=0;
void input_data()
{
for (int i = 1;i <= 38;i++) //把没有到达过的置为-1
tree[root].next[i] = -1;
tree[root].haved_end = false;
scanf("%d",&n);
for (int i = 1;i <= n;i++) //输入n个路径
{
char sss[250];
scanf("%s",sss);
string s = " ",ss; //用scanf来读入字符串
ss = string(sss);
s+=ss;
int l = s.size();
int j = 1;
int p = root;
while (j!=-1) //如果路径还没读完就继续
{
int t = s.find('/',j+1); //j到t之间是下一个文件夹的名字
bool flag = false;
if (tree[p].next[27] == -1) //如果之前没有达到过这个/就表示要新建一个文件夹了
{ //比如/home/fj 则我们先到左边一个/的位置。然后再往下走h-o-m-e的路径
tot++; //新建一个即可。
for (int k = 1;k <= 38;k++)
tree[tot].next[k] = -1;
tree[tot].haved_end = false;
tree[p].next[27] = tot;
p = tot;
flag = true;
}
else
p = tree[p].next[27];
int end;
if (t == -1) //这是最后一个文件夹的情况.往下走的时候要特殊处理下.
{
end = s.size()-1;
}
else
end = t-1;
for (int k = j+1;k <= end;k++) //一直往下走。
{
int what;
if (s[k]>='0' && s[k]<='9') //获取其是数字还是字母
what = s[k]-'0'+28;
else
what = s[k]-'a'+1;
if (tree[p].next[what] == -1) //如果没有创建过这个节点则创建表示有一个新的文件夹。
{
tot++;
for (int m = 1;m <= 38;m++) //初始化这个节点
tree[tot].next[m] = -1;
tree[p].next[what] = tot;
p = tot;
flag = true;
}
else
p = tree[p].next[what];
}
if (tree[p].haved_end == false) //标记这个节点是某串字符的最后一个节点。
{
tree[p].haved_end = true;
flag = true;
}
j = t;
if (flag)
num++;
}
printf("%d
",num);
}
}
int main()
{
//freopen("F:\rush.txt","r",stdin);
input_data();
return 0;
}