-problem: 一棵树n<50000节点, 每个节点上有<1000000人, 问每个节点的子节点(可以是非直接)人数比自己多的节点数量. solution: 树状数组(以人数为下标)+树形DP ----link: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1866 ----code: http://docs.google.com/document/pub?id=1bFekAUqaPJBXzOvU3qDokRi2n83ggHbB0SFyrwlv2O4
注意遍历下一棵子树之前不用清空树状数组, 只需要计算两次sum, 然后用后一次的sum减去前一次的即可.
这里有个小技巧, 因为树状数组是维护一个数组的前缀和, 而本题要求的是大于某人数的节点总数, 所以输入的时候把每个节点的人数用>1e6减一下即可, >1e6是因为树状数组下标0处不可用.
Comments 4
谢谢了~还有ZOJ2865这是一个大数的运算，但是循环变量我搞不定。。。。
还有ZOJ2961是一搜索题，麻烦你了。。。万分感谢~~ T T
2865没什么意思, 倒是2961看上去像个数学题, 是不是模线性方程组什么的…我不会…
不好意思~请问一下结构体里面
int l(int v)
void inc(int i, int v)
int sum(int i)
三个函数的具体用处是什么？
有点糊涂~呵呵。。。谢了~
结构体是binary index array, 即树状数组.
l是lowbit, inc是对树状数组某元素的增减操作, sum是前缀和.
Post a Comment