洛谷 P5093 [USACO04OPEN]The Cow Lineup

题目相关

题目链接：洛谷 P5093 [USACO04OPEN]The Cow Lineup

题目描述：

  约翰的 $N$ ( $1 \leq N \leq 100000 $ )只奶牛站成了一列。每只奶牛都写有一个号牌，表示她的品种，号牌上的号码在 $1 \ldots K $ ( $1 \leq K \leq 10000$ )范围内。
  比如有这样一个队列：1,5,3,2,5,3,4,4,2,5,1,2,3。
  根据约翰敏锐的数学神经，他发现一些子序列在这个队列里出现，比如”3,4,1,3”，而另一些没有。子序列的各项之间穿插有其他数，也可认为这个子序列存在。现在，他想找出一个最短的子序列，使之不在奶牛序列里出现。达个子序列的长度是多少呢？

输入输出格式：

输入格式：
  第1行输入两个整数 $N$ 和 $K$ ，接下来 $N$ 行输入奶牛序列。
输出格式：
  输出一行，最短的不出现子序列的长度。

输入输出样例：

输入#1	输出#1
14 5 1 5 3 2 5 1 3 4 4 2 5 1 2 3	3

说明：

样例解释：
  所有长度为1和2的可能的子序列都出现了，但长度为3的子序列”2,2,4”却没有出现。
数据范围：
  $1 \leq N \leq 100000 $,$1 \leq K \leq 10000$

博主乱搞

蒟蒻解析：

  想要直接找到不存在的最短序列存在困难，我们转变思路：寻找最长的全排列（注：这里的全排列指的是所有的可能排列都包括在内），结果即为长度+1。
  我们对整个序列从左到右划分，一旦所有 $K$ 个数字出现我们就把其之前化为一组，继续寻找下一组。假设最后一共划分了 $m$ 组（最后可能剩下一些元素不属于任何一组）。我们有如下结论：确保长度为 $m$ 及更短的序列的所有排列都存在的条件是划分了至少 $m$ 组。
  证明？显然对于所有组，$K$ 个数字中每一个数字都出现了一次，所以长度为 $m$ 及更短的序列一定出现过（在 $G_1,G_2, \cdots ,G_m$ 中分别取特定的一个拼成）。虽然存在长度大于 $m$ 的序列存在，但要求包括所有的序列，则要求 $K$ 中每一个数字必须至少出现一次，对于划分了 $m$ 组的数据来说，实现 $m+1$ 的全部可能组合是矛盾的，如果出现了 $m+1$ 的所有可能，则必定有新的一组出现。
  然后这道题的想法就简单了：答案为划分的组数+1。

蒟蒻代码：

cpp

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define il inline
il int read(){
    int x=0,f=1; char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1; ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+ch-'0'; ch=getchar();
    }
    return x*f;
}
int n,k,r;
int vis[10010],tot;
int ans;
int main(){
    n=read(); k=read();
    for (int i=1;i<=n;++i){
        r=read();
        if (!vis[r]){
            vis[r]=1; tot++;
            if (tot==k){
                ++ans; tot=0;
                memset(vis,0,sizeof(vis));
            }
        }
    }
    printf("%d",ans+1);
    return 0;
}