某岛

… : "…アッカリ~ン . .. . " .. .
April 17, 2010

“解题报告”的书写格式…

Brief description:

欧几里德图里求两点间的最短路径。

Brief description(题意简述)是我最重要的标签之一,阅读大段的字幕是很伤神的,特别是到处都是英文题库的 ACM 世界里更是这样,而且偶尔路过这里的同学们也不一定再次之前读过这题,再说大家也都是很匆忙的,可能不一定会愿意读下面的文字,这个标签的目的是希望可以通过一个简短的描述,给题目的类型一些说明,这个标签的文字会是严肃的,通常也会写像上面例子里那样写一些图论术语。

而且这个部分也是我理解题意的部分,而且这个标签是每篇都会写的,一些特别水的题可能只包含一个 ” Brief description ” 标签就没了,写这个部分的时候我会特别仔细,我相信她也可以做一个很好的导航作用,来让大家想要不要帮我看一下这道题的错误或者是从解题报告里学习一些东西,或者呢是决定要不也要 follow us 把这道题做一遍。

.

Algorithm analyse:

嗯嗯,普通的动态规划题,所以我们先预处理出需要的代价函数 w, 然后呢用切割的次数 i 划分阶段,用左上角和右下角的坐标考察每一个字矩形。可以得到下面的状态转移方程。
$dp[i, x1, y1, x2, y2] = min{ dp[i-1, x1, y1, k1, y2] + w(k1+1, y1, x2, y2) , d[i-1, k1+1, y1, x2, y2] + w(x1, y1, k1, y2) } (x1<=a<x2)$

除了一些比较简单的题目外,Algorithm analyse(算法分析)标签是第二重要的标签,遣词酌句会比前面那个稍微随意一些,不过也是很严肃的,算法设计 ( Design ) 的部分也是这个标签所要涵盖的主题,另外在代码较复杂的时候,必要的复杂度分析也会包含在这个标签里,我不会把它们单独分开,另外这个标签也是最常会使用 ” LaTeX For WordPress ” 的地方额(额,在写这篇文章的时候,这个插件还是有 Bug 的,我还在调…)

这两个标签我会在一边读题的时候一边就想好怎么写,也就是说在正式动手编码之前我也许我就会把些部分先整理好,大部分的“报告书”包含这两个标签和一个 AC 的代码就没了,但是也不一定都会这样。

.

Solving boardcast:

不会做,读完题睡觉 Unsubmit –pm 21:30
写了一个朴素 TLE — Next day morning.

花了一晚上时间,写了一个七维线段树 AC (0.01s) — Nov. 12th am 00:14

上面的句子是我捏造的…额,算了当我认识到这道题目可能超出我目前所学范围或者我发现这题的代码量异常巨大,可能不是一时半会可以写好的时候我会做好这个标签,” Solving boardcast ” (广播剧)。

也有一些情况下是我当天脑子浆糊掉不停的 PE、 WA 啊、 CE 呀 也可能为这个标签的出现留下隐患。(我要尽力避免这种情况呜。)

当然上面的段落也并没有涵盖所有的情况,其实我很久以前就有写解题报告的习惯,写 WebLog 的好处是我可以更好的呢去维护它们,当我在某年里的某月学习了一种新的算法的时候,也许我会跑来给以前写过的一道题写一份更新的速度更快的算法,也会写在这个标签里。

时间的格式可能会有一些诡异(细心的同学会发现整个博客时间的格式都很诡异…但是在具体写出的时刻我则会保持格式一致,并且描述我在解题时所在的时区,通常我会省略月、年这些可以根据上下文推断出来的文字。)(通常时发贴的时间,如果是在同一天里的话我会只写时刻,不会精确到秒)(或者是一些 “相对” 的标签,Day II afternoon..)
(但是不排除一些题会一直难着我被我做了两三年还没做出来…)

段与段之间会有额外的空行,标签用两个<h3>标记保护起来,除了上面三个部分呢,偶尔也会出现一些“非主流”的标签项…(例如为了挖掘题目的潜力,用来供我背单词的 ” Vocabulary book ” (单词簿)、用来吐槽的 ” Background knowledge ” (背景知识,额特别是这个标签还会出现在 ” Brief description ” 的前面…),) 额,这些部分有可能隔几年才出现一次或者一辈子只在一道题里面出现。…至于它们是什么什么时候出现…我就不知道了…要看写题时的心情了…