真是巧妙的算法！
比起树上倍增，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,
继续阅读 »
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
继续阅读 »
问题描述：已知数组a以及若干个查询(x, y)，求a[x~y]之间的最小值。
分析
不难发现：若取t使得$2^t\leq y-x+1$且$2^{t+1}>y-x+1$，则有：
$$[x, x+t]\bigcup[y-t+1,y]=[x,y]$$
运用二进制的思想，我们只需预处理出$i~i+2^k-1$之间的最小值，即可快速完成查询。设dp[i][j]为$i~i+2^j-1$之间的最小值，则有：
$$dp[i][j]=min(dp[i][j-1],dp[i+2^{j-1}][j-1])$$。
Code
var
a: array [1..100000] of longint;
dp: array [1..1000
继续阅读 »
链接：Link 耗时：0.586s
昨晚做的太急了，没时间写总结，正好下午有空，补上。
这是一道典型的树形动态规划，不是很难，但十分坑语言。思路大致如下：
对于第i个节点，用d(i)表示其上诉所需的最小工人数。若i为叶节点，则d(i)=1；否则，遍历求出i的子节点所对应的d值，并由小到大排序，取出最小的几个相加，即为d(i)。
很容易想到用递归来实现。但对于“子节点的d值的排序”实现起来却十分困难：因为事先不知道有多少个数。当然啦，如果是C++组，用vector可以轻松搞定，可至于P党，实现起来却难上加难。思来想去，决定试试Pascal的动态数组。磕磕碰碰调了近1个小时，终于AC了。
Code:
```pascal
//
继续阅读 »
介绍
所谓树状数组，就是将线性的数组预处理成树状的结构以降低时间复杂度。先来看一幅经典的图：
其中的a数组为原生数组，c数组为辅助数组，计算方式为： $$c_1=a_1——{(1)}{10}={(1)}_2$$ $$c_2=a_2+c_1——{(2)}{10}={(10)}_2$$ $$\ldots$$ 不难发现，c[k]存储的实际上是从k开始向前数k的二进制表示中右边第一个1所代表的数字个元素的和。这样写的好处便是可以利用位运算轻松计算sum。上代码。
Code
var
n, i: longint;
a, c: array [1..10000] of longint;
//计算x最右边的1所代表的数字。
继续阅读 »
在学习数论时我们都知道：只用2的幂次可以组合出所有的正整数。这便是二进制的魅力——状态简单而又变化万千。
引子
实际算法中，常常有一些线性的但数据量特别大的问题，如区间求和、求最小值等。很多时候，为了把时间复杂度从$O(n^2)$甚至更高的地方降下来，我们需要对数据进行一些预处理，以提高计算的速度。在这其中，有很大一部分是来自二进制运算特点的启发。
目录
树状数组
RMQ
LCA&树上倍增
继续阅读 »
链接：The Tower of Babylon 耗时：0.015s
这是刘汝佳的紫书中"DAG中的动态规划"中的习题，我拿它用来熟悉DAG中的动态规划。
我们不妨进行逆向考虑：现堆上面的方块，然后考虑在下面进行叠加。这样子一来，影响决策的就只是最下面方块的尺寸了。
对于这种出现了"大套小"这样的二元关系的题，我们可以将其视为一个有向无环图：其中每个节点为一个状态，状态的转移是有固定的方向的（在此题中，状态转移为从小的方块到大的方块）。
但是这道题又不同于平常的DAG动态规划：若将边长视为状态的话，则要开一个巨大的数组，这是不可以接受的。因此，我们要换一种思维方式：只记录方块的序号和摆放的方式（如现将边长从小到大进行排序，然后
继续阅读 »
测试位置：WikiOI1078
type
TEdge = record
start, terminal: longint;
weight: int64;
end;
TEdgeArr = array of TEdge;
operator (e1, e2: TEdge)res: Boolean;
begin
res := e1.weight > e2.weight;
end;
procedure SortEdge(A: TEdgeArr; l, r: longint);
var
i, j: longint;
t, m: TEdge;
begin
继续阅读 »
这是一道区间型DP，转移方程很简单，但在实现的过程中却遇见了很多坑，在此记录一下。 链接：Link 耗时：0.368s
容易想到，前i个数的划分情况可以由1,2,3...,i-1的划分情况来决定。因此很容易得到状态转移方程：
d[i] = min(d[i], d[j]+1) //j = 0, 1, 2...n-1 并且 s[j+1, i]为回文串，初始条件：d[i] = i。
d[i]表示前i项的最小划分。这样一来状态转移的复杂度就为O($n^2$)。
但状态转移的判断呢？“回文串”是一个复杂的条件，判断一个串是否为回文串需要将该串至少遍历一遍。这样一来时间复杂度就上升为O($n^3$)了。而事实上在这种算法中有许多无谓的计
继续阅读 »
链接：Link 耗时：0.028s
一道简单的动态规划，主要思路就是：
用f[i,j]表示到达(i,j)的最长路径的长度。找到每个最高点，从其开始向四周的低处搜索。如果该点已搜过并且f值大于当前长度则退出回溯。直到达到某个最低点为止。
不多说了，直接上代码：
```pascal
const
delta :array [1..4, 1..2] of integer = ((-1, 0), (1, 0), (0, 1), (0, -1)); //四个方向向量
var
_: Integer;
name: string;
n, m, i, j, x: Integer;
ans: longint
继续阅读 »