求思路

灌水区

Dream__Sky @ 2023-05-15 16:42:54

4.梦里的难题

【问题描述】

生化危机血腥暴力的场面对小星星的冲击很大，晚上频繁地做起了梦，梦里他担负起拯

救世人消灭僵尸的重任，眼看就能拿到消除 T 病毒的解药还世界清静，但 T 病毒人工智能

电脑挡住了星星的去路，它声称研制出 T 病毒的目的是因为察觉人类智力退化，只有聪明

的人才能存活下来，如果想要拿到解药，必须回答出下面这个难题：

有 N(1≤N≤100000)个数字（由 1 到 K 组成，1≤K≤10000），排成一列形成数字串，例如

1,5,3,2,5,1,3,4,4,2,5,1,2,3 它包含了很多的子序列，比如(5)、(1,3,2)、(1,5,3)、(3,4,1,3)，请思 考该列数字串不包含的最短的由 1 到 K 组成的的子序列长度是多少？

【输入】

第一行输入两个整数 N 和 K，接下来 N 行分别输入这 N 个数字

【输出】

一个整数表示原数字串中不包含的最短子序列长度

【样例输入】

14 5

1

5

3

2

5

1

3

4

4

2

5

1

2

3

【样例输出】

3

【样例解释】

所有的长度为 1 和为 2 的子序列都存在。

长度为 1 的子序列有：（1）、（2）、（3）、（4）、（5）

长度为 2 的子序列有：（1,1）、（1,2）、（1,3）、（1,4）、（1,5）、（2,1）、（2,2）、（2,3）、（2,4）、（2,5）、 （3,1）、（3,2）、（3,3）、（3,4）、（3,5）、（4,1）、（4,2）、（4,3）、（4,4）、（4,5）、（5,1）、（5,2）、 （5,3）、（5,4）、（5,5）

长度为 3 的序列不全都有，例如：(2,2,4)

by impuk @ 2023-05-15 16:47:20

↑不会百度导致的

by Dream__Sky @ 2023-05-15 16:49:51

@impuk 看不懂

by Pizar @ 2023-05-15 17:33:33

您要不简述个题意

by int_4096andstr @ 2023-05-15 17:43:35

同意楼上

by Big_Dinosaur @ 2023-05-15 18:36:24

40pts

统计每一个数个数求最小值。

by Dream__Sky @ 2023-05-15 19:53:14

@zhouyitao123 zyt，你会满分思路吗

by Big_Dinosaur @ 2023-05-15 19:56:54

@Dream__Sky 在考场上，我40，现在我找到了一年前满分代码：

#include<bits/stdc++.h>
using namespace std;
int a,n,g[100001],i,k,o=1,t;
void fu1(){for(int i=1;i<=k;i++)g[i]=1;}
int main(){
    cin>>n>>k;
    t=k;
    fu1();
    for(i=1;i<=n;i++){
        cin>>a;
        if(g[a]){
            g[a]=0;
            t--;
            if(t==0){
                ++o;
                fu1();
                t=k;
            }
        }
    }
    cout<<o;
}

by Dream__Sky @ 2023-05-15 20:11:21

@zhouyitao123 okok我研究研究

by Big_Dinosaur @ 2023-05-15 20:25:18

Here（征求测试点）

by Dream__Sky @ 2023-05-15 22:31:04

@zhouyitao123 我到时候做一个

| 下一页