题解 P3879 【[TJOI2010]阅读理解】
VCarlyle
·
·
题解
前言
\rm{STL}\bold{\text{大法好！}}
思路
现有题解里好像很多用\rm{map}+\rm{vector}再桶去重的……？
既然用了\rm{STL}，为什么不试试\rm{set}呢？
>> 那么$\rm{set}$该怎么用？
和$\rm{STL}$中的其它容器一样，一个所有元素为整型的$\rm{set}$这样定义：
```cpp
set<int> s;
```
另外，$\rm{set}$库中还封装了以下函数：
- `s.insert()` —— 把一个元素插入$\rm{s}$；
- `s.clear()` —— 清空$\rm{s}$；
- `s.empty()` —— 返回$\rm{s}$是否为空；
- `s.size()` —— 返回$\rm{s}$中的元素个数；
- `s.count(int n)` —— 返回元素$\rm{n}$是否在$\rm{s}$中；
- 以及迭代器为基础的`s.begin()`及`end()`。
顺便提一下$\rm{set}$的遍历，和其它容器一样也需要使用一个迭代器（$\rm{iterator}$）：
```cpp
set<int>::iterator iter; //迭代器定义方法
iter=s.begin(); //将迭代器指向s的第一个元素的地址
while(iter!=s.end()) //只要迭代器没有指向s的最后一个元素的地址
{
cout<<*iter; //因为迭代器指向的是元素的地址，所以*iter就是元素的值了
iter++; //使迭代器指向下一个元素的地址
}
```
由于$\rm{set}$中元素是从小到大排序的，所以这段代码将会从小到大把$\rm{s}$中所有元素输出。当然，这个循环也可以用更简短的`for`循环完成——
```cpp
set<int>::iterator iter;
for(iter=s.begin();iter!=s.end();++iter)
cout<<*iter;
```
有了$\rm{set}$这个工具，再加上$\rm{map}$（喜闻乐见？），这道题就迎刃而解了。
---
> 代码实现
首先定义一个$\rm{string}$映射到$\rm{set}$的$\rm{map}$来统计一个单词在哪几篇短文中出现过：
```cpp
map<string,set<int> > m; //两个'>'之间的空格不能少
//这里我把m用作map了，所以题面中的m后面以p代替
```
然后边输入把短文的序号存入$\rm{set}$中：
```cpp
for(int i=1;i<=n;++i)//i为短文序号
{
int l;//单词个数
cin>>l;
for(int j=0;j<l;++j)
{
string s;//单词
cin>>s;
m[s].insert(i);
}
}
```
查询也十分方便：
```cpp
while(p--) //更简短的p次循环
{
string s;
cin>>s;
if(m.count(s)) //如果m中存在元素s
for(iter=m[s].begin();iter!=m[s].end();++iter)
cout<<*iter<<" "; //上面提到的迭代器遍历用法
cout<<endl;
}
```
最后是完整代码：
```cpp
#include<map>
#include<set>
#include<string>
#include<iostream>
using namespace std;
map<string,set<int> > m;
set<int>::iterator iter;
int main()
{
ios::sync_with_stdio(false); //关闭同步，让cin与cout更高效
int n,p;
cin>>n;
for(int i=1;i<=n;++i)
{
int l;
cin>>l;
for(int j=0;j<l;++j)
{
string s;
cin>>s;
m[s].insert(i);
}
}
cin>>p;
while(p--)
{
string s;
cin>>s;
if(m.count(s))
for(iter=m[s].begin();iter!=m[s].end();++iter)
cout<<*iter<<" ";
cout<<endl;
}
return 0;
}
```
$\rm{Done.}
附言
最后拿$\rm{NOIp}$的某公告煞尾吧——
[](http://www.noi.cn/newsview.html?id=229&hash=878FD2&type=6)
$$\mathfrak{-End-}$$