和CF2A一样，不过多了map的嵌套。

题目描述

英语老师留了N篇阅读理解作业，但是每篇英文短文都有很多生词需要查字典，为了节约时间，现在要做个统计，算一算某些生词都在哪几篇短文中出现过。

输入输出格式

输入格式

第一行为整数N，表示短文篇数，其中每篇短文只含空格和小写字母。

按下来的N行，每行描述一篇短文。每行的开头是一个整数L，表示这篇短文由L个单词组成。接下来是L个单词，单词之间用一个空格分隔。

然后为一个整数M，表示要做几次询问。后面有M行，每行表示一个要统计的生词。

输出格式

对于每个生词输出一行，统计其在哪几篇短文中出现过，并按从小到大输出短文的序号，序号不应有重复，序号之间用一个空格隔开（注意第一个序号的前面和最后一个序号的后面不应有空格）。如果该单词一直没出现过，则输出一个空行。

INPUT & OUTPUT’s examples

Input’s eg #1

3
9 you are a good boy ha ha o yeah
13 o my god you like bleach naruto one piece and so do i
11 but i do not think you will get all the points
5
you
i
o
all
naruto

Output’s eg #1

说明

对于30%的数据，$1 \leq M \leq 1,000$

对于100%的数据，$1 \leq M \leq 10,000，1 \leq N \leq 1000$

每篇短文长度（含相邻单词之间的空格） $\leq 5,000$ 字符，每个单词长度 $\leq 20$ 字符

每个测试点时限2秒。

分析

Herself32的提交记录。

本题又是一道经典的map映射练手。

我们在CF2A的题解中已经讲解了map映射的简单使用方法。

但在这道题中，某个单词可能在很多个句子中出现，所以不能单纯的使用int。

我们开一个map<string,vector<int> >来存储对应单词在哪几个句子中出现。

代码

/* Headers */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<iostream>
#include<set>
#include<cctype>
using namespace std;
namespace FastIO{
    const int BUFSIZE=1<<20;
    char ibuf[BUFSIZE],*is=ibuf,*its=ibuf;
    char obuf[BUFSIZE],*os=obuf,*ot=obuf+BUFSIZE;
    inline char getch(){
        if(is==its)
            its=(is=ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is==its)?EOF:*is++;
    }
    inline int getint(){
        int res=0,neg=0,ch=getch();
        while(!(isdigit(ch)||ch=='-')&&ch!=EOF)
            ch=getch();
        if(ch=='-'){
            neg=1;ch=getch();
        }
        while(isdigit(ch)){
            res=(res<<3)+(res<<1)+(ch-'0');
            ch=getch();
        }
        return neg?-res:res;
    }
    inline void flush(){
        fwrite(obuf,1,os-obuf,stdout);
        os=obuf;
    }
    inline void putch(char ch){
        *os++=ch;
        if(os==ot)	flush();
    }
    inline void putint(int res){
        static char q[10];
        if(res==0)	putch('0');
        else if(res<0){
            putch('-');
            res=-res;
        } 
        int top=0;
        while(res){
            q[top++]=res%10+'0';
            res/=10;
        }
        while(top--)	putch(q[top]);
    }
} 
using namespace FastIO;
/* definitions */
map<string,vector<int> >upon;
int n,m;
string s;
/* functions */
inline void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int words;
		scanf("%d",&words);
		for(int j=1;j<=words;j++){
			cin>>s;
			upon[s].push_back(i);
		}
	}
}
inline void search(){
	scanf("%d",&m);
	for(int i=1;i<=m;i++){
		cin>>s;
		int Size=upon[s].size();
		for(int j=0;j<Size;++j){
			if(j!=0&&upon[s][j]==upon[s][j-1])continue;
			cout<<upon[s][j]<<" ";
		}
		cout<<endl;
	}
}
int main(int argc,char *argv[]){
	init();
	search();
	return 0;
}

洛谷P3879「TJOI2010」题解