ACM(一)——FBI Tree

被迫无奈,在老师的一再要求下要把代码写在知乎专栏里投稿,既然为知乎写了一份,怎么能不在自己博客里放一份呢?

所以又开了一个新坑了——ACM

FBI Tree

题目描述

我们可以把由“0”和“1”组成的字符串分为三类:全“0”串称为B串,全“1”串称为I串,既含“0”又含“1”的串则称为F串。

FBI树是一种二叉树,它的结点类型也包括F结点,B结点和I结点三种。由一个长度为2^N的“01”串S可以构造出一棵FBI树T,递归的构造方法如下:

1. T的根结点为R,其类型与串S的类型相同;

2. 若串S的长度大于1,将串S从中间分开,分为等长的左右子串S_1​和S_2​;由左子串S_1​构造R的左子树T_1​,由右子串S_2​构造R的右子树T_2。

现在给定一个长度为2^N的“01”串,请用上述构造方法构造出一棵FBI树,并输出它的后序遍历序列。

输入格式

第一行是一个整数N(0≤N≤10),

第二行是一个长度为2^N的“01”串。

输出格式

一个字符串,即FBI树的后序遍历序列。

输入输出样例

输入 

3

10001011

输出 

IBFBBBFIBFIIIFF

说明/提示

对于40%的数据, N≤2;

对于全部的数据, N≤10。

noip2004普及组第3题


题解

递归实现:

#include<stdio.h>
int a;
char c,t;
char get(int n){
    if(n){
        if((t=get(n-1))!=get(n-1))  t='F';
    }
    else{
        do{
            scanf("%c",&c);
        }while(c=='\n'||c=='\r');
        if(c-48) t='I';
        else t='B';
    }
    printf("%c",t);
    return t;
}
int main(){
    scanf("%d",&a);
    get(a);
    return 0;
}

测试结果:

优点:

可以说是洛谷里时间最短、内存最小、代码量最少的 (“开挂”的除外)

1、运行时间短:洛谷测试耗时20ms,没有字符串的运算,处理速度更快。

2、占用内存小:洛谷测试消耗内存652Bytes,只定义了1个int,2个char和1个长度为3的char数组。

3、代码量少:只有340Bytes。

4、数据承受量大:没有开数组而是读一个字符处理一个,数据量越大,储存空间和字符串运算的时间开销相对越小,而且不用设置数组下标,所以只要不爆栈,对于N<231-1的所有数据都能应对自如。经测试N=20时,任务管理器监视内存消耗0.4MB,python监视时间消耗700ms左右。

缺点:

数据量大了之后可能会栈溢出

循环实现:

#include<stdio.h>
#include<stdlib.h>
int main(){
    int n,length,i=0;
    char h[3],*a=(char *)calloc(n,sizeof(char)),c;
    scanf("%d",&n);
    gets(h);
    while(i<=n){
        scanf("%c",&c);
        if(c-48) c='I';
        else c='B';
        int j=0;
        while(1){
            printf("%c",c);
            if(a[j]){
                if(c-a[j]) c='F';
                a[j++]=0;
            }
            else{
                a[j++]=c;
                break;
            }
        }
        i=j>i?j:i;
    }
    return 0;
}

测试结果:

优点:

1、运行速度快、内存占用小、对大数据更友好

2、比递归实现更好的地方:不会爆栈

缺点:

代码没有递归实现简洁,数据量大时运行速度没有递归快

 

Leave a Reply

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据