发表于 | 分类于 | | 阅读次数:

在之前的一篇博文中，我们介绍了使用Sparse Table（ST稀疏表）解决RMQ问题的方法。使用ST稀疏表对已知数据进行预处理，对于任意的询问请求都可以以O(1)的效率进行解答，作为一种离线算法，非常高效快速，特别适合用于进行RMQ问题的求解。
现在让我们考虑一种动态的RMQ问题，动态是指在我们询问的过程中，区间内某一位置的值会受到外界干预而发生改变，我们需要做的就是在每次改变的基础上对收到的询问给出正确的结果。
对于动态RMQ问题我们有如下三种思路：

  • 使用朴素算法进行遍历查找；
  • 使用SparseTable稀疏表进行求解，每次变化更新稀疏表；
  • 使用二分线段树进行求解，每次变化进行相应的信息修改。
    下面我们在一个较小数据量(10^4)的条件下对上述三种算法进行分析实现。
    阅读全文 »

发表于 | 分类于 | | 阅读次数:

之前我们曾介绍了两种求解最近公共祖先的方法【链接】，分别使用了并查集方法和DFS深度优先遍历的方法，其中并查集方法虽然思路简单，但是时间效率并不高，只适用于样本值较少的情况下，而对于深度优先遍历DFS这种离线算法我们很难决定是当有询问发生的时候旧进行遍历求解还是等待一定数量的请求之后再进行遍历求解，毕竟无论多次请求还是一次请求，我们的求解过程都是进行一趟遍历。
所以我们希望只针对一个询问就可以开展计算，同时还要有着较高的时间效率，所以本文将介绍一种使用RMQ-ST算法的在线求解算法，关于RMQ-ST算法可以参考上篇博文【链接】。

阅读全文 »

发表于 | 分类于 | | 阅读次数:

RMQ问题(Random Minimum/Maximum Query, 即区间最值问题)，指的是给定一个长度为n的数列A，对于A数列进行若干次询问，询问在闭区间[l, r]之中的最小/最大值是多少。RMQ问题有很多种解法，包括朴素算法、线段树、ST算法等，本文主要介绍使用ST稀疏表算法。

ST算法思想

ST(Sparse Table, 稀疏表)可以以O(nlogn)的时间效率对RMQ问题进行预处理，然后以O(1)的时间效率回答每个问题。
ST算法的实质是一种动态规划算法，我们定义了状态数组dp[i][j]表示从数组下标i开始包含$2^j$个数组元素在内的子数组中最小/大值。则此时，假设我们令$dp[1][0] = 2$, $dp[2][0] = 3$,则$dp[1][1] = min(dp[1][0], dp[2][0])$。即当我们需要求$dp[i][j+1]$的时候，我们可以将这一段子数组分成两段，分别求取两段的最值$dp[i][j]$和$dp[i+2^j][j]$，最后取这两个的最值的比较结果就可以得到结果。所以预处理的状态转移方程为$$dp[i][j+1] = min(dp[i][j], dp[i+2^j][j])$$
只要初始化当$j==0$的时候，最值是本身就可以很轻松的完成预处理。
针对题目要求，求取对任意给定的闭区间[l,r]中的最值，我只要找到小于这个区间长度的最大的2的非负整数次幂——T，分别求取前一段$dp[l][T]$和后一段$dp[r - s^T + 1][T]$最后进行比较就可以得出整个区间的结果，所以$$RMQ(l, r) = min(dp[l][T], dp[r - 2^T + 1][T])$$
其中$T = log_2(r-l+1)$。

阅读全文 »

发表于 | 分类于 | | 阅读次数:

最近公共祖先问题，即LCA（Lowest Common Ancestors）问题，是一个基于并查集和深度优先搜索的算法问题。题目假设我们已经知道了N个人的信息——他们的父亲是谁，然后对任意输入的两个人名，给出这两个人公共祖先中辈分最低的一个祖先。

并查集方法

题目介绍

输入输出介绍和样例如下，题目出自hihoCoder。（点击查看原题介绍讲述）
【输入】
每个测试点（输入文件）有且仅有一组测试数据。
每组测试数据的第1行为一个整数N，意义如前文所述。
每组测试数据的第2~N+1行，每行分别描述一对父子关系，其中第i+1行为两个由大小写字母组成的字符串Father_i, Son_i，分别表示父亲的名字和儿子的名字。
每组测试数据的第N+2行为一个整数M，表示小Hi总共询问的次数。
每组测试数据的第N+3~N+M+2行，每行分别描述一个询问，其中第N+i+2行为两个由大小写字母组成的字符串Name1_i, Name2_i，分别表示询问中的两个名字。
对于100%的数据，满足N<=10^2，M<=10^2, 且数据中所有涉及的人物中不存在两个名字相同的人（即姓名唯一的确定了一个人）。
【输出】
对于每组测试数据，输出一行，表示查询的结果：如果根据已知信息，可以判定询问中的两个人存在共同的祖先，则输出他们的所有共同祖先中辈分最低的一个人的名字，否则输出-1。
【样例输入】

11
JiaYan JiaDaihua
JiaDaihua JiaFu
JiaDaihua JiaJing
JiaJing JiaZhen
JiaZhen JiaRong
JiaYuan JiaDaishan
JiaDaishan JiaShe
JiaDaishan JiaZheng
JiaShe JiaLian
JiaZheng JiaZhu
JiaZheng JiaBaoyu
3
JiaBaoyu JiaLian
JiaBaoyu JiaZheng
JiaBaoyu LinDaiyu

【样例输出】

JiaDaishan
JiaZheng
-1
阅读全文 »

发表于 | 分类于 | | 阅读次数:

二叉苹果树作为树形规划的经典例题，对于我们学习动态规划有着很大的借鉴意义，本文通过介绍二叉苹果树的一种解法思路以及二叉苹果树的另一种变形，深入理解动态规划的思想和方式。

二叉苹果树

题目要求

有一棵苹果树，苹果树的是一棵完全二叉树，共N个节点，树节点编号为1~N，编号为1的节点为树根，边可理解为树的分枝，每个分支都长着若干个苹果（每条边有值对应树枝上的苹果数量），现在要要求减去若干个分支，保留M个分支，要求这M个分支的苹果数量最多。
【输入格式】
第 1 行 2 个数，N 和 Q(1<=Q<= N,1<N<=100)。
N 表示树的结点数，Q 表示要保留的树枝数量。接下来 N-1 行描述树枝的信息。
每行 3 个整数，前两个是它连接的结点的编号。第 3 个数是这根树枝上苹果的数量。
每根树枝上的苹果不超过 30000 个。
【输出格式】
一个数，最多能留住的苹果的数量。
【输入样例】

5 2
1 3 1
1 4 10
2 3 20
3 5 20

【输出样例】

21

解题思路

  • 要求的结果是以1号根节点为根的M个分支所能具有的最多苹果数量
  • 由于是完全二叉树，所以每个结点有且只有可能有两个儿子结点，否则就是叶子结点；
  • 使用一个vector<vector<pair<int, int>>>存储树的结构，将每条分支的权值分配给儿子结点；
  • 使用res[i][j]表示以i结点为根节点的j个分支能包含的最大苹果数量，使用tot[i]表示以i结点（包括i结点本身）为根节点的子树所包含的结点总数；
  • 使用动态规划的思路来进行求解，状态转移方程为：res[i][j] = max{res[i][j], res[i][j-k] + res[i_child][k]}，其中1<=k<j。
    注意：这里j需要从大到小遍历，这样当j=4时求取res[i][4]时，k=1,2,3时读取的res[i][3], res[i][2], res[i][1]因为之前的计算结果所以不包含i_child子树中的结点，其他同理，从而避免了重复的结点选择。
  • 使用深度优先搜索DFS来对树结构进行遍历，从下而上对各结点的状态方程进行求解；
阅读全文 »

发表于 | 分类于 | | 阅读次数:

动态规划是我们最常用的算法之一，在我看来动态规划就是利用额外内存空间将运算过程中所需要的重复变量进行记录，下次访问使用的时候直接进行读取从而减少了额外的重复计算，提高了算法的效率，从某种角度来说也算是空间换取时间的一种方式。道理很简单，动态规划的核心是我们对问题的分割和思考，如何构建状态转移方程、分割事件，如何分解一整个问题，这才是动态规划最核心的解决问题的核心思想。
树归即树形动态规划，是在树形结构中使用动态规划的一类问题。因为树形结构没有环，进行深度优先遍历搜索的时候不会重复进行，再加上树形结构本身有着良好的性质和特点，树归的问题非常多，思路也特别有意思。下面将对我在学习过程中遇到的树归问题进行介绍和记录。

阅读全文 »

发表于 | 分类于 | | 阅读次数:

二叉树是一种非常重要的数据结构，由二叉树演变而来的树堆、红黑树、平衡树、SPlay伸展树等数据结构都在其各自适应领域有着广泛的应用。通过总结这一段时间对二叉树知识的学习，接下来将通过一系列二叉树专题的文章来进行归纳总结。
首先让我们来了解一下二叉树的遍历，二叉树有着先序、中序和后序三种遍历顺序，其中中序遍历更是可以直接将二叉树中元素以有序序列输出。因为二叉树本身就是一个递归的结构实现，所以我们可以使用递归很轻松地实现二叉树的三种遍历，同时也可以利用数据栈实现非递归的二叉树三种遍历。

建立二叉树

二叉树结构

1
2
3
4
5
6
7
8
9
10
11
typedef struct node
{
    int data;
    node *left, *right, *father;
    node(int data_) : data(data_)
    {
        left = NULL;
        right = NULL;
        father = NULL;
    }
}*Node;

这里定义了一个node结构表示二叉树中的一个结点，Node表示指向一个node结点的指针。

阅读全文 »

发表于 | 分类于 | | 阅读次数:

Github
突破1000 Cons了，小小mark一下！接下来还要继续努力！
最近写代码的感悟：

  • 再复杂的算法都是可以梳清理顺的，发明这个算法的人是有思路有其道理可言的，我们需要做的就是耐下心来，一点点抽丝剥茧，总会柳暗花明，水落石出。
  • 先想后写，思路和思考才是算法的核心，停下来多想一想理理思路总是要强过闷头敲键盘的。
  • 学习新的算法，要经常总结经常回顾，不只是算法的熟悉掌握，还会获得新的想法和体会。
  • 一定要耐心，尤其是改Bug的时候，有错误肯定是自己在写代码的过程中粗心大意了呗，往往越是低级的错误越是难查，所以多理理代码流程还是好的。
  • 不只是写代码，做算法还需要各种数学知识、数论基础，都需要我们在平时慢慢积累，在此膜拜一下高德纳Donald_Knuth老爷子，不多说了，我去读《计算机程序设计的艺术》去了。

发表于 | 分类于 | | 阅读次数:

使用C语言进行网络编程的过程中会调用各种库文件，对于这些经常用到的库文件，现在分类记录如下，并会随着今后的学习不断进行更新。

C语言库文件包含关系

1
2
3
4
5
6
7
8
<netinet/in.h>         htons htonl
<bits/socket.h>        sockaddr
<arpa/inet.h>          inet_addr sockaddr_in(字符串IP转换到网络序IP)
<sys/socket.h>         socket bind listen send recv
<sys/types.h>          accept connect
<unistd.h>             fork close
<string.h>             memset memcpy
<stdlib.h>             exit

发表于 | 分类于 | | 阅读次数:

一个字符串中连续的一段就是这个字符串的子串，而回文串指的是12421这种从前往后读和从后往前读一模一样的字符串，所以最长回文子串的意思就是这个字符串中最长的身为回文串的子串啦！

求解思路

对于最长回文字符串的求解，有如下要点：

  • 以字符串中每个结点为中心结点，向左向右进行回文字符串的判定求解，遍历字符串得出结果；
  • 在左右判定之前，首先判断中心结点是否处于连续的相同字符子串中，比如abbbab进行判定的时候，应该将中间bbb看做一个整体作为一个结点进行计算；
  • 为了便于判定遍历的结束，在字符串开始添加一个&符号作为结束标志，即将字符串由abbbabba转换成&abbbabba；
阅读全文 »
0%