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$ 你只能从该点的左下方进入点才可以拿钱。 问最多能获得多少钱。 ...
51Nod-1593 公园晨跑 题意 给定一个环，环上有$n$个点，每个点有一个权值$h$代表着如果从$i$到$j$的话，你必须加上$2h_i+2h_j$。并且加上他们之间的距离$L$。并且在环上会有一个区间被占用导致只能从另外一个方向走。 ...
最大子段和学习笔记 什么是最大子段和？ 给定$n$个整数(可以为负数)组成的序列$a_1,a_2,…,a_n$，求该序列连续的字段和最大值。显然如果都是负数最大值可以为0。 解决方案1 暴力枚举开始位置$i$和终止位置$j$，对每一种可能性计算和。 ...
[POJ3264]Balanced Lineup 题意 给一个数列，求数列中$l,r$范围内最大值和最小值的差。 题解 st表模板题。求两次rmq即可。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 #include #include #include #include using #define #define #define #define typedef typedef const //head const int int int int int int rep(i,0 rep(j,0 st[i][j+1 st2[i][j+1 } } int int return } int int return } int #ifdef freopen("shui.in" #endif while rep(i,0 ST(); while int l--,r--; printf } } return } [POJ3264]Balanced Lineup ...