• <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>
            隨筆 - 6, 文章 - 0, 評論 - 24, 引用 - 0
            數據加載中……

            Trie在程序設計競賽中的應用

            Trie在程序設計競賽中的應用

            題目

             Message Flood
            Problem 

            Well, how do you feel about mobile phone? Your answer would probably be something like that “It’s so convenient and benefits people a lot”. However, if you ask Merlin this question on the New Year’s Eve, he will definitely answer “What a trouble! I have to keep my fingers moving on the phone the whole night, because I have so many greeting messages to send! ”. Yes, Merlin has such a long name list of his friends, and he would like to send a greeting message to each of them. What’s worse, Merlin has another long name list of senders that have sent message to him, and he doesn’t want to send another message to bother them (Merlin is so polite that he always replies each message he receives immediately). So, before he begins to send messages, he needs to figure to how many friends are left to be sent. Please write a program to help him. 

            Here is something that you should note. First, Merlin’s friend list is not ordered, and each name is alphabetic strings and case insensitive. These names are guaranteed to be not duplicated. Second, some senders may send more than one message to Merlin, therefore the sender list may be duplicated. Third, Merlin is known by so many people, that’s why some message senders are even not included in his friend list.

            Input

            There are multiple test cases. In each case, at the first line there are two numbers n and m (1<=n, m<=20000), which is the number of friends and the number of messages he has received. And then there are n lines of alphabetic strings (the length of each will be less than 10), indicating the names of Merlin’s friends, one per line. After that there are m lines of alphabetic strings, which are the names of message senders.

             The input is terminated by n=0. 

            Output

            For each case, print one integer in one line which indicates the number of left friends he must send. 

            Sample Input
            5 3
            Inkfish
            Henry
            Carp
            Max
            Jericho
            Carp
            Max
            Carp
            0
            Sample Output
            3


            代碼

             1#include <iostream>
             2#include <string>
             3#include "trie.h"
             4
             5struct Index {
             6    int operator[](char ch) {
             7        if (isupper(ch)) return ch - 'A';
             8        return ch - 'a';
             9    }

            10}
            ;
            11
            12int n, m;
            13std::string name;
            14trie<26, Index> name_set;
            15
            16int main() {
            17    while (std::cin>>n>>&& n) {
            18        name_set.clear();
            19        for (int i = 0; i < n; ++i) {
            20            std::cin>>name;
            21            name_set.insert(name.begin(), name.end());
            22        }

            23        int count = 0;
            24        while (m--{
            25            std::cin>>name;
            26            count += name_set.erase(name.begin(), name.end());
            27        }

            28        printf("%d\n", n - count);
            29    }

            30}

            31


            測試數據

            輸入數據
            輸出數據

            參考資料
            郭嵩山、張子臻、王磊、湯振東著  國際大學生程序設計競賽例題解(五)  電子工業出版社

            posted on 2009-03-28 11:45 yuyang7 閱讀(1711) 評論(0)  編輯 收藏 引用 所屬分類: 程序設計競賽

            无码任你躁久久久久久老妇App| 亚洲精品WWW久久久久久| 久久亚洲sm情趣捆绑调教 | 无码八A片人妻少妇久久| 亚洲国产另类久久久精品| 久久久久亚洲AV无码永不| 国产精品永久久久久久久久久| 久久久久18| 97久久超碰国产精品2021| 久久精品国产精品亚洲人人| 99精品久久久久久久婷婷 | 久久久久亚洲AV无码去区首| 狠狠色婷婷久久综合频道日韩| 久久精品国产免费| 日韩人妻无码一区二区三区久久 | 7777久久亚洲中文字幕| 四虎影视久久久免费观看| 国产精品久久自在自线观看| 亚洲欧洲精品成人久久奇米网| 精品午夜久久福利大片| 亚洲精品乱码久久久久久蜜桃不卡| av无码久久久久不卡免费网站| 午夜福利91久久福利| 88久久精品无码一区二区毛片 | 中文字幕乱码人妻无码久久| 久久精品国产欧美日韩| 99久久精品影院老鸭窝| 久久久亚洲欧洲日产国码aⅴ| 偷窥少妇久久久久久久久| 亚洲国产成人精品91久久久 | 久久五月精品中文字幕| 久久精品九九亚洲精品天堂 | 久久成人精品| 久久久国产精华液| 久久青青草原精品国产不卡| 国产免费久久精品丫丫| 免费观看久久精彩视频| 亚洲国产成人久久综合碰碰动漫3d| 国产亚洲欧美精品久久久| 国产成人精品久久二区二区| 久久国产亚洲精品无码|