ACM学习历程——hihoCoder挑战赛10A 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

 

由于不能存在001和11，故只能10101交叉。故任意两个1之间必定需要一个0，故1的数目不能大于0的数目加1.又由于需要字典树最小的，故在前提满足的情况下把一个0放到第一位，然后全补后串后面。于是需要特判能否在第一位放一个0.

 

代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>

using namespace std;

int n, m;

int main()
{
    //freopen("test.txt", "r", stdin);
    int num0, num1;
    while (scanf("%d%d", &n, &m) != EOF)
    {
        if (m > n+1)
        {
            printf("NO\n");
            continue;
        }
        num0 = n - m + 1;
        if (m == 0)
            num0--;
        num1 = m;
        if (num0 > 0)
        {
            printf("0");
            num0--;
        }
        for (int i = 0; i < num1; ++i)
        {
            if (i == 0)
                printf("1");
            else
                printf("01");
        }
        for (int i = 0; i < num0; ++i)
            printf("0");
        printf("\n");
    }
    return 0;
}