• <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, 評(píng)論 - 24, 引用 - 0
            數(shù)據(jù)加載中……

            Trie在程序設(shè)計(jì)競(jìng)賽中的應(yīng)用

            Trie在程序設(shè)計(jì)競(jìng)賽中的應(yīng)用

            題目

             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


            測(cè)試數(shù)據(jù)

            輸入數(shù)據(jù)
            輸出數(shù)據(jù)

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

            posted on 2009-03-28 11:45 yuyang7 閱讀(1713) 評(píng)論(0)  編輯 收藏 引用 所屬分類: 程序設(shè)計(jì)競(jìng)賽

            欧美一区二区三区久久综合| 国产精品久久久久影院色| 久久夜色tv网站| 一本色道久久88加勒比—综合| 一级做a爰片久久毛片16| 日本久久久久久中文字幕| 精品久久久久久无码中文野结衣| 国产AⅤ精品一区二区三区久久 | 久久久中文字幕日本| 免费精品久久久久久中文字幕| 天堂无码久久综合东京热| 成人资源影音先锋久久资源网| 97精品伊人久久久大香线蕉| 精品综合久久久久久98| 无码国产69精品久久久久网站| 久久久久亚洲AV无码去区首| 久久天天躁狠狠躁夜夜躁2014| 久久这里只有精品18| 人妻丰满?V无码久久不卡| 狠狠色丁香久久综合婷婷| 精品久久久无码人妻中文字幕| 久久国产精品久久| 午夜精品久久久久久99热| 观看 国产综合久久久久鬼色 欧美 亚洲 一区二区| 无码任你躁久久久久久老妇App| 久久本道久久综合伊人| 久久久噜噜噜久久中文字幕色伊伊 | 久久国产精品视频| 99久久免费国产精精品| 中文字幕精品久久| 久久人人爽人人爽人人片av麻烦 | 久久人妻少妇嫩草AV无码专区| 综合人妻久久一区二区精品| 久久免费视频1| 狠狠色狠狠色综合久久| 久久亚洲2019中文字幕| 久久国产精品免费一区| 91精品国产乱码久久久久久| 九九久久自然熟的香蕉图片| 狠狠色丁香婷婷综合久久来| 久久久久久夜精品精品免费啦|