排序方案速度测试

看书的时候时不时会遇到对各种排序算法的介绍。有这么多排序算法,在比赛中一般用哪种会比较好?一方面想着,“快排大法好!现成不用码!”但又听说有的数据会专门卡快排。而且,快排真的有那么快吗?种种顾虑涌上心头。所以,今天晚上我决定对两三个常见的排序算法测个明白,来个感性的认识。

当然,子勤下面的探究结果对于不同的情境可能不适用,我也无法保证一下结论的正确性(就连今天下午测得的结果也与今天晚上的有相互矛盾之处)。毕竟,有不同问题、不同数据、不同平台等众多因素的差异嘛。亲爱的朋友,套用下面的结论请谨慎。

继续阅读

UVa 457 - Linear Cellular Automata 解题报告

题目链接:http://uva.onlinejudge.org/external/4/457.html


题目分析

题目的背景是细胞增殖,这种增殖受到 DNA 的控制。题目给出了 dish 中的细胞的增殖规则,要求程序读入 DNA,输出第 1 - 50 天中每个 dish 的细胞数。

关键的地方在于:某 dish 该天的细胞数 = DNA[K],K = 该 dish 昨天的细胞数 + 左右 dish 昨天的细胞数
还要处理两处特殊情况:最左(右) dish 的左(右)侧没有 dish

继续阅读

UVa 10055 - Hashmat the brave warrior 解题报告

跟着《算法竞赛入门经典》的脚步,子勤试着在 UVa Online Judge 上做题。#10055 - Hashmat the brave warrior 是我做的第1题。但没想到的是,第1题就把我给坑到了,WA 了两次才过。


题目分析

这道题应该算得上是 UVa 上非常简单的一道题目。它以战士 Hashmat 与敌方的士兵数量之差为背景,其实就是让我们计算两数之差。值得注意的有:

继续阅读

为什么我不继续担任计社负责人

高一第二学期快要结束的时候,一中的三十八个学生社团都开展了社长换届工作,我们灵动计算机社也不例外。在换届之际,作为一名高一的副社长,我有机会参加新一轮的社团负责人竞选;而且,由于有一年的工作经历,我能够被选上的几率也许会相对大一些。但我选择了退出。

为什么我不继续担任计算机社负责人?得知我的这一选择后,有不少朋友向我问起了这个问题。虽然在寒假的时候,我就做出了初步的选择;但如果要我回答一个完全清晰的理由,我却很难马上答得上来,毕竟我自己也对此犹豫了很久,甚至有时候自己也没能说服自己。但我最终还是决定了。我想,同学们问我这个问题,也是因为看得起我吧。因此,我想在此尽可能全面地回答一下这个问题,弥补一下许多次对同学们的随便回应,也当做是给自己理理思绪。

我知道,我并不是“功成身退”,因为我既没有取得很大成就,又没有完全离开计社:过去的一年里,在全体工作人员的努力下,计算机社在新校区渐渐走上了发展的轨道,但我们也清楚地知道,她仍有许多不足之处,计社的工作仍有不少可以提升的空间。而不继续担任社团负责人,并不意味着我不再关心计社;相反地,我仍旧热爱着计社,仍旧关心她的发展,愿意为她出一份力。我也不是“累感不爱”(字面意思理解),尽管在计社的工作既充满困难和挑战又不乏繁琐枯燥之处,它们常常让我感到身心劳累,但这没有消磨掉我的热情,我依然享受与她共同奋斗的每一分、每一秒。社团工作也把学习成绩的退步和家人的反对带给了我,但这些是我可以面对的;它们虽然影响着我的选择,但并不是决定性的因素。

继续阅读

《算法竞赛入门经典》第3章习题

第3章的题子勤做得不太好,有些实现可能思路不够清晰,请原谅。


3-1 分数统计 (stat)

题目:

输入一些学生的分数,哪个分数出现的次数最多?如果有多个并列,从小到大输出。
任务 1:分数均为不超过 100 的非负整数。
任务 2:分数均为不超过 100 的非负实数,但最多保留两位小数。

分析:

由于不知道人数的范围,但分数的范围是确定的,因此我们可以以分数为数组下标、次数为数组元素值,全部读入后进行比较,找出最大的。要做到并列的从小到大输出,只需要从小到大遍历一边就好了,反正数组不太大。对于任务2而言,因为“最多保留两位小数”,所以可以扩大 100 倍,变实数为整数存进数组里,输出时再变回实数。

继续阅读

写了个发布博客更新的小脚本

博客换成 Hexo 之后,觉得写新博文方便了许多。不过,回想一下,现在发一篇新的博文还是有些事情要做的:

  1. 用 Markdown 写好博文,然后向 master 分支提交更新
  2. 用 Hexo 生成网页
  3. 把生成的网页拷贝到其他文件夹里,然后切换到 gitcafe-pages 分支
  4. 删除旧的网页,然后把刚刚拷出去的新网页拷回来,再向 gitcafe-pages 提交一次更新
  5. 向 GitCafe 推送更新
  6. 切换回 master 分支,方便下一次操作

这前前后后的操作加起来,折算成命令行操作的话,就有十几行了。看来工作量还是有不少的。我想,反正这些操作都是相同的,不如写成脚本吧。这样,写好文章后,执行一下这个脚本就可以了。(这也太懒了吧 ←_←)

所以子勤写一个这样的文件:

继续阅读

小天地改版了——博客演变记

先感慨一下:

好久没写博客啦!

自从上了高中,子勤的小天地就有很长时间没更新过了。一方面,是因为高中紧张的全日制住宿生活让我没什么时间更新博客;另一方面,就是更新博客太麻烦了。

子勤的小天地 v1.0 是通过直接书写 HTML 完成的。在这基础上,我用 Google Code Prettify 实现了代码高亮,用友言做评论框,还用 audio.js 实现了播放音乐的功能。这些以外的部分,都是我一点一点地打出来的。每一种颜色的选取,每一处阴影的设计,都凝聚着付出的汗水。

直接编写 HTML 的博客,在更新文章时的工作量可想而知。首先要拷贝模板进行修改,用 HTML 把新博文写好;然后,要把更新同步到首页和文章列表里;为了让搜索引擎知道更新,还要去修改 Sitemap。一次流程下来,大部分的时间都花在各种同步设置上了,因而压榨了书写内容的时间,也影响了更新的积极性。

继续阅读