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

Solution

• 所有子段的 $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$，所以不会影响最大值。

#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;
}