算法题整理——线段树
POJ2777_Count Color描述有一块长度为L厘米的板子，我们可以把板子分成L块，每块一厘米长。
我们现在给板上色，规则是一块只能涂一种颜色，使用不同的整数取描述某种颜色，我们可以做的操作有：
“C A B C” 把区间[A,B]涂成颜色C。
“P A B” 输出区间[A,B]之间的不同颜
...
算法题整理——KMP
发表于
|
分类于
基础算法
在做字符串的匹配时，我们有字符串S和T，现在想要从S中找到等于T的连续子串，一个朴素的想法是从S的每个字符开始，逐个和T的字符匹配，如果匹配不成功，再从S的下一个字符开始逐个匹配，这样的算法复杂度是O(NM)。
为了优化算法，我们注意到一个事实，即当我们匹配失败时，前面一定有一部分字符是匹配成功了的
...
算法题整理——Huffman树和字典树
发表于
|
分类于
基础算法
Huffman树CH1701_合并果子描述在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。
每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并
...
算法题整理——Hash
发表于
|
分类于
基础算法
POJ3349_Snowflake Snow Snowflakes描述有n片雪花，每个雪花使用6个整数来描述其每个角。比如1，2，3，4，5，6，描述可以从任意一个角开始，比如上面的雪花也可以被描述为2，3，4，5，6，1，也可以是逆序的如3，2，1，6，5，4只要按一个圈来描述六个角就行。
现在，
...
算法题整理——差分和前缀和
发表于
|
分类于
基础算法
差分POJ3263_Tallest Cow描述Farmer John 有N头牛排列成一排，当两头牛i，j之间的牛身高都小于它们时，这两头牛可以看到对方。
现在，知道最高的牛的编号是I，身高为H，以及R对可以相互看到对方的牛的编号。
在让每头牛都尽可能高的情况下，求出所有牛的身高。
数据范围1 ≤ N
...
算法题整理——A*和IDA*搜索
发表于
|
分类于
基础算法
A*POJ1077_Eight
据说这道题是不做人生就不完整的典中典
看到这个9Puzzle，我突然想起了隔壁MasterMa努力两周不眠不休的16Puzzle
幸好我没选上人工智能……
描述求解八数码问题，并用“lrud”来描述空格子移动的方向，输出移动次数最少的
...