专栏文章

CF2065E 题解

zztd___
CF2065E题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@miqall21
此快照首次捕获于
2025/12/04 01:40
3 个月前
此快照最后确认于
2025/12/04 01:40
3 个月前
查看原文
我在 CF2065 中的过题顺序：A，C1，E，D。是的你没有看错，我没有过掉 B，所以我认为该题比 B，C2，D 都简单，而 B 比 A，C1，D，E 都难。
考虑最简单的构造方案：显然对于一个字符串 SS，如果里面全是 00 或 11，那么 SS 的平衡值就是 SS 的长度。
所以构造方案非常显然，先输出 kk 个 00 或 11，然后剩下的按 1010 或 0101 交替输出，最后再输出剩下的就可以了。这样由前面的 kk 个字符组成的子串的平衡值一定是 kk。后面的 00 和 11 互相抵消，平衡值必然不会超过 kk。
考虑判无解。如果 k>max⁡(n,m)k > \max(n,m)，显然一开始的 kk 个 00 或 11 是不够用的，无解。其次如果 k<∣n−m∣k < \lvert n - m \rvert，那么整个字符串的平衡值会比 kk 还大，无解。
代码也是非常简单。
CPP
#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;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...