题目出处:codeforces 401C
题目描述
你有 (n(1 le n le 10^6)) 个字符‘0’ 和 (m(1 le m le 10^6)) 个字符‘1’。你需要使用这些字符拼接成一个01字符串,使得满足如下两个条件:
- 字符串中不能出现连续的两个‘0’;
- 字符串中不能出现连续的三个‘1’。
请问这样的字符串能够拼接出来。
如果不存在这样的拼接方案,输出“-1”;否则,输出所有拼接方案中字典序最小的方案。
比如,如果 (n=1,m=2) ,此时可选的方案有“011”、“101”、“110”,其中字典序最小的方案是“011”,所以输出“011”。
输入格式
输入一行包含两个正数 (n) 和 (m(1 le n,m le 10^6)) ,以一个空格分隔,分别用于表示字符‘0’和‘1’出现的次数。
输出格式
如果不存在合法的拼接方案,输出“-1”;否则,输出字典序最小的拼接结果。
样例输入1
1 2
样例输出1
011
样例输入2
2 2
样例输出2
0101
样例输入3
3 2
样例输出3
01010
样例输入4
4 2
样例输出4
-1
题目分析
首先,在 (n) 已经确定的情况下, (m) 的取值范围是:
- 最小值 (n-1) ,此时相当于在每两个相邻的‘0’之间插入一个‘1’;
- 最大值 (2 imes (n+1)) ,此时相当于在每两个相邻的‘0’之间插入两个‘1’,同时在最左边的那个‘0’的左边插入两个‘1’,在最右边的那个‘0’的右边插入两个‘1’。
所以,入门满足 (n-1 le m le 2 imes (n+1)) 的条件,我们才能继续判断;如果不满足这个条件,说明没有结果,输出“-1”即可结束。
在存在解的情况下,首先我们要判断 (m gt 2 imes n) 是否成立,如果成立的话所有最前面的那个‘0’前面有 (m - 2 imes n) 个 ‘1’,需要先输出这几个‘1’。然后我们每次去判断 (m == 2 imes n) 是否成立,如果成立则输出“011”,m -=2; n--; 否则,输出“01”, m--,n--; 当然我们要注意,在最后一个‘0’后面可能没有‘1’了,所以还需要判断一下当前的m是否已经等于0了,如果 (m = 0) ,则说明最后一个‘0’后面没有‘1’,则最后一个‘0’后面不需要输出‘1’。
实现代码如下:
#include <bits/stdc++.h>
using namespace std;
int n, m;
int main() {
cin >> n >> m;
if (m >= n-1 && m <= 2*(n+1)) {
while (m > 2*n) { putchar('1'); m --; }
while (n) {
int c = (m == 2*n) ? 2 : 1;
c = min(c, m);
n --;
m -= c;
putchar('0');
while (c --) putchar('1');
}
}
else {
cout << -1 << endl;
}
return 0;
}