NOJ 1121 Message Flood (Trie树 或者 map)

2024-03-20 14:32
文章标签 map message trie noj flood 1121

本文主要是介绍NOJ 1121 Message Flood (Trie树 或者 map),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!


Message Flood

时间限制(普通/Java): 2000MS/6000MS         运行内存限制:65536KByte
总提交:399          测试通过:105

题目描述

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 andcase 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.


输入

 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 pre line . After that there are m lines of alphabetic string s ,which are the names of message senders .
 The input is terminated by n=0.

输出

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

样例输入

5 3
Inkfish
Henry
Carp
Max
Jericho
Carp
Max
Carp
0

样例输出

3

题目来源

第九届中山大学程序设计竞赛预选题


题目链接:http://acm.njupt.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1121


题目大意:一个人要传消息给他的n个朋友,其中已经有m个(可能重复)收到了,问这个人还要发多少消息


题目分析:如果用trie树做注意红色标出的意思是不分大小写,建立26叉字典树,基本建树插入,ans初始化为n,查找的时候找到一个将其从字典中删除即可,用set + string做比较费时,但是代码很好写,很好理解


Trie树:

#include <cstdio>
#include <cstring>
char s[11];
int cnt, ans;int change(char ch)
{if(ch <= 'Z' && ch >= 'A')return ch - 'A';if(ch <= 'z' && ch >= 'a')return ch - 'a'; 
}struct node
{   node *next[26];bool end;node(){memset(next, 0, sizeof(next));end = false;}
};void Insert(node *p, char *s)
{for(int i = 0; s[i] != '\0'; i++){int idx = change(s[i]);if(p -> next[idx] == NULL)p -> next[idx] = new node();p = p -> next[idx];}p -> end = true;
}void Search(node *p, char *s)
{   int i;for(i = 0; s[i] != '\0'; i++){int idx = change(s[i]);if(p -> next[idx] == NULL)return;p = p -> next[idx];}if(p -> end){ans --;p -> end = false;}
}int main()
{int n, m;while(scanf("%d", &n) && n){ans = n;node *root = new node();scanf("%d", &m);for(int i = 0; i < n; i++){scanf("%s", s);Insert(root, s);}for(int i = 0; i < m; i++){scanf("%s", s);Search(root, s);}   printf("%d\n", ans);}
}

set + string:

#include <cstdio>
#include <string>
#include <iostream>
#include <set>
using namespace std;
int main()
{int n, m;string str;while(scanf("%d %d", &n, &m) != EOF && n){set <string> s;for(int i = 0; i < n; i++){cin >> str;for(int j = 0; j < str.length(); j++)str[j] = toupper(str[j]);s.insert(str);}for(int i = 0; i < m; i++){cin >> str;for(int j = 0; j < str.length(); j++)str[j] = toupper(str[j]);set <string> :: iterator it = s.find(str);if(it != s.end())s.erase(str);}cout << s.size() << endl;}
}


这篇关于NOJ 1121 Message Flood (Trie树 或者 map)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/829774

相关文章

Collection List Set Map的区别和联系

Collection List Set Map的区别和联系 这些都代表了Java中的集合,这里主要从其元素是否有序,是否可重复来进行区别记忆,以便恰当地使用,当然还存在同步方面的差异,见上一篇相关文章。 有序否 允许元素重复否 Collection 否 是 List 是 是 Set AbstractSet 否

Map

Map 是 Java 中用于存储键值对的集合接口。以下是对 Map 的详细介绍: 特点 键值对存储:每个元素包含一个键和一个值。 键唯一:键不能重复,但值可以重复。 无序/有序:根据具体实现,键值对的顺序可能无序(如 HashMap)或有序(如 TreeMap、LinkedHashMap)。 主要实现类 HashMap 基于哈希表,无序存储。 允许一个 null 键和多个 null 值。

Java中集合类Set、List和Map的区别

Java中的集合包括三大类,它们是Set、List和Map,它们都处于java.util包中,Set、List和Map都是接口,它们有各自的实现类。Set的实现类主要有HashSet和TreeSet,List的实现类主要有ArrayList,Map的实现类主要有HashMap和TreeMap。那么它们有什么区别呢? Set中的对象不按特定方式排序,并且没有重复对象。但它的有些实现类能对集合中的对

C++数据结构重要知识点(5)(哈希表、unordered_map和unordered_set封装)

1.哈希思想和哈希表 (1)哈希思想和哈希表的区别 哈希(散列、hash)是一种映射思想,本质上是值和值建立映射关系,key-value就使用了这种思想。哈希表(散列表,数据结构),主要功能是值和存储位置建立映射关系,它通过key-value模型中的key来定位数组的下标,将value存进该位置。 哈希思想和哈希表数据结构这两个概念要分清,哈希是哈希表的核心思想。 (2)unordered

【C++STL(十四)】一个哈希桶简单模拟实现unordered_map/set

目录 前言 一、改造哈希桶 改造结点类 改造主体  模板参数改造  迭代器(重点) 改造完整哈希桶 unordered_map模拟实现 unordered_set模拟实现 前言 前面的文章都有说unordered_map/set的底层结构就是哈希表,严格来说是哈希桶,那么接下来我们就尝试使用同一个哈希桶来模拟实现一下。整体的逻辑和一棵红黑树封装map/set类似,所以

Java中Map取值转String Null值处理

Map<String, Object> 直接取值转String String value = (String)map.get("key") 当map.get(“key”)为Null值时会报错。 使用String类的valueOf静态方法可以解决这个问题 String value = String.valueOf(map.get("key"))

Creating OpenAI Gym Environment from Map Data

题意:从地图数据创建 OpenAI Gym 环境 问题背景: I am just starting out with reinforcement learning and trying to create a custom environment with OpenAI gym. However, I am stumped with trying to create an enviro

【Java编程的逻辑】Map和Set

HashMap Map有键和值的概念。一个键映射到一个值,Map按照键存储和访问值,键不能重复。 HashMap实现了Map接口。 基本原理 HashMap的基本实现原理:内部有一个哈希表,即数组table,每个元素table[i]指向一个单向链表,根据键存取值,用键算出hash值,取模得到数组中的索引位置index,然后操作table[index]指向的单向链表。 存取的时候依据键的

RDD的map和flatMap

在 Apache Spark 中,map 和 flatMap 是 RDD(弹性分布式数据集)中最常用的转换操作之一。 map 假设你有一个包含整数的 RDD,你想要计算每个元素的平方。 from pyspark import SparkContextsc = SparkContext(appName="MapExample")# 创建一个包含整数的 RDDnumbers = sc.para

【python 多进程传参】pool.map() 函数传多参数

无意中发现了一个巨牛的人工智能教程,忍不住分享一下给大家。教程不仅是零基础,通俗易懂,而且非常风趣幽默,像看小说一样!觉得太牛了,所以分享给大家。点这里可以跳转到教程。人工智能教程 一、背景介绍 相信很多人都用过,pool.map()函数,这个函数,有两个参数可以传,第一个参数传的是函数,第二个参数传的是数据列表。 那么怎么在第二个数据列表,多传几个参数呢,方法是通过对有多个参数的方法进行封装