标签 树形dp 下的文章:

4015: [FJOI2014]树的重心 树形dp
发表于: | 分类:Oi | 评论:0 | 阅读:94
挺强的一个非线性dp 当树有两个重心的时候必然相邻,一个想法是直接大力在中间加个点把它变成重心。 注意当他是唯一的一个重心的时候就是满足只有他一个点的$f*2<n$,否则的话不满足重心定义或者不满足只有一个重心 然后考虑动态规划,$g(i,j,k)$表示前$...

阅读全文>>

BZOJ 4911: [Sdoi2017]切树游戏 基于变换合并的树上动态 DP 的链分治算法 树链剖分 线段树 树形dp
发表于: | 分类:Oi | 评论:0 | 阅读:78
跪烂 immortalco 这题的话我们直接链分治就行了,完全是那个动态链分治做法的套路 注意到需要算异或所以套个$FWT$就行了 复杂度爆炸,有关链分治的简单讲解戳这里就行了链分治 一个细节是0没有逆元所以单独记录一下0的个数就行了,关于0的运算可以看里面的 d...

阅读全文>>

HDU5909 Tree Cutting 树形dp+FWT
发表于: | 分类:Oi | 评论:0 | 阅读:58
题目大意:给出一棵树,每个点有一个点权,求对于每个$i\in[0,m)$输出有多少个连通诱导子图的异或和为i $n\le 1000,m<2^{10}$ $f(x,y)$表示$x$节点在他的儿子里一通选最后异或和为$y$的方案数 转移显然,注意每个儿子都存在根...

阅读全文>>

ZJOI Day1 T1 仙人掌 树形dp
发表于: | 分类:Oi | 评论:0 | 阅读:59
考试的时候全程刚这题现在一看实在是有点亏啊………… 这题的仙人掌要求是没有重边的,那么我们可以在连完一种方案之后把剩下的没有被覆盖的边变成一个重边让他有覆盖 这样就变成了给定一棵树,找个方案使他的所有的边都被覆盖 树形dp即可 $f(x)$ 表示做完了 $x$ 的...

阅读全文>>

BZOJ3722【PA2014】Budowa 博弈 树形dp
发表于: | 分类:Oi | 评论:0 | 阅读:49
因为一个傻逼问题我花了一个下午在这道题上………… 首先就是去掉所有为0的点,剩下的点就能判断答案是 $Tak$ 还是 $Nie$ 原因是所有的点都有奇数个儿子,两个人轮流放之后结果就是不变的 对于$n^2$算法,直接枚举每个为$0$的点然后暴力判断就行了 对于 $...

阅读全文>>

Title - Artist
0:00

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

TOP