题目名称 812. 单词默写
输入输出 engzam.in/out
难度等级 ★☆
时间限制 1000 ms (1 s)
内存限制 128 MB
测试数据 10 简单对比
题目来源 2012-06-14
开放分组 全部用户
提交状态
分类标签
字典树 二分图
通过:49, 提交:196, 通过率:25%
Gravatar+1s 100 0.642 s C++
Gravatar+1s 100 0.653 s C++
Gravatar+1s 100 0.737 s C++
Gravatar+1s 100 0.738 s C++
Gravatarswttc 100 0.826 s C++
Gravatarswttc 100 0.845 s C++
Gravatarhzoi_xx 100 0.925 s C++
Gravatar~玖湫~ 100 1.078 s C++
Gravatar+1s 100 1.151 s C++
GravatarBennettz 100 1.244 s C++
关于 单词默写 的讨论
仰慕程志博的dfs~比我的快排還快~唉,string确实很慢很慢!
GravatarMakazeu
2012-06-18 21:12 1楼
动态指针居然还快一些orz
GravatarHouJikan
2014-09-23 10:13 2楼
太谨慎导致开爆了内存
Gravatar一個人的雨
2015-09-18 14:18 3楼
我算的内存明明不应该有问题的!!!可是为什么会MMMMMMMMMM???
啊啊啊,明明可以一遍过………………
Gravatar浮生随想
2016-11-08 20:39 4楼
就加了一句 if(!at)return 0;
从连WA带T的20分变成AC
GravatarRegnig Etalsnart
2017-10-25 15:20 5楼
Gravataryymxw
2017-10-25 19:46 6楼
数组就是快!!!
(其实是 ** 指针)
Gravatar~玖湫~
2017-11-03 20:56 7楼
数据已加强。
GravatarFisher.
2017-11-07 17:29 8楼
orz考场acdalao
我这种垃圾只会打暴力
GravatarHyoi_Turkey
2017-11-07 19:31 9楼
mmp,vector的空间和普通数组占用的空间加起来超过空间限制居然报RE。。。搞了2小时。。。
Gravatarswttc
2017-11-07 20:51 10楼
费劲心思写快读主函数外置并将数组下标访问改为指针访问结果就是冲不到榜首
Gravatar+1s
2018-07-10 17:01 11楼

812. 单词默写

★☆   输入文件:engzam.in   输出文件:engzam.out   简单对比
时间限制:1 s   内存限制:128 MB

【问题描述】

  小D前一段日子刚刚参加了一次非常苛刻的英语考试。
考试不仅包括了听力、选择、填空等基本题型,还包括了一种特殊的单词默写题。这类题目都是按照以下形式给出的:
在本学期你所学的所有前缀是B的单词中,在课本中出现次数不少于L的有多少个。
例如小D这个学期只学过三个单词a、ab、bc,它们出现的次数分别是1、2、3;若给出询问(B = a,L = 2),那么前缀为a的单词一共有两个,是a和ab,其中频率不少于2的只有一个,是ab。
这个学期小D学过的单词非常多,而考试给出的这类询问也非常多。这么困难的任务小D当然不可能解决,于是这个问题被交给了你。

【输入文件】

    输入文件第一行包含两个用空格隔开的整数N、M,分别表示小D本学期学过的单词数和考试中出现的询问数。
    接下来N行,每行包含用空格隔开的一个单词A和一个整数P,描述小D本学期学过的一个单词A以及其出现的次数P。
接下来M行,每行包含用空格隔开的一个单词B和一个整数L,描述考试中给出的一个询问。
你可以假定所有单词均由小写字母组成,且长度不超过10。

【输出文件】

输出文件一共包含M行。
对于每个考试的询问输出一行一个整数,表示该问题的答案。

【样例输入】

3 3
a 1
ab 2
bc 3
a 2
a 1
a 3

【样例输出】

1
2
0

【样例说明】

    前缀为a的单词一共有两个,是a和ab,出现次数分别为1和2。

【评分标准】

    本题包含10个测试点,对于每个测试点,如果你的输出和标准输出完全一样则得到该测试点的全部分数,否则得0分。

【数据规模】

对于50%的测试数据,满足N、M ≤ 1 000
对于100%的测试数据,满足N、M ≤ 100 000,P、L ≤ 100 000

注:数据已加强。