洛谷P3879 [TJOI2010] 阅读理解 题解
题意:
英语老师留了 \(N\) 篇阅读理解作业,但是每篇英文短文都有很多生词需要查字典,为了节约时间,现在要做个统计,算一算某些生词都在哪几篇短文中出现过。
第一行为整数 \(N\) ,表示短文篇数,其中每篇短文只含空格和小写字母。
按下来的 \(N\) 行,每行描述一篇短文。每行的开头是一个整数 \(L\) ,表示这篇短文由 \(L\) 个单词组成。接下来是 \(L\) 个单词,单词之间用一个空格分隔。
然后为一个整数 \(M\) ,表示要做几次询问。后面有 \(M\) 行,每行表示一个要统计的生词。
对于 \(100\%\) 的数据,\(1\le M\le 10^4\),\(1\le N\le 10^3\) 。
每篇短文长度(含相邻单词之间的空格)\(\le 5\times 10^3\) 字符,每个单词长度 \(\le 20\) 字符。
要写 \(\tt{trie}\) 也不是不行。但是懒。
直接用 \(\tt{unordered\_map+vector}\) 水过
跑的还蛮快。注意要去重(不想用set,常数太大)
时间复杂度 \(O(\sum |s_i|\times m)\)
代码:
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
#include <unordered_map>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(5e3+15)
int n,Q;
string s;
int vis[N];
unordered_map<string,vector<int> >mp;
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cin >> n;
for(int i=1,x; i<=n; i++)
{
cin >> x;
for(int j=1; j<=x; j++)
cin >> s,mp[s].push_back(i);
}
cin >> Q;
while(Q--)
{
cin >> s;
for(int i=1; i<=n; i++) vis[i]=0;
for(int i=0; i<mp[s].size(); i++)
if(!vis[mp[s][i]])
{
cout << mp[s][i] << ' ';
vis[mp[s][i]]=1;
}
cout << '\n';
}
return 0;
}