CF2065E 题解

ztd___ · 2025-02-10 09:22:15 · 题解

我在 CF2065 中的过题顺序：A，C1，E，D。是的你没有看错，我没有过掉 B，所以我认为该题比 B，C2，D 都简单，而 B 比 A，C1，D，E 都难。

考虑最简单的构造方案：显然对于一个字符串 S，如果里面全是 0 或 1，那么 S 的平衡值就是 S 的长度。

所以构造方案非常显然，先输出 k 个 0 或 1，然后剩下的按 10 或 01 交替输出，最后再输出剩下的就可以了。这样由前面的 k 个字符组成的子串的平衡值一定是 k。后面的 0 和 1 互相抵消，平衡值必然不会超过 k。

考虑判无解。如果 k > \max(n,m)，显然一开始的 k 个 0 或 1 是不够用的，无解。其次如果 k < \lvert n - m \rvert，那么整个字符串的平衡值会比 k 还大，无解。

代码也是非常简单。

#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int n, m, k;
        cin >> n >> m >> k;
        if (abs(n - m) > k || (k > n && k > m)) {
            cout << "-1\n";
        } else {
            if (n > m) {
                n -= k;
                for (int i = 0;i < k;i++) cout << "0";
                for (int i = 1;i <= min(n, m);i++) cout << "10";
                if (n < m) {
                    for (int i = 1;i <= m - n;i++) cout << "1";
                } else if (m < n) {
                    for (int i = 1;i <= n - m;i++) cout << "0";
                }
            } else {
                m -= k;
                for (int i = 0;i < k;i++) cout << "1";
                for (int i = 1;i <= min(n, m);i++) cout << "01";
                if (n < m) {
                    for (int i = 1;i <= m - n;i++) cout << "1";
                } else if (m < n) {
                    for (int i = 1;i <= n - m;i++) cout << "0";
                }
            }
            cout << "\n";
        }
    }
    return 0;
}