wxyww

分类

未归档(12) 精品(28) 题解(65)

/ 注册

全部文章（共395篇）

树的重心

定义树的重心是指树上的某个节点，满足删除当前点之后，生成的树的大小的最大值最小。性质性质1 以树的重心为根，那么根节点的每棵子树的大小都小于等于\(\frac{n}{2}\)。性质2 每棵子树的大小都小于等于\(\frac{n}{2}\)的点一定是这棵树的重心。即性质\(1\)的...

树的重心学习笔记

2019-01-29

0 602

树的重心

定义树的重心是指树上的某个节点，满足删除当前点之后，生成的树的大小的最大值最小。性质性质1 以树的重心为根，那么根节点的每棵子树的大小都小于等于\(\frac{n}{2}\)。性质2 每棵子树的大小都小于等于\(\frac{n}{2}\)的点一定是这棵树的重心。即性质\(1\)的...

树的重心学习笔记

2019-01-29

0 485

hdu4899 Hero meet devil

题目链接题意给出一个长度字符串\(T\)，其中只包含四种字符\((A,C,G,T)\),需要找一个字符串\(S\)，使得\(S\)的长度为\(m\)，问\(S\)和\(T\)的\(lcs\)为\(0,1,2...|T|\)时，分别有多少种情况。 \(|T| <= 15,m <= ...

动态规划dp 状态压缩 dp套dp

2019-01-24

0 574

hdu4899 Hero meet devil

题目链接题意给出一个长度字符串\(T\)，其中只包含四种字符\((A,C,G,T)\),需要找一个字符串\(S\)，使得\(S\)的长度为\(m\)，问\(S\)和\(T\)的\(lcs\)为\(0,1,2...|T|\)时，分别有多少种情况。 \(|T| <= 15,m <= ...

动态规划dp 状态压缩 dp套dp

2019-01-24

0 596

hihocoder1364 奖券兑换

题目链接思路乍一看这是一个01背包的裸题。但是数据范围\(10^5\)是无法承受的。但是发现\(p_i\)和\(w_i\)只有10，也就是说最多只有100种物品。所以可以对他们进行分组。然后用二进制优化多重背包来做。二进制优化多重背包多重背包是指限定物品数量的一种背包问题。多重背...

动态规划dp 背包

2019-01-24

0 493

hihocoder1364 奖券兑换

题目链接思路乍一看这是一个01背包的裸题。但是数据范围\(10^5\)是无法承受的。但是发现\(p_i\)和\(w_i\)只有10，也就是说最多只有100种物品。所以可以对他们进行分组。然后用二进制优化多重背包来做。二进制优化多重背包多重背包是指限定物品数量的一种背包问题。多重背...

动态规划dp 背包

2019-01-24

0 443

bzoj2086 Blocks

题目链接题面思路可以发现其实就是询问一个最长的区间，使得这个区间的平均数大于等于k。所以将区间内所有数字减去k，然后做一遍前缀和。只要是前缀和之差大于等于0的区间。就是满足条件的。所以现在问题就成了对于前缀和上的每个数字，找到一个最靠前的比他小的数字。这个可以用单调栈。可以发现如...

动态规划dp 单调栈

2019-01-24

0 458

bzoj2086 Blocks

题目链接题面思路可以发现其实就是询问一个最长的区间，使得这个区间的平均数大于等于k。所以将区间内所有数字减去k，然后做一遍前缀和。只要是前缀和之差大于等于0的区间。就是满足条件的。所以现在问题就成了对于前缀和上的每个数字，找到一个最靠前的比他小的数字。这个可以用单调栈。可以发现如...

动态规划dp 单调栈

2019-01-24

0 420

bzoj2448 挖油

题目链接题面思路先考虑\(n \leq 100\)的做法。区间dp。状态。用\(f[l][r]\)表示知道l到r内\(x\)的位置最少需要的时间转移。枚举一个\(l \leq k \leq r\)。那么现在我们要在k处挖油了，然后我们根据k处有没有油再去确定下次是挖\([k +...

动态规划dp 单调队列

2019-01-24

0 535

bzoj2448 挖油

题目链接题面思路先考虑\(n \leq 100\)的做法。区间dp。状态。用\(f[l][r]\)表示知道l到r内\(x\)的位置最少需要的时间转移。枚举一个\(l \leq k \leq r\)。那么现在我们要在k处挖油了，然后我们根据k处有没有油再去确定下次是挖\([k +...

动态规划dp 单调队列

2019-01-24

0 504