题目描述
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： 复制
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-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;
}