Game 题意 给一颗树，已知每个点有权值和陷阱，你不能往回走，如果走过$c$个陷阱或者无路可走就结束，可以从任一点开始走，问能获得多少权值。 题解 树形dp。 $dp[i][j][0/1]$是在以$i$为终点，经过$j$个陷阱，$1$代表起点有陷阱，$0$代表起点没有陷阱。转移方程 ...

八数码问题 前提知识 康拓展开 用途 相当于hash存储序列，使用更加小的空间来存储排列。 公式 $X = a_n*(n-1)!+a_{n-1}(n-2)+…+a_10!$，$a_i$表示当前未出现的数字是排在第几个元素。$0 \leq a_i 八数码问题 ...

Color the ball 题意 给定$n$次操作，吧$l,r$区间内+1，最后问每个点是多少。 题解 树状数组骚操作。 既然我单点更新只能更新一个点，那么我就更新$l$点加上1，之后$r+1$的点减1，那么我对于在区间中的点，求得就是他之前$l$出现的次数。 ...

HDOJ 4661: Message Passing 题意 每个人拥有一个信息，也可以传给另外一个人他拥有的所有信息。现在给定一个联络树，问至少多少次传递可以让所有人拥有所有信息。 题解 可以看出至少要$(n-1)*2$次传递，因为每个人都至少传出一次，传入一次。而怎么可以最少传递呢？我们可以假设根为中心，先将所有信息传递给他，之后再从他传递回来。这里有一点很巧妙，传入和传出的可能种类是一样的，所以我们只需要计算一次传入，平方后便是该点为中心的方案数。 ...

Stand in a line 题意 给定$n-1​$组关系，节点$a​$不能站在节点$b​$的前面，使得$n​$站成一行，问有多少种站法。 题解 树形dp + 组合数学 先建树，把没有父亲的节点都并入$0$节点，这样我们就有一颗完整的树了。 ...

[nowcoder1]J. Different Integers 题意 给出一段序列$a_1,a_2,…,a_n$，和$l,r$，求区间$[1,l],[r,n]$中不同数字的个数。 题解 树状数组+倍增序列 将查询的$l,r$转化为查询序列$[r,l+n]$中不同中数字的个数。 ...

A.run 题意 白云可以跑$k$米或者走$1$米，但不能连续跑，问到达终点有多少种方案。 题解 1步2步上楼梯的加强版。典型的dp题。 $dp[i][0/1]$表示第$i$米最终是走还是跑的方案数 转移方程 ...

单调队列 定义 单调队列，就是指队列中的元素是单调的。 $a_1,a_2,a_3,…,a_n$满足$a1\leq a_2\leq a_3…\leq a_n$的序列便是单调序列。 ...

[hdoj6438]Buy and Resell 题意 给定$n$个城市和无限制的初始金钱你可以在每个城市里 以$a_i$的价格买个商品 以$a_i$的价格卖出商品 啥都不做 问最多能赚多少钱？ 题解 贪心 + 数据结构 ...

[hdoj6447] YJJ’s Salesman 题意 给定一个地图，只能向右或者向上走，地图上有很多点，有以下条件 每个点有钱$val$ 你只能从该点的左下方进入点才可以拿钱。 问最多能获得多少钱。 ...