D. Genius‘s Gambit(很多情况)

Problem - D - Codeforces

已知三个整数a b k。求两个二进制整数z和y (æ > y)满足1. y都由a个0和b个1组成;2. X - y(也是二进制形式)恰好有k个1。z和y不允许使用前导零。输入唯一的一行包含三个整数a, b和k (0 <a;1 <b;0<k < a+b< 2- 105) -结果中0、1和1的个数。输出如果有可能找到两个合适的整数，打印“Yes”后面跟着以2为基数的z和y。否则打印“No”。如果有多个可能的答案，打印其中任何一个。

Examples

input

Copy

4 2 3

output

Copy

Yes
101000
100001

input

Copy

3 2 1

output

Copy

Yes
10100
10010

input

Copy

3 2 5

output

Copy

No

请注意在第一个例子中，= 1010002 = 25 + 23 = 4010,y = 1000012 = 25 +2°= 3310,4010 - 3310 = 710 = 22 +2 +2°= 1112。因此- y以2为底有3个1。在第二个例子中，= 101002 = 24 + 22 = 2010,y = 100102 = 24 + 2 = 18,2 - y = 20 - 18 = 210 = 102。这是1。在第三个例子中，你可能会发现，答案是不可能找到的。

题解:
题意很容易理解,关键是情况有很多,很难全部找出

首先我们应该知道最多可以构造出来多少个1

应该是a + b - 2个1

如果b >= 2

1100000.0

100000...1

这样肯定是最优的,最开始两位为0,其他全为1,如果有多余的1,填在1,2串相等的位置即可,就可以抵消

所以a+b - 2 < k不成立

但是会有一个特解0 1 0就是成立的

其次如果b = 1,k肯定应该等于0,由于数不能有前导0

还有a = 0,k也肯定等于0,全是1,相减肯定为0

剩下就是一般情况构造即可,思路类似构造最优情况

#include <cstdio>
#include <cstring>
#include <algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<map>
using namespace std;
int mod = 1e9 + 7;
typedef long long ll;
int x[200050];
int y[200050];
void solve()
{int a,b,k;cin >> a >> b >> k;if(a == 0&&b == 1&&k == 0){cout <<"YES\n1\n1";}else if(k > a + b - 2||(b == 1&&k != 0)||(a == 0&&k != 0)){cout <<"NO\n";}else{cout <<"YES\n";y[1] = 1;x[1] = 1;if(k <= a){for(int i = 2;i <= b;i++)x[i] = 1;for(int i = 2;i <= b - 1;i++){y[i] = 1;}y[b + k] = 1;}else{for(int i = 2;i <= b;i++){x[i] = 1;}for(int i = 2;i <= b;i++){y[i] = 1;}y[a+b] = 1;y[a+b-k] = 0;}for(int i = 1;i <= a+b;i++)cout << x[i];cout <<"\n";for(int i = 1;i <= a+b;i++)cout << y[i];}
}
//3 6 6
//111111000
//110111001
signed main()
{
//	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);int t = 1;
//	cin >> t;while(t--){solve();}
}