培训行业网站建设的重要性百搜科技
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();}
}