题解：B4371 [GXPC-S 2025] 序列 / sequence

Mark_Pei · 2025-07-30 11:07:41 · 题解

Solution

我们需要构造一个由 n 个 1 和 m 个 0 组成的 01 字符串，满足以下条件：

• 所有子段的 K 的最大值恰好为 k，其中 K 是子段中 0 的数量减去子段中 1 的数量。

• 在所有满足条件的字符串中，选择字典序最小的那个。

要构造满足条件的字符串，我们需要确保贪心：

• 字典序最小的字符串应该尽可能将 0 放在前面。

• 为了确保所有子段的 K 的最大值是 k，我们需要控制 0 和 1 的分布，避免出现某个子段的 K 超过 k。

• 特别地，最长的连续 0 的子段会贡献最大的 K 值。因此，我们可以先放置 k 个连续的 0，这样这些 0 的子段的 K 就是 k。

• 然后，我们需要确保其他子段的 K 不超过 k。可以通过交替放置 1 和 0 来实现这一点。

构造方法：

1. 首先放置 k 个 0。这样，这 k 个 0 的子段的 K 就是 k。

2. 然后，将剩余的 0 和 1 以 10 的形式交替放置。这样，每个 10 对的 K 是 1 - 1 = 0，不会增加 K 的最大值。

3. 最后，如果还有剩余的 1，直接放在末尾。因为 1 会减少 K，所以不会影响最大值。

代码其实很短。

AC code

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=k;i++)// 第一步：输出 k 个 0
        cout<<0;
    m -= k; // 剩余的 0 的数量
    for(int i=1;i<=m;i++) // 第二步：交替输出 1 和 0，每次输出 "10"，共 m 次
        cout<<10;
    n -= m; // 剩余的 1 的数量
    for(int i=1;i<=n;i++)// 第三步：输出剩余的 1
        cout<<1;
    return 0;
}