2010年1月31日星期日.ural1067-pku1760
算是數(shù)據(jù)結(jié)構(gòu)類(lèi)的題吧。
其實(shí)不難只不過(guò)怪我不該不仔細(xì)讀題，然后還看了pku上僅有的兩個(gè)發(fā)言，
有一哥們說(shuō)不是絕對(duì)路徑，然后我就全理解錯(cuò)了。
看到
http://www.nocow.cn/index.php/URAL%E9%A2%98%E8%A7%A3
上有題解，不過(guò)是pascal的，努力看了看，才發(fā)現(xiàn)我理解錯(cuò)了。。。
其實(shí)題目的意思是
給出從根開(kāi)始的文件夾名字，讓你組建樹(shù)結(jié)構(gòu)
注意：如果給出兩個(gè)路徑
a\b
b\c
那么結(jié)果應(yīng)該是
a
b
b
c
而不是
a
b
c
我一開(kāi)始就是這么理解的，然后錯(cuò)了。。。
一個(gè)方法是按照樹(shù)的遍歷那么寫(xiě)，還有一個(gè)方法還可以對(duì)每個(gè)路徑排序，然后遞歸輸出。
還有就是要注意按照字典序輸出。
還有就是pku和ural的編譯器好像都不是很標(biāo)準(zhǔn)的g++
ural的是vc++ 7.0
pku的是MinGW,和vc++ 8.0
我是在linux下用g++-4.4寫(xiě)的，然后傳上去之后兩個(gè)地方全報(bào)編譯錯(cuò)誤。。。
都是string 的 <運(yùn)算符重載問(wèn)題。
1
2 #define pb(x) push_back(x)
3 const int N = 512 * 4;
4
5 int n;
6 bool getword(char s[N])
7 {//http://www.shnenglu.com/schindlerlee
8 int i = 0;
9 char t;
10 //t = getchar();
11 scanf("%c", &t);
12 while (t != '\\' && t != '\n') {
13 s[i++] = t;
14 //t = getchar();
15 scanf("%c", &t);
16 }
17 s[i++] = 0;
18 return t == '\n';
19 }
20
21 struct L {
22 string s;
23 vector < L * >next;
24 } *root, pool[N * 10];
25 int sp, top;
26 string str[N];
27
28 bool cmp(L * a, L * b) { return strcmp((a->s).c_str() , (b->s).c_str()) < 0; }
29 void insert(L * root, int idx)
30 {
31 //printf("idx =%d\n",idx);
32 if (idx == sp) return;
33
34 int i, sz = root->next.size();
35 for (i = 0; i < sz; i++) {
36 if (!strcmp(root->next[i]->s.c_str() , str[idx].c_str())) {
37 return insert(root->next[i], idx + 1);
38 }
39 }
40 if (i == sz) {
41 pool[top].s = str[idx];
42 root->next.pb(&pool[top]);
43 insert(&pool[top++], idx + 1);
44 }
45 }
46
47 void dfs(L * root, int margin)
48 {
49 sort(root->next.begin(), root->next.end(), cmp);
50 int i, sz = root->next.size();
51 for (i = 0; i < sz; i++) {
52 int j = margin;
53 while (j--)
54 putchar(' ');
55 cout << (root->next[i]->s.c_str()) << endl;
56 dfs(root->next[i], margin + 1);
57 }
58 }
59
60 char s[N];
61 int main()
62 {
63 root = &pool[top++], root->s = "";
64 int i, j;
65 scanf("%d\n", &n);
66 for (i = 0; i < n; i++) {
67 sp = 0;
68 while (1) {
69 int isend = getword(s);
70 str[sp++] = s;
71 if (isend) break;
72 }
73 insert(root, 0);
74 }
75 dfs(root, 0);
76 return 0;
77 }
78