題目背景

小晨的電腦上安裝了一個機器翻譯軟件，他經常用這個軟件來翻譯英語文章。

題目描述

這個翻譯軟件的原理很簡單，它只是從頭到尾，依次將每個英文單詞用對應的中文含義來替換。對于每個英文單詞，軟件會先在內存中查找這個單詞的中文含義，如果內存中有，軟件就會用它進行翻譯；如果內存中沒有，軟件就會在外存中的詞典內查找，查出單詞的中文含義然后翻譯，并將這個單詞和譯義放入內存，以備后續的查找和翻譯。

假設內存中有M個單元，每單元能存放一個單詞和譯義。每當軟件將一個新單詞存入內存前，如果當前內存中已存入的單詞數不超過M-1，軟件會將新單詞存入一個未使用的內存單元；若內存中已存入M個單詞，軟件會清空最早進入內存的那個單詞，騰出單元來，存放新單詞。

假設一篇英語文章的長度為N個單詞。給定這篇待譯文章，翻譯軟件需要去外存查找多少次詞典？假設在翻譯開始前，內存中沒有任何單詞。

輸入輸出格式

輸入格式：

輸入文件共2行。每行中兩個數之間用一個空格隔開。

第一行為兩個正整數M和N，代表內存容量和文章的長度。

第二行為N個非負整數，按照文章的順序，每個數（大小不超過1000）代表一個英文單詞。文章中兩個單詞是同一個單詞，當且僅當它們對應的非負整數相同。

輸出格式：

包含一個整數，為軟件需要查詞典的次數。

思路1：暴力

#include<cstdio> #include<cstring> #include<iostream> using namespace std; int zd[1001],m; bool find(int x){int i;for(i=1;i<=m;i++)if(zd[i]==x)return true;return false; } int i,n,j,k,z; int main(){memset(zd,-1,sizeof(zd));cin>>m>>n;for(i=1;i<=n;i++){scanf("%d",&z);if(!find(z)){j++;k++;while(k>m)k-=m;zd[k]=z;}}cout<<j;return 0; }

我AC前WA了N次~~~主要是因為數組模擬思路不夠明確，一下想標記，一下想隊列~

~So, WA得慘不忍睹~

思路2：Hash+隊列

#include<iostream> using namespace std; int d[1000+5],p[1000+5]; int main(){int i,j,k,m,n;int f=1,l=0;cin>>m>>n;int ans=0;for(i=1;i<=n;i++){cin>>k;if(p[k]==0){ans++;d[++l]=k;p[k]=l;if(l-f>=m){p[d[f]]=0;f++;}}}cout<<ans<<endl; return 0; }

具體來說，就是判斷每個單詞是否進入隊列以及隊列是不是要炸了（就彈掉）。沒用STL，直接數組模擬就好了。

總結

以上是生活随笔為你收集整理的Luogu P1540 机器翻译的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。