Google Code Jam 2009 (Qualification)

书接上篇

1. [84%/84%] Alien Language:给定pattern,求辞典中满足pattern的词的个数。

这道题,题目吓一跳,以为是和practise一样的,结果是另外一道。

内容再次吓一跳,perl代码简单到爆。直接把'(‘、’)’换成'[‘、’]’,当作字符类编译成正则,然后挨个匹配计数就行了。

2. [88%/86%] Watersheds:给定地图和高度,求有几个水凼凼。

这道题遍历每个cell,判断水流,由链表确定等价类,最后从小到大标号既可。

3. [88%/56%] Welcome to Code Jam:给定目标,求子串。

这道题一看,大量操作单个字符,选c会比perl有优势,所以用c。

简单的动态规划即可,有大量重复子问题。当前text中包含target的数量,等于当前text中,所有的target[0]其后的子串,所包含的target[1~end]的数量之和。

由于结果只需要4位,所以用int表示结果已经足够,计数的时候,超过9999,则减去10000。

可惜这道题的大数据集,我还是超时了,因为小数据集我time了一下,只用了0.001s,所以偷懒了一下,没有加缓存,准备直接用机器硬抗大数据集,等了近5分钟,居然还没算出结果,这时再更改程序加缓存、编译、上传就来不及了。

加入4行代码的缓存之后,大数据集time结果如下:

real    0m0.031s
user   0m0.028s
sys    0m0.000s

不到0.1s,很难想像加入缓存会有如此大的区别,真是遇鬼了。

GCJ 2009 Qualification Solution Download