现在位置: 首页 > 算法 > 文章
2018年09月23日 算法 ⁄ 共 1775字 评论关闭
题目链接:   poj 1470 题目大意:   给出一棵树,然后有有限次查询(a,b)                   每次查询节点a与节点b的最近公共祖先                   输出节点作为最近公共祖先的次数 解题思路:   离线查询最近公共祖先                   把每次查到的结果visit[ ]++,最后遍历一遍就行了 代码: //Final LCA离线算法求最近公共祖先 #include <stdio.h> #include <string.h> #include <stdlib.h> #include ...
阅读全文
2018年09月22日 算法 ⁄ 共 1666字 评论关闭
题目链接:   poj 1986 题目大意:   给出一棵树,求a—b路径的长度 解题思路:   与hdu 2874类似                   LCA离线查找最近公共祖先                   dist[ ]求距离: 距离=dist[ a ] + dist[ b ] — 2*dist[ LCA(a,b) ] 代码: //Final LCA离线 查找两点最短距离 #include <stdio.h> #include <string.h> #include <stdlib.h> #define MAX 50100 struct { int to,w,next; }Hash[MAX<<2],Qes[MA...
阅读全文
2018年09月22日 算法 ⁄ 共 1413字 评论关闭
题目链接:   poj 1226 题目大意:   给出N个字符串,找出一个最长的子串                   使得它和N个字符串正向或者逆向匹配,输出长度 解题思路:   如果这个字串存在,那么它必定存在与N个字符串中最小的那个串                   找到N个字符串中最小的串,然后枚举最小串的所有子串                   从最长的子串开始枚举,长度逐渐减少                   只要存在这样的子串和其他的字符串匹配,当前长度就是最优解...
阅读全文
2018年09月22日 算法 ⁄ 共 829字 评论关闭
题目链接:   poj 3461 题目大意:   给出主串和模式串,求模式串在主串中出现的次数(部分可以重合) 解题思路:   KMP从主串的第一个字符开始匹配                    开始是匹配成功就立刻退出,再次从上次退出的下一个字符开始匹配,TLE...                    利用上next[ ]数组的含义,每次不全部退出,而是退出部分j=next[ j ] 代码: //Final Kmp,给出模式串和主串,求模式串在主串中出现的次数(可以部分重叠) #include...
阅读全文
2018年09月22日 算法 ⁄ 共 795字 评论关闭
题目链接:   poj 2752 题目大意:   给出字符串,找出所有的前缀和后缀相等的子串                   按小到大输出这些子串的长度 解题思路:                                  如图所示,根据next[  ]前缀的性质左边有颜色部分和右边有颜色部分完全相等                   因为左边的红色和右边的红色相等,如果左边的红色和左边的绿色相等,则左边的红色必定与右边的绿色相等                   既左红+左蓝+左绿和左绿是我们...
阅读全文
2018年09月22日 算法 ⁄ 共 970字 评论关闭
题目链接:   poj 2406 题目大意:   给出一个由某个串重复有限次得到的字符串                   求重复次数最多是多少,既找出最小重复子串 解题思路:    字符串abcabcabc的next[ ]值为                    0  1  2  3  4  5  6  7  8  9                    a  b  c  a  b  c  a  b  c                   -1  0  0  0  1  2  3  4  5  6                   假设主串为abcabcabcX,模式串为abcabcabcK,Kmp的匹配过程         ...
阅读全文
2018年09月22日 算法 ⁄ 共 1475字 评论关闭
题目链接:    http://poj.org/problem?id=3264 题目大意:   给出初始化的区间值,m次查询                   每次查询区间[a,b]的最大值-最小值 解题思路:   线段树    更新: 无更新    查询:区间查询                   建立线段树的时候,每个结点存储左右子树的最大值和最小值                   查询时直接访问区间最大值和最小值,不需要查找到最低                   查询时间复杂度O(logN) 代码: #include <stdio...
阅读全文
2018年09月22日 算法 ⁄ 共 1878字 评论关闭
题目链接:   http://poj.org/problem?id=2828 题目大意:   有N个人在排队买票,每个人可站的位置从0到N                   后面来的人可能会插队,也有可能站在当前队伍的最后面                   N行,每行两个数,pas表示刚来的这个人会站在当前队伍的第pas位置上                   val表示这个人对应的值(0<=val<=i-1),最后按每个人所在的位置输出其相应的值 解题思路:   后面加入的人,必定会站在当前队伍之间或...
阅读全文
2018年09月22日 算法 ⁄ 共 2259字 评论关闭
题目链接:  http://poj.org/problem?id=3468 题目大意:  给出N个数,和M次查询                  C a b c  区间[a,b]的值都加上c                  Q a b     查询区间[a,b]值的和 解题思路:  线段树区间lazy延迟更新,每次插入区间标记lazy                  下次再操作此区间时用lazy更新下面的子树                   每个结点存储值是区间的和                   更新和查询的时间复杂度都是O(logN) 代码: #include <st...
阅读全文
2018年09月22日 算法 ⁄ 共 2545字 评论关闭
题目链接:  http://poj.org/problem?id=2528 题目大意:   给出一面宽度未知的海报墙                   再给出N张海报,每张海报会贴在墙的区间[a,b],高度与墙相等                   所有的海报按照顺序贴完,最后可以看到多少张海报(露出来就算) 解题思路:   海报所占用的区间可能会非常大,空间复杂度很高                   所以首先要做的就是离散化所有海报的区间                   如:  1  4                       ...
阅读全文