题目: https://codeforces.ml/contest/1492/problem/D
题意:用a个0和b个1来构造x和y,使得x - y 的二进制表示1的个数为k。
分析:
构造方法:
1 1 ***********0
1 0 ***********1
首先把最前面必须放一个1,这是保证前置不为0的要求。
另外再选一个1和一个0,将他们分别放置,拉开一个k的距离,这样在这个k - 1的范围内,无论是填1还是0都是没有影响的。
No的情况是挑不出两个1或者是一个0或者是第二次挑选之间的距离不够。
另外k == 0 的情况比较特别,需要特判。
代码:
#include <bits/stdc++.h>
#define lowbit(x) x&(-x)
using namespace std;
typedef long long ll;
typedef pair<int, int > PII;
const ll llINF = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;
const int mod = 100003;
const int N = 2e5 + 50;
int a, b, k;
int x[N], y[N];
int main()
{
scanf("%d%d%d", &a, &b, &k);
int n = a + b;
if (k == 0) {
printf("Yes\n");
for (int i = 1; i <= n; i++) {
if (b) x[i] = 1, b--;
else if (a) a--;
}
for (int i = 1; i <= n; i++)
printf("%d", x[i]);
printf("\n");
for (int i = 1; i <= n; i++)
printf("%d", x[i]);
printf("\n");
} else if (a + b - 3 < k - 1 || b < 2 || a < 1) printf("No\n");
else {
x[1] = 1, y[1] = 1; b--;
x[2] = 1, y[2 + k] = 1; b--, a--;
for (int i = 3; i <= n; i++) {
if (i == 2 + k) continue;
if (a) a--;
else if (b) x[i] = y[i] = 1, b--;
}
printf("Yes\n");
for (int i = 1; i <= n; i++)
printf("%d", x[i]);
printf("\n");
for (int i = 1; i <= n; i++)
printf("%d", y[i]);
printf("\n");
}
return 0;
}