CF1637B MEX and Array

Eason_AC · 2022-02-13 17:31:04 · 题解

Content

设我们有一个长度为 k 的数组 b，并且划分为了 c 段，每段为 [l_1,r_1],[l_2,r_2],\dots,[l_c,r_c]，满足 l_c=1，r_c=k，且 \forall i\in[2,c]，r_{i-1}+1=l_i。换句话说，数组 b 中的每一个元素都在恰好一段里面。

让我们定义数组 b 的如上划分的代价为

其中 \operatorname{MEX}(S) 为最小的没有出现在集合 S 中的非负整数。换句话说，如上划分的代价为划分的段数加上每一段的 \operatorname{MEX} 值。

现在，给定一个长度为 n 的数组 a，你需要求出其所有子段的最大代价的总和。我们称数组 y 是数组 x 的一个子段，当且仅当我们可以通过在数组 x 的开头和结尾删去连续的若干个元素得到数组 y。

数据范围：t 组数据，1\leqslant t\leqslant 30，1\leqslant n,\sum n\leqslant 100，0\leqslant a_i\leqslant 10^9。

Solution

由于 n 很小，我们考虑一种不用脑子的枚举子段的做法。首先肯定是得枚举子段，然后我们考虑如何计算每个子段的代价。

经过手玩样例不难发现，将一个数组全部划分为长度为 1 的子段的代价一定是最大的。因为每当一个子段的长度加 1，其能够分成的子段个数减少 1，而其 \operatorname{MEX} 值最多增加 1（很有可能不变），因此全部分成长度为 1 的子段的代价一定不会比其余方案的代价更小。然后我们发现，除了整个大的子段的长度对代价有贡献，所有长度 1 的子段中，只有单独一个 0 的 \operatorname{MEX} 值为 1，其余的都是 0。所以，对于一个大的子段 [l,r]，其最大代价为 r-l+1+cnt_0，其中 cnt_0 为大的子段 [l,r] 中 0 的个数。

然后就这么统计所有子段的最大代价就做完了。

Code

namespace Solution {
    const int N = 107;
    int n, Test, ans, a[N];

    void Main() {
        read(Test);
        while(Test--) {
            read(n);
            ans = 0;
            for(int i = 1; i <= n; ++i)
                read(a[i]);
            for(int i = 1; i <= n; ++i)
                for(int j = i; j <= n; ++j) {
                    int cnt = 0;
                    for(int k = i; k <= j; ++k)
                        if(!a[k])
                            cnt++;
                    ans += (j - i + 1 + cnt);
                }
            write(ans);
            puts("");
        }
        return;
    }
}