题解

POJ 2777 Count Color 线段树染色

早些日子为了学习线段树,在Du神牛的带领下,做了此题,入门好题也! poj2777 Count Color

此题是本人线段树第二题,前一道是TYVJ1039 忠诚2(一道动态RMQ问题)

输入区间长度L (1 <= L <= 100000),颜色数目 T (1 <= T <= 30) 和 指令数O (1 <= O <= 100000)

接下来O行C x y z 代表将[x,y]区间染成z色,P x y z 代表询问[x,y]有多少种颜色,起始各处颜色为1;

我第一眼看到”1 <= T <= 30″就格外激动为啥不是40呢?显然是为了小于32,所以显然可以用二进制每位表达一种颜色,颜色1是1(0x1)颜色10就是1024(0x400),在线段树里查询便可以获得这一段的几种颜色然后做一次OR操作便可得到所有颜色

我看到T的范围就马上想到到了Matrix67牛的一个位运算优化:位运算简介及实用技巧(二):进阶篇(1)计算二进制中的1的个数的方法
Continue reading

P49 加分二叉树 题解

题目中说二叉树的中序遍历是顺序的,这说明:对于区间[i,j]其根root满足i<=root<=j

也就是说,对于区间[i,j]其最大加分为选取其中一个作为根R,其左边[i,R-1]的最大加分乘以[R+1,j]区间最大加分+Value[R],对于所有可能的R取表达式最大值.状态转移方程:

\(f[i][j] = Max\left\{ {f[i,k – 1] \times f[k + 1][j] + v[k] ~|~ k = i~to~j} \right\}\)注意:题目要求若一棵树没有左或者右子树,则其加分为存在的那棵子树

初始值for i=1 to n f[i][i]=v[i];

输出便利的方法是:每次记录取到最大值时的根节点编号,设Node[i][j]=x表示在[i][j]区间取到最大加分的数的根节点为x
Continue reading