老牌网站建,广州宣传片制作,wordpress不显示中文图片,怎么做cc网站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;0k ab 2- 105) -结果中0、1和1的个数…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;0k ab 2- 105) -结果中0、1和1的个数。输出如果有可能找到两个合适的整数打印“Yes”后面跟着以2为基数的z和y。否则打印“No”。如果有多个可能的答案打印其中任何一个。
Examples
input
Copy
4 2 3output
Copy
Yes
101000
100001input
Copy
3 2 1output
Copy
Yes
10100
10010input
Copy
3 2 5output
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串相等的位置即可,就可以抵消
所以ab - 2 k不成立
但是会有一个特解0 1 0就是成立的
其次如果b 1,k肯定应该等于0,由于数不能有前导0
还有a 0,k也肯定等于0,全是1,相减肯定为0
剩下就是一般情况构造即可,思路类似构造最优情况
#include cstdio
#include cstring
#include algorithm
#includeiostream
#includevector
#includeset
#includemap
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 0b 1k 0){cout YES\n1\n1;}else if(k a b - 2||(b 1k ! 0)||(a 0k ! 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[ab] 1;y[ab-k] 0;}for(int i 1;i ab;i)cout x[i];cout \n;for(int i 1;i ab;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();}
}
