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个。
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个数,表示该数字串每一位的数字。
第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就是答案了。(画个图卖个萌)
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;
}
推荐阅读
-
php取中文字符串中出现次数最多的子串的代码
-
如何取得中文字符串中出现次数最多的子串
-
PHP中substr_count()函数获取子字符串出现次数的方法
-
如何取得中文字符串中出现次数最多的子串
-
【汇编学习笔记】3:查询子串出现的位置
-
LeetCode题解(1297):寻找符合特定条件且出现次数最大的子串(Python)
-
LeetCode28 实现strStr()(找到子串第一次出现的位置BF,KMP)
-
如何取得中文字符串中出现次数最多的子串_PHP
-
《剑指offer》-- 复杂链表的复制、字符串的排列、数组中出现次数超过一半的数字、连续子数组的最大和
-
PHP中substr_count()函数获取子字符串出现次数的方法