Max Mex

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

在现代基因组学研究中,科学家常常需要在染色体序列中扫描连续的基因片段,以研究特定功能基因标记的分布情况。不同基因标记用非负整数编码,代表某种生物学功能位点。为了评估某段长度固定的染色体区域内缺失基因标记的最小编号(即最小缺失位点),我们引入了 mex\mathrm{mex}(minimum excluded value)指标。

对一个非负整数序列 SS 而言,mex(S)\mathrm{mex}(S) 是不在 SS 中出现的最小非负整数,例如:S={1,0,3,4},mex(S)=2S = \{1, 0, 3, 4\},mex(S) = 2。

现给定染色体上长度为nn的基因标记序列aa,请你考察所有长度恰好为 kk的连续片段,分别计算它们的mexmex,并输出这些值中的最大值。该值对应的片段在最小缺失标记方面最为“丰富”,对后续基因功能挖掘具有重要指导意义。

输入格式

第一行包含两个正整数 n,k(1≤k≤n≤105)n,k(1 \le k \le n \le 10^5),分别表示基因序列的长度和你需要检查的片段的长度。 第二行包含nn 个非负整数a1,a2,...,an(0≤ai≤105)a_1, a_2, ...,a_n(0 \le a_i \le 10^5),表示基因标记序列aa。

输出格式

输出一行一个整数,基因标记序列aa中所有长度为kk的片段的mexmex的最大值。

样例

5 3
0 1 0 1 0
2
5 3
0 1 2 3 4
3
7 1
1 7 2 4 2 9 1
0

提示

对于样例1,$mex\{0,1,0\} = 2,mex\{1, 0, 1\} = 2, mex\{0, 1, 0\} = 2$,最大值为22。

对于样例2,$mex\{0, 1, 2\} = 3, mex\{1, 2, 3\} = 0, mex\{2, 3, 4\} = 0$,最大值为33。

对于样例3,所有长度为11的连续片段的mexmex都为00。

2025级SYUCT-ACM新生第三次训练

未参加
状态
已结束
规则
XCPC
题目
24
开始于
2025-10-29 18:30
结束于
2025-11-10 0:00
持续时间
269.5 小时
主持人
参赛人数
152