Coding Beans: 1月 2016

2016年1月31日星期日

[SPOJ APIO10A][DP] Commando

題目連結
最單純的想法是1D/1D的DP，但是顯然不夠快。
這時候看看SPOJ的tag上寫著Convex Hull，然後就可以無恥的去做凸包優化了。

[POJ 1741][男人八題][樹分治] Tree

題目連結

不多說......就是樹分治的經典問題......在那個科技還不發達的年代還是挺難做的......

找重心，分治計算答案。最難的地方大概是答案的加減要想清楚，不然很容易完全寫錯。

啟發式合併貌似也挺快的，晚點補上code。

2016年1月29日星期五

[教學][String][Data Structure] 後綴自動機(Suffix Automaton)

==========!! Warning !!==========
此文內容皆是出自自己的理解，若有與實際情況不符之處，請以論文或是大神文章為主
==========!! Warning !!==========

後綴自動機(Suffix Automaton)大概是我見過網路上最多教學資源的資料結構了，許多大陸和外國的神人都有寫教學文，包括寫過持久化資料結構介紹的clj大神。
不過有鑒於許多教學不是為了力求邏輯通順，定義複雜繁瑣，就是講解過程中，省略許多思考步驟，導致讀起來不甚順暢。
最後我還是決定自己完整的給出一篇教學文，使用最少的定義(3個)，盡量簡化構造它和使用它的思考流程，對於重要的性質除非必須，否則說明點到即止，不加以證明。

2016年1月28日星期四

[SPOJ SUBLEX][Suffix Automaton] SUBLEX - Lexicographical Substring Search

題目連結

撇去Suffix Automaton的部份不談，這題有很多細節值得仔細探討

[Codeforces Round #146 (Div. 1)] Cyclical Quest

題目連結

題目要求在一給定字串S上求出某一字串T的所有循環字串出現幾次
(此處循環字串的意義詳見原題)

[SPOJ NSUBSTR][Suffix Automaton] NSUBSTR - Substrings

題目連結

恩....一樣是個只給O(n)方法過的字串題，倍增算法之類的只能吃土了QQ
後綴自動機的介紹請參考這裡

2016年1月27日星期三

[SPOJ LCS2][Suffix Automaton] LCS2 - Longest Common Substring II

題目連結

跟 LCS 這篇的作法非常相似，基本概念就不說了
不過寫這題的時候花了頗大量的時間釐清答案的更新順序和debug(最後的bug竟然是錯在toposort寫爛了...)

難點在於要怎麼兩兩合併計算答案，這要對後綴自動機上的狀態表示感受到一定深度才能體會(?
code中的許多assert可以幫助理解一些關鍵點和常有的bug

[SPOJ LCS][Suffix Automaton] LCS - Longest Common Substring

原題連結

Suffix Automaton(後綴自動機)的初級練習題，關於Suffix Automaton的教學和介紹網路上有很多資源，我之後也會自己補上一篇的
這題會用SAM的主要原因是SPOJ會莫名的把O(nlogn)的Suffix Array解卡掉，所以能過的大概只有後綴自動機或是O(n)後綴樹、後綴陣列的構造法吧