学步园

题目链接:   poj 1330 题目大意:   给出你一棵树，最后一行询问顶点a和顶点b的最近公共祖先 解题思路:   Tarjan离线查找最近公共祖先：                  搜到新的顶点，此顶点的临时祖先就是上一层的顶点                  直到搜到叶子就开始回溯，回溯的时候                  从这点出发搜过的顶点的临时祖先合并为这个顶点的上一层顶点 代码: //Final LCA离线算法求最近公共祖先 #include <stdio.h> #include &l...

题目链接:   poj 1470 题目大意:   给出一棵树，然后有有限次查询(a,b)                   每次查询节点a与节点b的最近公共祖先                   输出节点作为最近公共祖先的次数 解题思路:   离线查询最近公共祖先                   把每次查到的结果visit[ ]++，最后遍历一遍就行了 代码: //Final LCA离线算法求最近公共祖先 #include <stdio.h> #include <string.h> #include <stdlib.h> #include ...

题目链接:   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...

题目链接:   poj 1226 题目大意:   给出N个字符串，找出一个最长的子串                   使得它和N个字符串正向或者逆向匹配，输出长度 解题思路:   如果这个字串存在，那么它必定存在与N个字符串中最小的那个串                   找到N个字符串中最小的串，然后枚举最小串的所有子串                   从最长的子串开始枚举，长度逐渐减少                   只要存在这样的子串和其他的字符串匹配，当前长度就是最优解...

题目链接:   poj 3461 题目大意:   给出主串和模式串，求模式串在主串中出现的次数(部分可以重合) 解题思路:   KMP从主串的第一个字符开始匹配                    开始是匹配成功就立刻退出，再次从上次退出的下一个字符开始匹配，TLE...                    利用上next[ ]数组的含义，每次不全部退出，而是退出部分j=next[ j ] 代码: //Final Kmp，给出模式串和主串，求模式串在主串中出现的次数(可以部分重叠) #include...

题目链接:   poj 2752 题目大意:   给出字符串，找出所有的前缀和后缀相等的子串                   按小到大输出这些子串的长度 解题思路:                                  如图所示，根据next[  ]前缀的性质左边有颜色部分和右边有颜色部分完全相等                   因为左边的红色和右边的红色相等，如果左边的红色和左边的绿色相等，则左边的红色必定与右边的绿色相等                   既左红+左蓝+左绿和左绿是我们...

题目链接:   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的匹配过程         ...

题目链接:    http://poj.org/problem?id=3264 题目大意:   给出初始化的区间值，m次查询                   每次查询区间[a，b]的最大值－最小值 解题思路:   线段树    更新: 无更新    查询:区间查询                   建立线段树的时候，每个结点存储左右子树的最大值和最小值                   查询时直接访问区间最大值和最小值，不需要查找到最低                   查询时间复杂度O(logN) 代码: #include <stdio...

题目链接:   http://poj.org/problem?id=2828 题目大意:   有N个人在排队买票，每个人可站的位置从0到N                   后面来的人可能会插队，也有可能站在当前队伍的最后面                   N行，每行两个数，pas表示刚来的这个人会站在当前队伍的第pas位置上                   val表示这个人对应的值(0<=val<=i-1)，最后按每个人所在的位置输出其相应的值 解题思路:   后面加入的人，必定会站在当前队伍之间或...

题目链接:  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...