645
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循環
方法：
用的是貪心，先假設每層隻有一個節點，找到第B層，然後回退，增加節點而%3是因為每個父節點隻可能有兩個子節點（2分），所以子節點個數沒到二的倍數時都要回退給父節點加1
一直循環回退增加，直至總點數大於N，或者回退到頂層，退出。在回退過程中判斷層數是否大於A，若沒大於則加1
正確性：
因為這樣貪心保證了越向下點越多，並且加以限定最大層數為B，所以R必然為最大值
算法很巧妙，但是寫法並不是很認同，特別是未初始化，這個在不同環境下都可能造成未知錯誤
最後更新：2017-04-03 18:51:53