2012年06月 存档

ZOJ 1503 One Person “The Price is Right”

2012年06月6日,星期三

好久没有做题了..刷刷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日,星期一

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

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

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

(更多…)

编程珠玑 第三章 习题解答

2012年06月3日,星期日

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

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

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

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

编程珠玑 第二章 习题解答

2012年06月2日,星期六

这一章很奇葩啊。。书中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;
    }
}

(更多…)