未出现的子串(unapeared)

未出现的子串(unapeared)

题目描述

有一个长度为n的数字串,其中会出现数字1,2,3,…,q(5≤q≤9)。现在的问题是,需要求出一个长度最小的串(出现的数字也是1~q),使得该串不是这个数字串的子串。为了简化问题,你只需要输出这个串的长度即可。例如对于数字串:
S=1 3 5 2 4 1 3 5 2 2 2 2 3 4 1 5 3 2(q=5)
长度为1和2的数字子串全出现过,但是你找不出子串s’=4。因此答案是3。
说明:此题中的数字子串,数字并不一定连续出现在母数字串中。如我们定义1 3是串153的一个子串,但3 5不是1 5 3的子串。串1 5 3的所有子串为:1,5,3,1 5,5 3,1 3,1 5 3,共7个。

输入

第1行两个数,串长n和出现的数字的个数q;
第2行有n个数,表示该数字串每一位的数字。

输出

未出现的子串的最小长度。

样例输入

18 5
1 3 5 2 4 1 3 5 2 2 2 2 3 4 1 5 3 2

样例输出

3

提示

对于30%的数据:1≤n≤20,q=5;
对于100%的数据:1≤n≤100000,5≤q≤9。

分析:因为是第一个未出现的串的长度,所以前面的长度的子串都出现过,所以从前往后统计1,2,...,q出现了几遍即可;

代码:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#include <ext/rope>
#define rep(i,m,n) for(i=m;i<=n;i++)
#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)
#define vi vector<int>
#define pii pair<int,int>
#define mod 1000000007
#define inf 0x3f3f3f3f
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ll long long
#define pi acos(-1.0)
const int maxn=1e5+;
const int dis[][]={{,},{-,},{,-},{,}};
using namespace std;
using namespace __gnu_cxx;
ll gcd(ll p,ll q){return q==?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=;while(q){if(q&)f=f*p;p=p*p;q>>=;}return f;}
int n,m,a[maxn],cnt;
set<int>p;
int main()
{
int i,j,k,t;
scanf("%d%d",&n,&m);
rep(i,,n-)scanf("%d",&a[i]);
cnt=;
rep(i,,n-)
{
p.insert(a[i]);
if(p.size()==m)cnt++,p.clear();
}
printf("%d\n",cnt);
//system ("pause");
return ;
}
上一篇:STL algorithm算法min,min_element(35)


下一篇:php添加pcntl扩展(Linux)