最近開(kāi)始寫trie樹(shù)，trie樹(shù)還可以和并查集一起運(yùn)用。

       poj 3283是一道典型的trie樹(shù)問(wèn)題，為了節(jié)約malloc的時(shí)間，我靜態(tài)生成需要申請(qǐng)的內(nèi)存，然后自己管理。由于預(yù)估poj的數(shù)據(jù)比較弱，所以這個(gè)方法可行。

      為了測(cè)試需要開(kāi)辟空間的大小，我無(wú)恥的用小號(hào)不斷的刷，終于確定了大小。

      用大號(hào)提交上去之后，饒有興致的看了一下排名。悲劇的發(fā)現(xiàn)，居然是第二名 63ms，而第一名是我無(wú)恥的小號(hào)littlenumber 47ms。我擦....         今天做了一個(gè)奇怪夢(mèng)，像看了部電影一般。醒來(lái)后居然都記得。故事有點(diǎn)科幻，有幾個(gè)主人公，記錄一下。


---------------------------------
 
        在現(xiàn)代化的大城市中心街區(qū)中，走來(lái)一伙人。有的西裝革履，有的嘻哈打扮，他們的眼神很奇怪。為首的是一個(gè)穿白大褂的學(xué)者，他高而瘦，帶著眼睛，眼里射出冰冷的目光。這伙人最終在一個(gè)立交橋下停了下來(lái)，他們好像在鞭打什么。

        一旁走來(lái)了三男三女，很好奇的，湊上一看。好像其中有三個(gè)人在欺負(fù)橋下的乞丐。他們?nèi)蚰_踢，甚至鞭笞那個(gè)乞丐。終于其中一名男子再也忍受不住大喝到“住手”，此人老實(shí)敦厚，但看上去正義凌然，應(yīng)該是一名退伍軍人。其他兩個(gè)男人也邁步向前。
 
        教授示意了一下三人停手，然后頭朝來(lái)人一拱，示意讓三個(gè)手下解決掉多余之人。三人齊上，同正義方三人一起打起來(lái)。正義一方中另兩為一個(gè)衣著時(shí)尚，英俊帥氣，貌似應(yīng)該在一些聲色場(chǎng)所做DJ之類；另一人呆頭呆鬧，但穿著保安的衣服。三個(gè)女人中有一個(gè)人是保安的妻子，看上去結(jié)婚多年。另一人衣著時(shí)尚，面容姣好應(yīng)該是個(gè)小白領(lǐng)；最后一個(gè)人簡(jiǎn)簡(jiǎn)單單，普普通通，但是眼中透著股靈氣，其實(shí)是個(gè)記者。

        保安的妻子擔(dān)心丈夫，竟直接向教授進(jìn)攻去了。很奇怪的戰(zhàn)斗，那伙匪徒每個(gè)人都好像在被動(dòng)挨打，沒(méi)有有效的反抗。教授被女人扇了幾個(gè)耳光后，嘴角有絲血跡，但是似乎冷笑了一下。

         大戰(zhàn)的結(jié)局，這伙匪徒居然被幾個(gè)人打炮了，而那個(gè)乞丐也不見(jiàn)了。莫名奇妙，白領(lǐng)在一旁看著DJ很有愛(ài)慕之意想要上去搭訕幾句，被冷冰冰的回絕；女記者心中充滿疑問(wèn)，詢問(wèn)了幾個(gè)人聯(lián)系方式后，向那伙人逃走的方向走去。。。

 [從這里開(kāi)始故事開(kāi)始分支]
          
          女記者的故事

          女記者跟蹤那伙人，居然發(fā)現(xiàn)這伙人不是這個(gè)世界上的人，或者說(shuō)他們是另外一個(gè)空間的人。有的人是去世后可以到這里獲得新生，有些人卻來(lái)這里協(xié)助他們?cè)谧鲆恍┕ぷ?。女記者潛入后，發(fā)現(xiàn)這個(gè)團(tuán)伙其實(shí)在做一些有意義的事情。在她了解到了真想之后，她主動(dòng)的來(lái)到他們的世界。


          保安的故事

          保安是個(gè)憤青，他為自己家庭的生活壓力大而煩惱。但是卻恨自己頭腦簡(jiǎn)單而掙不了更多錢，妻子也在外面拼命的打工。女記者來(lái)到保安家里，暗示可以去某個(gè)地方看看增加自己的競(jìng)爭(zhēng)力。保安來(lái)到后發(fā)現(xiàn)是一個(gè)教室，教室中有些書(shū)籍。（具體的略過(guò)）他居然發(fā)現(xiàn)講課的人就是白衣教授。教授用那天他對(duì)待別人的方式對(duì)待保安自己，仿佛在暗示輪回和因果的關(guān)系。保安激動(dòng)的想獲得了真理，并開(kāi)始在為這個(gè)組織做事。后來(lái)有拉了他老婆入伙。他老婆入伙的方式也和那天情景相識(shí)。

           女白領(lǐng)和DJ的故事

           （具體的不記得了）DJ是一個(gè)有自閉癥的人，不知與別人相處。女白領(lǐng)發(fā)現(xiàn)他周圍很多女性，但DJ似乎都沒(méi)有什么興趣。DJ死于一次意外后，來(lái)到了教授的旗下。女白領(lǐng)在得知消息后，非常沮喪。但居然有一天在街上再次看到DJ的背影后，開(kāi)始懷疑。（之后略）

           退伍軍人的故事

           退伍軍人是一個(gè)強(qiáng)迫癥患者，他與他的妻子雖然在一起但是沒(méi)有任何的感情，他的妻子不了解他。最后在若干年后他才來(lái)到教授的世界中，他終于找到了解開(kāi)心結(jié)的方法。


            大結(jié)局

            保安夫妻很幸福，女記者幫助退伍軍人重新認(rèn)識(shí)自己，退伍軍人看到自己的妻子也找到另外一半；女白領(lǐng)付出了很多，DJ終于慢慢的開(kāi)竅。



--------------------

有很多細(xì)節(jié)忘記了，但是總之故事很離奇，也很完整。我驚嘆有這樣的夢(mèng)，懷疑自己是不是被inception了。




初期:
一.基本算法: 
     (1)枚舉. (poj1753,poj2965)
     (2)貪心(poj1328,poj2109,poj2586)
     (3)遞歸和分治法. 
     (4)遞推. 
     (5)構(gòu)造法.(poj3295)
     (6)模擬法.(poj1068,poj2632,poj1573,poj2993,poj2996)
二.圖算法: 
     (1)圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷. 
     (2)最短路徑算法(dijkstra,bellman-ford,floyd,heap+dijkstra) 
        (poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)
     (3)最小生成樹(shù)算法(prim,kruskal)
        (poj1789,poj2485,poj1258,poj3026)
     (4)拓?fù)渑判?(poj1094)
     (5)二分圖的最大匹配 (匈牙利算法) (poj3041,poj3020)
     (6)最大流的增廣路算法(KM算法). (poj1459,poj3436)
三.數(shù)據(jù)結(jié)構(gòu). 
     (1)串 (poj1035,poj3080,poj1936)
     (2)排序(快排、歸并排(與逆序數(shù)有關(guān))、堆排) (poj2388,poj2299)
     (3)簡(jiǎn)單并查集的應(yīng)用. 
     (4)哈希表和二分查找等高效查找法(數(shù)的Hash,串的Hash)   
        (poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)
     (5)哈夫曼樹(shù)(poj3253)
     (6)堆 
     (7)trie樹(shù)(靜態(tài)建樹(shù)、動(dòng)態(tài)建樹(shù)) (poj2513)
四.簡(jiǎn)單搜索 
     (1)深度優(yōu)先搜索 (poj2488,poj3083,poj3009,poj1321,poj2251)
     (2)廣度優(yōu)先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)
     (3)簡(jiǎn)單搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)
五.動(dòng)態(tài)規(guī)劃 
     (1)背包問(wèn)題. (poj1837,poj1276)
     (2)型如下表的簡(jiǎn)單DP(可參考lrj的書(shū) page149): 
       1.E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533)
       2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最長(zhǎng)公共子序列)
   
         (poj3176,poj1080,poj1159)
       3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最優(yōu)二分檢索樹(shù)問(wèn)題) 
六.數(shù)學(xué) 
     (1)組合數(shù)學(xué): 
        1.加法原理和乘法原理. 
        2.排列組合. 
        3.遞推關(guān)系. 
          (POJ3252,poj1850,poj1019,poj1942)
     (2)數(shù)論. 
        1.素?cái)?shù)與整除問(wèn)題 
        2.進(jìn)制位. 
        3.同余模運(yùn)算.
          (poj2635, poj3292,poj1845,poj2115)
     (3)計(jì)算方法. 
        1.二分法求解單調(diào)函數(shù)相關(guān)知識(shí).(poj3273,poj3258,poj1905,poj3122)
七.計(jì)算幾何學(xué). 
     (1)幾何公式.
     (2)叉積和點(diǎn)積的運(yùn)用(如線段相交的判定,點(diǎn)到線段的距離等). (poj2031,poj1039)
 
     (3)多邊型的簡(jiǎn)單算法(求面積)和相關(guān)判定(點(diǎn)在多邊型內(nèi),多邊型是否相交) 
         (poj1408,poj1584)
     (4)凸包.  (poj2187,poj1113)

 

中級(jí):
一.基本算法: 
     (1)C++的標(biāo)準(zhǔn)模版庫(kù)的應(yīng)用. (poj3096,poj3007)
     (2)較為復(fù)雜的模擬題的訓(xùn)練(poj3393,poj1472,poj3371,poj1027,poj2706)
二.圖算法: 
     (1)差分約束系統(tǒng)的建立和求解. (poj1201,poj2983)
     (2)最小費(fèi)用最大流(poj2516,poj2195)
     (3)雙連通分量(poj2942)
     (4)強(qiáng)連通分支及其縮點(diǎn).(poj2186)
     (5)圖的割邊和割點(diǎn)(poj3352)
     (6)最小割模型、網(wǎng)絡(luò)流規(guī)約(poj3308, )
三.數(shù)據(jù)結(jié)構(gòu). 
     (1)線段樹(shù). (poj2528,poj2828,poj2777,poj2886,poj2750)
     (2)靜態(tài)二叉檢索樹(shù). (poj2482,poj2352)
     (3)樹(shù)狀樹(shù)組(poj1195,poj3321)
     (4)RMQ. (poj3264,poj3368)
     (5)并查集的高級(jí)應(yīng)用. (poj1703,2492)
     (6)KMP算法. (poj1961,poj2406)
四.搜索 
     (1)最優(yōu)化剪枝和可行性剪枝 
     (2)搜索的技巧和優(yōu)化 (poj3411,poj1724)
     (3)記憶化搜索(poj3373,poj1691)
     
五.動(dòng)態(tài)規(guī)劃 
     (1)較為復(fù)雜的動(dòng)態(tài)規(guī)劃(如動(dòng)態(tài)規(guī)劃解特別的施行商問(wèn)題等)
         (poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)
     (2)記錄狀態(tài)的動(dòng)態(tài)規(guī)劃. (POJ3254,poj2411,poj1185)
     (3)樹(shù)型動(dòng)態(tài)規(guī)劃(poj2057,poj1947,poj2486,poj3140)
六.數(shù)學(xué) 
     (1)組合數(shù)學(xué): 
        1.容斥原理. 
        2.抽屜原理. 
        3.置換群與Polya定理(poj1286,poj2409,poj3270,poj1026). 
        4.遞推關(guān)系和母函數(shù). 
        
     (2)數(shù)學(xué). 
        1.高斯消元法(poj2947,poj1487, poj2065,poj1166,poj1222)
        2.概率問(wèn)題. (poj3071,poj3440)
        3.GCD、擴(kuò)展的歐幾里德(中國(guó)剩余定理) (poj3101) 
     (3)計(jì)算方法. 
        1.0/1分?jǐn)?shù)規(guī)劃. (poj2976)
        2.三分法求解單峰(單谷)的極值. 
        3.矩陣法(poj3150,poj3422,poj3070)
        4.迭代逼近(poj3301)
     (4)隨機(jī)化算法(poj3318,poj2454)
     (5)雜題.
         (poj1870,poj3296,poj3286,poj1095)
七.計(jì)算幾何學(xué). 
        (1)坐標(biāo)離散化. 
        (2)掃描線算法(例如求矩形的面積和周長(zhǎng)并,常和線段樹(shù)或堆一起使用). 
            (poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)
        (3)多邊形的內(nèi)核(半平面交)(poj3130,poj3335)
        (4)幾何工具的綜合應(yīng)用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429
)

 

高級(jí):
一.基本算法要求:  
      (1)代碼快速寫成,精簡(jiǎn)但不失風(fēng)格  
          (poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)
      (2)保證正確性和高效性.  poj3434
二.圖算法: 
      (1)度限制最小生成樹(shù)和第K最短路. (poj1639)
      (2)最短路,最小生成樹(shù),二分圖,最大流問(wèn)題的相關(guān)理論(主要是模型建立和求解)

         (poj3155, poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446
      (3)最優(yōu)比率生成樹(shù).  (poj2728)
      (4)最小樹(shù)形圖(poj3164)
      (5)次小生成樹(shù). 
      (6)無(wú)向圖、有向圖的最小環(huán)   
三.數(shù)據(jù)結(jié)構(gòu).  
      (1)trie圖的建立和應(yīng)用. (poj2778)
      (2)LCA和RMQ問(wèn)題(LCA(最近公共祖先問(wèn)題) 有離線算法(并查集+dfs) 和 在線算法
 
          (RMQ+dfs)).(poj1330)
      (3)雙端隊(duì)列和它的應(yīng)用(維護(hù)一個(gè)單調(diào)的隊(duì)列,常常在動(dòng)態(tài)規(guī)劃中起到優(yōu)化狀態(tài)轉(zhuǎn)移
的
          目的).  (poj2823)
      (4)左偏樹(shù)(可合并堆).  
      (5)后綴樹(shù)(非常有用的數(shù)據(jù)結(jié)構(gòu),也是賽區(qū)考題的熱點(diǎn)). 
         (poj3415,poj3294)
四.搜索  
      (1)較麻煩的搜索題目訓(xùn)練(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)
 
      (2)廣搜的狀態(tài)優(yōu)化:利用M進(jìn)制數(shù)存儲(chǔ)狀態(tài)、轉(zhuǎn)化為串用hash表判重、按位壓縮存儲(chǔ)
狀態(tài)、雙向廣搜、A*算法. (poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)
      (3)深搜的優(yōu)化:盡量用位運(yùn)算、一定要加剪枝、函數(shù)參數(shù)盡可能少、層數(shù)不易過(guò)大
、可以考慮雙向搜索或者是輪換搜索、IDA*算法. (poj3131,poj2870,poj2286)
五.動(dòng)態(tài)規(guī)劃  
      (1)需要用數(shù)據(jù)結(jié)構(gòu)優(yōu)化的動(dòng)態(tài)規(guī)劃.
         (poj2754,poj3378,poj3017)
      (2)四邊形不等式理論. 
      (3)較難的狀態(tài)DP(poj3133)
六.數(shù)學(xué)  
      (1)組合數(shù)學(xué). 
        1.MoBius反演(poj2888,poj2154)
        2.偏序關(guān)系理論. 
      (2)博奕論. 
        1.極大極小過(guò)程(poj3317,poj1085)
        2.Nim問(wèn)題. 
七.計(jì)算幾何學(xué).  
      (1)半平面求交(poj3384,poj2540)
      (2)可視圖的建立(poj2966)
      (3)點(diǎn)集最小圓覆蓋. 
      (4)對(duì)踵點(diǎn)(poj2079)
      八.綜合題.
      (poj3109,poj1478,poj1462,poj2729,poj2048,poj3336,poj3315,poj2148,poj1263
)

       這是一題相當(dāng)有水平的并查集問(wèn)題。雖然我一次性ac，但是基本上是沒(méi)有任何思路搜索了一下牛人思路才過(guò)的。

       思考這題時(shí)，我陷入到了以下怪圈：
1.并查集應(yīng)該是無(wú)限的，但是貌似這題的并集只有三個(gè)
2.當(dāng)兩者關(guān)系未被確認(rèn)是哪個(gè)集合時(shí)，會(huì)出現(xiàn)無(wú)限多的臨時(shí)子集
3.如何表示臨時(shí)子集
  
       看了看牛人的思路，相當(dāng)巧妙：并查集基本還是無(wú)限集，有限集用關(guān)系向量來(lái)表示。
1.使用關(guān)系向量的方法，讓我獲益匪淺。
2.計(jì)算關(guān)系向量的方法，又如此的巧合。
3.并查集并不一定是相同的才并一起，又回歸到第一點(diǎn)，當(dāng)關(guān)系向量可以用有限集表示時(shí)，并查集里的元素可以不是同一類元素。

最后還要說(shuō)，這題相當(dāng)牛B.

     tle和wa 到麻木.... 又一題并查集。這周做題時(shí)間少了很多，原因工作太忙，準(zhǔn)備晉升。希望晉升成功！    上周ac了3道 基本的線段樹(shù)。這周開(kāi)始做并查集，慶祝一下poj達(dá)到40題，雖然都是水題居多。        連續(xù)兩天AC了兩道線段樹(shù)經(jīng)典題目。

       3277用了157ms居然排到了第三，哈哈哈哈....      摘要: 線段樹(shù)經(jīng)典解決問(wèn)題poj1151，計(jì)算圖形覆蓋總面積。1.用了半小時(shí)寫了一個(gè)簡(jiǎn)單算法，看了看測(cè)試數(shù)據(jù)沒(méi)過(guò)，原來(lái)理解題意錯(cuò)誤。（如果提交就是WA）2.然后又用了樸素的枚舉，這次是TLE，看來(lái)是水平不行，要學(xué)習(xí)學(xué)習(xí)別人的思路了。3.看完別人代碼后，花了半天用自己的思路寫了一遍，RTE。4.原來(lái)是數(shù)組設(shè)小了，再次提交PE。4.最后居然是要輸出兩個(gè)換行，暈倒!AC線段樹(shù)的應(yīng)用還有很多，就此題來(lái)說(shuō)基本的思維...  閱讀全文         Bridge模式看過(guò)很多遍，說(shuō)實(shí)話沒(méi)看懂過(guò)。今天終于覺(jué)悟....

        Bridge模式的定義是：將抽象和實(shí)現(xiàn)解耦。

        這個(gè)定義是最讓人費(fèi)解的，抽象和實(shí)現(xiàn)解耦和Bridge有什么關(guān)系，特別是UML的圖形給出來(lái)的時(shí)候更讓我感覺(jué)到這個(gè)定義的匪夷所思。

        下面來(lái)舉個(gè)例子吧：

        我很久前遇到的問(wèn)題就是：寫一個(gè)系統(tǒng)，當(dāng)輸入可能內(nèi)存、文件.....而輸出可能是內(nèi)存、文件等等的時(shí)候。如果按照C接口的定義方式，你可能要做一下的定義。
         MemToMem()
         MemToFile()
         FileToMem()
         FileToFile()
         
         一下就要定義2x2的接口，而如果在增加一個(gè)輸入，那么就是2x3的接口，再增加同樣的輸出就是3x3的接口。

        如果在C++里面，就是有雙重的集成關(guān)系，首先是基類，然后是n中輸入類，再來(lái)就是n^2個(gè)輸出類。

        所以Bridge模式要解決的就是這種變化關(guān)系。

        Bridge模式的思想就是將n個(gè)輸入類和n個(gè)輸出類解耦（抽象和實(shí)現(xiàn)接口）讓他們分別依賴自己的基類，而最終通過(guò)組合的方式讓兩者分離。

        簡(jiǎn)單的代碼
   
 
ps.此文檔之作為技術(shù)的隨筆，供以后搜索，如果疑問(wèn)概不回答。     昨天，玩推箱子游戲玩到第四關(guān)實(shí)在過(guò)不去了，用C++寫了一個(gè)BFS+DP的算法求解。結(jié)果是170步。

     其實(shí)我一開(kāi)始是想用python來(lái)寫的，但是覺(jué)得二位矩陣這個(gè)東西很難用python來(lái)描述，于是作罷。寫完后看看自己的代碼，覺(jué)得惡心的不行。于是在網(wǎng)上搜索了一下，發(fā)現(xiàn)大牛居然可以把python寫得如此之簡(jiǎn)潔，又一次拜服了！

《用python求解迷宮問(wèn)題》
http://v.youku.com/v_show/id_XMTcwMzc5MTAw.html

下面是我按照視頻里面敲的python代碼，我的實(shí)在垃圾就不拿出來(lái)了。

這段代碼最然我感到驚嘆的是他對(duì)迷宮模型的表示方式，二位矩陣就如此輕描淡寫的表示出來(lái)！

ps,網(wǎng)頁(yè)代碼的對(duì)齊有點(diǎn)問(wèn)題。