万能的Splay-处理区间问题
为什么会用到Splay呢，Splay虽然很强大但是不）同问题上替代品也有不少。其实主要是最近看到动态树、Link-cut Tree，里面需要维护一条路径的信息，而且路劲还是可分割，可合并的，这里Splay就是最佳的组件了。
Splay如果仅仅作为一棵二叉平衡查找树（BST）来使用的话的确效率是不尽人意，不过正如Splay的中文名—伸展树，它的发明不仅仅是作为一棵平庸的BST来使用的，较高的常数和看起来不怎么爽的平摊O(logN)的效率带来的是其非常丰富的功能。比如现在所讲的—如何用Splay处理区间问题。
给个例题，POJ3468，题目意思是：给一个连续的区间[1..N]，区间里每个元素上面都有一个数值。每次有两种询问，第一种是给定区间[A,B]，把里面所有元素的数值加上某个数字C，第二种询问是给定区间[A,B]，求区间里所有元素数值的和。
其实这题用线段树还是能非常轻松的过掉的。不过今天就要自虐一下写个Splay。
首先呢，我们以元素的序号为关键字建一个二叉查找树（平衡不平衡这里其实无所谓，反正Splay几下就均摊平衡了。），树上的每个节点代表一个元素，为了方便起见我们可以再插入两个元素0和N+1（等下你就知道为什么需要这俩东西了。）。
接下来的问题呢，是如何把一段连续的区间在树上展现出来，一般人都会比较混沌，因为树上的结构看起来或许很乱。但是Splay在这里就发挥了他十分大的优势，比如，询问区间为[A,B]，我们可以先把元素A-1旋到树根，这样询问区间里的所有元素都在树根的右子树里，接下来的手法类似，就是单独取下那棵右子树（[0..A-1]区间里的元素就这样被我们忽略了），然后把B+1选到树根上，这样树根的左子树就是代表着我们需要处理的区间[A,B]了。
接下来的事情就比较简单了，对于第一种询问，我们可以对于每个节点多记录下一个新信息size，表示以该节点为根的子树下有多少个节点，然后再用类似线段树的标记传递的方法覆盖下去。对于第二种询问，我们可以对每个节点维护sum，表示以该节点为根的子树下所有元素的和是多少。然后问题就此解决了哈哈～
（Splay的基础知识参考NOI WinterCamp2004杨思雨的论文）
NetworkFlow.Dinic Let's do it.
网络流算法有许多种,最基本的一种方法是Fold-Fulkerson.不过裸奔的Fold-Fulkerson的效率总是不尽如人意.于是各种优化层出不穷.
比较牛X的一个就是基于分层图思想的MPLA(最短路径增值).在层次图里,从源点开始,不管怎么走,总能走到汇点,而且保证是最短路.这是一个非常优美的性质.复杂度证明...找WC2007王欣上论文吧..
于是便有了以下的裸的MPLA程序(附件1).每次计算出一个层次图.然后进行若干次DFS寻找增广路.
Dinic是基于MPLA上的另外一个改进.引入一个新的名词叫做块流,表示在一张剩余图上所有可增广的流量.Dinic在每次计算出层次图后,仅用一次DFS来找出这张图的块流,避免了许多废的搜索状态和回溯状态.详见程序(附件2).
Win7 7106 简体中文版简要评测报告
昨晚作为第一波下完的(9点左右才下好),赶紧给装上.
采用的是F8的修复计算机安装(我原本用的还是Win7 7000 beta),安装的速度快的惊人啊.
总共只花了十五分钟左右..在我这台07年的本本上.
新装的系统速度快了很多.中文版的..开机的"Starting Windows"变成了"正在启动Windows"
以及..Windows 7 Ultimate变成了Windows 7 旗舰版(这个还是有点儿囧..)
先上截图..
在Ural上被阴了一题 -> Ural 1028
题目就不多说了..原本是找些线段树的题目来练练手.
结果这题..看起来好水..可以用树状数组切掉..
看到这么水的题目不忍心放弃..就开始随便写..
结果交上去TLE..觉得非常新奇..找了段线段树的程序扔上去AC了.(没天理啊..)
仔细观察题目.才发现..当坐标为0的时候..我可怜的树状数组啊..就开始无限的循环下去了.
还好..赶紧解决..可以把所有坐标加个1..也可以对于0的情况特判.
以下为我AC的程序:
#include <stdio.h> #include <memory.h> int n,a[15001],b[15001],ans[15001],tree[60000],t; int Query(int a) { if (!a) return tree[0]; int ans = 0; while (a) { ans += tree[a]; a -= (a & (-a)); } return ans + tree[0]; } void update(int a) { if (!a) { ++ tree[0]; return; } while (a <= 32768) { ++ tree[a]; a += (a & (-a)); } } int main() { freopen("input.txt","r",stdin); scanf("%d",&n); for (int i=1; i<=n; ++i) scanf("%d %d",&a[i],&b[i]); for (int i=1; i<=n; ++i) { update(a[i]); t = Query(a[i]); ++ ans[t]; } for (int i=1; i<=n; ++i) printf("%d\n",ans[i]); }
POJ 3719 Art of Balance
PKU某月的月赛中的一道题.写一写来练手.
题目大意是: 给出m个砝码(m<=16),有一个有n个节点的二叉树(n<=100),这棵树上有m个叶子节点,每个叶子节点可以挂上一颗砝码,一颗子树的重量是地下挂的所有砝码的重量之和,定义不平衡量为abs((lch.weight / root.weight)-1/2)*1000 , 要求给出一种方案,是的不平衡量的总和最小.
稍微想了下..m只有16..好吧...状态压缩的treedp.
记下f[root,state]为处理根为root的子树,底下用的砝码的状态为state..然后直接转移吧..
#include <stdio.h> #include <memory.h> typedef struct treenode{ int lch,rch,count; }; int cases,n,m,a[17],st[17][65538]; double f[102][65538],w[65538]; struct treenode tree[102]; int dfs(int root) //统计每棵子树所包含的叶子节点的数目. { if (tree[root].lch < 0 && tree[root].rch < 0) tree[root].count = 1; else tree[root].count += dfs(tree[root].lch) + dfs(tree[root].rch); return tree[root].count; } void calc_w() //计算各种状态的重量 { memset(w,0,sizeof(w)); for (int i=1; i<(1 << m); ++i) for (int j=0; j<m; ++j) if (i & (1 << j)) w[i] += a[j+1]; } void build_state(int state,int posi,int len) //生成有用状态 { if (posi > 16) return; build_state(state,posi+1,len); state = state | (1 << (posi-1)); st[++len][++st[len][0]] = state; build_state(state,posi+1,len); } double abs(double a) { if (a < 0) a = -a; return a; } double search(int root,int state) //DP主过程.(记忆化搜索) { if (f[root][state] < 0) { f[root][state] = 2000000000; if (tree[root].count == 1) { f[root][state] = 0; return 0; } for (int i=1; i<=st[tree[tree[root].lch].count][0]; ++i) { int tstate = st[tree[tree[root].lch].count][i]; if ((state & tstate) == tstate) { double temp = search(tree[root].lch,tstate)+search(tree[root].rch,state ^ tstate)+abs((w[tstate]/w[state])-0.5)*1000; if (f[root][state] > temp) f[root][state] = temp; } } } return f[root][state]; } int main() { scanf("%d",&cases); build_state(0,1,0); for (; cases; --cases) { scanf("%d",&n); memset(tree,0,sizeof(tree)); for (int i=1; i<=n; ++i) scanf("%d %d",&tree[i].lch,&tree[i].rch); dfs(1); scanf("%d",&m); memset(a,0,sizeof(a)); for (int i=1; i<=m; ++i) scanf("%d",&a[i]); calc_w(); for (int i=1; i<=n; ++i) for (int j=1; j<(1 << m); ++j) f[i][j] = -1.0; printf("%.3lf\n",search(1,(1 << m)-1)); } }
