某島

… : "…アッカリ~ン . .. . " .. .
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 ” 的前面…),) 額,這些部分有可能隔幾年才出現一次或者一輩子只在一道題裡面出現。…至於它們是什麼什麼時候出現…我就不知道了…要看寫題時的心情了…