星星灰暗着。

星星灰暗着。

你所见的的确是一个NOIp退役OIer的博客。

题解 P1305 【新二叉树】

posted on 2017-06-08 16:55:15 | under 题解 |

我觉得题解不少人写得比较复杂,这个题目总的来说要点有三个:

①构造二叉树,这里需要注意的是n的范围没有给出,我一开始以为26个字母只会出现一次就只弄了100的数组,但结果就爆了,所以我开了10000,对于这个题目来说常数可以了;

②三四行的前序遍历

③洛谷专属(但其实好像是Linux评测系统?)输入格式,吞换行字符不能只getchar,这里建议C/C++党用C++的getline,会快一些(毕竟string类方便)

然后就是代码

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#define f(i,a,b) for(i=a;i<=b;++i)
using std::cin;
using std::string;//不太建议using namespace std
int n;
char a[10010];
string s;
void preorder(int i)
{
    if(a[i]==0)return;
    if(a[i]!='*')printf("%c",a[i]);
    preorder(i<<1);//位运算,表示i*2,下面表示i*2+1,这样快一些
    preorder(i<<1|1);
}
int main()
{
    int i,j;
    scanf("%d",&n);
    string instead;
    getline(cin,instead);//吞换行
    getline(cin,s);//第一个直接进去
    a[1]=s[0],a[2]=s[1],a[3]=s[2];
    f(i,2,n)
    {
    getline(cin,s);
    f(j,1,10000)if(a[j]==s[0])a[j<<1]=s[1],a[j<<1|1]=s[2];//拼常数
    }
    preorder(1);//根节点1
}