相关链接
题目传送门：https://arena.topcoder.com/#/u/practiceCode/15657/31723/12515/1/317358
中文题面及题解：http://picks.logdown.com/posts/208980-solutions-to-topcoder-open-2013s-hard-problems
解题报告
这题从头到尾都只会 $O(n^3)$ 的 $DP$
想了四个小时啊 QwQ
考虑搞出一个二叉搜索树
显然我们可以控制一个节点的左右儿子有多少个
因为我们可以询问当前区间的端点，所以我们还可以控制有没有左右儿子
换一句话说，我们可以钦定这棵搜索树的形态
我们继续观察可以发现一下两条：
- 我们可以根据一个节点左右儿子子树的大小，求得往左、往右走的概率
- 每一个深度在$[A,B]$的节点都是一个合法的结束
于是我们就可以枚举第$A$层有多少结点，然后贪心往下放就可以啦！
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
class WellTimedSearch {
public:
double getProbability(int n, int A, int B) {
int vout = 0;
for (int i=1,up,down;i<=n;i++) {
if (A > 1) up = Get_Top(i+1>>1, A-1);
else {if (i == 1) up = 0; else up = 1e9;}
if (n - up - i < 0) break;
down = Get_Down(B-A, n - up - i, i<<1);
vout = max(vout, i + down);
}
return (double)vout / n;
}
private:
int Get_Top(int len, int t) {
if (t > 1) return min((int)1e9, len + (len>1? Get_Top(len+1>>1, t-1): t-1));
if (t == 1 && len > 1) return 1e9;
return 1;
}
int Get_Down(int t, int num_node, int cur) {
if (!t) return 0;
if (cur >= num_node) return num_node;
return cur + Get_Down(t-1, num_node - cur, cur<<1);
}
};
My brother recommended I might like this blog. He was entirely right.
This post truly made my day. You cann’t imagine just how much time I had spent for this information! Thanks!
Excellent blog here! Also your site loads up
very fast! What host are you using? Can I get your affiliate link to your host?
I wish my web site loaded up as fast as yours lol
When someone writes an paragraph he/she retains
the image of a user in his/her mind that how a user can know it.
So that’s why this post is amazing. Thanks!
Excellent blog here! Also your website loads up very fast!
What host are you using? Can I get your affiliate link to your host?
I wish my site loaded up as quickly as yours lol
What’s up to every body, it’s my first pay a visit of this weblog; this blog consists of
amazing and genuinely fine information for visitors.
Saved as a favorite, I love your web site!
Great blog you have here.. It’s difficult to find good quality
writing like yours nowadays. I truly appreciate people like you!
Take care!!
Hi! This is kind of off topic but I need some
guidance from an established blog. Is it difficult to set
up your own blog? I’m not very techincal but I can figure things out pretty
fast. I’m thinking about creating my own but I’m not sure where to begin. Do you have any points or suggestions?
Cheers
The other day, while I was at work, my cousin stole my
iPad and tested to see if it can survive a 25 foot drop, just so
she can be a youtube sensation. My iPad is now destroyed and she has 83 views.
I know this is entirely off topic but I had to share it with someone!
When some one searches for his vital thing, therefore
he/she wants to be available that in detail, thus
that thing is maintained over here.
When someone writes an paragraph he/she retains the plan of a user in his/her
mind that how a user can know it. Thus that’s
why this article is outstdanding. Thanks!
It’s remarkable to go to see this web page and reading the views of all friends about this article, while I am also zealous of getting
know-how.
Some really interesting details you have written.Assisted me a lot, just what I was searching for : D.
It’s hard to find knowledgeable people on this topic,
but you sound like you know what you’re talking about!
Thanks
I enjoy reading an article that can make people think. Also, many thanks for allowing me to comment!
This is a good tip especially to those new to the blogosphere.
Simple but very accurate info… Thanks for sharing this one.
A must read article!
Excellent goods from you, man. I’ve understand your stuff previous
to and you’re just extremely excellent. I really like what you’ve acquired here, certainly like what you are
saying and the way in which you say it. You make it enjoyable and you still care for to keep it sensible.
I cant wait to read far more from you. This
is really a tremendous web site.
What’s up to every body, it’s my first pay a quick visit of this website; this web site contains amazing and truly excellent stuff in favor of visitors.
Pretty! This has been an extremely wonderful article.
Thank you for providing these details.
I know this web page presents quality dependent articles and additional data, is
there any other web page which offers these kinds of things in quality?
Good day! Do you know if they make any plugins to safeguard against hackers?
I’m kinda paranoid about losing everything I’ve worked hard on. Any tips?
Hi to all, the contents existing at this web site are in fact
amazing for people knowledge, well, keep up the good work
fellows.
Thank you for sharing with us, I conceive this website genuinely stands out : D.
Thank you ever so for you blog article.Really looking forward to read more. Great.