当前位置: 首页 > news >正文

P1540 [NOIP2010 提高组] 机器翻译(模拟)

[NOIP2010 提高组] 机器翻译

题目背景

小晨的电脑上安装了一个机器翻译软件,他经常用这个软件来翻译英语文章。

题目描述

这个翻译软件的原理很简单,它只是从头到尾,依次将每个英文单词用对应的中文含义来替换。对于每个英文单词,软件会先在内存中查找这个单词的中文含义,如果内存中有,软件就会用它进行翻译;如果内存中没有,软件就会在外存中的词典内查找,查出单词的中文含义然后翻译,并将这个单词和译义放入内存,以备后续的查找和翻译。

假设内存中有 M M M 个单元,每单元能存放一个单词和译义。每当软件将一个新单词存入内存前,如果当前内存中已存入的单词数不超过 M − 1 M-1 M1,软件会将新单词存入一个未使用的内存单元;若内存中已存入 M M M 个单词,软件会清空最早进入内存的那个单词,腾出单元来,存放新单词。

假设一篇英语文章的长度为 N N N 个单词。给定这篇待译文章,翻译软件需要去外存查找多少次词典?假设在翻译开始前,内存中没有任何单词。

输入格式

2 2 2 行。每行中两个数之间用一个空格隔开。

第一行为两个正整数 M , N M,N M,N,代表内存容量和文章的长度。

第二行为 N N N 个非负整数,按照文章的顺序,每个数(大小不超过 1000 1000 1000)代表一个英文单词。文章中两个单词是同一个单词,当且仅当它们对应的非负整数相同。

输出格式

一个整数,为软件需要查词典的次数。

样例 #1

样例输入 #1

3 7
1 2 1 5 4 4 1

样例输出 #1

5

提示

样例解释

整个查字典过程如下:每行表示一个单词的翻译,冒号前为本次翻译后的内存状况:

  1. 1:查找单词 1 并调入内存。
  2. 1 2:查找单词 2 并调入内存。
  3. 1 2:在内存中找到单词 1。
  4. 1 2 5:查找单词 5 并调入内存。
  5. 2 5 4:查找单词 4 并调入内存替代单词 1。
  6. 2 5 4:在内存中找到单词 4。
  7. 5 4 1:查找单词 1 并调入内存替代单词 2。

共计查了 5 5 5 次词典。

数据范围

  • 对于 10 % 10\% 10% 的数据有 M = 1 M=1 M=1 N ≤ 5 N \leq 5 N5
  • 对于 100 % 100\% 100% 的数据有 1 ≤ M ≤ 100 1 \leq M \leq 100 1M100 1 ≤ N ≤ 1000 1 \leq N \leq 1000 1N1000

模拟水题

用队列实现替换操作,可以单独开一个桶储存当前有哪些单词(甚至你 O ( n ) O(n) O(n)扫一遍队列也不会超时)

#include<iostream>
#include<cstdio>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
const int N=1e4+23;
int n,m,ans=0;
int a[N],len=0;
int ma[N];
queue<int> q;
int main(){
//	freopen("translate.in","r",stdin);
//	freopen("translate.out","w",stdout);cin>>m>>n;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=n;i++){if(len<m){if(ma[a[i]]==0){ma[a[i]]=1;len++;q.push(a[i]);ans++;}}else {if(ma[a[i]]==0){int tmp=q.front();ma[tmp]=0;ma[a[i]]=1;q.pop();q.push(a[i]);ans++;}}//cout<<len<<" "<<ans<<" "<<a[i]<<endl;}cout<<ans<<endl;
//	fclose(stdin);
//	fclose(stdout);return 0;
}

封面

请添加图片描述

相关文章:

P1540 [NOIP2010 提高组] 机器翻译(模拟)

[NOIP2010 提高组] 机器翻译 题目背景 小晨的电脑上安装了一个机器翻译软件&#xff0c;他经常用这个软件来翻译英语文章。 题目描述 这个翻译软件的原理很简单&#xff0c;它只是从头到尾&#xff0c;依次将每个英文单词用对应的中文含义来替换。对于每个英文单词&#xf…...

生信教程:ABBA-BABA分析之滑动窗口

简介 ABBA BABA 统计&#xff08;也称为 D 统计&#xff09;为偏离严格的分叉进化历史提供了简单而有力的检验。因此&#xff0c;它们经常用于使用基因组规模的 SNP 数据测试基因渗入。 虽然最初开发用于基因渗入的全基因组测试&#xff0c;但它们也可以应用于较小的窗口&#…...

二分答案(求最大值的最小值||求最小值的最大值)

引入 二分答案要建立在二分查找的基础上&#xff0c;在此之前&#xff0c;要知道二分查找的三个模板 模板一 while(l<r) {int mid(lr)>>1;if(check(mid)) rmid;else lmid1; }模板二 while(l<r) {int midlr1>>1;if(check(mid)) lmid;else rmid-1; }模板三…...

思维模型 周期

本系列文章 主要是 分享 思维模型&#xff0c;涉及各个领域&#xff0c;重在提升认知。周期是一个看似极为简单&#xff0c;但背后却蕴藏着大智慧的模型&#xff0c;了解周期&#xff0c;对于了解王朝更替&#xff0c;数学之美&#xff0c;经济运转等都有帮助。 1 周期的应用 …...

从 0 到 1 ,手把手教你编写《消息队列》项目(Java实现) —— 介绍项目/ 需求分析

文章目录 一、消息队列是什么&#xff1f;二、需求分析结构解析功能解析规则解析绑定关系交换机类型消息应答 三、持久化存储四、网络通信提供的API复用TCP连接 五、消息队列概念图 一、消息队列是什么&#xff1f; 消息队列 (Message Queue, MQ)就是将阻塞队列这一数据结构提取…...

Python学习之索引与切片

Python学习之索引与切片 s “0abcdefghijklmnopqrstuvwxyz”&#xff0c;第一个元素‘0’&#xff0c;索引号为0&#xff0c;最后一个元素‘z’&#xff0c;索引号为26 1. s[0]获取索引号为0的元素 2. s[1:3]获取索引号为1的元素&#xff0c;直到但不包括索引号为3的元素。即…...

编程每日一练(多语言实现)基础篇:满足abcd=(ab+cd)^2的数 (增加Go语言实现)

文章目录 一、实例描述二、技术要点三、代码实现3.1 C 语言实现3.2 Python 语言实现3.3 Java 语言实现3.4 JavaScript 语言实现3.5 Go 语言实现 一、实例描述 假设 abcd 是一个四位整数&#xff0c;将它分成两段&#xff0c;即 ab 和 cd&#xff0c;使之相加求和后再平方。求满…...

LeetCode 热题 HOT 100:回溯专题

LeetCode 热题 HOT 100&#xff1a;https://leetcode.cn/problem-list/2cktkvj/ 文章目录 17. 电话号码的字母组合22. 括号生成39. 组合总和46. 全排列补充&#xff1a;47. 全排列 II &#xff08;待优化)78. 子集79. 单词搜索124. 二叉树中的最大路径和200. 岛屿数量437. 路径…...

喝健康白酒 有益生心健康

中国的制酒史源远流长&#xff0c;酒渗透在中华五千年的文化中。酒与烟不同&#xff0c;烟对人体有百害而无一利&#xff0c;而对于酒&#xff0c;若掌握好饮酒的度&#xff0c;对人体有一定的养生作用&#xff0c;所以我们通常会说“戒烟限酒”。 据一些专家研究&#xff0c;…...

动态规划:两个数组的dp问题(C++)

动态规划&#xff1a;两个数组的dp问题 前言两个数组的dp问题1.最长公共子序列&#xff08;中等&#xff09;2.不同的子序列&#xff08;困难&#xff09;3.通配符匹配&#xff08;困难&#xff09;4.正则表达式&#xff08;困难&#xff09;5.交错字符串&#xff08;中等&…...

BASH shell脚本篇2——条件命令

这篇文章介绍下BASH shell中的条件相关的命令&#xff0c;包括&#xff1a;if, case, while, until, for, break, continue。之前有介绍过shell的其它基本命令&#xff0c;请参考&#xff1a;BASH shell脚本篇1——基本命令 1. If语句 if语句用于在顺序执行语句的流程中执行条…...

【图论C++】Floyd算法(多源最短路径长 及 完整路径)

>>>竞赛算法 /*** file * author jUicE_g2R(qq:3406291309)————彬(bin-必应)* 一个某双流一大学通信与信息专业大二在读 * * brief 一直在算法竞赛学习的路上* * copyright 2023.9* COPYRIGHT 原创技术笔记&#xff…...

小谈设计模式(11)—模板方法模式

小谈设计模式&#xff08;11&#xff09;—模板方法模式 专栏介绍专栏地址专栏介绍 模板方法模式角色分类抽象类&#xff08;Abstract Class&#xff09;具体子类&#xff08;Concrete Class&#xff09;抽象方法&#xff08;Abstract Method&#xff09;具体方法&#xff08;C…...

C#程序中很多ntdll.dll、clr.dll的线程

如下图 需要“右键工程——调试——取消勾选‘启用本地代码调试’”即可。...

低代码工作流程管理系统:提升企业运营效率的利器

业务运营状况是否良好&#xff0c;除了人员需要配合以外&#xff0c;真正发挥作用的是背后的工作流程。将重复的工作进行自动化处理&#xff0c;确保这些流程最终指向同一个目标、实现一致的运营结果。而设计和实施不佳的工作流程则产生相反的效果——导致处理时间延长、运营成…...

HIVE SQL regexp_extract和regexp_replace配合使用正则提取多个符合条件的值

《平凡的世界》评分不错&#xff0c;《巴黎圣母院》改变成的电影不错&#xff0c;还有<<1984>>也蛮好看。 如何使用regexp_extract&regexp_replace函数将以上文本中所有书籍名称都提取出来&#xff1f; select substr(regexp_replace(regexp_extract(regexp_…...

debian 安装matlab2022b报错解决方法与问题解决思路

报错 terminate called after throwing an instance of ‘std::runtime_error’ 在安装目录执行 ./bin/glnxa64/MATLABWindow通过执行以上命令发现是和libharfbuzz库有关。 该库在调用freetype库时&#xff0c;有方法找不到。 偿试remove freetype库&#xff0c;发现该库有大…...

Jenkins集成AppScan实现

一、Jenkins上安装插件 在Jenkins里安装以下插件 ibm-security-appscanstandard-scanner 二、打开AppScan 1、配置需要扫描的地址 配置需要扫描的地址 2、记录好要扫描的URL登录序列 记录好要扫描的URL登录序列 3、导出要扫描的URL登录序列设置 导出要扫描的URL登录序列设置 三…...

10.1 File类

前言&#xff1a; java.io包中的File类是唯一一个可以代表磁盘文件的对象&#xff0c;它定义了一些用于操作文件的方法。通过调用File类提供的各种方法&#xff0c;可以创建、删除或者重命名文件&#xff0c;判断硬盘上某个文件是否存在&#xff0c;查询文件最后修改时间&…...

[论文笔记]UNILM

引言 今天带来论文Unified Language Model Pre-training for Natural Language Understanding and Generation的笔记,论文标题是 统一预训练语言模型用于自然语言理解和生成。 本篇工作提出了一个新的统一预训练语言模型(Unifield pre-trained Language Model,UniLM),可以同…...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度​

一、引言&#xff1a;多云环境的技术复杂性本质​​ 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时&#xff0c;​​基础设施的技术债呈现指数级积累​​。网络连接、身份认证、成本管理这三大核心挑战相互嵌套&#xff1a;跨云网络构建数据…...

从零实现富文本编辑器#5-编辑器选区模型的状态结构表达

先前我们总结了浏览器选区模型的交互策略&#xff0c;并且实现了基本的选区操作&#xff0c;还调研了自绘选区的实现。那么相对的&#xff0c;我们还需要设计编辑器的选区表达&#xff0c;也可以称为模型选区。编辑器中应用变更时的操作范围&#xff0c;就是以模型选区为基准来…...

Docker 运行 Kafka 带 SASL 认证教程

Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明&#xff1a;server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用

1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...

QT: `long long` 类型转换为 `QString` 2025.6.5

在 Qt 中&#xff0c;将 long long 类型转换为 QString 可以通过以下两种常用方法实现&#xff1a; 方法 1&#xff1a;使用 QString::number() 直接调用 QString 的静态方法 number()&#xff0c;将数值转换为字符串&#xff1a; long long value 1234567890123456789LL; …...

Java面试专项一-准备篇

一、企业简历筛选规则 一般企业的简历筛选流程&#xff1a;首先由HR先筛选一部分简历后&#xff0c;在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如&#xff1a;Boss直聘&#xff08;招聘方平台&#xff09; 直接按照条件进行筛选 例如&#xff1a…...

JS设计模式(4):观察者模式

JS设计模式(4):观察者模式 一、引入 在开发中&#xff0c;我们经常会遇到这样的场景&#xff1a;一个对象的状态变化需要自动通知其他对象&#xff0c;比如&#xff1a; 电商平台中&#xff0c;商品库存变化时需要通知所有订阅该商品的用户&#xff1b;新闻网站中&#xff0…...

【Go语言基础【12】】指针:声明、取地址、解引用

文章目录 零、概述&#xff1a;指针 vs. 引用&#xff08;类比其他语言&#xff09;一、指针基础概念二、指针声明与初始化三、指针操作符1. &&#xff1a;取地址&#xff08;拿到内存地址&#xff09;2. *&#xff1a;解引用&#xff08;拿到值&#xff09; 四、空指针&am…...

面向无人机海岸带生态系统监测的语义分割基准数据集

描述&#xff1a;海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而&#xff0c;目前该领域仍面临一个挑战&#xff0c;即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...

【C++特殊工具与技术】优化内存分配(一):C++中的内存分配

目录 一、C 内存的基本概念​ 1.1 内存的物理与逻辑结构​ 1.2 C 程序的内存区域划分​ 二、栈内存分配​ 2.1 栈内存的特点​ 2.2 栈内存分配示例​ 三、堆内存分配​ 3.1 new和delete操作符​ 4.2 内存泄漏与悬空指针问题​ 4.3 new和delete的重载​ 四、智能指针…...