這個是學習編程時的一個耳熟能詳的問題了：

n個人(編號爲0,1,...,n-1)圍成一個圈子，從0號開始依次報數，每數到第m個人，這個人就得自殺，之後從下個人開始繼續報數，直到所有人都死亡爲止。問最後一個死的人的編號(其實看到別人都死了之後最後剩下的人可以選擇不自殺……)。

這個問題一般有兩種問法：

• 給出自殺順序。不少數據結構初學書都會以這個問題爲習題考驗讀者對線性表的掌握。比較常見的解法是把所有存活的人組織成一個循環鏈表，這樣做時間複雜度是O(n*m)的。另外可以使用order statistic tree(支持查詢第k小的元素以及詢問元素的排名)優化到O(n log n)。另外有篇1983年的論文An O(n log m) Algorithm for the Josephus Problem，但可惜我沒找到下載鏈接。
• 求出最後一個人的編號。可以套用上一種問法的解法，但另外有更加高效的解法，下文展開討論。

Read More

關於做題這回事，引用一下：

1
2

Chao Xu，Haskell用戶.
acm算是用來訓練秒面試題的一個方式。 像我這種非cs系學生全靠玩acm的訓練秒各個公司。

深以爲然。算法題帶來的代碼能力的效用實在是太大了，除了訓練思維外對速度、準確性也有極大幫助。真切感受到解決一個大作業花了數小數編寫，再花了更長的時間調試，和立刻寫完、寫完就對的差異。訂閱過一些郵件列表，偶爾能看到一些非常蒼白的問題的人，也能看到內容可能更空洞的回覆。以及市面上很多浮誇的書。如果方法恰當潛心研習一段時間應該不會出現這樣的問題呢。所以當我看到《編程之美》這個書名的時候，第一印象也是那類浮華的書，等待之前某次活動拿到一本看才發現不是，”編程“、”美“字樣在我心目中的地位都被這些浮誇的事物玷污了。

我現在發現自己看過的東西拓撲順序不太對了，簡單說就是ld -la -lb -la，這可以算作一個tech joke吧。昨天經過fqj1994指導，今天終於把https開起來了，感覺又有所提高，好開心啊。

Read More

Hexo

我一直走靜態博客路線。最早用make+m4搭建博客，後來改用Haskell的Hakyll，因爲網站相關的工具鍊(HTML、CSS、JS模板引擎等)不夠用去年11月又換成了Node.js社區的DocPad。最近升級DocPad壞掉了，於是8月上旬又折騰了下遷移到了Hexo。

Read More

首部

Carbon Copy (Cc:)

Carbon copying指的是用複寫紙複寫，電子郵件世界裏借用了這個術語表示把副本抄送給非主要收件人。

Blind Carbon Copy (Bcc:)

RFC5322提及郵件客戶端有三種處理Bcc:的方式：

• To、Cc、Bcc收件人均收到同樣的郵件，該郵件中Bcc:首部被移除
• To、Cc收件人收到Bcc:首部被移除的郵件。Bcc收件人收到帶有Bcc:首部的郵件， 實現可以決定Bcc收件人是否能見到其他Bcc收件人。
• To、Cc收件人會看到空的Bcc:首部。

供參考，下面是RFC5322的3.6.3節對Bcc:的描述原文：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

The "Bcc:" field (where the "Bcc" means "Blind Carbon Copy") contains
addresses of recipients of the message whose addresses are not to be
revealed to other recipients of the message.  There are three ways in
which the "Bcc:" field is used.  In the first case, when a message
containing a "Bcc:" field is prepared to be sent, the "Bcc:" line is
removed even though all of the recipients (including those specified
in the "Bcc:" field) are sent a copy of the message.  In the second
case, recipients specified in the "To:" and "Cc:" lines each are sent
a copy of the message with the "Bcc:" line removed as above, but the
recipients on the "Bcc:" line get a separate copy of the message
containing a "Bcc:" line.  (When there are multiple recipient
addresses in the "Bcc:" field, some implementations actually send a
separate copy of the message to each recipient with a "Bcc:"
containing only the address of that particular recipient.)  Finally,
since a "Bcc:" field may contain no addresses, a "Bcc:" field can be
sent without any addresses indicating to the recipients that blind
copies were sent to someone.  Which method to use with "Bcc:" fields
is implementation dependent, but refer to the "Security
Considerations" section of this document for a discussion of each.

在Gmail裏發封沒有To:、Cc:，只有Bcc:的郵件，收件人就會看到To: undisclosed-recipients: ;

Signature Block

附在郵件正文後面作爲簽名信息，通常會包含發件人的職位、聯繫方式等。 爲了和正文分隔開，一般使用兩個連字符跟着一個空格和一個換行符(sig dashes)，用C語言的字面字符串表示方式就是" -\n"。 郵件客戶端可以認出雙連字符記號用與正文不同的樣式標記出來或者隱藏。

Top Posting vs Bottom Posting

Posting這個詞是用來描述新聞組的，

在回覆郵件時，表示回覆文本時在原文下面寫回覆(bottom posting)還是在原文上面先回覆(top posting)。 傳統的方式是採用bottom posting， 先發生的事(引文)出現在前面、後發生的(回覆)出現在後面在時間順序上較爲自然， 而top posting則會對理清事件的先後順序造成阻礙：

1
2

> Where are you?
At home.

他們抨擊top posting的理由就是後者顛倒了引文和回覆的時間順序：

1
2

At home.
> Where are you?

對閱讀郵件特別是很長的線索時造成障礙。在很多郵件列表，網絡禮儀就是使用bottom posting，

另外還有interleaved posting，把原文分爲多段，在每一段後寫下自己的回覆。 這種風格可以被用作point-by-point rebuttal，逐條駁斥對方的觀點。

現在top posting佔到了上風，我覺得很大一部分原因是網頁版郵件客戶端的興起和非黑客郵件使用者數目的激增。 郵件客戶端缺乏標註引文和切換引文顯示功能時，採取top posting的方式能減少鼠標滾動，更容易看到回覆的內容。

比如說Mutt默認就設置了快捷鍵跳到下一個不包含引文的行：

1
2
3
4

<skip-quoted> (default: S)

    This function will go to the next line of non-quoted text which comes after
    a line of quoted text in the internal pager.

以及用於切換引文是否顯示的：

1
2
3
4
5
6
7

<toggle-quoted> (default: T)

    The pager uses the $quote_regexp variable to detect quoted text when
    displaying the body of the message. This function toggles the display of
    the quoted material in the message. It is particularly useful when being
    interested in just the response and there is a large amount of quoted text
    in the way.

Reply-To

這個郵件首部爲用戶回覆郵件時提供建議，設定新郵件的To:首部。

Thread

References

In-Reply-To

format=flowed

Mail-Followup-To

回覆郵件時如果選擇了follow up(或者說reply to all)的方式，那麼收件人會被填爲Mail-Followup-To設定的地址。 避免發件人如果訂閱了該郵件列表的話收到兩封相同的郵件。

Mutt在你設置subscribe該郵件列表時會自動設置Mail-Followup-To首部。

X-Mailer

一些不友好的客戶端：

QQMail

不使用References:首部。

Mutt

query_command

1
2

set query_command="echo; grep %s ~/.mutt/aliases | cut -d' ' -f3-"
bind editor <tab> complete-query

其他

• 三種“From”：http://stackoverflow.com/questions/1235534/what-is-the-behavior-difference-between-return-path-reply-to-and-from

参考配置

http://www.spinnaker.de/mutt/muttrc

Sender Policy Framework

Natas Wargame是關於web安全的wargame。

Read More

7月31日

我和Kelwin、zTrix、LittleFatter等同行，在大本營集合，並領到了隊服：

隊服背面logo總感覺需要重新設計一下。另外三名隊員已經到達拉斯維加斯了，而Fish尚未啓程。在UA888飛機上待了三個多小時，因爲飛機故障我們被安排在北京臨空皇冠假日酒店住一宿。

Read More

記得DEFCON CTF Quals是在6月15日到6月17日早晨，而8:00我要參加數字邏輯電路的期末考試。0:00多回到寢室，舍友告訴我之前臺灣小學期的事還有很多手續要辦，而我都沒處理。我得在北京市出入境管理管理辦事大廳上預約，做完各項活動已是1:00多，5:30起牀“預習”數字邏輯電路兩小時就邁向考場。

Read More

昨天逛微博時無疑發現今天居然就是第二屆青少年開發者大會了，之後又看到果殼網也有介紹，背景圖片第一眼看去就是郭老師，再一眼劉嘯宇，感覺奇怪……推測一下原來第三個人似乎是我，想起來第一屆大會時的情形了……恰好ppwwyyxx和zxytim也在學校，就約定今天來湊個熱鬧了。會場在中國科學院計算中心研究所，入會場時大概剛好9:00，人還是不多。這一次確確實實是青少年的開發者大會了，參會學生很多，而不像第一次大會主要都是已經工作的講者。我記得第一屆大會郭老師還說大會還有年齡限制，他都快到限制了。現在我們三個“老人”來這裏算不算不接地氣。以前人人時似乎有一羣“跪圈”在北京活躍的人，不過老實說我真不喜歡“跪圈”這個說法。互相學習是件好事，不過膜拜和跪來跪去還是免了。這些人似乎都沒有來，和去年相比平均年齡也許能下降10歲吧。我們三個就成了這裏年紀最大的幾個人了。這可能是因爲北京的青少年開發者比深圳多？也可能是宣傳做好了。不過用just-ping.com測試2013.adc-cn.org，大多數檢測點都返回Packets lost (100%)。

Read More

Suricata

Intrusion detection System(IDS)監控網絡或系統，尋找各類違反安全方針的行爲。Suricata是Open Information Security Foundation和其他相關支持協會從2009年開始開發的一套用於網路入侵檢測(IDS)、入侵防護(IPS)及網絡監控的系統。這方面最著名的產品是Sourcefire的Snort。那麼爲什麼要選擇Suricata呢？我在這方面的知識還幾近空白，無法在架構之類的方面作出判斷，想的到的用Suricata的理由只有這三點：

Read More

下篇見調試技巧2。

Debug Hacks

作者爲吉岡弘隆、大和一洋、大巖尚宏、安部東洋、吉田俊輔，有中文版《Debug Hacks中文版—深入調試的技術和工具》。這本書涉及了很多調試技巧，對調試器使用、內核調試方法、常見錯誤的原因，還介紹了systemtap、strace、ltrace等一大堆工具，非常值得一讀。

Read More