P1540 [NOIP2010 提高组] 机器翻译(模拟)
[NOIP2010 提高组] 机器翻译
题目背景
小晨的电脑上安装了一个机器翻译软件,他经常用这个软件来翻译英语文章。
题目描述
这个翻译软件的原理很简单,它只是从头到尾,依次将每个英文单词用对应的中文含义来替换。对于每个英文单词,软件会先在内存中查找这个单词的中文含义,如果内存中有,软件就会用它进行翻译;如果内存中没有,软件就会在外存中的词典内查找,查出单词的中文含义然后翻译,并将这个单词和译义放入内存,以备后续的查找和翻译。
假设内存中有 M M M 个单元,每单元能存放一个单词和译义。每当软件将一个新单词存入内存前,如果当前内存中已存入的单词数不超过 M − 1 M-1 M−1,软件会将新单词存入一个未使用的内存单元;若内存中已存入 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:查找单词 2 并调入内存。1 2:在内存中找到单词 1。1 2 5:查找单词 5 并调入内存。2 5 4:查找单词 4 并调入内存替代单词 1。2 5 4:在内存中找到单词 4。5 4 1:查找单词 1 并调入内存替代单词 2。
共计查了 5 5 5 次词典。
数据范围
- 对于 10 % 10\% 10% 的数据有 M = 1 M=1 M=1, N ≤ 5 N \leq 5 N≤5;
- 对于 100 % 100\% 100% 的数据有 1 ≤ M ≤ 100 1 \leq M \leq 100 1≤M≤100, 1 ≤ N ≤ 1000 1 \leq N \leq 1000 1≤N≤1000。
模拟水题
用队列实现替换操作,可以单独开一个桶储存当前有哪些单词(甚至你 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 提高组] 机器翻译 题目背景 小晨的电脑上安装了一个机器翻译软件,他经常用这个软件来翻译英语文章。 题目描述 这个翻译软件的原理很简单,它只是从头到尾,依次将每个英文单词用对应的中文含义来替换。对于每个英文单词…...
生信教程:ABBA-BABA分析之滑动窗口
简介 ABBA BABA 统计(也称为 D 统计)为偏离严格的分叉进化历史提供了简单而有力的检验。因此,它们经常用于使用基因组规模的 SNP 数据测试基因渗入。 虽然最初开发用于基因渗入的全基因组测试,但它们也可以应用于较小的窗口&#…...
二分答案(求最大值的最小值||求最小值的最大值)
引入 二分答案要建立在二分查找的基础上,在此之前,要知道二分查找的三个模板 模板一 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; }模板三…...
思维模型 周期
本系列文章 主要是 分享 思维模型,涉及各个领域,重在提升认知。周期是一个看似极为简单,但背后却蕴藏着大智慧的模型,了解周期,对于了解王朝更替,数学之美,经济运转等都有帮助。 1 周期的应用 …...
从 0 到 1 ,手把手教你编写《消息队列》项目(Java实现) —— 介绍项目/ 需求分析
文章目录 一、消息队列是什么?二、需求分析结构解析功能解析规则解析绑定关系交换机类型消息应答 三、持久化存储四、网络通信提供的API复用TCP连接 五、消息队列概念图 一、消息队列是什么? 消息队列 (Message Queue, MQ)就是将阻塞队列这一数据结构提取…...
Python学习之索引与切片
Python学习之索引与切片 s “0abcdefghijklmnopqrstuvwxyz”,第一个元素‘0’,索引号为0,最后一个元素‘z’,索引号为26 1. s[0]获取索引号为0的元素 2. s[1:3]获取索引号为1的元素,直到但不包括索引号为3的元素。即…...
编程每日一练(多语言实现)基础篇:满足abcd=(ab+cd)^2的数 (增加Go语言实现)
文章目录 一、实例描述二、技术要点三、代码实现3.1 C 语言实现3.2 Python 语言实现3.3 Java 语言实现3.4 JavaScript 语言实现3.5 Go 语言实现 一、实例描述 假设 abcd 是一个四位整数,将它分成两段,即 ab 和 cd,使之相加求和后再平方。求满…...
LeetCode 热题 HOT 100:回溯专题
LeetCode 热题 HOT 100:https://leetcode.cn/problem-list/2cktkvj/ 文章目录 17. 电话号码的字母组合22. 括号生成39. 组合总和46. 全排列补充:47. 全排列 II (待优化)78. 子集79. 单词搜索124. 二叉树中的最大路径和200. 岛屿数量437. 路径…...
喝健康白酒 有益生心健康
中国的制酒史源远流长,酒渗透在中华五千年的文化中。酒与烟不同,烟对人体有百害而无一利,而对于酒,若掌握好饮酒的度,对人体有一定的养生作用,所以我们通常会说“戒烟限酒”。 据一些专家研究,…...
动态规划:两个数组的dp问题(C++)
动态规划:两个数组的dp问题 前言两个数组的dp问题1.最长公共子序列(中等)2.不同的子序列(困难)3.通配符匹配(困难)4.正则表达式(困难)5.交错字符串(中等&…...
BASH shell脚本篇2——条件命令
这篇文章介绍下BASH shell中的条件相关的命令,包括:if, case, while, until, for, break, continue。之前有介绍过shell的其它基本命令,请参考:BASH shell脚本篇1——基本命令 1. If语句 if语句用于在顺序执行语句的流程中执行条…...
【图论C++】Floyd算法(多源最短路径长 及 完整路径)
>>>竞赛算法 /*** file * author jUicE_g2R(qq:3406291309)————彬(bin-必应)* 一个某双流一大学通信与信息专业大二在读 * * brief 一直在算法竞赛学习的路上* * copyright 2023.9* COPYRIGHT 原创技术笔记ÿ…...
小谈设计模式(11)—模板方法模式
小谈设计模式(11)—模板方法模式 专栏介绍专栏地址专栏介绍 模板方法模式角色分类抽象类(Abstract Class)具体子类(Concrete Class)抽象方法(Abstract Method)具体方法(C…...
C#程序中很多ntdll.dll、clr.dll的线程
如下图 需要“右键工程——调试——取消勾选‘启用本地代码调试’”即可。...
低代码工作流程管理系统:提升企业运营效率的利器
业务运营状况是否良好,除了人员需要配合以外,真正发挥作用的是背后的工作流程。将重复的工作进行自动化处理,确保这些流程最终指向同一个目标、实现一致的运营结果。而设计和实施不佳的工作流程则产生相反的效果——导致处理时间延长、运营成…...
HIVE SQL regexp_extract和regexp_replace配合使用正则提取多个符合条件的值
《平凡的世界》评分不错,《巴黎圣母院》改变成的电影不错,还有<<1984>>也蛮好看。 如何使用regexp_extract®exp_replace函数将以上文本中所有书籍名称都提取出来? select substr(regexp_replace(regexp_extract(regexp_…...
debian 安装matlab2022b报错解决方法与问题解决思路
报错 terminate called after throwing an instance of ‘std::runtime_error’ 在安装目录执行 ./bin/glnxa64/MATLABWindow通过执行以上命令发现是和libharfbuzz库有关。 该库在调用freetype库时,有方法找不到。 偿试remove freetype库,发现该库有大…...
Jenkins集成AppScan实现
一、Jenkins上安装插件 在Jenkins里安装以下插件 ibm-security-appscanstandard-scanner 二、打开AppScan 1、配置需要扫描的地址 配置需要扫描的地址 2、记录好要扫描的URL登录序列 记录好要扫描的URL登录序列 3、导出要扫描的URL登录序列设置 导出要扫描的URL登录序列设置 三…...
10.1 File类
前言: java.io包中的File类是唯一一个可以代表磁盘文件的对象,它定义了一些用于操作文件的方法。通过调用File类提供的各种方法,可以创建、删除或者重命名文件,判断硬盘上某个文件是否存在,查询文件最后修改时间&…...
[论文笔记]UNILM
引言 今天带来论文Unified Language Model Pre-training for Natural Language Understanding and Generation的笔记,论文标题是 统一预训练语言模型用于自然语言理解和生成。 本篇工作提出了一个新的统一预训练语言模型(Unifield pre-trained Language Model,UniLM),可以同…...
linux之kylin系统nginx的安装
一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源(HTML/CSS/图片等),响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址,提高安全性 3.负载均衡服务器 支持多种策略分发流量…...
python打卡day49
知识点回顾: 通道注意力模块复习空间注意力模块CBAM的定义 作业:尝试对今天的模型检查参数数目,并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...
【JVM】- 内存结构
引言 JVM:Java Virtual Machine 定义:Java虚拟机,Java二进制字节码的运行环境好处: 一次编写,到处运行自动内存管理,垃圾回收的功能数组下标越界检查(会抛异常,不会覆盖到其他代码…...
在四层代理中还原真实客户端ngx_stream_realip_module
一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡(如 HAProxy、AWS NLB、阿里 SLB)发起上游连接时,将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后,ngx_stream_realip_module 从中提取原始信息…...
OPENCV形态学基础之二腐蚀
一.腐蚀的原理 (图1) 数学表达式:dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一,腐蚀跟膨胀属于反向操作,膨胀是把图像图像变大,而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...
《C++ 模板》
目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板,就像一个模具,里面可以将不同类型的材料做成一个形状,其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式:templa…...
免费PDF转图片工具
免费PDF转图片工具 一款简单易用的PDF转图片工具,可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件,也不需要在线上传文件,保护您的隐私。 工具截图 主要特点 🚀 快速转换:本地转换,无需等待上…...
计算机基础知识解析:从应用到架构的全面拆解
目录 前言 1、 计算机的应用领域:无处不在的数字助手 2、 计算机的进化史:从算盘到量子计算 3、计算机的分类:不止 “台式机和笔记本” 4、计算机的组件:硬件与软件的协同 4.1 硬件:五大核心部件 4.2 软件&#…...
关于easyexcel动态下拉选问题处理
前些日子突然碰到一个问题,说是客户的导入文件模版想支持部分导入内容的下拉选,于是我就找了easyexcel官网寻找解决方案,并没有找到合适的方案,没办法只能自己动手并分享出来,针对Java生成Excel下拉菜单时因选项过多导…...
elementUI点击浏览table所选行数据查看文档
项目场景: table按照要求特定的数据变成按钮可以点击 解决方案: <el-table-columnprop"mlname"label"名称"align"center"width"180"><template slot-scope"scope"><el-buttonv-if&qu…...
