首页 > 试题广场 >

机器翻译

[编程题]机器翻译

热度指数：2636 时间限制：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 次。

备注:

算法知识视频讲解

Python3

意若久时天然呆

m, n = map(int, input().strip().split())
w, t, c = list(map(int, input().strip().split())), [], 0
for i in w:
    if i in t:
        continue
    else:
        if len(t) >= m:
            t.pop(0)
        c += 1
        t.append(i)
print(c)

发表于 2025-11-26 10:00:57 回复(0)

C++

甲醇苯酚钠

#include <iostream>
using namespace std;
#include<deque>
#include<vector>
bool isInCache(int a,deque<int>d){
      for(int i=0;i<d.size();i++){
           if(a==d[i]){
               return 1;
           }
      }
      return 0;
}
int main() {
   int M,N;
   cin>>M>>N;
    vector<int>v;
   for(int i=0;i<N;i++){
        int a;
        cin>>a;
        v.push_back(a);
   }
   int miss=0;
   deque<int>d;
   for(int i=0;i<v.size();i++){
           if(isInCache(v[i],d)){
                 continue;
           }
           else if(!isInCache(v[i],d)){
            miss++;
                if(d.size()==M){
                    d.pop_front();
                    d.push_back(v[i]);
                }
                else{
                    d.push_back(v[i]);
                }
           }
         }
         cout<<miss;
   }

// 64 位输出请用 printf("%lld")

发表于 2025-12-06 21:03:52 回复(0)

Comeand

#include <stdint.h>

#include <stdio.h>

int main() {

int M,N,miss=0;

scanf("%d%d",&M,&N);

int queue[M],front=0;

for(int i=0;i<N;i++){

int x;

scanf("%d",&x);

for(int j=0;j<front;j++){

if(x==queue[j]){

goto ta;

}

if(front<M) {

queue[front++]=x;

miss++;

}

else{int temp=x;

for(int u=0;u<M-1;u++){

queue[u]=queue[u+1];

}

queue[M-1]=x;

miss++;

}

ta: continue;

}

printf("%d",miss);

return 0;

}

发表于 2025-11-28 00:03:55 回复(0)

Python3

袁钦照

m,n = map(int,input().split())
w = list(map(int,input().split()))
list_w = []
cnt = 0
for i in w:
    if i not in list_w:
        cnt += 1
        if len(list_w) == m:
            list_w.pop(0)
            list_w.append(i)
        if len(list_w) < m:
            list_w.append(i)
    else:
        continue
print(cnt)

发表于 2025-11-21 14:33:57 回复(0)

Solitude_sundae

#include <bits/stdc++.h>

using namespace std;

int main() {

int M, N, w, count = 0;

cin >> M >> N;

queue <int> q, temp;

bool h = false;

while (N--) {

h = false;

cin >> w;

while (!q.empty()) {

if (q.front() == w)

h = true;

temp.push(q.front());

q.pop();

}

while (!temp.empty()) {

q.push(temp.front());

temp.pop();

}

if (!h) {

if (q.size() == M)

q.pop();

q.push(w);

count++;

}

cout << count;

return 0;

}

// 64 位输出请用 printf("%lld")

发表于 2025-11-12 17:23:32 回复(0)

Python3

极客喵

class Queue:
    def __init__(self):
        self.in_stack: list[int] = []
        self.out_stack: list[int] = []

    def push(self, x: int):
        self.in_stack.append(x)

    def _dump_if_needed(self):
        if not self.out_stack:
            while self.in_stack:
                self.out_stack.append(self.in_stack.pop())

    def pop(self) -> int:
        if self.isEmpty():
            raise IndexError("pop from an empty queue")

        self._dump_if_needed()

        return self.out_stack.pop()

    def query(self) -> int:
        if self.isEmpty():
            raise IndexError("pop from an empty queue")

        self._dump_if_needed()

        return self.out_stack[-1]

    @property
    def size(self) -> int:
        return len(self.in_stack) + len(self.out_stack)

    def isEmpty(self) -> bool:
        return not self.in_stack and not self.out_stack

    def __len__(self) -> int:
        return self.size
    
    def __contains__(self, x : int) -> bool:
        return x in self.in_stack&nbs***bsp;x in self.out_stack

def totalQuery(M : int, words : list[int]) -> int:
    vocab = Queue()
    total_number_of_query = 0
    for word in words:
        if word not in vocab:
            total_number_of_query += 1
            if vocab.size >= M:
                vocab.pop()
            vocab.push(word)

    return total_number_of_query

def main():
    M, N = map(int, input().split())
    words = list(map(int, input().split()))
    print(totalQuery(M, words))

if __name__ == "__main__":
    main()

发表于 2025-11-12 01:27:51 回复(0)

C++

Nitrene

#include <iostream>

using namespace std;

int vis[1002],

temp[1002]; //vis指这个数字是否已经缓存；temp指目前最新的存储单词；

int main() {

int M, count = 0, N, tempPos = 0; //M，N题目已经给出，count指已经存储几个数据，tempPos表示temp开到几；

cin >> M >> N;

int op, sum = 0; //op为当前输入序号，sum指查过几次；

while (N--) {

cin >> op;

if (vis[op] == 1) {

continue;//已经缓存，次数加1后，直接下一轮；

}

sum++;

if (count >= M) {

vis[temp[tempPos - M]] = 0; //不断的更新temp库元素；

vis[op] = 1;

temp[tempPos++] = op;

} else {

vis[op] = 1;

temp[tempPos++] = op;

count++;

}

cout << sum << endl;

return 0;

}

// 64 位输出请用 printf("%lld")

发表于 2025-10-15 16:58:21 回复(0)

Python3

嵩胜Sycml

# 小白版本

a,b = map(int, input().split())

nums = list(map(int,input().split()))
stack=[]
res = 0
for aaa in nums:
    if aaa in stack:
        # res+= 1
        continue
    elif len(stack)<a:
        res+=1
        stack.append(aaa)
    else:
        stack.pop(0)
        res+=1
        stack.append(aaa)
print(res)

发表于 2025-09-06 23:32:22 回复(0)

BraveCoder

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int M = scanner.nextInt(); // 缓存容量
        int N = scanner.nextInt(); // 单词数量
        
        int[] words = new int[N];
        for (int i = 0; i < N; i++) {
            words[i] = scanner.nextInt();
        }
        
        // 使用队列实现
        Queue<Integer> cacheQueue = new LinkedList<>();
        int missCount = 0; // 未命中次数
        
        for (int word : words) {
            if (cacheQueue.contains(word)) {
                // 缓存命中，无需操作
                continue;
            } else {
                // 缓存未命中，查词典次数加1
                missCount++;
                // 若缓存已满，移除最早进入的元素（队首）
                if (cacheQueue.size() >= M) {
                    cacheQueue.poll();
                }
                // 将新单词加入队尾
                cacheQueue.offer(word);
            }
        }
        
        System.out.println(missCount);
        scanner.close();
    }
}

发表于 2025-08-05 17:12:59 回复(0)

badcola

经典队列的应用。

import sys

class Queue:

def __init__(self):

self.que = []

def inqueue(self,x):

self.que.insert(0,x)

def outqueue(self):

if self.que:

return self.que.pop()

else: return 'ERR_CANNOT_POP'

def first_queue(self):

if self.que:

return self.que[-1]

else: return 'ERR_CANNOT_QUERY'

def size(self):

return len(self.que)

def find(self,item):

if item in self.que:

return True

else: return False

m,n = map(int,input().split())

l = list(map(int,input().split()))

que = Queue()

cnt = 0

for i in range(n):

if not que.find(l[i]):

if que.size() < m:

que.inqueue(l[i])

else:

que.outqueue()

que.inqueue(l[i])

cnt += 1

print(cnt)

发表于 2025-08-01 13:04:15 回复(0)

Java

拒绝无效加班的柯基很想被叫靓仔

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

// 注意 hasNext 和 hasNextLine 的区别

while (in.hasNextInt()) { // 注意 while 处理多个 case

int m = in.nextInt();

int n = in.nextInt();

int[] list = new int[n];

for(int i = 0;i < n;i++){

list[i] = in.nextInt();

}

Queue<Integer> huancun = new LinkedList<>();

ArrayList<Integer> arr = new ArrayList<>();

int count = 0;

for(int i = 0;i < n;i++){

Boolean find = false;

if(huancun.isEmpty()){

count++;

huancun.add(list[i]);

arr.add(list[i]);

}else{

if(arr.size() > m){

for(int j = arr.size() - m;j < arr.size();j++){

if(arr.get(j) == list[i]){

find = true;

}

}else{

for(int j = 0;j < arr.size();j++){

if(arr.get(j) == list[i]){

find = true;

}

if(find == true){

continue;

}else{

if(arr.size() < m){

count++;

huancun.add(list[i]);

arr.add(list[i]);

}else{

huancun.poll();

count++;

huancun.add(list[i]);

arr.add(list[i]);

}

System.out.println(count);

}

发表于 2025-07-16 15:44:24 回复(0)

Python3

GB279824

def page_replaced(l,k,pages):
    cache = []
    missed_count = 0
    for page in pages:
        if page not in cache:
            missed_count += 1
            if l == len(cache):
                cache.pop(0)
            cache.append(page)
    return missed_count

l,k = map(int,input().strip().split(" "))
pages = list(map(int,input().strip().split(" ")))

print(page_replaced(l,k,pages))

发表于 2025-06-11 02:10:25 回复(0)