CF1003B Binary String Constructing 数学规律

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

题目描述

You are given three integers aa , bb and xx . Your task is to construct a binary string ss of length n = a + bn=a+b such that there are exactly aa zeroes, exactly bb ones and exactly xx indices ii (where 1 \le i < n1≤i<n ) such that 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 ii such that 1 \le i < n1≤i<n and s_i \ne s_{i + 1}si≠si+1 ( i = 1, 2, 3, 4i=1,2,3,4 ). For the string "111001" there are two such indices ii ( i = 3, 5i=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 aa , bb and xx ( 1 \le a, b \le 100, 1 \le x < a + b)1≤a,b≤100,1≤x<a+b) .

输出格式：

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

输入输出样例

输入样例#1：复制

2 2 1

输出样例#1：复制

输入样例#2：复制

3 3 3

输出样例#2：复制

输入样例#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-1个，还是不行，最后看别人网上的，才知道有个规律。

我们先假设a>b

如果给你个x，那么你至少需要x/2个01,然后发现如果x为奇数（x=5, 0101），那么会少两个不同点：如果x为偶数，那么会少一个不同点(x=6, 010101)。

X偶数时，肯定要01后加1，输出完1，在输出0.这样就可以获得一个不同点。

x奇数时，肯定要01后加0，输出完0，在输出1.这样也可以获得两个不同点。

注意只有0比较多的时候才能输出01，不然就是10.

改变题目条件：

打印出全部符号要求的公式，我的全排列就有用了。

教训:

题目规律要先找。

代码实现

#include<cstdio>  
#include<cstring>  
#include<cstdlib>  
#include<cctype>  
#include<cmath>  
#include<iostream>  
#include<sstream>  
#include<iterator>  
#include<algorithm>  
#include<string>  
#include<vector>  
#include<set>  
#include<map>  
#include<stack>  
#include<deque>  
#include<queue>  
#include<list>  
using namespace std;  
const double eps = 1e-8;  
typedef long long LL;  
typedef unsigned long long ULL;  
const int INF = 0x3f3f3f3f;  
const int INT_M_INF = 0x7f7f7f7f;  
const LL LL_INF = 0x3f3f3f3f3f3f3f3f;  
const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f;  
const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1};  
const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1};  
const int MOD = 1e9 + 7;  
const double pi = acos(-1.0);  
const int MAXN=5010;  
const int MAXM=100010;
const int M=50010;int main()
{int a,b,w;while(scanf("%d%d%d",&a,&b,&w)!=EOF){int sum=a+b;int x,y;if(a<=b){swap(a,b);x=1,y=0;  }else {x=0,y=1;}for(int i=0;i<w/2;i++){cout<<x<<y;a--;b--;}if(w%2==0){while(b--) cout<<y;while(a--) cout<<x;}else{while(a--) cout<<x;while(b--) cout<<y;}cout<<endl;}return 0;
}

全排列代码实现：

#include<cstdio>  
#include<cstring>  
#include<cstdlib>  
#include<cctype>  
#include<cmath>  
#include<iostream>  
#include<sstream>  
#include<iterator>  
#include<algorithm>  
#include<string>  
#include<vector>  
#include<set>  
#include<map>  
#include<stack>  
#include<deque>  
#include<queue>  
#include<list>  
using namespace std;  
const double eps = 1e-8;  
typedef long long LL;  
typedef unsigned long long ULL;  
const int INF = 0x3f3f3f3f;  
const int INT_M_INF = 0x7f7f7f7f;  
const LL LL_INF = 0x3f3f3f3f3f3f3f3f;  
const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f;  
const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1};  
const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1};  
const int MOD = 1e9 + 7;  
const double pi = acos(-1.0);  
const int MAXN=5010;  
const int MAXM=100010;
const int M=50010;int main()
{int a,b,x;while(scanf("%d%d%d",&a,&b,&x)!=EOF){int i;int n[210];for( i=0;i<a;i++)n[i]=0;for(;i<a+b;i++)n[i]=1;do{int ans=0;for(int j=0;j<a+b-1;j++){if(n[j]!=n[j+1])ans++;}	if(ans==x) break;}while(next_permutation(n,n+a+b));for(i=0;i<a+b;i++)cout<<n[i];cout<<endl;}return 0;
}

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