Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 16 Solved: 11
约翰的N(1≤N≤100000)只奶牛站成了一列.每只奶牛都写有一个号牌,表示她的品种,号牌上的号码在1…K(1≤K≤10000)范围内.比如有这样一个队列
1,5,3,2,5,3,4,4,2,5,1,2,3
根据约翰敏锐的数学神经,他发现一些子序列在这个队列里出现,比如3,4,1,3,而另一些没有.子序列的各项之间穿插有其他数,也可认为这个子序列存在, 现在,他想找出一个最短的子序列(由1..K组成),使之不在奶牛序列里出现.达个子序列的长度是多少呢?
第1行输入两个整数N和K,接下来N行输入奶牛序列.
最短的不出现子序列.
14 5 1 5 3 2 5 1 3 4 4 2 5 1 2 3
3 样例说明 所有的长度为1和为2的子序列都出现.长度为3的序列“2,2,4”不出现
题解:这是一道很神的乱搞题。。。居然结果弄来弄去是完全连续块的个数+1
(完全连续块表示连续的某一段包含了所有的数字,比如样例(1,5,3,2,5,1,3,4),(4,2,5,1,2,3)可以分成两块,所以答案是2+1=3)
1 /**************************************************************
2 Problem: 3377
3 User: HansBug
4 Language: Pascal
5 Result: Accepted
6 Time:84 ms
7 Memory:304 kb
8 ****************************************************************/
9
10 var
11 i,j,k,l,m,n:longint;
12 a:array[0..20000] of longint;
13 begin
14 readln(n,m);l:=0;k:=1;
15 for i:=1 to n do
16 begin
17 readln(j);
18 l:=l+k-a[j];
19 a[j]:=k;
20 if l=m then
21 begin
22 inc(k);
23 l:=0;
24 end;
25 end;
26 writeln(k);
27 readln;
28 end.