首页 > 试题广场 >

机器翻译

[编程题]机器翻译

热度指数：64 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 牛牛的电脑上安装了一个机器翻译软件，它依次将每个英文单词替换为对应的中文含义。软件内部有 $M$ 个缓存单元，每个单元存放一个单词和译义。翻译某个单词时：
$\hspace{23pt}\bullet\,$ 如果缓存中已有该单词，则直接使用（缓存命中）；
$\hspace{23pt}\bullet\,$ 否则需要到外存词典查找（缓存未命中），并将该单词及译义插入缓存：若缓存未满，则占用一个空闲单元；若缓存已满，则清除最早进入缓存的单词后插入新单词。
$\hspace{15pt}$ 给定长度为 $N$ 的文章（由 $N$ 个整数编码表示单词），初始缓存为空，统计翻译过程中需要查词典的次数。

输入描述:

第一行输入两个整数 （，），分别表示缓存容量和文章单词数。
第二行输入  个整数 （），表示文章中按顺序出现的单词编码。

输出描述:

输出一个整数，表示翻译过程中缓存未命中（查词典）的总次数。

示例1

输入

3 7
1 2 1 5 4 4 1

输出

说明

翻译过程示例（缓存状态记录自左向右为最早到最近）：
初始：空
1: miss，缓存->[1]
2: miss，缓存->[1,2]
1: hit，缓存->[1,2]
5: miss，缓存->[1,2,5]
4: miss，缓存->[2,5,4]（替换1）
4: hit，缓存->[2,5,4]
1: miss，缓存->[5,4,1]（替换2）
共 miss 5 次。

备注:

算法知识视频讲解

SuperShocker

发表于 2021-09-27 21:55:14

设置一个数组vis用来记录当前数据num是否在内存空间中，如果在则vis[num]=1，否则为0 设置一个数组temp来存放文章的单词，即后输入的n个数字；设置pos来指向temp最新存放的数据当输入文章单词的时候首先判断它在不在内存中，即vis[num]是否为1（1）如果在，则跳出当前循环，进入展开全文

21计科宫禹辰

发表于 2022-03-15 01:05:40

链接：https://ac.nowcoder.com/acm/problem/16589 小晨的电脑上安装了一个机器翻译软件，他经常用这个软件来翻译英语文章。这个翻译软件的原理很简单，它只是从头到尾，依次将每个英文单词用对应的中文含义来替换。对于每个英文单词，软件会先在内存中查找这个单词的中文含义展开全文

xxxxllll

发表于 2022-02-11 23:51:40

刚开始没有考虑0也是一个单词的情况，卡在90分很久...后来终于发现了问题所在，改正后ac了，很高兴。错误点：数组初始化全为0，这样就默认了字典中已经知道了一个单词0，题干中说开始默认一个单词都不知道. 改正：应该初始化存放字典的数组为无穷大（INF=0x3f3f3f3f),然后用原来的方法就通过展开全文

小小AC一下

发表于 2022-06-23 16:59:46

最基础的队列 ">using namespace std; int res[1000],vis[1000],cnt=0; int main(){ int x,m,n; cin>>m>>n; for(int i=0;i<n;i++){ 展开全文

托尼的云

发表于 2023-07-26 10:02:42

利用一个数组，下标为要存的数，数值为每次存储的顺序。例如样例中，当1为下标时，存储时数值为1；当2为下标时，存储时数值为2；当5为下标时，存储时数值为4······ #include<bits/stdc++.h> using namespace std; in 展开全文

luckyii

发表于 2024-01-26 15:20:22

#include <bits/stdc++.h> using namespace std; /* 特点：先进先出-队列外存查询条件：队列中无该单词队列替换条件：队列的容量等于三 */ int num=0; queue<int>&nb 展开全文

RUNW

发表于 2023-07-06 13:54:31

解题思路本题是一个很典型的队列问题，符合先进先出的思想，由于一般队列不进行遍历的操作（如果要用到遍历的操作一般就不会使用队列了），解题时需要注意保存单词是否在队中，每次单词进队，查询次数就增加一次，最后返回查询次数即可。代码实现 #include <iostream> #includ 展开全文

coco2009

发表于 2020-10-18 16:43:16

题意：输入一串数值，且定下队列长度，依次输入数值，若达到最大存储范围，删去第一个数，在最后再存，若数值在队列中已经出现，则不需存下，若没有，则计数器加1，输出计数器的值。本人完全按照题意来打代码，在此附上： #include<bits/stdc++.h> using namespace 展开全文

龙文浩2100130836

发表于 2022-07-22 16:32:02

简单题，用字符串或者数组都可以做出来 #include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #inclu 展开全文

装糊涂高手_

发表于 2021-12-22 17:43:59

枚举可以用队列（先进先出）结构来解决这里给出一种仅用数组的方法开两个大数组a和flag 其中a用来按顺序存储载入内存的数据（包括历史数据），同时设置一个游标fm指向下一个空位置，设置另一个游标cl_f指向当前内存的首位数据（有点类似静态链表的游标）；flag用来存储相应数据的状态，0为不在内存展开全文

问题信息

NOIP复赛枚举

难度：

1条回答 1收藏 81浏览

通过挑战的用户

查看代码

_Qingyu

2018-09-09 15:40:25
Carmon

2018-09-07 15:49:14
buffoons

2018-09-03 19:29:48
系统消息

2018-08-25 17:28:40
Hs-Zzz

2018-08-09 00:17:45

机器翻译

输入描述:

输出描述:

输入

输出

说明

备注:

问题信息

热门推荐

通过挑战的用户

相关试题