10pts(On)

由于有10%的数据$m=1$,那么我们其实只需要更新一个单词即可

代码实现

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m;
    cin>>m>>n;
    int res=0;
    int last=-1;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        if(last!=x) //判断是否和上一个单词相同
        {
            last=x; //更新内存中的单词
            res++; //查询次数增加
        }
    }
    cout<<res;
    return 0;
}

使用队列表示内存,再用一个标记数组表示内存中的每个单词的状态.$O(n)$

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
bool st[N];//标记当前这个数是否在内存之中 
int main()
{
	int m,n;
	cin>>m>>n;
	queue<int> q; //内存队列 
	int res=0;
	for(int i=1;i<=n;i++)
	{
	
		int x;
		cin>>x;
		if(!st[x]) //x不在队列之中 
		{
			res++;//增加了一次查字典的次数 
			q.push(x);//加入到队列之中
			st[x]=true; //标记已经在内存之中 
			if(q.size()>m)
			{
				int t=q.front();
				st[t]=0;//标记不在内存之中
				q.pop(); 
			} 
		}
	}
	cout<<res;
	return 0;
}