POJ 3037 Skiing(Dijkstra) http://poj.org/problem?id=3037 题意:你在一个R*C网格的左上角,现在问你从左上角走到右下角需要的最少时间.其中网格中的任意两点的时间花费可以计算出来. 分析:        首先我们需要证明的是从左上角出发到R*C网格中其他任意一点的速度都是固定的.对于下面的矩阵: 1 5 3 6 3 5 2 4 3 我们想计算到数值为6的点时的速度? 从1->6的话 v6=v1*2…

2014年7月5日 0条评论 2点热度 阅读全文

HDU 1811 Rank of Tetris(并查集+拓扑排序) http://acm.hdu.edu.cn/showproblem.php?pid=1811 题意:         给你N个点(编号从0到N-1)和M个关系,要你判断这个图的所有点的顺序是否可以全部确定.不过对于任意点的关系可能存在A>B或A<B或A=B三种情况,如果A=B的话,那么就比较他们的编号,编号大的点分数大.(如果A=B且A编号>B编号,那么A分数大). 分析:   &…

2014年6月14日 0条评论 2点热度 阅读全文

POJ 2367 Genealogical tree(拓扑排序:输出方案) http://poj.org/problem?id=2367 题意:         大意就是给你一个N个点的图,并且给你图中的有向边,要你输出一个可行的点拓扑序列即可.输入格式为,第一行点数N,以下接着有N行,每行以0结尾.第i行包含了以i点为起点的有向边所指的所有节点. 分析:         直接用 vector G[maxn][maxn] 和in[max…

2014年6月13日 0条评论 2点热度 阅读全文

POJ 2585 Window Pains(拓扑排序判定) http://poj.org/problem?id=2585 题意:          给你一个4*4的棋盘窗口,现在电脑上有9个应用,每个应用占用固定的2*2正方形网格位置.你通过不同的顺序操作9个应用可以使得4*4的窗口当前显示的内容(数字代表)不同,现在给你一个4*4棋盘窗口的内容,问你这个内容是否合法. 分析:         其实本题就是一个判定拓扑排序是否…

2014年6月13日 0条评论 1点热度 阅读全文

POJ 1270 Following Orders(拓扑排序:输出所有可能) http://poj.org/problem?id=1270 题意:         输入数据有两行,第一行给你由26个单个小写字母表示的变量,第二行给出成对的变量如(x,y),表示x要在y前面.然后要你输出所有可能的变量序列且满足第二行的顺序约束.如果存在多解,按字典序从小到大输出所有结果. 分析:         注意了由于这里要输出所有的合法拓扑排序序列…

2014年6月12日 0条评论 1点热度 阅读全文

HDU 4099 Revenge of Fibonacci(高精度加法+字典树Trie) http://acm.hdu.edu.cn/showproblem.php?pid=4099 题意:         给你一个数,这个数是斐波那契数列中的一个数的前缀,要你找出满足这个前缀的最小下标.且这个下标如果查过了10W,还没有符合要求的数,就输出-1.且输入数不会查过40位,且没有前导0。 分析:         直觉的思路是:将…

2014年4月8日 0条评论 2点热度 阅读全文

POJ 1056 IMMEDIATEDECODABILITY(字典树Trie) http://poj.org/problem?id=1056 题意:         给你一个由很多01字符串组成的集合,问你集合中有没有一个字符串是其他另外一个或多个字符串的前缀. 分析:         直接建立字典树,并且在插入字符串的时候判断有没有该字符串的前缀或有没有包含该字符串的长字符串即可.        …

2014年4月8日 0条评论 1点热度 阅读全文

HDU 1671 Phone List(字典树Trie) http://acm.hdu.edu.cn/showproblem.php?pid=1671 题意:         给你多个由0-9构成的字符串集合,问你这个集合中是否有一个字符串是其他字符串的前缀? 分析:        直接构造字典树,然后一一插入每个字符串,判断是否有比当前字符串短或长的同一路径的字符串已经在树中了.     &nb…

2014年4月7日 0条评论 2点热度 阅读全文

HDU 2087 剪花布条(KMP:贪心) http://acm.hdu.edu.cn/showproblem.php?pid=2087 题意:         给你两个串S和T,问你S中最多不重叠的包含了多少个T串? 分析:         直接用KMP算法,用T模式串去匹配S主串即可,但是当匹配成功的时候要看看当前匹配点离上一个匹配点是不是距离差>=T的长度。         那么我们按…

2014年4月6日 0条评论 2点热度 阅读全文

HDU 3613 Best Reward(扩展KMP:回文判断) http://acm.hdu.edu.cn/showproblem.php?pid=3613 题意:给你一个字符串,要你把这个字符串分成两段,并使得被分开的两段价值和最大.一个串如果是回文,那么它的价值就是所有字符的价值和,否则价值为0. 分析:        首先原始串为S,将S逆转得到串T.(S=abcaaa,那么T=aaacba).     &n…

2014年4月6日 0条评论 1点热度 阅读全文