Codeforces Round #704 (Div. 2) D. Genius‘s Gambit（构造+思维）

Codeforces Round #704 (Div. 2) D. Genius’s Gambit（构造+思维）

D. Genius’s Gambit

题意

/*
构造两个串x、y，每个串由a个0和b个1构成，不包含前导零
同时x-y包含不超过k个1
*/

1
2
3
4
5

思路

/*
很常见的一种构造01串，我们知道不能包含前导零，所以x、y串第一个字符一定是1
随后特判掉三种特殊情况：
      ①  不包含0的情况：全为1，所以k必须为0
      ②  不包含1的情况(去除第一个1之后)：全为0，所以k必须为0
      ③  k大于最大可以构成的情况：最多情况为x串第二个是1，y串第二个是0，
      							且x串最后一个是0，y串最后一个是1
      							形如：(1)为第一个1，保证无前导零
      							x串：(1)10000
                      y串：(1)00001  k=4
剩下的1，就全部在x、y串相同位置都有就行了，这样相减也会抵消掉
                      形如：(1)为第一个1，保证无前导零
                      x串：(1)10110
                      y串：(1)00111  k=4
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int a,b,k,num,sum;
bool x[N],y[N];

int main(){
    scanf("%d%d%d",&a,&b,&k);
    x[1]=y[1]=true; b--;//x、y串第一个字符一定是1
    sum=a+b;
    if(a==0){//①
        if(k==0){
            puts("Yes");
            printf("1"); for(int i=1;i<=sum;i++) printf("1"); printf("\n");
            printf("1"); for(int i=1;i<=sum;i++) printf("1"); printf("\n");
        }
        else puts("No");
        return 0;
    }
    if(b==0){//②
        if(k==0){
            puts("Yes");
            printf("1"); for(int i=1;i<=sum;i++) printf("0"); printf("\n");
            printf("1"); for(int i=1;i<=sum;i++) printf("0"); printf("\n");
        }
        else puts("No");
        return 0;
    }
    if(k>sum-1){puts("No");return 0;}//③
    int num=2+k,idx=3;
    x[2]=y[num]=true; b--;
    while(b){
        if(idx==num) idx++;//num位置y串为1了，x串不能为0
        else{
            x[idx]=y[idx]=true;//x串、y串相同位置为1
            idx++;
            b--;
        }
    }
    puts("Yes");
    for(int i=1;i<=sum+1;i++){
        if(x[i]) printf("1");
        else printf("0");
    }
    puts("");
    for(int i=1;i<=sum+1;i++){
        if(y[i]) printf("1");
        else printf("0");
    }
    puts("");
    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
53
54