2014-11-02 Xie Jingyi
真是巧妙的算法! 比起树上倍增,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, 继续阅读 »
2014-11-02 Xie Jingyi
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-02 Xie Jingyi
问题描述:已知数组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 继续阅读 »
2014-09-27 Xie Jingyi
链接:Link 耗时:0.586s 昨晚做的太急了,没时间写总结,正好下午有空,补上。 这是一道典型的树形动态规划,不是很难,但十分坑语言。思路大致如下: 对于第i个节点,用d(i)表示其上诉所需的最小工人数。若i为叶节点,则d(i)=1;否则,遍历求出i的子节点所对应的d值,并由小到大排序,取出最小的几个相加,即为d(i)。 很容易想到用递归来实现。但对于“子节点的d值的排序”实现起来却十分困难:因为事先不知道有多少个数。当然啦,如果是C++组,用vector可以轻松搞定,可至于P党,实现起来却难上加难。思来想去,决定试试Pascal的动态数组。磕磕碰碰调了近1个小时,终于AC了。 Code: ```pascal // 继续阅读 »
2014-11-02 Xie Jingyi
介绍 所谓树状数组,就是将线性的数组预处理成树状的结构以降低时间复杂度。先来看一幅经典的图: 其中的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所代表的数字。 继续阅读 »
2014-11-01 Xie Jingyi
在学习数论时我们都知道:只用2的幂次可以组合出所有的正整数。这便是二进制的魅力——状态简单而又变化万千。 引子 实际算法中,常常有一些线性的但数据量特别大的问题,如区间求和、求最小值等。很多时候,为了把时间复杂度从$O(n^2)$甚至更高的地方降下来,我们需要对数据进行一些预处理,以提高计算的速度。在这其中,有很大一部分是来自二进制运算特点的启发。 目录 树状数组 RMQ LCA&树上倍增 继续阅读 »
2014-09-23 Xie Jingyi
链接:The Tower of Babylon 耗时:0.015s 这是刘汝佳的紫书中"DAG中的动态规划"中的习题,我拿它用来熟悉DAG中的动态规划。 我们不妨进行逆向考虑:现堆上面的方块,然后考虑在下面进行叠加。这样子一来,影响决策的就只是最下面方块的尺寸了。 对于这种出现了"大套小"这样的二元关系的题,我们可以将其视为一个有向无环图:其中每个节点为一个状态,状态的转移是有固定的方向的(在此题中,状态转移为从小的方块到大的方块)。 但是这道题又不同于平常的DAG动态规划:若将边长视为状态的话,则要开一个巨大的数组,这是不可以接受的。因此,我们要换一种思维方式:只记录方块的序号和摆放的方式(如现将边长从小到大进行排序,然后 继续阅读 »
2014-10-26 Xie Jingyi
测试位置: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 继续阅读 »
2014-09-24 Xie Jingyi
这是一道区间型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$)了。而事实上在这种算法中有许多无谓的计 继续阅读 »
2014-09-29 Xie Jingyi
链接: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 继续阅读 »