首页 > 其他分享 >洛谷题单指南-集合-P3879 [TJOI2010] 阅读理解

洛谷题单指南-集合-P3879 [TJOI2010] 阅读理解

时间:2024-03-26 16:46:29浏览次数:26  
标签:单词 倒排 int 洛谷题 cin P3879 TJOI2010 文章

原题链接:https://www.luogu.com.cn/problem/P3879

题意解读:此题本质上是计算倒排索引,所谓倒排索引,即不是通过文章来找单词,而是通过单词来找文章。

解题思路:

要建立单词和文章之间的关系,一个单词对应多篇文章,且要按照文章编号排序,可以使用如下数据结构:

map<string, set<int>> h;

只需要遍历每一篇文章,对每一篇文章遍历每一个单词,将单词w对应的文章号i存入h[w].insert(i)即可建立倒排索引。

100分代码:

#include <bits/stdc++.h>
using namespace std;

map<string, set<int>> h;
int n, l, m;
string w;

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> l;
        while(l--)
        {
            cin >> w;
            h[w].insert(i); //将w单词对应的文章号i存入h[w]这个set<int>中
        }
    }

    cin >> m;
    while(m--)
    {
        cin >> w;
        for(auto i : h[w]) cout << i << " "; //查找单词w对应的文章号并输出
        cout << endl;
    }
    
    return 0;
}

 

标签:单词,倒排,int,洛谷题,cin,P3879,TJOI2010,文章
From: https://www.cnblogs.com/jcwy/p/18097020

相关文章

  • 洛谷题单指南-集合-P1955 [NOI2015] 程序自动分析
    原题链接:https://www.luogu.com.cn/problem/P1955题意解读:要判断约数条件是否可以同时满足,主要是要判断不相等的情况。解题思路:对于相等的条件,直接进行集合合并即可;对于不相等的条件,判断两者是否属于同一个集合,如果形成矛盾,则条件不能成立。由于i,j的范围至10^9,定义并查集如果......
  • 洛谷题单指南-集合-P1892 [BOI2003] 团伙
    原题链接:https://www.luogu.com.cn/problem/P1892题意解读:此题与关押罪犯问题非常像,本质上就是要合并所有的朋友。解题思路:首先,初始化并查集;对于每一对人的关系,如果是朋友,直接进行合并;如果是敌人,先查看双方之前是否有记录其他敌人,如果有,则将一方与另一方的敌人进行合并,如果没......
  • 洛谷题单指南-集合-P1621 集合
    原题链接:https://www.luogu.com.cn/problem/P1621题意解读:a~b之间的数,把有大于等于p的公共质因数的数进行合并作为一个集合,求一共有多少个集合。解题思路:要进行集合合并、统计集合数,可以使用并查集,有两种做法:1、暴力法80%的数据在1000范围内,因此通过双重循环枚举,判断两个数的......
  • 洛谷题单算法1-6二分查找与二分答案
    代码仅供参考,不足之处望理解。P2249【深基13.例1】查找#include<iostream>usingnamespacestd;constintN=1e6+5;intn,m,a[N];intmain(){ios::sync_with_stdio(false);//输入cin>>n>>m;for(inti=1;i<=n;i++)cin>>a[i];for(inti=1......
  • C语言:洛谷题目分享(4)小书童--凯撒密码和笨小猴
    目录1.前言2.俩道题目1.小书童--凯撒密码1.题目背景2.题目描述3.输入格式4.输出格式5.题解2.笨小猴1.题目描述2.输入格式3.输出格式4.题解3.小结1.前言哈喽大家好啊,今天我继续为大家分享洛谷题单的俩道题目,请大家多多支持喔~2.俩道题目1.小书童--凯撒密码......
  • 洛谷题单指南-集合-P1525 [NOIP2010 提高组] 关押罪犯
    原题链接:https://www.luogu.com.cn/problem/P1525题意解读:有很多罪犯,要关到两座监狱,有一些罪犯之间有仇,并且可以量化出仇恨值,如果关在一起就会冲突,造成的影响就是仇恨值,要使得造成的影响最小,如果可以完全不起冲突,输出0。解题思路:首先,要让冲突影响最小化,显然应该把仇恨大的罪犯......
  • 洛谷题单指南-集合-P1102 A-B 数对
    原题链接:https://www.luogu.com.cn/problem/P1102题意解读:前文https://www.cnblogs.com/jcwy/p/18043197介绍了二分和双指针的做法,本文介绍hash的做法。解题思路:定义map<int,int>h,保存每个数+c出现的个数同样,先将所有数由小到大哦排序遍历每一个数x,答案累加ans+=h[x]然......
  • 洛谷题单指南-集合-P5266 【深基17.例6】学籍管理
    原题链接:https://www.luogu.com.cn/problem/P5266题意解读:本题考察map的应用。解题思路:直接使用map即可解题。100分代码:#include<bits/stdc++.h>usingnamespacestd;map<string,int>h;stringname;intn,op,score;intmain(){cin>>n;while(n--)......
  • 洛谷题单指南-集合-P5250 【深基17.例5】木材仓库
    原题链接:https://www.luogu.com.cn/problem/P5250题意解读:根据题目要求,需要一种数据结构,支持去重、排序、logN的查找,set是最合适的。解题思路:先回顾一下set的关键操作:设set<int>s;1、添加:s.insert(x)2、查询个数:s.count(x)3、查找第一个>=x的元素,返回迭代器:set<int>::iter......
  • 洛谷题单指南-集合-P3370 【模板】字符串哈希
    原题链接:https://www.luogu.com.cn/problem/P3370题意解读:本题要求理解哈希的原理,自行建立哈希表解题,如果直接使用map,就不推荐。解题思路:先介绍哈希的原理1、什么是哈希?什么是哈希表?先从一个问题出发:给定不超过105个整数(取值1~109),要统计不重复整数的数量。首先,如果取值范围......