[题解]P1087 FBI树
USSENTERPRISE · · 题解
-
0. 前言
题目传送门
看到这道题，我的脑子中蹦出来了一个毒瘤想法,此题为线段树树的遍历
可能太毒瘤了，机房高二学长一直在想如何hack掉我的代码
(如果有大佬能hack掉我的代码，请私信我，把数据发过来，谢谢}
-
1. 思路
首先，很明显，此题字符串的处理运用了二分的思想
很像线段树不是吗？
所以就有了建树方法
inline void pushup(int now){
if(tree[ls]=='F'||tree[rs]=='F'){ tree[now]='F'; return;}
if(tree[ls]==tree[rs]){ tree[now]=tree[ls]; return;}
tree[now]='F';
}
inline void build(int now,int l,int r){
if(l==r){ tree[now]=(a[l]?'I':'B'); return; }
rg int mid=(l+r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
pushup(now);
}
各位可以自行脑补一下
如果一个节点的两个子节点有一个是
如果一个节点的两个子节点相同，那么这个节点肯定与他的左节点（或右节点）相同
否则这个节点一定是
-
2. DFS 输出树的后序遍历
具体思路就不再详细讲解了，直接上代码吧
inline void dfs(int now){
if(!tree[now]) return;
if((!tree[ls])&&(!tree[rs])){ putchar(tree[now]); return; }
dfs(ls);
dfs(rs);
putchar(tree[now]);
}-
3. 完整代码
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<cctype>
#include<algorithm>
#include<stack>
#include<string>
#include<queue>
#include<vector>
#include<map>
#include<deque>
#include<bitset>
#include<set>
using namespace std;
#define ll long long
#define ull unsigned long long
#define rg register
inline int read(){
rg int s=0,f=0;
rg char ch=getchar();
while(not isdigit(ch)) f|=(ch=='-'),ch=getchar();
while(isdigit(ch)) s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
return f?-s:s;
}
const int CSP_S=2019;
int n,a[CSP_S];
char tree[CSP_S<<2];
#define ls (now<<1)
#define rs (now<<1|1)
inline void pushup(int now){
if(tree[ls]=='F'||tree[rs]=='F'){ tree[now]='F'; return;}
if(tree[ls]==tree[rs]){ tree[now]=tree[ls]; return;}
tree[now]='F';
}
inline void build(int now,int l,int r){
if(l==r){ tree[now]=(a[l]?'I':'B'); return; }
rg int mid=(l+r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
pushup(now);
}
inline void dfs(int now){
if(!tree[now]) return;
if((!tree[ls])&&(!tree[rs])){ putchar(tree[now]); return; }
dfs(ls);
dfs(rs);
putchar(tree[now]);
}
signed main(){
// freopen("test.txt","w",stdout);
n=read();
getchar();
// 快读选手在洛谷IDE及洛谷评测必须加此行，否则当场去世（原因过于神奇）
for(rg int i=1;i<=(1<<n);i=-~i) a[i]=getchar()=='0'?0:1;
build(1,1,(1<<n));
dfs(1);
return 0;
}