[NOIP2010-提高] 机器翻译

GitHub跳转原题关系图返回列表

用队列按进入顺序模拟容量 M 的内存、布尔数组判命中：未命中计数入队，满员淘汰队首，O(N) 求出查词典次数。

OJ: roj

题目 ID: 3582

难度:普及-

标签:模拟队列python

创建: 2026-10-02 09:04

更新: 2026-10-06 14:35

后置题目

luogu P2058[NOIP 2016 普及组] 海港B 的 main.py 用 deque 保存窗口乘客，过期时 while 从队头 popleft，正是 A 教的「队头 popleft 淘汰最早进入的元素」这一步，只是把淘汰条件从容量满换成时间超过 86400 秒，并额外叠加 Counter 统计不同国籍的计数层。

题目描述

翻译软件逐词翻译文章：内存中有该单词就直接使用；没有就查一次外存词典，并把单词放入内存。内存有 $M$ 个单元，放入新单词前若已存满 $M$ 个，先清空最早进入内存的单词腾出单元（命中不改变单词的进入顺序）。单词用不超过 $1000$ 的非负整数编码，相同整数代表同一单词，翻译开始前内存为空，求查词典的总次数。

输入：第一行两个正整数 $M, N$ （数据范围 $0 \leqslant M \leqslant 100$ ， $0 \leqslant N \leqslant 1000$ ）；第二行 $N$ 个非负整数，按文章顺序给出。输出：一个整数，为查词典的次数。样例输入 $M=3$ 、序列 1 2 1 5 4 4 1，输出 5。

思路

内存的变化只有"尾部追加新词、头部淘汰最老词"，命中不刷新顺序，所以用队列按进入顺序存单词，命中判断用布尔数组 in_memory[] 做 $O(1)$ 完成。逐词扫描：命中则跳过，否则答案加一，满员时先弹出队首再把新词入队， $M=0$ 时只计数不入队。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 09:04
# update_at: 2026-10-02 09:04

import sys
from collections import deque


def count_lookups(capacity: int, words: list[int]) -> int:
    """FIFO 内存模拟：统计需要去外存查词典（未命中）的次数。

    deque 按进入顺序存词，集合 O(1) 判在不在；内存满时淘汰队首，
    即题面要求的"清空最早进入内存的那个单词"。
    """
    cache: deque[int] = deque()   # 进入内存的先后顺序
    present: set[int] = set()     # 配合 deque 做 O(1) 命中判断
    lookups = 0

    for word in words:
        if word in present:
            continue                                   # 内存里有，不查词典
        lookups += 1                                   # 没有，去外存查一次
        if capacity == 0:                              # M=0 时内存存不下任何词
            continue
        if len(cache) == capacity:                         # 内存满了
            oldest = cache.popleft()                       # 淘汰最早进入的词
            present.discard(oldest)
        cache.append(word)
        present.add(word)

    return lookups


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    capacity = next(data)  # M：内存单元数
    length = next(data)    # N：文章单词数
    words = [next(data) for _ in range(length)]

    print(count_lookups(capacity, words))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 14:34
 * update_at: 2026-10-06 14:34
 */

#include <cstdio>

typedef long long ll;

const int MAXV = 1005; // 单词大小不超过 1000

int m, n;
int word;              // 当前读入的单词
int q[MAXV];           // 内存队列：q[head] 是最早进入的单词，q[tail-1] 是最新的
int head, tail;        // 队列的队首和队尾（左闭右开）
bool in_memory[MAXV];  // in_memory[w] 表示单词 w 当前是否在内存里
ll ans;                // 查词典的总次数

int main() {
    scanf("%d %d", &m, &n);
    // M 可以为 0：此时内存永远为空，每个词都要查词典
    for (int i = 1; i <= n; i++) {
        scanf("%d", &word);
        if (in_memory[word])
            continue;            // 内存里已有，命中，不查词典
        ans++;                   // 未命中，查一次词典
        if (m > 0) {             // M=0 时存不下任何词，只计数
            if (tail - head == m) {              // 内存已满
                in_memory[q[head]] = false;      // 淘汰最早进入的单词
                head++;
            }
            q[tail] = word;      // 新单词进入内存
            tail++;
            in_memory[word] = true;
        }
    }
    printf("%lld\n", ans);
    return 0;
}