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月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)後綴樹、後綴陣列的構造法吧

2016年1月26日 星期二

[Codeforces 100495A][2014 KTU ACM ICPC Qualification Round][Dijkstra] Crystals

原題連結

注意到因為n很小...所以對於任何一個水晶集合都可以將狀態用一個int表示出來(點),然後將集合的變換看成狀態的轉移(邊)

那麼本題就可以套用經典的最短路算法解決O(NlogN),此時N=(2^n)

[Codeforces 100488M][2014-2015 Samara SAU ACM ICPC Quarterfinal Qualification Contest] Construct a Permutation

原題連結

題意即構造最長排列使得LIS長度為a,LDS長度為b(Longest Decreasing Subsequence)

[Codeforces 100488K][2014-2015 Samara SAU ACM ICPC Quarterfinal Qualification Contest] Two Pirates

原題連結

首先貪心顯然是要WA的,就不解釋了
困難之處在於無法知道最終兩人分別會取到什麼樣的數字集合

[Codeforces 100488C][2014-2015 Samara SAU ACM ICPC Quarterfinal Qualification Contest] Lost Temple

原題連結

題意其實就是求出所有正整數對(a,b)使得a*b=k(a+b)
化簡之後可以得到(a-k)(b-k)=k^2

2016年1月25日 星期一

[Codeforces 452E][MemSQL Start[c]UP 2.0 - Round 1][Suffix Array] Three strings

原題連結

首先老規矩,把三個字串用神秘的符號分隔後拼接起來,構造SuffixArray和Height陣列

相似的後綴會被排在一起,而且我們可以很快知道在SuffixArray的一群連續後綴的LCP(by H陣列)