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

Google Code Jam 2009 (Qualification)》上有2条评论

  1. 第三题的解法很神奇,某参赛者的源码

    char wel[] = “welcome to code jam”;

    int main()
    {
    int t, nt;
    char buf[512];
    scanf(“%d”, &nt);
    gets(buf);
    for(t = 1; gets(buf); t++)
    {
    int pd[32], len = strlen(buf);
    memset(pd, 0, sizeof(pd));
    pd[0] = 1;
    for(int i = 0; i = 0; j–)
    if(wel[j] == buf[i])
    pd[j+1] = (pd[j+1] + pd[j])%10000;
    printf(“Case #%d: %04dn”, t, pd[19]);
    }
    return 0;
    }

  2. Pingback引用通告: 碧云涛小屋 » Google Code Jam 2011 (Qualification)

发表评论

电子邮件地址不会被公开。 必填项已用*标注