A simple Blog for wyx I've been down the bottle hoping.
BZOJ 2286 树形dp
发表于: | 分类:Oi | 评论:0 | 阅读:146
第一次写虚树…… 学了一下午 我们先来看朴素的$dp$吧 用$f(i)$表示将$i$及其子树与1隔离的最小花费 如果$i$是一个资源点 $f(i) = inf$ 否则的话 $f(i) = min {f{son_i},val}$ 说白了就是让儿子做还是自己选边的问题...

阅读全文>>

BZOJ 2818 Gcd
发表于: | 分类:Oi | 评论:0 | 阅读:145
传送门 题目大意就是求在给定范围内 $gcd(x,y)=prime$ 的所有的有序$(x,y)$的对数 分析 我们令$gcd(x,y) =k$,$k$是质数,那么就有$\gcd(x/k,y/k)=1$ 不妨先让$(x,y)$中的$y>x$ 问题就变成了求$y...

阅读全文>>

BZOJ 2427 软件安装 树形dp+tarjan
发表于: | 分类:Oi | 评论:0 | 阅读:157
现在我们的手头有N个软件,对于一个软件i,它要占用Wi的磁盘空间,它的价值为Vi。我们希望从中选择一些软件安装到一台磁盘容量为M计算机上,使得这些软件的价值尽可能大(即Vi的和最大)。 但是现在有个问题:软件之间存在依赖关系,即软件i只有在安装了软件j(包括软件...

阅读全文>>

3702: 二叉树 线段树
发表于: | 分类:Oi | 评论:0 | 阅读:150
现在有一棵二叉树,所有非叶子节点都有两个孩子。在每个叶子节点上有一个权值(有n个叶子节点,满足这些权值为1..n的一个排列)。可以任意交换每个非叶子节点的左右孩子。 要求进行一系列交换,使得最终所有叶子节点的权值按照中序遍历写出来,逆序对个数最少。 这算是线段...

阅读全文>>

Title - Artist
0:00

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

TOP