早些日子为了学习线段树,在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 “POJ 2777 Count Color 线段树染色”
本来是个水题，我一交，WA：90，第一点错误，答案1位选手输出20位。
得，骗数据，共1个物体，4*4大小，推断可能是：
1
4 4
1000
0000
0000
0000
这叫什么数据。。
一定要注意可能n*m的方块没有占用n*m的情况，于是乎，我放上来了
MYCODE:
Continue reading “p44 拼图 回溯题解”
题目中说二叉树的中序遍历是顺序的，这说明：对于区间[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 “P49 加分二叉树 题解”