蓝桥杯算法训练VIP-s01串 （C语言代码）

解题思路:
刚开始，要求s01串，不复杂，只有两种变换方式，输入数据的规模也不大，用两个数组，从一个数组里读取当前需要变换的子串，另一个数组不断往后增加变换得到的新串，就能逐步变换；可是，算法的时间和空间怎样限定呢？对空间，逐步探测，先假设串长只有1000个字符，输入n为15时，计算得到串长为987，输入n为16时，超出了1000个字符，发生段错误，再增设串长在10000个字符以内，输入n为16时，串长为1597，输入n为19时，串长为6765，未发生段错误。空间限定好以后，再看时间，这里的特别之处在于计时函数clock()的使用，函数返回自程序开始运行的处理器时间，如果无可用信息，返回-1，返回值除以CLOCKS_PER_SEC得到的值以“秒”为单位(注: 如果编译器是POSIX兼容的, CLOCKS_PER_SEC定义为1000000)，输入n为19，求s01串，时间用了0.03秒，满足题目的要求。

注意事项:
每次在求变换后的新串前，都需要初始化接受新串的字符数组：sb[0]设置为'\0'，这样新串才正确并不会超长。

参考代码:

#include<stdio.h>
#include<string.h>
#include<time.h>
int main(){
    int i,n;
    char sa[10000],sb[10000];
    scanf("%d",&n);
    sa[0]='0';sa[1]='\0';sb[0]='\0';                //s01串初始为"0"
    while(n--){                                     //n次变换
        for(i=0;sa[i]!='\0';i++){                   //从a串中取出子串
            if(sa[i]=='0') strcat(sb,"1");          //若为"0"就往新串后加"1"
            else if(sa[i]=='1') strcat(sb,"01");    //若为"1"就往新串后加"01"
        }
        strcpy(sa,sb);                              //为下次变换记录中间结果
        sb[0]='\0';
    }
    printf("%s\n%d\n",sa,strlen(sa));
    printf("Time used = %.2lf\n",(double)clock()/CLOCKS_PER_SEC);
    return 0;
}