CF1003B Binary String Constructing

本文主要是介绍CF1003B Binary String Constructing，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

You are given three integers a a a , b b b and x x x . Your task is to construct a binary string s s s of length n=a+b n = a + b n=a+b such that there are exactly a a a zeroes, exactly b b b ones and exactly x x x indices i i i (where 1≤i<n 1 \le i < n 1≤i<n ) such that si≠si+1 s_i \ne s_{i + 1} si​≠si+1​ . It is guaranteed that the answer always exists.

For example, for the string "01010" there are four indices i i i such that 1≤i<n 1 \le i < n 1≤i<n and si≠si+1 s_i \ne s_{i + 1} si​≠si+1​ ( i=1,2,3,4 i = 1, 2, 3, 4 i=1,2,3,4 ). For the string "111001" there are two such indices i i i ( i=3,5 i = 3, 5 i=3,5 ).

Recall that binary string is a non-empty sequence of characters where each character is either 0 or 1.

输入输出格式

输入格式：

 

The first line of the input contains three integers a a a , b b b and x x x ( 1≤a,b≤100,1≤x<a+b) 1 \le a, b \le 100, 1 \le x < a + b) 1≤a,b≤100,1≤x<a+b) .

 

输出格式：

 

Print only one string s s s , where s s s is any binary string satisfying conditions described above. It is guaranteed that the answer always exists.

 

输入输出样例

输入样例#1： 复制

2 2 1

输出样例#1： 复制

1100

输入样例#2： 复制

3 3 3

输出样例#2： 复制

101100

输入样例#3： 复制

5 3 6

输出样例#3： 复制

01010100

说明

All possible answers for the first example:

• 1100;
• 0011.

All possible answers for the second example:

• 110100;
• 101100;
• 110010;
• 100110;
• 011001;
• 001101;
• 010011;
• 001011.

思路：对于x，x/2对0和1（n对0和1交错出现可以提供2*n-1个符合题意的ai），然后将剩余的0和剩余的1连续输出（提供1个符合条件的ai）若X为偶数输出顺序与原来相同，否则相反，这样就刚好是x个符合条件的ai了，需要注意的是，我们要优先将个数多的放在前面，例如，有10个1,5个0的话，我们先输出x/2个“10”，否则，输出x/2个“01”）

   

#include "iostream"using namespace std;int main(){int a,b,x,n;char u,v;cin>>a>>b>>x;n=a+b;if(a>b) u='0',v='1';else {u='1',v='0';swap(a,b);}for(int i=0;i<x/2;i++) {cout<<u<<v;a--,b--;}if(x%2==0){while(b--) cout<<v;while(a--) cout<<u;}else{while(a--) cout<<u;while(b--) cout<<v;}return 0;}

 

 

以上代码非本人所写，

下面的代码存在错输暂存

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<string>
#include<iostream>
using namespace std;
int a[2],x;
int main()
{string str="";scanf("%d%d%d",&a[0],&a[1],&x);if(x%2==0){if(a[0]<a[1]){while(a[1]--){a[0]--;str=str+"1";if(a[0]>=0)str=str+"0";}}else if(a[0]>=a[1]){while((a[0]--)>=0){a[1]--;if(a[0]==a[1]&&a[1]==0){str=str+"1";str=str+"0";break;}if(a[0]>=0)str=str+"0";if(a[1]>=0)str=str+"1";}}}else{if(a[0]<a[1]){while(a[0]--||a[1]--){str=str+"1";if(a[0]==1){str=str+"1";a[1]--;}if(a[0]>=0)str=str+"0";}}else if(a[0]>=a[1]){while((a[0]--)>=0){a[1]--;if(a[0]>0)str=str+"0";if(a[1]==1){str=str+"0";a[0]--;}if(a[1]>=0)str=str+"1";}}}cout<<str<<endl;return 0;
}

 

这篇关于CF1003B Binary String Constructing的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---