---
title: "机器翻译"
created: 2025-11-28
tags:
  - 算法
---

# 机器翻译

## 题目 [机器翻译](https://www.acwing.com/problem/content/description/498/)

![[image-51cc5d44.png]]

## 思路分析

一头进一头出 队列

然后怎么判断一个单词是否已经出现过 可以想到用哈希 省去遍历找

但是它这里没有用单词本身作为索引 而是用数字代替

那完全就可以用值做下标做判重

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N=1010;

int q[N];

bool st[N];

int m,n;

int main()

{

    cin>>m>>n;

    int hh=0,tt=-1;

    int res=0;

    while(n--){

        int x;

        cin>>x;

        if(!st[x]){

            if(tt-hh+1==m){

                st[q[hh]]=false;

                hh++;

            }

            q[++tt]=x;

            st[x]=true;

            res++;

        }

    }

    cout<<res<<endl;

    return 0;

}
```

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N=1010;

queue<int> q;

bool st[N];

int m,n;

int main()

{

    cin>>m>>n;

    int res=0;

    while(n--){

        int x;

        cin>>x;

        if(!st[x]){

            if(q.size()==m){

                st[q.front()]=false;

                q.pop();

            }

            q.push(x);

            st[x]=true;

            res++;

        }

    }

    cout<<res<<endl;

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[小组队列|小组队列]] 🏠 [[00-刷题理模型]] ➡️ [[海港|海港]]