题解：P14130

Silver_winter · 2025-10-02 15:06:24 · 题解

题目传送门

首先梳理一下题目：

有一个长度为 n 的非负整数序列 a_1, \ldots, a_n。

你需要将这个序列划分为尽可能多个子序列，使得：

• 每个子序列至少包含一个元素；
• 每个元素至少被划分进了一个子序列；
• 没有两个子序列包含重复的元素；
• 每个子序列的 \operatorname*{mex} 都不为 0。

先分析第一个条件：每个子序列至少包含一个元素。这意味着不能有空序列。

第二个条件和第三个条件：每个元素至少被划分进了一个子序列；没有两个子序列包含重复的元素。声明了每个元素都必定会有其归属的子串，而一个元素不能同时出现在两个子串里面。

第四个条件，也是最重要的条件：每个子序列的 \operatorname*{mex} 都不为 0。而非负整数序列的 \operatorname*{mex} 的定义为该序列中没有出现过的最小非负整数。换句话说就是每个子序列中最小的残缺数字绝对不会是0，我们又知道 \operatorname*{mex} 的值不为负数，可以得出这句话的隐含意思是：每个子串都有一个及以上的 0。

剩下的就好办了，就像是切一个西瓜来分，要保证每一份的西瓜都至少有一个西瓜籽，请问最多能分多少份西瓜？

这很容易，肯定是一份西瓜一个西瓜籽，以此类推，题目中就是一个 0 一个子串，那么解法就是求出序列中 0 的数量。

代码很简单，但还是摆一下：

#include<bits/stdc++.h>
using namespace std;
int t;
int x;//只用一次，所以没定义数组
int y;
int main(){
    cin>>t;
    for(int i=1;i<=t;i++){
        cin>>x;
        if(x==0)y++;//累计0的数量
    }
    cout<<y;//直接输出
    return 0; 
}