题解：P11638 Max,Mex

M1__ · 2025-01-29 20:14:25 · 题解

题解：P11638 Max,Mex

题目传送门

前置知识

思路

本题中定义 \max\{S\} 为 S 中的最大值，\operatorname{mex}\{S\} 为 S 中最小没出现过的自然数。一次操作你可以选定一个 (i,j)，满足 1\le i,j\le n 以及 i\neq j，令 x=\max\{a_i,a_j\}，y=\operatorname{mex}\{a_i,a_j\}，那么 a_i=x，a_j=y。

subtask 1&2

• 对于 subtask1 与 subtask2，直接输出 sum 即可。证明如下：

  • 当 a_i \ge 2 时，\operatorname{mex}\{a_i,a_j\}=0，即 a_j=0，对 \sum_{i=1}^n a_i 没有贡献，所以不需要进行操作，在代码中进行特判即可。这样可拿到 [10,30] 分。

    subtask 3&4

• 对于 subtask3 与 subtask4，因为无特殊性质，所以需要判断关于 \operatorname{mex}\{a_i,a_j\} 的所有情况，求出他们分别对 \sum_{i=1}^n a_i 的贡献值并得出规律。

• 我们会发现如下规律：

  • 对于一个操作，不论是 \operatorname{mex}\{a_i,a_j\} 还是 \max\{a_i,a_j\}，只要 a_i,a_j \ge 2 时，根据 subtask 1&2 的结论，再进行操作显然对 \sum_{i=1}^n a_i 没有贡献，所以我们只需统计数列中小于 2 的个数和大于等于 2 的数之和，并求出小于 2 的数的最大贡献值即可。
  • 因此，对于一组 a_i,a_j 有以下几种情况：
    • 当 a_i=0,a_j=0 时，令 a_j=\operatorname{mex}\{0,0\}=1。此时 a_i=0,a_j=1。
    • 当 a_i=0,a_j=1 时，令 a_i=\max\{0,1\}=1，a_j=\operatorname{mex}\{0,1\}=2。此时 a_i=1,a_j=2。
    • 当 a_i=1,a_j=2 时，令 a_i=\max\{1,2\}=2，a_j=\operatorname{mex}\{2,2\}=0。此时 a_i=2,a_j=0。显然对 \sum_{i=1}^n a_i 没有贡献，所以这个操作要舍去。
  • 综上，我们一共操作了三次，操作过后结果为 a_i=1,a_j=2，此时贡献值为 1+2=3。
  • 因此，我们可以推导出 subtask 3&4 的通项公式。即对于 cnt 个 0，ans 个 1，最后会有 cnt+ans-1 个数操作成 2，剩下的一个数无法进行操作，即为 1。即对于小于等于 2 的 a_i,a_j，最大贡献次数为： 2 \times ((cnt+ans)-1)+1
  • 因此，subtask 3&4 的通项公式为： \sum _{i=1}^n a_i+2 \times ((cnt+ans)-1)+1-ans

    即：

    \sum _{i=1}^n [a_i\neq 0 \wedge a_i \neq 1 ]+2 \times cnt + ans-1

    关于hack数据

    事实上，这是本代码的一个小 Bug。
    当 n=1,a_i=0 时，因为之前 cnt 记录 0 的个数时，cnt 便不会为 0，因此卡过了上文中的关于 subtask1 的部分。所以只要在这之前进行特判便没有问题了。

    代码实现

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll cnt,ans,sum,n,a;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a;
        sum+=a;
        if(n==1){
            cout<<a;
            return 0;
        }
        if(a==0) cnt++;
        if(a==1) ans++;
    }
    if(cnt+ans==0) cout<<sum;
    else cout<<cnt*2+ans+sum-1;
    return 0;
}

本题思维难度略大，代码实现方面比较简单。