Loading...
310-01-ACOJ-0488-统计节点 题目大意： 给定一棵有$n$个结点的树，给定树上$m$个点，称作标兵，再给定一个距离范围$k$。求树上有多少点，其本身不是标兵，且到每个标兵的距离都不超过$k$。每条边的长度固定为$1$。 题解： 对于这道题，要统计距离所有标兵的距离都不超过$k$的个数。换言之，就是统计节点，对于每一个满足要求的节点，要有其距离最远的标兵的距离不超过$k$。 有了...
307-15-背包的二进制优化 P2851 [USACO06DEC]最少的硬币The Fewest Coins 题目描述 Farmer John has gone to town to buy some farm supplies. Being a very efficient man, he always pays for his goods in such a way that t...
307-13-14-子集枚举DP P3959 宝藏 题目描述 参与考古挖掘的小明得到了一份藏宝图，藏宝图上标出了$n$个深埋在地下的宝藏屋， 也给出了这$n$个宝藏屋之间可供开发的$m$条道路和它们的长度。 小明决心亲自前往挖掘所有宝藏屋中的宝藏。但是，每个宝藏屋距离地面都很远， 也就是说，从地面打通一条到某个宝藏屋的道路是很困难的，而开发宝藏屋之间的道路 则相对容易很多。 小明的决心感动了...
307-09-10矩阵乘法与快速幂 矩阵乘法 定义矩阵$A$，$B$，其中$A$的大小为$a \times b$，$B$的大小为$b \times c$，对于矩阵$C=AB$中的每一个元素$C(i.j),~i\in [1, a],~j\in [1,c]$，存在以下：
307-07-逐行递推 逐行递推：$dp$在某种情况下按照一行一行的顺序进行递推。 P2704 [NOI2001]炮兵阵地 题目描述 司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成，地图的每一格可能是山地（用“H” 表示），也可能是平原（用“P”表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图...
307-06-期望$dp$ 概述 做一件事情成功：$p$，失败：$\overline{p} = 1-p$。 和性：$E[x+y] = E[x] + E[y]$ 期望的意义就是对于做一件事情，期望多少次这件事情可以做成功。 P1291 [SHOI2002]百事世界杯之旅 题目描述 “……在2002年6月之前购买的百事任何饮料的瓶盖上都会有一个百事球星的名字。只要凑齐所有百事球星的名字，就可参加...