Fookwood - fookwood.com - FOOKWOOD
General Information:
Latest News:
最长上升子序列nlogn算法 21 Aug 2013 | 10:07 pm
以前搞算法的时候看到过这个算法，但是没有仔细钻研过，似懂非懂，这两天看了看，总算是搞明白了。 问题的背景我就不多说了，相信通过搜索引擎来到这里的都是为了寻求简单易懂的nlogn的答案。 这个算法dp的状态有点诡异： dp[i] = 长度为i+1的上升子序列中末尾元素的最小值（没有某个长度的上升自序列的话相应位置是无穷大） 初看有点不太明白，为什么是末尾的最小值呢？为什么可以求出最长的公共子...
HTTP协议漫谈:概述 15 Sep 2012 | 11:35 am
自从学习linux编程以来，一直对与服务器的工作原理十分感兴趣，想写一个，然而暑假由于各种原因耽搁了下来，前几天是课程设计，大概两周时间，我就趁这个时间，简单实现了一下。又恰逢《HTTP权威指南》出版，入手了一本，大概翻了一遍，对于HTTP的细节了解了很多，收获还是很大的。我简单总结一下，巩固知识&&方便以后查看。 HTTP，超文本传输协议，是使用非常广泛的网络协议，我们平时上网看新闻，刷微博都要...
编程珠玑 第四章 习题解答 8 Jul 2012 | 04:44 pm
1.为了保证范围不超过范围，我们需要在初始化的时候，让变量不超出范围。这样每次循环得到的新的范围是慢慢缩小的，不会越界。 2.迭代的二分查找。 这个二分可以返回所需要查询的元素第一次出现的位置，如果不存在，则返回-1.在每个循环内，我们假定元素第一次出现的范围是闭区间[l，r]内，当循环体内语句执行完之后，我们得到了一个新的区间。新的区间的范围是一直在收敛的（不会存在r，l执行完循环之后大小没...
ZOJ 1503 One Person “The Price is Right” 6 Jun 2012 | 01:58 pm
好久没有做题了..刷刷DP吧,之前都没有好好做过这方面的题,比赛一遇到就放过..没有一点思路. 这是个比较基础的,还好是我自己想出来的,没有看hints.对于每对猜测次数G和生命值L,需要得到一个最大的N,让其可以找到一个策略,能在G和L都没用完前猜出正确的数,即必胜策略. 我们平时玩这种游戏的时候都是二分..然后从经验上判断这个是最快能猜到那个数的.这里因为有生命值,所以复杂了些.我们假设这个...
Markdown 简洁入门 4 Jun 2012 | 01:38 am
最近折腾github比较多，在里面看到很多用Markdown的地方，比如wiki页面编辑，README.md文件，progit，感觉他是一个十分简单的标记语言，于是就打算学学。 Markdown的目标是实现“易读易写”，语法的目标是，“成为一种适用于网络的书写语言”。在写文档或者blog的时候可以避免一些排版上的苦恼。Markdown可以方便地转换为HTML，有对应关系，但他比HTML来的方便，...
编程珠玑 第三章 习题解答 3 Jun 2012 | 06:15 pm
为什么我看完这一章不知道该写啥？。。整体来看是比较基础的。 1.if-else语句的每个分支的形式都差不多，我们可以用数组来使循环简单一点。数组中每个点表明一个阶段，用level[i]表示阶段i的起始点，tax[i]表示阶段i的税率，用have [i]表示这个阶段已经有的税收，然后得到收入后二分到相应的阶段，计算税收。 2.不知所云（用递归实现应该很简单，不用数组的话代码量会比较大）。 3....
编程珠玑 第二章 习题解答 2 Jun 2012 | 10:33 pm
这一章很奇葩啊。。书中B问题在一面的时候被问到，C在笔试的时候是第一大题（当时写了好多）。 1.在给定单词和字典的情况下，遍历字典，计算每个的标签，然后与给定的单词的标签比较。可以预处理的话就好说了，将所有单词按照标签排序，然后可以用equal_range求出区间，O(logN)。 2.可以类比如何找出没有出现的整数。43 0000 0000 大于int的表示范围。可以先扫面一遍，把第一位为0...
编程珠玑 第一章 习题解答 21 May 2012 | 02:47 pm
编程珠玑虽然说给了习题的题目和答案，而且也比较详尽，但是鉴于以前看书有答案的往往看的不是太仔细，以至于很多东西都没有搞清楚，所以我决定把习题都记录下来。这样有助于我研究题目，解决问题。 第一章简单来说就介绍了个用bitmap排序的实例，从思维上给了我们思考问题的另一个角度。 1.c语言的话可以用qsort，但是感觉qsort的比较函数的定义较为复杂，还是推荐用c++中的sort。 c++中的...
Boa源码分析 – 4 – 转意处理 26 Apr 2012 | 02:49 pm
build_needs_escape函数目的是要建立一个位图bitmap，表示哪些字符需要转意。此函数在escape.c中，首先到escape.h中看看。 escape.h中的东西让我看了很久才看懂。之前看programming pearls时也实现了个bitmap，在这里。 然后来看看escape.c 好吧，就这么多了，，感觉这一部分用c++的bitset比较好。。唉。。
Boa源码分析 – 3 – 三个函数简析 26 Mar 2012 | 12:28 am
下面看一下boa.c里面的三个函数：create_server_socket， drop_privs和 drop_privs。这三个函数都被声明为static表示，静态函数对普通函数的区别就是他只能在当前文件中可见。 下面来看第二个函数 drop_privs从语义上来讲是放弃一些权限， 不知道为啥要这样做。。 在设计应用程序时，我们总是试图使用最小特权（least privilege）模型。...
