LCA之离线Tarjan算法

2014-11-02 Xie Jingyi
LCA NOIP
真是巧妙的算法！ 比起树上倍增，Tarjan算法实现起来更为简单，一个DFS加并查集即可。缺点便是：需要先把所有的查询都读进来，并且要储存结果。复杂度为O(n+q)。 Code var sets: array [1..100] of longint; visited: array [1..100] of Boolean; a: array [1..100, 1..100] of Boolean; questions: array [1..1000] of record x, y: longint; ans: longint; end; qn, n, 继续阅读 »

LCA树上倍增

2014-11-02 Xie Jingyi
NOIP
var a: array [1..100, 1..100] of boolean; depth: array [1..100] of longint; father: array [1..100, 0..16] of longint; n, m, i, x, y: longint; root: longint; procedure dfs(x: longint); var i: longint; j: longint; begin depth[x] := depth[father[x][0]]+1; j := 1; while 1< 0 then 继续阅读 »

二进制的启示

2014-11-01 Xie Jingyi
NOIP
在学习数论时我们都知道：只用2的幂次可以组合出所有的正整数。这便是二进制的魅力——状态简单而又变化万千。 引子 实际算法中，常常有一些线性的但数据量特别大的问题，如区间求和、求最小值等。很多时候，为了把时间复杂度从$O(n^2)$甚至更高的地方降下来，我们需要对数据进行一些预处理，以提高计算的速度。在这其中，有很大一部分是来自二进制运算特点的启发。 目录 树状数组 RMQ LCA&树上倍增 继续阅读 »