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

Yxa_Sheep · 2025-07-27 15:48:13 · 题解

题目传送门

题意

让一个序列中包含 n 个 1 与 m 个 0，使得/这个序列的每个子序列中/ 1 与 0 的数量的差/的最大值/为 k（多么精妙的断句）。记住，要输出字典序最小的。如果你是因为没看懂题意来看题解的话，请在评论区发一个 1 再回去写，也可以点个赞。

思路

这里要输出字典序最小的，于是我们很容易想到，尽量放 0，如果实在放不了了再放 1。
那么什么时候是放不了的呢？第一种是没有 0 了，我们可以每放一个 0，m 就减一，如果 m 等于 0 就放不了了。第二种我们可以用 x 记录下当前最大的 K（题目里这样叫的，见题目描述第二段开头），如果 x 小于 k（这个是输入时的 k，见输入格式），那么就可以放进去一个 1， x 也要加一。
其他具体细节见代码，这里不再赘述。

代码

#include <bits/stdc++.h>
#define code using
#define from namespace
#define Yxa_Sheep std
code from Yxa_Sheep;
int n, m, k, x;
string ans;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m >> k;
    while (n || m)
    {
        if (m && x < k)
            ans += '0', x++, m--;
        else
            ans += '1', x--, n--;
    }
    cout << ans;
    return 0;
}

题解来之不易，且看且珍惜。给个赞再走吧。

题目传送门