回复 活动 录播课基础算法2课堂练习6 5. NOIP2010-S-1-机器翻译 1

[鲁子欣 (萌新)]

题目描述：

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

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

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

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

输入格式：

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

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

0
<
≤
1000
)
(0<M≤100, 0<N≤1000)

第二行为 N 个非负整数，按照文章的顺序，每个数（大小不超过1000）代表一个英文单词。(相同的数字表示同一个单词)

输出格式：

输出一个整数，为软件需要查词典的次数。

样例输入：

3 7 
1 2 1 5 4 4 1

样例输出：

5

样例说明：

文章共有7个单词，从前往后分别是1 2 1 5 4 4 1，翻译软件最多能存3个单词。

遇到第1个单词1时，翻译软件中无单词1，查阅并存入新单词1，此时内存为1，查阅了1次；

遇到第2个单词2时，翻译软件中无单词2，查阅并存入新单词2，此时内存为2，查阅了2次；

遇到第3个单词1时，翻译软件中有单词1，此时内存为2，查阅次数不变，依然为2；

遇到第4个单词5时，翻译软件中无单词5，查阅并存入新单词5，此时内存为3，查阅了3次；

遇到第5个单词4时，翻译软件中无单词4，需查阅并存入新单词4，但此时内存为3，已达到最大内存，弹出最前面的1，存入4，此时内存为3，查阅了4次；

遇到第6个单词4时，翻译软件中有单词4，此时内存为3，查阅次数不变，依然为4；

遇到第7个单词1时，翻译软件中无单词1，弹出最前面的2，查阅并存入新单词1，此时内存为3，查阅了5次；

没有思路

[林子熙1 (good)]

可以用队列很快速地实现

AC代码

你以为我会给你呀，有也是错的

伪代码

定义
queue  q;
int main(){输入
	for(int i=1;i<=n;i++)
		输入
		if(v[x]==0)
			if(当溢出即q.size()>=m)：
				v[q.front()]=0;
				q.pop();
			q.push(x),v[x]=1,ans++;
		
	输出
这可是自己改AC代码的，100%（只要你肯调）

解决方案

[江隽铭 (FPV飞着飞着着火炸了)]

要解决这个问题，我们需要使用一个模拟缓存替换的策略来计算需要查词典的次数。这个问题类似于LRU（Least Recently Used）缓存替换策略。以下是代码实现：

（无）

代码解释

1. 输入读取：

   • 读取内存容量 ( M ) 和文章长度 ( N )。
   • 读取文章中的单词序列。

2. 使用数据结构：

   • 使用 unordered_set 作为缓存来存储当前在内存中的单词。
   • 使用 queue 来维护单词的插入顺序，以便在缓存满时移除最早插入的单词。

3. 模拟翻译过程：

   • 对于每个单词，检查是否在缓存中：
     • 如果不在缓存中，增加查词典次数 misses。
     • 如果缓存已满，移除最早插入的单词。
     • 将新单词插入缓存，并将其插入顺序队列中。

4. 输出结果：

   • 最后输出需要查词典的总次数。

示例解释

对于输入：

3 7
1 2 1 5 4 4 1

输出：

5

解释：

1. 读取单词1，不在缓存中，查词典，缓存为[1]，查词典次数为1。
2. 读取单词2，不在缓存中，查词典，缓存为[1, 2]，查词典次数为2。
3. 读取单词1，在缓存中，缓存不变，查词典次数不变。
4. 读取单词5，不在缓存中，查词典，缓存为[1, 2, 5]，查词典次数为3。
5. 读取单词4，不在缓存中，查词典，缓存满，移除最早的1，缓存为[2, 5, 4]，查词典次数为4。
6. 读取单词4，在缓存中，缓存不变，查词典次数不变。
7. 读取单词1，不在缓存中，查词典，缓存满，移除最早的2，缓存为[5, 4, 1]，查词典次数为5。

这样就计算出了需要查词典的总次数。

[鲁子欣 (萌新)]

[yhxyd0324 (唐翊峻)]

单向队列

[周子寓 (zzy10124)]

@鲁子欣 你也可以用数组模拟