• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            Google code jam Round1B

            Posted on 2010-05-25 23:29 rikisand 閱讀(372) 評論(0)  編輯 收藏 引用

            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);
              }
            }
            
            
            久久精品国产乱子伦| 久久妇女高潮几次MBA| 日韩精品无码久久一区二区三| 亚洲国产日韩欧美综合久久| 99久久精品免费看国产一区二区三区 | 少妇被又大又粗又爽毛片久久黑人| 久久国产精品成人影院| 婷婷久久久亚洲欧洲日产国码AV| 无码精品久久久天天影视 | 美女写真久久影院| 伊人久久一区二区三区无码| 狠狠色丁香久久综合五月| 久久久久黑人强伦姧人妻 | 精品久久久久久国产91| 久久777国产线看观看精品| 亚洲国产精品久久久久久| 久久有码中文字幕| 久久er热视频在这里精品| 国产精品美女久久久网AV| 国产亚洲美女精品久久久2020| 精品综合久久久久久97| 精品久久久久久久| 人妻少妇久久中文字幕| 亚洲国产成人精品女人久久久 | 国产69精品久久久久777| 国产精品久久久久久久人人看| 国产午夜福利精品久久2021| 国产精品一区二区久久精品| 久久精品人成免费| 亚洲AV无码1区2区久久| 99久久国产综合精品成人影院| 国产精品久久新婚兰兰| 久久精品无码一区二区三区日韩 | 99久久免费只有精品国产| 亚洲精品乱码久久久久66| 久久久人妻精品无码一区| 精品久久久噜噜噜久久久 | 国产精品久久久久…| 久久久久久精品无码人妻| 久久99精品国产麻豆蜜芽| 久久国产一区二区|