topcoder 2C 1000 WellTimedSearch dfs+枚举

      首先上题解的传送门。

       这个关键就是求出个f(x,A)也就是x结点在A层所需要的额外点数。我们所要求的就是枚举x，然后判断A-B层中的节点数，取最大值除以N即是我们要求的最大概率

       求解f(x,A)时直接dfs，因为f(1,1)=1 ,f(x,A)=ceil(x/2) + f(ceil(x/2), A-1) 

题解:

int getLesser(int A, int x)
{
    if (x == 1) {
        // cut execution time, in case x = 1, we know we
        // need A - 1 more nodes: This ensures getLesser is O(log(x))
        return A - 1;
    } else if (A == 1) {
        // A == 1 and x is not 1, this is not possible
        // use a large constant INF to mark invalid cases:
        return INF;
    } else {
        int p = (x+1) / 2 ;
        return p + getLesser(A-1, p);
    }
}
int getTheMost(int rem, int x, int d)
{
    if ( (d == 0) || (rem == 0) ) {
        // Out of tree depth or out of nodes.
        return 0;
    } else {
        // Take the x nodes out of the remaining count
        int s = std::min(rem, x);
        // Continue, multiply x*2 and reduce the depth:
        return s + getTheMost(rem - s, x*2, d-1);
        // O(log(rem))
    }
}

double getProbability(int N, int A, int B)
{
    int mx = 0;
    for (int x = 1; x <= N; x++) {
        // Required number of nodes to support the x nodes of depth A:
        int less = getLesser(A, x);
        if (less + x <= N) {
            // Maximum number of nodes of depth between A and B:
            // (If x nodes have depth A)
            int good = getTheMost(N - less, x, B - A + 1);
            mx = std::max(mx, good);
        }
    }
    return mx / (double)N;
}

如下

int P['   '], S, D=1;
struct WellTimedSearch {
    float R, getProbability(int N, int A, int B) {
        for(; D;)
            ++P[D]%3 && D<B && ++S<N ? D++ : R+=D-->=A;
        return R/N;
    }
};

下面说明下这个精巧的代码:

p['     ']其实就是p[1000001]之类的（具体数字没试），但是多数编译器过不了，因为开了多字符警告

第一行的完整写法应该是这样的 int P[1000001]={0},S=0,D=1;

S为总点数，D为层数

类方法内部就是个for循环

方法：

   而%3是因为每个父节点只可能有两个子节点（2分），所以子节点个数没到二的倍数时都要回退给父节点加1

   一直循环回退增加，直至总点数大于N，或者回退到顶层，退出。在回退过程中判断层数是否大于A，若没大于则加1

正确性：

   因为这样贪心保证了越向下点越多，并且加以限定最大层数为B，所以R必然为最大值

算法很巧妙，但是写法并不是很认同，特别是未初始化，这个在不同环境下都可能造成未知错误