本文主要是介绍#1144 : 01串 ( 按条件排除即可+简单模拟 ),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
#1144 : 01串
时间限制:7000ms
单点时限:1000ms
内存限制:256MB
描述
给定两个整数n和m,求是否存在恰好包含n个0和m个1的01串S,使得S中不存在子串"001"和"11"。
如果存在符合条件的01串则输出字典序最小的S,否则输出NO。
输入
一行两个整数,表示n和m。(0<=n,m<=100000,0<n+m)
输出
一行一个字符串,为字典序最小的S或者NO。
样例输入
2 3
样例输出
10101
相当于排列组合的插空法,题目说不能有11,和001,那么我们可以这样考虑_1_1_1......在空的地方填0,
具体见代码注释
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<bits/stdc++.h>
using namespace std;
template<class T>inline T read(T&x)
{char c;while((c=getchar())<=32)if(c==EOF)return 0;bool ok=false;if(c=='-')ok=true,c=getchar();for(x=0; c>32; c=getchar())x=x*10+c-'0';if(ok)x=-x;return 1;
}
template<class T> inline T read_(T&x,T&y)
{return read(x)&&read(y);
}
template<class T> inline T read__(T&x,T&y,T&z)
{return read(x)&&read(y)&&read(z);
}
template<class T> inline void write(T x)
{if(x<0)putchar('-'),x=-x;if(x<10)putchar(x+'0');else write(x/10),putchar(x%10+'0');
}
template<class T>inline void writeln(T x)
{write(x);putchar('\n');
}
//-------ZCC IO template------
const int maxn=1000001;
const double inf=999999999;
#define lson (rt<<1),L,M
#define rson (rt<<1|1),M+1,R
#define M ((L+R)>>1)
#define For(i,t,n) for(int i=(t);i<(n);i++)
typedef long long LL;
typedef double DB;
typedef pair<int,int> P;
#define bug printf("---\n");
#define mod 1000000007int main()
{//#ifndef ONLINE_JUDGE//freopen("in.txt","r",stdin);//freopen("zccccc.txt","w",stdout);//#endif // ONLINE_JUDGEint n,m,i,j,t,k;while(read_(n,m)){if(m-n>=2||(n==0&&m==0))//1比0个数多于2个以上,那么无论怎么放0,肯定有11在一起,puts("NO");else if(m-n==1)//1比0 多一个,只能在1之间放0{For(i,0,(n+m)/2)printf("10");printf("1\n");}else if(n-m==1)//0比1多一个,在0之间放1{For(i,0,(n+m)/2)printf("01");printf("0\n");}else if(n==m)//相等就是01的循环{For(i,0,n)printf("01");printf("\n");}else//0比1多余1个,那么要避免001,就得把01尽可能的放在前面{For(i,0,m)printf("01");For(i,0,n-m)printf("0");printf("\n");}}return 0;
}
这篇关于#1144 : 01串 ( 按条件排除即可+简单模拟 )的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!