【UER #1】跳蚤OS（Trie）

跳蚤OS 是跳蚤国自主研发的功能强大的操作系统。

跳蚤OS的文件系统与普通的文件系统类似，是个文件夹套文件夹的结构。文件系统根目录称为“//”。我们可以用文件路径来表明文件所在的位置，比如“/flea/uoj/flea/uoj”表示根目录下的fleaflea文件夹下的uojuoj文件。

跳蚤OS的文件系统中。快捷方式是一种特殊的文件夹，点开该快捷方式相当于打开该快捷方式指向的文件夹。

比如，如果有一个快捷方式 “/etc/abc/etc/abc”，该快捷方式指向 “/flea/def/flea/def”这个文件夹，那么一旦访问“/etc/abc/etc/abc”就相当于访问“/flea/def/flea/def”。

这一天，跳蚤国王正在使用跳蚤OS。初始时文件系统为空，只有根目录。他每次会进行如下操作：

首先，随便写出两个文件路径 ss 和 tt。
接着，如果位置 tt 处不存在文件，则在该处创建一个空文件夹。
最后，跳蚤国王保证 ss 这个位置没有文件，于是在 ss 处创建一个快捷方式指向 tt。如果 tt 是个快捷方式，那么 ss 将指向 tt 所指向的文件夹。

上文所说的“创建”在父级目录不存在的时候要一并创建其父级目录。比如，假设文件系统里只有 “/v/v” 这个文件夹，那么现在我创建 “/v/flea/king/qaq/v/flea/king/qaq” 就会在文件系统中新增三个文件夹：“/v/flea/v/flea”, “/v/flea/king/v/flea/king”, “/v/flea/king/qaq/v/flea/king/qaq”。

跳蚤国王进行了 nn 次这样的操作后，开始不断问他的助手伏特：现在我如果在 pp 这个路径处创建一个文件夹（如果已存在则不创建），那么这个文件夹的真实路径是什么？

于是伏特只好向你求助了，请你帮一帮他吧！请参照样例来更清晰地理解题意。

输入格式

第一行两个正整数n,mn,m，表示跳蚤国王进行了nn个操作，提了mm个问题。

接下来nn行每行两个用空格隔开的字符串s,ts,t，表示跳蚤国王的一次操作。

接下来 mm 行每行一个字符串 pp 表示跳蚤国王的一个询问。

保证所有的 s,t,ps,t,p 都是合法的文件路径。即，文件夹名一定是由小写英文字母组成的非空字符串，路径名一定形如“/xxx/xxx/xxx/.../xxx/xxx/xxx/xxx/.../xxx”这样子。保证当路径不为根目录“//”时，路径不以“//”结尾。

输出格式

对于跳蚤国王的每个询问输出真实路径。

样例一

input

6 5

/root /

/duliu /picks

/vfk /vfleaking

/orz/orz/orz /duliu

/otl /duliu/duliu

/vfk/sb /vfleaking

/vfk/sb/nothing/nothing

/orz

/orz/orz/orz

/qaq

/otl

output

/vfleaking/nothing/nothing

/orz

/picks

/qaq

/picks/duliu

explanation

创建的快捷方式分别为：

/root→//root→/
/duliu→/picks/duliu→/picks
/vfk→/vfleaking/vfk→/vfleaking
/orz/orz/orz→/picks/orz/orz/orz→/picks
/otl→/picks/duliu/otl→/picks/duliu
/vfleaking/sb→/vfleaking/vfleaking/sb→/vfleaking

样例二

input

2 3

/ba/la /

/w/o/w /w

/ba/la/ba/la/ba/la/ba/la/ba/la/ba/la/ba/la

/ba/la/ba/la/ba/la/ba/la/ba/la/ba/la/ba/la/ba

/w/o/w/o/w/o/w/o

output

/

/ba

/w/o

样例三

见样例数据下载

限制与约定

测试点编号	nn	mm	其他
1	≤200≤200	≤10≤10	保证单个字符串长度不会超过 4040
2
3
4	≤20000≤20000		保证每个输入的路径字符串中仅包含一个“//”且位于字符串开头。保证单个字符串长度不超过1515。
5
6
7	≤20000≤20000
8
9
10

对于所有数据，输入中路径字符串总长度不会超过 5×1055×105。

时间限制：1s1s

空间限制：256MB256MB

为了防止有些同学看晕了，我还是再罗嗦几句。下面的路径名都是非法的：

/orz//orz/
/orz//otl/orz//otl
/233/233 （注意，只能含有小写英文字母）

下面的路径名都是合法的：

//
/orz/otl/oorrzz/oottll/orz/otl/oorrzz/oottll
/a

【思路】

Trie+链接

给每个节点加个go指针，使之作为快捷方式链接真实路径字符串在 Trie 中对应的结点。

于是我们可以读入字符串，然后顺着Trie树走。当下一个字符是 “/” 或者已到达字符串结尾时，尝试从 go 指针跳转

【代码】

 #include<cmath>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define FOR(a,b,c) for(int a=(b);a<=(c);a++)

 using namespace std;

 const int N = *1e5+;

 int n,m;

 char s[N],q[N];

 struct Trie {

     int sz; char b[N];

     int ch[N][],go[N],fa[N];

     Trie() { sz=; }

     int insert() {

         int u=;

         scanf("%s",s);

         int len=strlen(s);

         if(s[len-]!='/') s[len++]='/';

         for(int i=;i<len;i++) {

             int c=s[i]-'a';

             if(s[i]=='/') c=;

             if(!ch[u][c]) {

                 ch[u][c]=++sz;

                 fa[sz]=u;

                 b[sz]=s[i];

             }

             u=ch[u][c];

             if(s[i]=='/') while(go[u]) u=go[u];

         }

         return u;

     }

 }T;

 int main() {

     scanf("%d%d",&n,&m);

     for(int i=;i<n;i++) {

         int x=T.insert(),y=T.insert();

         T.go[x]=y;

     }

     for(int i=;i<m;i++) {

         int x=T.insert();

         int top=;

         for(int i=x;i!=;i=T.fa[i])

             q[++top]=T.b[i];

         if(top==) puts("/");

         else {

             while(top>) printf("%c",q[top--]);

             puts("");

         }

     }

     return ;

 }

秒客网

【UER #1】跳蚤OS（Trie）

输入格式

输出格式

样例一

input

output

explanation

样例二

input

output

样例三

限制与约定

相关文章