Codeforces Round #704 (Div. 2) Genius‘s Gambit_c - genius's gambit

传送门
一、题意： 给出a个0和b个1，组合出两个含有a个0和b个1的数的二进制形式，并且最高位不为0，问是否存在两个数相减的结果中含有k个1。若存在输出Yes和这两个数，否则No。
二、思路： 经过构造样例可以发现一个规律:
1…0
0…1
假设该数二进制长度为len，省略号位置若对应的位置同为1或者同为0，此时相减将会得到len-1个1。
所以只需要能够构造出一个长度为k+1的字段，就存在这样的两个数字。
cpp代码

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<vector>
#include<queue>
#include<stack>
#include<string>
#include<set>
#include<cmath>
#include<map>
#define ll long long
using namespace std;
const ll mod = 998244353;
const int inf = 1e9 + 7;
int ans1[200005], ans2[200005];
int main()
{
	int a, b, k;
	cin >> a >> b >> k;
	if (k == 0) {
		printf("Yes\n");
		for (int i = 1; i <= b; i++)printf("1");
		for (int i = 1; i <= a; i++)printf("0");
		printf("\n");
		for (int i = 1; i <= b; i++)printf("1");
		for (int i = 1; i <= a; i++)printf("0");
	}
	else if (k > a + b - 2||b<2||a<1)printf("No");
	else {
		int flag = 0;
		for (int i = 1; i <= b; i++)ans1[i] =ans2[i]= 1;
		for (int i = b+1; i <= a+b; i++)ans1[i]=ans2[i] = 0;
		for (int i = 2; i <= a+b; i++) {
			if (ans2[i + k] == 0&&ans2[i]==1) {
				flag = 1;
				swap(ans2[i], ans2[i+k]);
				break;
			}
		}
		if (!flag)printf("No");
		else {
			printf("Yes\n");
			for (int i = 1; i <= a + b; i++)printf("%d", ans1[i]);
			printf("\n");
			for (int i = 1; i <= a + b; i++)printf("%d", ans2[i]);
		}
	}
	return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52