A 简单的模拟 ,不过我写的很麻烦
Problem
On Unix computers, data is stored in directories. There is one root directory, and this might have several directories contained inside of it, each with different names. These directories might have even more directories contained inside of them, and so on.
A directory is uniquely identified by its name and its parent directory (the directory it is directly contained in). This is usually encoded in a path, which consists of several parts each preceded by a forward slash ('/'). The final part is the name of the directory, and everything else gives the path of its parent directory. For example, consider the path:
/home/gcj/finals
This refers to the directory with name "finals" in the directory described by "/home/gcj", which in turn refers to the directory with name "gcj" in the directory described by the path "/home". In this path, there is only one part, which means it refers to the directory with the name "home" in the root directory.
To create a directory, you can use the mkdir command. You specify a path, and thenmkdir will create the directory described by that path, but only if the parent directory already exists. For example, if you wanted to create the "/home/gcj/finals" and "/home/gcj/quals" directories from scratch, you would need four commands:
mkdir /home
mkdir /home/gcj
mkdir /home/gcj/finals
mkdir /home/gcj/quals
Given the full set of directories already existing on your computer, and a set of new directories you want to create if they do not already exist, how many mkdir commands do you need to use?
Input
The first line of the input gives the number of test cases, T. T test cases follow. Each case begins with a line containing two integers N and M, separated by a space.
The next N lines each give the path of one directory that already exists on your computer. This list will include every directory already on your computer other than the root directory. (The root directory is on every computer, so there is no need to list it explicitly.)
The next M lines each give the path of one directory that you want to create.
Each of the paths in the input is formatted as in the problem statement above. Specifically, a path consists of one or more lower-case alpha-numeric strings (i.e., strings containing only the symbols 'a'-'z' and '0'-'9'), each preceded by a single forward slash. These alpha-numeric strings are never empty.
Output
For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the number of mkdir you need.
Limits
1 ≤ T ≤ 100.
No path will have more than 100 characters in it.
No path will appear twice in the list of directories already on your computer, or in the list of directories you wish to create. A path may appear once in both lists however. (See example case #2 below).
If a directory is listed as being on your computer, then its parent directory will also be listed, unless the parent is the root directory.
The input file will be no longer than 100,000 bytes in total.
Small dataset
0 ≤ N ≤ 10.
1 ≤ M ≤ 10.
Large dataset
0 ≤ N ≤ 100.
1 ≤ M ≤ 100.
Sample
Input
Output
3
0 2
/home/gcj/finals
/home/gcj/quals
2 1
/chicken
/chicken/egg
/chicken
1 3
/a
/a/b
/a/c
/b/b
Gluk的解法:
set <string> S;
REP (i, n)
{
string s;
cin >> s;
S.insert(s);//已有的路径用set表示
}
int res =0 ;
REP (i, m)
{
string s;
cin >> s;
vector <string> ss;
REP (j, s.size())
if(s[j] == '/')
s[j] = ' ';//用空格替换’/’，然后使用istringstream分隔各级目录
istringstream iss (s);
while (iss >> s) {
ss.pb (s);
}
s = "";
REP (i, ss.size ())
{
s = s+"/"+ss[i];
if (S.find(s) == S.end())//依次加入各级目录，/a /a/b /a/b/c 增加递增的所有目录
{
res ++;
S.insert(s);
}
}
}题目中的这一句
If a directory is listed as being on your computer, then its parent directory will also be listed, unless the parent is the root directory.
告诉我们如果/a/b被list存在，那么/a也一定被list出来了 ，所以上面代码可以不去分隔处理已经给出的目录
yuhch123的解法
struct node {
map <string, node *> sons;//每个节点，用map实现儿子节点
};
node *root;//一个根节点
int T;
int N, M;
char tmp[100005];
int ans = 0;
void insert(node *cnt, char *tmp) {//在节点cnt处，插入tmp子树
int i;
if (tmp[0] == 0)//为空则返回
return;
assert(tmp[0] == '/');
string str;
for (i = 1; tmp[i] != '/' && tmp[i] != 0; i ++)//第一层
str += tmp[i];
if (cnt -> sons.find(str) == cnt -> sons.end()) {//如果没有这子树，则创建子树
ans ++;//需要一次mkdir
struct node *tmp2 = new node();
cnt -> sons[str] = tmp2;
}
insert(cnt -> sons[str], tmp + i);// 递归创建子树
}
int main() {
int i;
int Case = 1;
scanf("%d", &T);
while (T --) {
scanf("%d%d", &N, &M);
root = new node();
for (i = 0; i < N; i ++) {
scanf("%s", tmp);
insert(root, tmp);
}
ans = 0;
for (i = 0; i < M; i ++) {
scanf("%s", tmp);
insert(root, tmp);
}
printf("Case #%d: %d\n", Case ++, ans);
}
return 0;
}neal.wu的解法
vector <string> parse (string s)
{
vector <string> v;
string next = "";
for (int i = 0; i < (int) s.length (); i++)
{
next += s [i];
if (i + 1 == (int) s.length () || s [i + 1] == '/')
{
v.push_back (next);
next = "";
}
}
return v;
}
set <string> direc;
int insert (vector <string> v)
{
int count = 0;
string s = "";
for (int i = 0; i < (int) v.size (); i++)
{
s += v [i];
count += direc.insert (s).second ? 1 : 0; //set返回一个pair<iterator,bool> bool指示插入是否成功 }
return count;
}
int main ()
{
freopen("d:\\input.txt","r",stdin);
for (scanf ("%d", &T); TC <= T; TC++)
{
scanf ("%d %d", &N, &M);
direc.clear ();
int make = 0;
char str [1000];
for (int i = 0; i < N; i++)
{
do gets (str); while (strlen (str) == 0);//do gets 过滤回车空字符串
insert (parse (str));
}
for (int i = 0; i < M; i++)
{
do gets (str); while (strlen (str) == 0);
make += insert (parse (str));
}
printf ("Case #%d: %d\n", TC, make);
}
//system ("pause");
return 0;
}ploh的解法:
int main(void)
{freopen("d:\\input.txt","r",stdin);
int T; cin >> T;
for (int t = 1; t <= T; t++) {
int ans = 0;
set <string> have, want;
int N, M;
cin >> N >> M;
for (int i = 0; i < N; i++) {
string path; cin >> path;
have.insert(path);
}
for (int i = 0; i < M; i++) {//用一个set保存所有需要加入的
string path; cin >> path;
want.insert(path);
for (int j = 1; j < path.length(); j++)
if (path[j] == '/')
want.insert(path.substr(0, j));
}
for (set <string>::iterator it = want.begin(); it != want.end(); it++)//遍历所有需要加入的，然后看是否存在
if (!have.count(*it))
ans++;
printf("Case #%d: %d\n", t, ans);
}
}