题解 P1540 【机器翻译】
隔壁的张栩嘉
2019-01-17 09:12:11
emmm……此题很坑（对CCF深深的怨念）
此题，我第一个想法是队列。于是，用了C++的queue，结果发现我并不会用STL（STL我就没学过），调了半天，最终放弃。
但是，天无绝人之路，有一个神奇的东西：“数组模拟队列”。 于是，我就开始数组模拟队列了。
于是，就有了这样的代码：
```cpp
#include<cstdio>
#define For(i,a,b) for (register int i=a;i<=b;i++)
using namespace std;
int n,a,m,s,t=1,head=1,end,memory[1001];
bool bz[1001];
int main()
{
scanf("%d%d",&m,&n);
end=m;
For (i,1,n)
{
scanf("%d",&a);
if (!bz[a])
{
s++;
if (memory[end]) bz[memory[head]]=false,head++,end++;
memory[++t]=a;
bz[a]=true;
}
}
printf("%d",s);
return 0;
}
```
后来，我看到了这个：
输入格式：
共22行。每行中两个数之间用一个空格隔开。
第一行为两个正整数$M,N$，代表内存容量和文章的长度。
第二行为$N$个** _非负整数_ **，按照文章的顺序，每个数（大小不超过$1000$）代表一个英文单词。文章中两个单词是同一个单词，当且仅当它们对应的非负整数相同。
于是：
```cpp
#include<cstdio>
#define For(i,a,b) for (register int i=a;i<=b;i++) //宏定义，缩短C++的for循环语句。register加速for。
using namespace std; //养成好习惯
int n,a,m,s,t=1,head=1,end,memory[1001]; //head是头指针，end是尾指针，memory是队列空间
bool bz[1001]; //bz[a]==true表示a在队列当中
int main()
{
scanf("%d%d",&m,&n);
end=m;
For (i,1,m) memory[i]=-1; //初始化队列空
For (i,1,n)
{
scanf("%d",&a);
if (!bz[a]) //判断a是否在队列中
{
s++;
if (memory[end]!=-1) bz[memory[head]]=false,head++,end++; //如果队列已满，把最早入队的元素出队
memory[++t]=a; //新元素入队
bz[a]=true; //标记新元素在队列中
}
}
printf("%d",s);
return 0; //养成好习惯
}
```