zkx06111's Blog

USACO googol

| Comments

第一次用py写了一道正经的题目。USACO竟然也有交互题。交互的方式还是通过stdin / stdout,好神奇啊。

有一棵二叉树,最多可能有个节点,对于任意节点,满足左子树比右子树大1或者相等。

树根为1。允许不超过70000次询问某个节点的左右孩子。请求出这棵树的总点数。

用py的一大理由就是不用写高精度蛤蛤蛤。暴力只需要从1开始,递归的询问左右孩子就好了,但这样铁定超时。

brute.py
def ask(x):
    print x
    sys.stdout.flush()
    return [int(_) for _ in raw_input().split()]

def count(x):
    if x == 0:
        return 0

    lc, rc = ask(x)
    rs = count(rc)
    ls = count(lc)
    return 1 + ls + rs

要利用题目中给的性质。在求出右子树的大小之后,左子树的大小要么是,要么是,只需要判断是哪一个。所以我们写一个函数表示在已知x的子树大小为或者之后求究竟是哪一个。

有一个有用的性质是:如果左子树大小和右子树大小之和知道的话,左子树的大小就是,而右子树的大小就是

所以的左右子树分别满足,

对于的奇偶性分类讨论:

如果,那么,所以左子树大小可以确定,右子树递归处理即可。

如果同理,右子树大小可以确定,左子树递归处理即可。

来分析下询问调用的次数,每次count会询问一次,count递归的次数取决于树高。count时子树的树高是递减的,从根开始分别是。count会调用countGiven,而countGiven递归的层数就是子树的树高,每一层递归都会询问一次。所以询问的调用次数是,这棵树相当平衡,所以是的。时间复杂度也是。

googol.py
import sys

def ask(x):
    print x
    sys.stdout.flush()
    return [int(_) for _ in raw_input().split()]

def countGiven(x, sz): # ret = sz or ret = sz + 1, get ret

    if x == 0:
        return 0
    
    lc, rc = ask(x)
    if sz % 2 == 1:
        rs = (sz - 1) / 2
        ls = countGiven(lc, rs)
        return 1 + ls + rs
    else:
        ls = sz / 2
        rs = countGiven(rc, ls - 1)
        return 1 + ls + rs


def count(x):
    if x == 0:
        return 0
    
    lc, rc = ask(x)
    rs = count(rc)
    ls = countGiven(lc, rs)
    return 1 + ls + rs

ans = count(1)
print "Answer %d" % ans

Comments

comments powered by Disqus