题目链接：http://hihocoder.com/problemset/problem/1383
题意：每一行代表一个路径，这个路径表示一本书的存放。现在给一堆路径，要把它们规范一下缩进。
思路：很容易想到trie数，但是每一个节点的元素是不一定的。所以可以用vector来存，最后排一遍序。
注意有文件名和目录同名的情况，要判断一下。
修剪过的代码：
1 #include <algorithm> 2 #include <iostream> 3 #include <iomanip> 4 #include <cstring> 5 #include <climits> 6 #include <complex> 7 #include <cassert> 8 #include <cstdio> 9 #include <bitset> 10 #include <vector> 11 #include <deque> 12 #include <queue> 13 #include <stack> 14 #include <ctime> 15 #include <set> 16 #include <map> 17 #include <cmath> 18 using namespace std; 19 #define fr first 20 #define sc second 21 #define cl clear 22 #define BUG puts("here!!!") 23 #define W(a) while(a--) 24 #define pb(a) push_back(a) 25 #define Rint(a) scanf("%d", &a) 26 #define Rll(a) scanf("%I64d", &a) 27 #define Rs(a) scanf("%s", a) 28 #define Cin(a) cin >> a 29 #define FRead() freopen("in", "r", stdin) 30 #define FWrite() freopen("out", "w", stdout) 31 #define Rep(i, len) for(int i = 0; i < (len); i++) 32 #define For(i, a, len) for(int i = (a); i < (len); i++) 33 #define Cls(a) memset((a), 0, sizeof(a)) 34 #define Clr(a, x) memset((a), (x), sizeof(a)) 35 #define Full(a) memset((a), 0x7f7f7f, sizeof(a)) 36 #define lrt rt << 1 37 #define rrt rt << 1 | 1 38 #define pi 3.14159265359 39 #define RT return 40 #define lowbit(x) x & (-x) 41 #define onecnt(x) __builtin_popcount(x) 42 typedef long long LL; 43 typedef long double LD; 44 typedef unsigned long long ULL; 45 typedef pair<int, int> pii; 46 typedef pair<string, int> psi; 47 typedef pair<LL, LL> pll; 48 typedef map<string, int> msi; 49 typedef vector<int> vi; 50 typedef vector<LL> vl; 51 typedef vector<vl> vvl; 52 typedef vector<bool> vb; 53 54 const int maxn = 100000; 55 vector<string> tmp; 56 vector<vector<string> > save; 57 char in[maxn], qq[maxn]; 58 59 void gao() { 60 int n = strlen(in); 61 int pre = 0, pos = 0; 62 tmp.clear(); 63 int cnt = 0; 64 while(pos < n) { 65 pre = pos; 66 while(in[pos] != '/' && in[pos]) pos++; 67 Cls(qq); 68 for(int i = pre; i < pos; i++) { 69 qq[i-pre] = in[i]; 70 } 71 tmp.push_back(qq); 72 pos++; 73 } 74 save.push_back(tmp); 75 } 76 77 typedef struct Node { 78 bool dir; 79 string key; 80 vector<Node*> next; 81 }Node; 82 int cnt; 83 Node* rt; 84 Node memory[maxn]; 85 86 bool cmp(Node* a, Node* b) { 87 if(a->dir == 0 && b->dir != 0) return 0; 88 if(a->dir != 0 && b->dir == 0) return 1; 89 return a->key < b->key; 90 } 91 92 void add(int idx, int cur, Node* rt) { 93 if(cur >= save[idx].size()) return; 94 bool flag = 0; 95 for(int i = 0; i < rt->next.size(); i++) { 96 if(rt->next[i]->key == save[idx][cur] 97 && !((rt->next[i]->dir && cur == save[idx].size()-1) 98 || (!rt->next[i]->dir && cur != save[idx].size()-1))) { 99 add(idx, cur+1, rt->next[i]); 100 return; 101 } 102 } 103 Node* x = &memory[cnt++]; 104 if(cur == save[idx].size() - 1) x->dir = 0; 105 else x->dir = 1; 106 x->key = save[idx][cur]; 107 x->next.clear(); 108 rt->next.push_back(x); 109 add(idx, cur+1, x); 110 } 111 112 void bfs() { 113 queue<Node*> q; 114 q.push(rt); 115 while(!q.empty()) { 116 Node* x = q.front(); q.pop(); 117 for(int i = 0; i < x->next.size(); i++) { 118 sort((*x).next.begin(), (*x).next.end(), cmp); 119 q.push(x->next[i]); 120 } 121 } 122 } 123 124 inline void X(int ind) { 125 Rep(i, ind) printf(" "); 126 } 127 128 void dfs(Node* p, int depth) { 129 if(p == rt) { 130 Rep(i, p->next.size()) { 131 cout << p->next[i]->key << endl; 132 dfs(p->next[i], depth+1); 133 } 134 } 135 else { 136 Rep(i, p->next.size()) { 137 X(depth); cout << p->next[i]->key << endl; 138 dfs(p->next[i], depth+1); 139 } 140 } 141 } 142 143 signed main() { 144 // FRead(); 145 int _ = 1; 146 while(gets(in) && strcmp(in, "0") != 0) { 147 save.clear(); 148 cnt = 0; rt = &memory[cnt++]; 149 rt->next.clear(); rt->key = "fuck"; rt->dir = 1; 150 gao(); 151 printf("Case %d: ", _++); 152 while(gets(in) && strcmp(in, "0") != 0) gao(); 153 Rep(i, save.size()) add(i, 0, rt); 154 bfs(); 155 dfs(rt, 0); 156 } 157 RT 0; 158 }
很搓的比赛代码：
1 #include <algorithm> 2 #include <iostream> 3 #include <iomanip> 4 #include <cstring> 5 #include <climits> 6 #include <complex> 7 #include <cassert> 8 #include <cstdio> 9 #include <bitset> 10 #include <vector> 11 #include <deque> 12 #include <queue> 13 #include <stack> 14 #include <ctime> 15 #include <set> 16 #include <map> 17 #include <cmath> 18 using namespace std; 19 #define fr first 20 #define sc second 21 #define cl clear 22 #define BUG puts("here!!!") 23 #define W(a) while(a--) 24 #define pb(a) push_back(a) 25 #define Rint(a) scanf("%d", &a) 26 #define Rll(a) scanf("%I64d", &a) 27 #define Rs(a) scanf("%s", a) 28 #define Cin(a) cin >> a 29 #define FRead() freopen("in", "r", stdin) 30 #define FWrite() freopen("out", "w", stdout) 31 #define Rep(i, len) for(int i = 0; i < (len); i++) 32 #define For(i, a, len) for(int i = (a); i < (len); i++) 33 #define Cls(a) memset((a), 0, sizeof(a)) 34 #define Clr(a, x) memset((a), (x), sizeof(a)) 35 #define Full(a) memset((a), 0x7f7f7f, sizeof(a)) 36 #define lrt rt << 1 37 #define rrt rt << 1 | 1 38 #define pi 3.14159265359 39 #define RT return 40 #define lowbit(x) x & (-x) 41 #define onecnt(x) __builtin_popcount(x) 42 typedef long long LL; 43 typedef long double LD; 44 typedef unsigned long long ULL; 45 typedef pair<int, int> pii; 46 typedef pair<string, int> psi; 47 typedef pair<LL, LL> pll; 48 typedef map<string, int> msi; 49 typedef vector<int> vi; 50 typedef vector<LL> vl; 51 typedef vector<vl> vvl; 52 typedef vector<bool> vb; 53 54 const int maxn = 100000; 55 vector<string> tmp; 56 vector<vector<string> > save; 57 char in[maxn], qq[maxn]; 58 59 void gao() { 60 int n = strlen(in); 61 int pre = 0, pos = 0; 62 tmp.clear(); 63 int cnt = 0; 64 while(pos < n) { 65 pre = pos; 66 while(in[pos] != '/' && in[pos]) pos++; 67 Cls(qq); 68 for(int i = pre; i < pos; i++) { 69 qq[i-pre] = in[i]; 70 } 71 tmp.push_back(qq); 72 pos++; 73 } 74 save.push_back(tmp); 75 } 76 77 typedef struct Node { 78 bool son, dir; 79 string key; 80 vector<Node*> next; 81 }Node; 82 int cnt; 83 Node* rt; 84 Node memory[maxn]; 85 86 bool cmp(Node* a, Node* b) { 87 if(a->son == 0 && b->son != 0) return 0; 88 if(a->son != 0 && b->son == 0) return 1; 89 return a->key < b->key; 90 } 91 92 void add(int idx, int cur, Node* rt) { 93 if(cur >= save[idx].size()) return; 94 bool flag = 0; 95 for(int i = 0; i < rt->next.size(); i++) { 96 rt->next[i]->son = 0; 97 if(rt->next[i]->key == save[idx][cur] 98 && !((rt->next[i]->dir && cur == save[idx].size()-1) 99 || (!rt->next[i]->dir && cur != save[idx].size()-1))) { 100 add(idx, cur+1, rt->next[i]); 101 return; 102 } 103 } 104 Node* x = &memory[cnt++]; 105 if(cur == save[idx].size() - 1) x->dir = 0; 106 else x->dir = 1; 107 x->son = 0; 108 x->key = save[idx][cur]; 109 x->next.clear(); 110 rt->next.push_back(x); 111 add(idx, cur+1, x); 112 } 113 114 void bfs() { 115 queue<Node*> q; 116 q.push(rt); 117 while(!q.empty()) { 118 Node* x = q.front(); q.pop(); 119 if(x->next.size() != 0) x->son = 1; 120 for(int i = 0; i < x->next.size(); i++) { 121 q.push(x->next[i]); 122 } 123 } 124 } 125 126 void bfs1() { 127 queue<Node*> q; 128 q.push(rt); 129 while(!q.empty()) { 130 Node* x = q.front(); q.pop(); 131 sort((*x).next.begin(), (*x).next.end(), cmp); 132 for(int i = 0; i < x->next.size(); i++) { 133 q.push(x->next[i]); 134 } 135 } 136 } 137 138 inline void X(int ind) { 139 Rep(i, ind) printf(" "); 140 } 141 142 void dfs(Node* p, int depth) { 143 if(p == rt) { 144 Rep(i, p->next.size()) { 145 cout << p->next[i]->key << endl; 146 dfs(p->next[i], depth+1); 147 } 148 } 149 else { 150 Rep(i, p->next.size()) { 151 X(depth); cout << p->next[i]->key << endl; 152 dfs(p->next[i], depth+1); 153 } 154 } 155 } 156 157 signed main() { 158 // FRead(); 159 int _ = 1; 160 while(gets(in) && strcmp(in, "0") != 0) { 161 save.clear(); 162 cnt = 0; rt = &memory[cnt++]; 163 rt->next.clear(); rt->key = "fuck"; rt->son = 0; rt->dir = 1; 164 gao(); 165 printf("Case %d: ", _++); 166 while(gets(in) && strcmp(in, "0") != 0) gao(); 167 Rep(i, save.size()) add(i, 0, rt); 168 bfs(); bfs1(); 169 dfs(rt, 0); 170 } 171 RT 0; 172 }