D. Genius‘s Gambit 构造题+思维

题目: 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;
}

上一篇:Codeforces Round #704 (Div. 2) D. Genius‘s Gambit


下一篇:D. Genius‘s Gambit(二进制构造+细节)