欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

UPC1491 【贪心】未出现的子串

程序员文章站 2022-03-26 11:31:35
...

题目:点击打开链接

题目描述

有一个长度为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

提示

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

思路:

这个题简直是骚操作。首先分析什么情况下所有子串都存在。

假如长度3的某个子串存在,那么如果将这个图划分成三个区域,从区域一中任取一个数提取出组成三长度子串的第一个数,区域二提取出第二个数,区域三提取出第三个数。这三个区域内是一定要保证分别有这三个数的。

同理如果所有长度为3的子串都存在,那么区域一内必须有1到q所有的数,区域2和3同理。所以要想知道最短的没有的子串,就需要找出这个串可以被分成多少个这样的区域。区域数+1就是答案了。(画个图卖个萌)

UPC1491 【贪心】未出现的子串

AC代码:

#include<iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <set>
using namespace std;
int n,q;
set<int>x;
int main()
{
    scanf("%d %d",&n,&q);
    int y;
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&y);
        x.insert(y);
        if(x.size()==q)
        {
            ans++;
            x.clear();
        }
    }
    printf("%d\n",ans+1);
    return 0;
}

相关标签: 贪心