Codeforces Round #704 (Div. 2)题解_cf1492d genius's gambit

CF 1492D Genius’s Gambit 构造

题目就是给我们a个0，b个1. 现在问我们能不能构造出两个二进制串使得他们相减后的二进制串中有k个1 . 构造的二进制串不含有前导0

• • 分析：
    两个二进制串的长度是一样的 也就是a+b
    那么由二进制的性质我们可知
    举个例子 0010000- 0000001 可以得到 0001111 那么根据这个特点
    我们利用一对01，去构造这个差位，第一个串是比较大的那个数，那么他的第a+b位应该放0 第a+b-k位应该放1 ，也就是我们构造出来二进制位的差以此来构造我们所需要的k个1 .
    具体实现：
    首先要注意上述情况针对于k>=1 因为不能有前导0 所以1必定会占用1次，而且后面凑k位差的时候还需要1 所以1至少要用2次，0至少要用1次
    所以要判断 (a-1)+(b-2)+1是否大于k 这是中间填补的位置
    （具体见代码）

ll a[222222];
ll b[222222];
signed main()
{
    ll n,m,k;
    read(n);
    read(m);
    read(k);
    if(k==0)
    {
        printf("Yes\n");

        for(int i=1; i<=m; i++)
        {
            printf("1");
        }
        for(int i=1; i<=n; i++)
        {
            printf("0");
        }
        printf("\n");
        for(int i=1; i<=m; i++)
        {

            printf("1");
        }
        for(int i=1; i<=n; i++)
        {
            printf("0");
        }
        return 0;
    }
    if(n==0&&k!=0)
    {
        printf("No");
        return 0;
    }
    if(m==1&&k!=0)
    {
        printf("No");
        return 0;
    }
    if(m>=2&&n>=1)
    {
        ll om=m-2;
        ll on=n-1;
        if(om+on+1<k)
        {
            printf("No");
            return 0;
        }
        else
        {
            for(int j=n+m; j>=n+m-k; j--)
            {

                if(j==n+m)
                {
                    a[j]=0;
                    b[j]=1;
                    continue;
                }
                if(j==n+m-k)
                {
                    a[j]=1;
                    b[j]=0;
                    continue;
                }
                if(om>0)
                {
                    om--;
                    a[j]=1;
                    b[j]=1;
                    continue;
                }
                if(on>0)
                {
                    on--;
                    a[j]=0;
                    b[j]=0;
                    continue;
                }
            }
            for(int i=1; i<=n+m-k-1; i++)
            {
                if(i==1)
                {
                    a[i]=1;
                    b[i]=1;
                    continue;
                }
                if(om>0)
                {
                    om--;
                    a[i]=1;
                    b[i]=1;
                    continue;
                }

                if(on>0)
                {
                    on--;
                    a[i]=0;
                    b[i]=0;
                    continue;

                }

            }
            printf("Yes\n");
            for(int i=1; i<=n+m; i++)
            {
                printf("%lld",a[i]);
            }
            printf("\n");
            for(int i=1; i<=n+m; i++)
            {
                printf("%lld",b[i]);
            }
            return 0;


        }
        printf("No");
        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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130