A simple Blog for wyx I've been down the bottle hoping.
BZOJ 3696 化合物 树形$dp$
发表于: | 分类:Oi | 评论:0 | 阅读:49
想看真正的正解的孩子可以现在就关闭窗口了…… 正解我不会,我只会$O(nh^2)$的暴力 我们还是来说暴力算法吧$OVO$ 我们枚举每一个点 讨论以$x$为$LCA$在以他为根的子树中对答案的贡献 假设已经合并了前$c-1$个子树,讨论第$c$个子树 假设在前$c...

阅读全文>>

BZOJ 4236: $JOIOJI$
发表于: | 分类:Oi | 评论:0 | 阅读:57
$J[i]-J[k-1] = O[i] - O[k-1]$ $J[i] - O[i] = J[k-1] - O[k-1]$ $O,I$同理 我们把$J[i]-O[i]$扔到一个$map$里存一下左端点,遇到相同的就更新答案就行了 注意0,0的初始化 时间复杂度$O...

阅读全文>>

3522: [Poi2014]Hotel 树形dp
发表于: | 分类:Oi | 评论:0 | 阅读:57
题目大意 给定一棵树,找到三个点,使得三个点到中心点的距离相同,中心点相同算相同方案,求一共多少种方案 树的节点数 $<=5000$ 大概这题的数据范围比较小……我就暴力过的…… 我要是知道正解以后再重写一下 先说一下暴力怎么写吧 枚举中间点,记录总数,两个...

阅读全文>>

BZOJ 1369: [Baltic2003]Gem 树形dp
发表于: | 分类:Oi | 评论:0 | 阅读:75
第一次想的太少了……直接分层01做的…… 错了之后马上就意识到了不对 我们可以通过利用大量的子树来逼迫一个点选2,3…… 发现手画4都不太好画出来…… 我们大胆猜测最多就能选10 然后乖乖的树形$dp$就行了 不知道$0ms$什么算法……TAT #include ...

阅读全文>>

BZOJ 2097 Exercise 二分答案+树形dp+贪心
发表于: | 分类:Oi | 评论:0 | 阅读:51
题目大意:给定一棵树,可以删掉k条边,求删掉后森林中所有树直径的最大值的最小值 最大值的最小值,我们容易想到贪心 但是现在验证出现了一点小麻烦 我们可以利用树形$dp$维护处$f(i)$表示点在他的子树中经过他的最长的链 显然 $$f(i) = max{f(son...

阅读全文>>

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP