ZOJ 1503 One Person “The Price is Right”

于 2012年06月6日 发布在 算法&&ACM 2 条评论 »

好久没有做题了..刷刷DP吧,之前都没有好好做过这方面的题,比赛一遇到就放过..没有一点思路.

这是个比较基础的,还好是我自己想出来的,没有看hints.对于每对猜测次数G和生命值L,需要得到一个最大的N,让其可以找到一个策略,能在G和L都没用完前猜出正确的数,即必胜策略. 我们平时玩这种游戏的时候都是二分..然后从经验上判断这个是最快能猜到那个数的.这里因为有生命值,所以复杂了些.我们假设这个某对GL对应的最大的N为nmax,第一步我们的必胜策略肯定是从中间找一个数k,然后判断这个数是大了还是小了还是刚好. 如果没有猜中,就从左边或者右边的范围内继续查找.假设dp[i][j]表示当猜测次数是i,生命值是j的时候能得到的最大的N.

再来看k,如果k猜大了,那么生命值就减少了1.需要从小于k的范围内再猜,在小于k的范围内所能得到的最大N是dp[i-1][j-1],在大于k的范围内的到最大N是dp[i-1][j],所以可得dp[i][j] = dp[i-1][j-1] + dp[i-1][j] + 1,这就是状态转移方程.

Markdown 简洁入门

于 2012年06月4日 发布在 linux应用 6 条评论 »

最近折腾github比较多,在里面看到很多用Markdown的地方,比如wiki页面编辑,README.md文件,progit,感觉他是一个十分简单的标记语言,于是就打算学学。

Markdown的目标是实现“易读易写”,语法的目标是,“成为一种适用于网络的书写语言”。在写文档或者blog的时候可以避免一些排版上的苦恼。Markdown可以方便地转换为HTML,有对应关系,但他比HTML来的方便,因为不用考虑成对的标签。如果某些Markdown有某些标签没有实现,我们可以在文本中直接使用HTML语言。

在介绍语法之前,现在介绍一款chrome插件 – MaDe,此插件可以在页面右侧实时现实效果,很方便。如果对某些东西有疑惑,试验一下即可:)

阅读全文 »

编程珠玑 第三章 习题解答

于 2012年06月3日 发布在 算法&&ACM 没有评论 »

为什么我看完这一章不知道该写啥?。。整体来看是比较基础的。

1.if-else语句的每个分支的形式都差不多,我们可以用数组来使循环简单一点。数组中每个点表明一个阶段,用level[i]表示阶段i的起始点,tax[i]表示阶段i的税率,用have [i]表示这个阶段已经有的税收,然后得到收入后二分到相应的阶段,计算税收。

2.不知所云(用递归实现应该很简单,不用数组的话代码量会比较大)。

3.这个不会,看了答案了。这个方法的精髓就是把重复出现n次的字符用 n+‘字符’来表示,重复出现的行用同样的方法可以得到。这个方法给了我很大的启示,以前没有思路的一道题目,瞬间来了灵感。
阅读全文 »

编程珠玑 第二章 习题解答

于 2012年06月2日 发布在 算法&&ACM 5 条评论 »

这一章很奇葩啊。。书中B问题在一面的时候被问到,C在笔试的时候是第一大题(当时写了好多)。

1.在给定单词和字典的情况下,遍历字典,计算每个的标签,然后与给定的单词的标签比较。可以预处理的话就好说了,将所有单词按照标签排序,然后可以用equal_range求出区间,O(logN)。

2.可以类比如何找出没有出现的整数。43 0000 0000 大于int的表示范围。可以先扫面一遍,把第一位为0的和第一位为1的放到两个不同的文件中,看哪个文件里面的数多,就开始处理这个文件,把第二位的0和1的数字放到两个文件中,看哪个的数字多,依此类推,最后肯定得到一个数,他出现了不止一次。

3.我实现了两个算法。gao函数是那个杂技算法,gaogao是块交换算法。经过简单的测试还没有发现什么问题。n和len的最大公约数就是置换的次数。

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int gcd( int a, int b ){
    return b==0?a:gcd(b, a%b);
}
int gao( int *start, int *end, int n ){
    int len = end - start;
    int d = gcd( n, len );
    for( int i = 0; i < d; i++ ){
        int t = *(start+i);
        int next = i;
        while( (next+n)%len != i ){
            *(start+next) = *(start+(next+n)%len);
            next = (next+n)%len;
        }
        *(start+next) = t;
    }
}

阅读全文 »

编程珠玑 第一章 习题解答

于 2012年05月21日 发布在 算法&&ACM 9 条评论 »
编程珠玑虽然说给了习题的题目和答案,而且也比较详尽,但是鉴于以前看书有答案的往往看的不是太仔细,以至于很多东西都没有搞清楚,所以我决定把习题都记录下来。这样有助于我研究题目,解决问题。
第一章简单来说就介绍了个用bitmap排序的实例,从思维上给了我们思考问题的另一个角度。
1.c语言的话可以用qsort,但是感觉qsort的比较函数的定义较为复杂,还是推荐用c++中的sort。

int main(void){
    vector v;
    for( int i = 0; i < 100; i++ )
        v.push_back( rand() );
    sort( v.begin(), v.end() );
    for( int i = 0; i < 100; i++ )
        cout << v[i] << endl;
    return 0;
}

阅读全文 »

Boa源码分析 – 4 – 转意处理

于 2012年04月26日 发布在 linux应用 没有评论 »

build_needs_escape函数目的是要建立一个位图bitmap,表示哪些字符需要转意。此函数在escape.c中,首先到escape.h中看看。

#include "config.h"

/* Highest character number that can possibly be passed through un-escaped */
#define NEEDS_ESCAPE_BITS 128
//表示128位就行
#ifndef NEEDS_ESCAPE_SHIFT
#define NEEDS_ESCAPE_SHIFT 5     /* 1 << 5 is 32 bits */
#endif

#define NEEDS_ESCAPE_WORD_LENGTH (1<<NEEDS_ESCAPE_SHIFT)
//
#define NEEDS_ESCAPE_INDEX(c) ((c)>>NEEDS_ESCAPE_SHIFT)
//index嘛,表示在_needs_escape中的第几个数上表示

/* Assume variable shift is fast, otherwise this could be a table lookup */
#define NEEDS_ESCAPE_MASK(c)  (1<<((c)&(NEEDS_ESCAPE_WORD_LENGTH - 1)))
//NEEDS_ESCAPE_WORD_LENGTH - 1相当于一个掩码,取c最右边的五bit,然后在把1左移这么多位,就可以通过它获得相应位的状态了

/* Newer compilers could use an inline function.
 * This macro works great, as long as you pass unsigned int or unsigned char.
 */
#define needs_escape(c) ((c)>=NEEDS_ESCAPE_BITS || _needs_escape[NEEDS_ESCAPE_INDEX(c)]&NEEDS_ESCAPE_MASK(c))
//实现很简洁。。。
extern unsigned long _needs_escape[(NEEDS_ESCAPE_BITS+NEEDS_ESCAPE_WORD_LENGTH-1)/NEEDS_ESCAPE_WORD_LENGTH];
void build_needs_escape(void);

阅读全文 »

Boa源码分析 – 3 – 三个函数简析

于 2012年03月25日 发布在 linux应用 没有评论 »

下面看一下boa.c里面的三个函数:create_server_socket, drop_privs和 drop_privs。这三个函数都被声明为static表示,静态函数对普通函数的区别就是他只能在当前文件中可见。

static int create_server_socket(void)
{
    int server_s;
    server_s = socket(SERVER_AF, SOCK_STREAM, IPPROTO_TCP);
    //创建套接字SERVER_AF在compat.h中声明被声明为INET或INET6
    if (server_s == -1) {
        DIE("unable to create socket");
    }
    //DIE在defines.h中的宏定义为
    //#define DIE(mesg) log_error_mesg(__FILE__, __LINE__, mesg), exit(1)
    //__FILE__和__LINE__分别表示当前文件和当前行
    //log_error_mesg在log.c中有定义,向标准输出输出错误信息

    /* server socket is nonblocking */
    if (set_nonblock_fd(server_s) == -1) {
        DIE("fcntl: unable to set server socket to nonblocking");
    }//把套接字设定成非阻塞的,set_nonblock_fd在defines.h中为宏替代real_set_nonblock_fd(在util.c中定义)

    /* close server socket on exec so cgi's can't write to it */
    if (fcntl(server_s, F_SETFD, 1) == -1) {
        DIE("can't set close-on-exec on server socket!");
    }//将文件描述符标记设定为1,当执行exec族函数时关闭套接字

阅读全文 »

Boa源码分析 – 2 – boa.c流程

于 2012年03月24日 发布在 linux应用 一条评论 »

下面来看看boa.c吧

/* set umask to u+rw, u-x, go-rwx */
    c = umask(~0600);
    if (c == -1) {
        perror("umask");
        exit(1);
    }
    devnullfd = open("/dev/null", 0);
    /* make STDIN and STDOUT point to /dev/null */
    if (devnullfd == -1) {
        DIE("can't open /dev/null");
    }
    if (dup2(devnullfd, STDIN_FILENO) == -1) {
        DIE("can't dup2 /dev/null to STDIN_FILENO");
    }
    if (dup2(devnullfd, STDOUT_FILENO) == -1) {
        DIE("can't dup2 /dev/null to STDOUT_FILENO");
    }

这里设定了权限掩码为~600,也就是生成文件权限为rw——-,然后打开/dev/null,它相当于一个黑洞,输入任何东西都会丢失,读取也什么都读取不到,因为服务器进程是在守护进程,所以将标准输入输出定向到/dev/null。下面看getopt:
阅读全文 »

Boa源码分析 – 1 – Makefile

于 2012年03月20日 发布在 linux应用 4 条评论 »

boa是一个小型的webserver,设计目标是速度和安全,虽然这个项目已经很多年没有更新了,但是对于初学linux编程,网络编程的同学来说。。还是很有价值的。boa的实际代码量只有7000+(去掉autotools自动生成的东西),初看压力不大。当然还有一些适合学习的开源项目,如thttpd(也是一个http server,代码12000+行),redis(key-value存储系统,和Memcached类似,里面貌似有好多数据结构?两万多行)和coreutils (常用linux命令源码,什么cd,chmod,cp等等),还有好多,github和sourceforge上有很丰富资源。。

直接入题吧,boa也用到了Autotools,但是我实在是搞不清楚autotools的几个命令是怎么组织的。。干脆直接./configure ,开始分析Makefile。
阅读全文 »

make 知识小记

于 2012年03月19日 发布在 linux应用 没有评论 »

/*写完来吐槽下,,make的语法够多够复杂的。。。*/

make 可以简化编译过程,如果有一个近百个源文件的项目,如果有个文件更改后工程需要重新编译,那么一直用gcc -c a.c这些个命令敲来敲去会屎人的。运行make时候,他会寻找指定目录下(默认是 .)的Makefile文件并且分析依赖关系进行必要的编译。

Makefile文件的基本格式很简单:

目标文件: 依赖文件1 依赖文件2 依赖文件3 。。。。

[tab]编译命令

他的意思是目标文件是依赖于冒号后面几个文件的,如果这些依赖文件有更新的,那么其目标文件也需要更新。
阅读全文 »

第 4 页,共 10 页« 最新...23456...10...最旧 »