洛谷 P3879 阅读理解

这篇具有很好参考价值的文章主要介绍了洛谷 P3879 阅读理解。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目描述

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

输入格式

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

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

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

输出格式

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

输入输出样例

输入 #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

输出 #1

1 2 3
2 3
1 2
3
2

说明/提示

对于 30% 的数据, 1≤M≤10^3 。

对于 100% 的数据,1≤M≤10^4,1≤N≤10^3 。

每篇短文长度(含相邻单词之间的空格)5×10^3 字符,每个单词长度 ≤20 字符。

每个测试点时限 2 秒。

解题思路

本题可以采用链地址法解决哈希冲突,采用二维结构体储存哈希值,结构体竖直方向为N篇阅读理解,水平方向为每个单词字符串转换数字映射到的位置采用链表储存,对于m个单词在n篇阅读理解里面查找就是通过下标查找,判断能否找到。

AC代码文章来源地址https://www.toymoban.com/news/detail-834824.html

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct linknode {//结构体存储n篇阅读理解
	char ss[21];
	struct linknode* next;
}a[1001][1997], * p, * tt, * q;
int n, m, d;
char s[21];
int haxi()//求对应的关键字
{
	int k = strlen(s), ans = 0;
	for (int i = 0; i < k; i++)
		ans = (ans * 26 + s[i]) % 1997;
	return ans;
}
int main()
{
	int i;
	scanf("%d", &n);
	for (i = 1; i <= n; i++)//初始化
		for (int j = 0; j < 1997; j++)
			a[i][j].next = NULL;
	for (int i = 1; i <= n; i++)//输入单词并储存在结构体中
	{
		scanf("%d", &d);
		while (d--)
		{
			scanf("%s", s);
			int t = haxi();
			q = (struct linknode*)malloc(sizeof(struct linknode));
			strcpy(q->ss, s);
			//头插法
			q->next = a[i][t].next; a[i][t].next = q;
		}
	}
	scanf("%d", &m);
	while (m--)
	{
		scanf("%s", s);
		int t = haxi();//找到单词对应的下标
		for (i = 1; i <= n; i++)
		{
			p = a[i][t].next;
			while (p != NULL)
			{
				if (strcmp(p->ss, s) == 0)//如果找到这个单词
				{
					printf("%d ", i);
					break;
				}
				p = p->next;
			}
		}
		printf("\n");
	}
	for (i = 1; i <= n; i++)//释放内存
		for (int j = 0; j < 1997; j++)
		{
			p = a[i][j].next;
			while (p != NULL)
			{
				tt = p;
				p = p->next;
				free(tt);
			}
		}
	return 0;
}

到了这里,关于洛谷 P3879 阅读理解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【论文阅读笔记】Mamba模型代码理解

    官方实现:state-spaces/mamba (github.com) 最简化实现:johnma2006/mamba-minimal: Simple, minimal implementation of the Mamba SSM in one file of PyTorch. (github.com) 直接实现:alxndrTL/mamba.py: A simple and efficient Mamba implementation in PyTorch and MLX. (github.com) 官方代码做了大量优化,目录层级较多,对于理解模型含

    2024年04月13日
    浏览(70)
  • k8s(Kubernetes)中yaml文件快速阅读理解

    简言         k8s yaml中文件内容一般有kind类型之分,每种类型有不同的功能(一般用---符号隔开) 常见的kind类型:         (1)Endpoints:Endpoints可以把外部的链接到k8s系统中(可以理解为引用外部资源,如将一个外部mysql连接到k8s中)         (2)Service:部署一

    2024年02月21日
    浏览(46)
  • Vison Pro/Unity/Poly Spatial开发笔记整理【三】(Poly Spatial阅读理解)

    名称 状态 描述 类型 PolySpatialSettings 详细 用于配置多边形空间相关参数的设置类。 ScriptableObject MaterialSwapSet 详细 用于在不同材质之间进行切换的集合。 ScriptableObject PolySpatialObjectUtils 详细 包含多种对象操作工具的实用工具类。 class PolySpatialShaderGlobals 详细 提供多边形空间

    2024年04月29日
    浏览(33)
  • 【安全】 阅读 RFC6749 及理解 Oauth2.0 下的授权码模式

    OAuth 2.0 规范来自 RFC6749。看了《Spring 微服务实战》对OAuth 2.0 的介绍后还是觉得存在一些翻译的问题。现在结合 RFC6749 一起重新梳理下。 1.1. 一个场景: o-stock 实现获取微信头像。 结论性的东西全部来自于该文档。 本文是主要以获取微信头像作为模型,对 Oauth2.0 知识点进行

    2024年02月11日
    浏览(44)
  • 自然语言处理实战项目11-阅读理解项目的数据处理与训练详细讲解,实验结果与分析

    大家好,我是微学AI,今天给大家介绍一下自然语言处理实战项目11-阅读理解项目的数据处理与训练详细讲解,阅读理解任务目标是让计算机从给定的文章中理解并回答问题。为了完成这个任务,我们需要对给定的数据进行处理和训练。该任务是一个涉及多个步骤和技术的复

    2024年02月09日
    浏览(57)
  • 《论文阅读》具有特殊Token和轮级注意力的层级对话理解 ICLR 2023

    前言 你是否也对于理解论文存在困惑? 你是否也像我之前搜索论文解读,得到只是中文翻译的解读后感到失望? 小白如何从零读懂论文?和我一起来探索吧! 今天为大家带来的是《HIERARCHICAL DIALOGUE UNDERSTANDING WITH SPECIAL TOKENS AND TURN-LEVEL ATTENTION》 出版:ICLR 时间ÿ

    2024年02月15日
    浏览(48)
  • 《SimpleNet: A Simple Network for Image Anomaly Detection and Localization》论文阅读理解

    将预训练特征转换为面向目标的特征有助于避免图像局部偏见的出现; 在特征空间中生成合成异常更有效,因为缺陷在图像空间中可能没有太多共性存在; 一个简单的鉴别器是非常有效和实用的; 提出了一种简单且容易应用的网络(SimpleNet),用于检测和定位异常; 在MV

    2024年02月08日
    浏览(63)
  • 《SQUID: Deep Feature In-Painting for Unsupervised Anomaly Detection》论文阅读理解

    对身体器官的射线扫描结果图片中展示了详细的结构化信息,充分利用这种身体各个部分之间的结构化信息,对检测出身体存在的异常非常重要; 提出了使用空间感知队列来进行图片绘制和检测图片中存在的异常的方法(称为SQUID); 在两个胸部X射线基准数据集上,本文所

    2024年02月15日
    浏览(42)
  • 论文阅读—2023.7.13:遥感图像语义分割空间全局上下文信息网络(主要为unet网络以及改unet)附加个人理解与代码解析

    前期看的文章大部分都是深度学习原理含量多一点,一直在纠结怎么改模型,论文看的很吃力,看一篇忘一篇,总感觉摸不到方向。想到自己是遥感专业,所以还是回归遥感影像去谈深度学习,回归问题,再想着用什么方法解决问题。 1、易丢失空间信息 在 Decoder 阶段输出多

    2024年02月16日
    浏览(46)
  • 230530-论文整理-课题组2

    对这些研究有点兴趣颇微。 我们定制了一个标准的FewDR数据集和评估协议,用于少量密集的检索。该数据集是在维基百科语料库上构建的,包含41,420个样本,有60个细粒度的类别。 具体内容上,和其他的dense retrieval方法,没有感觉到有太大的不同。 传统上, 大部分seq2seq任务

    2024年02月07日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包