题目大意

在长度为n的数列中找出恰好有k个不同数字的子数列。

思路

纯模拟简单题。

代码

#include<iostream>
#include<stdio.h>
#include<cstring>
using namespace std;
int n,k;
int num[100000];
int mark[100001];
void solved()
{
	for(int i=0,sum=0;i<n;i++)
	{
		if(!mark[num[i]])
			sum++;
		mark[num[i]]++;
		if(sum==k)
		{
			for(int j=0;j<=i;j++)
			{
				mark[num[j]]--;
				if(mark[num[j]]==0)
				{
					printf("%d ",j+1);
					break;
				}
			}
			printf("%d\n",i+1);
			return;
		}
	}
	printf("-1 -1\n");
}
int main()
{
	while(~scanf("%d%d",&n,&k))
	{
		memset(mark,0,sizeof(mark));
		for(int i=0;i<n;i++)
			scanf("%d",&num[i]);
		solved();
	}
}

后记

这么道简单题，WA了好几次，花费了很长时间才通过，并且赛后大数据还没过，原因是mark数组范围少了个0……总结下这道简单题如此失败的原因：

  • 读题实在太不仔细，很久才明白题意。刚开始一直不明白为何测试数据只有一个结果而不是多个，直至发Output中的最后一句话“If there are multiple correct answers, print any of them.”。等反映过来之后已经不知道过了多长时间了。
  • 对题干中的“exactly”理解不透彻，子数列应该满足“去掉数列第一个或最后一个数字都会导致数列不满足‘拥有k个不同数字’的条件。”，换句话说，数列第一个数字与最后一个数字都应是数列中独一无二没有重复的数字，都属于k个不同数字之一。