题解 | #[NOIP2004]FBI树#

package main

import (
	"bufio"
	. "fmt"
	"io"
	"os"
)

type Node struct {
	left, right *Node
	t           string
}

func buildTree(s string, l, r int) *Node {
	if l == r {
		t := "B"
		if string(s[l]) == "1" {
			t = "I"
		}
		return &Node{nil, nil, t}
	} else if l < r {
		mid := l + (r-l)/2
		left := buildTree(s, l, mid)
		right := buildTree(s, mid+1, r)

		t := "F"
		if left.t == "I" && right.t == "I" {
			t = "I"
		} else if left.t == "B" && right.t == "B" {
			t = "B"
		}
		return &Node{left, right, t}
	}
	return nil
}

// https://ac.nowcoder.com/acm/problem/16660
func NC16660(_r io.Reader, _w io.Writer) {
	in, out := bufio.NewReader(_r), bufio.NewWriter(_w)
	defer out.Flush()
	var n int
	var s string
	Fscan(in, &n, &s)
	FBITree := buildTree(s, 0, len(s)-1)

	var postOrder func(*Node)
	postOrder = func(node *Node) {
		if node == nil {
			return
		}
		postOrder(node.left)
		postOrder(node.right)
		Fprint(out, node.t)
	}
	postOrder(FBITree)
}

func main() {
	NC16660(os.Stdin, os.Stdout)
}