现在位置: 首页 > 算法 > 文章
2018年09月23日 算法 ⁄ 共 884字 评论关闭
题目链接:http://poj.org/problem?id=2782 题目大意:  给出n袋长度不一定相同的垃圾,把它们全部装在长度不超过L的垃圾桶里;                     每个垃圾桶至多有两袋垃圾,并且垃圾的长度相加小于L;                     求最少用多少个垃圾桶可以装入全部垃圾; 解题思路:  每个垃圾桶最多只能有两袋垃圾,也就是说可以装是一袋或者两袋;                     先排序,然后分别从最小、最大两个极端开始枚举:      ...
阅读全文
2018年09月23日 算法 ⁄ 共 1654字 评论关闭
题目链接:http://poj.org/problem?id=2785 题目大意:  给出四个长度为n的列表(从上到下)                     从每个列表分别取出一个数据,使得相加的结果为0                     问最多存在多少种情况? 解题思路:  n的范围(1<=n<=4000),如果直接搜索 O(n^4) 那么肯定TLE.(计算机每秒钟的运行速度大概是10^8)                     可以转化为O(2*n^2):                     把1组和2组列表分别相加存到a[ ]数组中...
阅读全文
2018年09月23日 算法 ⁄ 共 1564字 评论关闭
题目链接:    http://poj.org/problem?id=3233 题目大意:    给出矩阵n*n的矩阵A,求对m取模后的结果 解题思路:    k的非常大,直接求解时间复杂度太高                    定义F[k]=A+A^2+A^3+....A^k                                                                   利用乘法的分配律可以减少运算 F[6]=A+A^2+A^3+A^4+A^5+A^6=(A+A^2+A^3)+(A+A^2+A^3)*A^3                                         每次运算二分减少规...
阅读全文
2018年09月23日 算法 ⁄ 共 1199字 评论关闭
题目链接:    http://poj.org/problem?id=3070 题目大意:    求Fibonacci数列第n项(0 ≤ n ≤ 1,000,000,000),对m取模后的结果 解题思路:    直接求解第n项,由于n太大,时间复杂度非常高                    我们需要构造一个矩阵使得与(a,b)相乘后等于(b,a+b)                    不防假设2x2矩阵为:                     x1      x2                     a               b                                            X  ...
阅读全文
2018年09月23日 算法 ⁄ 共 1561字 评论关闭
题目链接:   poj 1330 题目大意:   给出你一棵树,最后一行询问顶点a和顶点b的最近公共祖先 解题思路:   Tarjan离线查找最近公共祖先:                  搜到新的顶点,此顶点的临时祖先就是上一层的顶点                  直到搜到叶子就开始回溯,回溯的时候                  从这点出发搜过的顶点的临时祖先合并为这个顶点的上一层顶点 代码: //Final LCA离线算法求最近公共祖先 #include <stdio.h> #include &l...
阅读全文
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[  ]前缀的性质左边有颜色部分和右边有颜色部分完全相等                   因为左边的红色和右边的红色相等,如果左边的红色和左边的绿色相等,则左边的红色必定与右边的绿色相等                   既左红+左蓝+左绿和左绿是我们...
阅读全文