發信人: fennec (fennec), 信區: Algorithm
标 題: acm 總結 by fennec
發信站: 吉林大學牡丹園站 (Wed Dec 8 16:27:55 2004)
ACM總結（fennec）
其實在北京比賽完的時候，我就想寫了，不過還是早了點，直到上海比賽結束，大家的心中都不是太好受。郭老師有句話：你們這樣做也是對的，不成功就成仁。讓我的心也能安慰了不少。
我是從大一下學期開始接觸ACM的，那時候我們學校才剛剛起步，siyee，wjiang師兄可以說是我的領路人了，沖名次，比做題真是一種幸福的感覺。
大二上學期很有幸與siyee隊長，jack學長一起代表學校參加了比賽，那時候我的心情是很放松的，對自己的目标也是ac一道就萬歲：）這也是今年我對windsbu說的話。畢竟那時不是隊長，是以對我來說，最重要的就是完成隊長布置的任務，其次就是在比賽中做出一道适合自己的題目。去年的最好結果是學校排名第九，大家雖然有種遺憾的感覺，但是畢竟是進步了。
到了大二下學期的選拔賽，湧現出了好多人才，很多人都很有能力，但是有一點最遺憾的是：許多人接觸的比較晚，可能是因為熱身賽或者選拔賽才了解了ACM，而我們學校的ACM訓練隻是一個課餘的活動，不能與許多學校專業的訓練來相比。這樣的結果是，缺乏底子好的老選手，即使出現了有很強能力的同學，也不能在極短的時間裡使他們達到一個相當的高度！
經過了暑假的集訓，學校在隊伍人選上很是下了一番功夫。從隊員到隊伍，無不精心研究。可能連統計學的許多知識都用上了：）
最終很高興能夠與codecpp，wind，組成了jojer隊，開始我是不太好意思使用jojer這個名字的，我害怕對不起這個名字，是以先暫時叫做j2吧。由于經驗少，剛開始訓練的時候有一種摸不到頭腦的感覺，許多時候知道有問題，但就是不知道該怎麼解決，walkoncloud老師就曾經批評過我：你們隊伍就是一個“神經病”帶着兩個“小神經病”一起“神經病”。這當然隻是一種玩笑，但是确實是我們隊伍初期的症狀，什麼事情都沒有章法，這時候我們隻好使用最原始的方法：讨論加總結。每次比賽結束後無論題目簡單與否都要首先将所有題目讨論一遍，将做錯的，不會的都配置設定到人繼續将它解決。然後大家單獨寫賽後總結，交到我這裡，在經過分析後，再開集體會議，批評+自我批評并制定下一步政策。用我的話說：這種方式挽救了我們，讓我們在極短的時間裡磨合了起來。
我們隊伍最後的分工是：
wind主要負責讀題，讀題時要将重點難點标記出來，構想出初級的邊緣測試資料。并主要負責計算幾何以及一些需要推理的數學題目。
codecpp主要負責1-2簡單題目，1到中檔搜尋題，以及編譯方面的題目。和wind對邊緣題目以及簡單題目形成互補，以及調試上的幫助。
fennec主要工作是對wind，codecpp讀過的題目進行分類，分析，對簡單題目直接決定配置設定的人手，對中檔題的複雜度，題型進行準确分析，引導思考方向。在有時間的情況下組織對較難題目的深層讨論。
我想最後我們還是基本實作這幾方面内容的。
具體到了比賽，首先就是網上預賽：兩次比賽感覺是發揮了自己的能力，這也算是隊伍第一次最嚴肅認真的比賽了，大家都很盡力，光從賽後東方餃子王的戰績上就能感覺到！
在北京賽區，我們很快的作出了三道題目，但在後面wa在了兩道題目的上面。這沒有什麼太好說的，我們隊伍這時候最大的缺點在于對于wa題目的處理。但是最後還是因為罰時少，取得了學校排名第七的成績。這也是一個可以接受的成績。
從北京回來就有好多是要做，接連的補作業，以及期末考試，将訓練計劃打散了不少。這也是很正常的，畢竟在學校和老師看來，學習是最重要的，我們不是培養一個ACM機器。
在上海的比賽就有些不盡人意了，一是疲勞，二是對題目難度缺乏正确的估計，三是一開始比賽的時候就有些亂套，四是沒有專心地做一個題，結果都沒有做對。但是很多問題都是因為我在大局上把握的失誤，我也感覺很自責，不過一切都過去了，希望後來人能夠吸取教訓吧。
我想對未來的同學有幾句話要說：
1 我們幾乎沒有noi上來的隊員，大家隻能依靠後期的更加刻苦的努力。
2 我們沒有專業的班級或者機制形成職業ACM隊伍，是以大家隻能盡早的投入進來，用盡一切課餘時間去訓練。
3 我們不能在數目上和傳統強隊比拼（除非隊伍中的三個人都很強），是以我們要在中低檔題目的ac時間和正确率上下功夫。
4 不要抱怨什麼，你所要做的就是盡力發揮自己的全部，并在發現問題後努力改正。
5 不要懶得動手，許多題目你覺得自己方法對了，或者怕麻煩就不寫了，這是一個最大的缺點，在比賽的時候你可能需要用2-3倍于别人的罰時去做出來。
6 不要隻是追求ac數目，作出一道不會的題目勝過做出10道已經會的題目。
7 多交流代碼！不要隻是閉門造車。
8 養成良好的代碼習慣。
9 在平時做題的時候就養成緊張的好習慣，不然在比賽的時候你會很吃虧的！
關于比賽的感覺：最重要的是四個字：天外有天
而對于真正想繼續從事ACM事業的同學，我有以下建議：
0 首先了解C/C++，以及資料結構。
1 首先在joj做夠50題，這是基本的熱身
2 看一本算法書，清華紫皮的感覺簡單點
3 在繼續做夠200題，這時候應該在輸入輸出上不會出大問題了，并了解了基本算法。
4 看看吳文虎，以及沙特的那本書。
5 在joj做夠400題
6 這時候應該能夠出山了，可以參加幾次各類的競賽
7 去uva分類做題，這時候不要再在意你的題目數目了，要有目的的，分類訓練了
首先可以是動态規劃，然後是搜尋，然後再是動态規劃，然後再是搜尋…這種循環往複的方法，并加以總結，會是你自身提高最快的時候。建議一定要作總結，可以參考我後面的例子。（另外一定要用好uva的論壇功能！）
8 在uva訓練200題目的時候，可以考慮一些典型代碼算法的東西了，如網絡流，poly計數，比對等等。并把這些算法做成模闆！并且要加強自己的理論修養了，看看離散數學，組合數學，機率論等等數學方面的東西。
9 總題目到達了1000的時候就可以查缺補漏了，這一段主要以套卷為主，将每次自己不會的題目搞懂就好了！并要适應比賽的節奏！
10 在題目到達1100-1500的時候，算是小成了。這樣的同學就應該能夠勝任隊長了。
11 剩下的隻能靠自己了：）
附錄1：（動态規劃總結）
近日開始學習動态規劃，特做些總結。
ZOJ 1011 NTA 本來想從頂至下搜，但是情況複雜，要儲存一牌的狀态。是以過來，從到數第二牌搜起，尋找可以是最底層成立的狀态，然後向前搜,以此類推。
ZOJ 1013 Great Equipment 人數<100,500不太明白，但應該是數的範圍。資料小，但是量多，應該是動态規劃，可是選法較複雜，如果單獨考慮每個人，将組合物品整體考慮，則可以省去物品組合，而且可以知道剩餘物品不能在組合成新物品，這時候如果枚舉的話，還是指數級，因為可以交叉組合，關鍵就在于如何對人數進行動态規劃嗎？莫非是利用前k個人可以産生的物品數進行動态規劃？比如說前k個人産生了分别a，b，c，d個物品，則加上新的一人，可得新的狀态，中間再用上剪枝？但似乎成了枚舉。狀态似乎太多了，那麼對人數進行遞推，但是狀态集變換一下，就是abcd的某種形式。現在的難點是對狀态集大小的分析，因為它關系到算法的複雜度的衡量。想到了搜尋的算法，想到了剪枝。
以下借用了别人的解法！
1013,經典DP
隻有最後結論，沒有想法過程
我們設計成為這樣一個規劃過程
編号所有的車輛是１，２，３，４。。。，n
我們設計一個函數F
F(i,x,y) 表示的是前面1...i輛車中裝載x件１裝備，y件二裝備之後
最多還能夠裝多少的３裝備
我們需要求出F(n,*,*)就是i = n的所有的F值
設裝備的重量和尺寸分别是這樣的
weight[3],size[3],防禦defence[3]
而汽車的容量分别是ss[1..n],ww[1..n]
規劃過程:
1.i = 1的時候，F(1,x,y)
如果x * weight[0] + y * weight[1] > ww[1] 顯然F(1,x,y) 不可行，我們取-1标記不可行
同理 x * size[0] + y * size[1] > ss[1]也是一樣
否則 F(1,x,y)可以由除去x,y之後的剩餘重量和剩餘尺寸算出來
2.設<i已經算出來，計算i的時候，也就是F(i,x,y) (i > 1)
顯然F(i,x,y)可以這樣算出來，設其中有h件１裝備，l件２裝備在i車中，則F(i,x,y) =
F(i - 1,x - h,y - l) + 第i車中剩餘的空間能夠裝下的最多的第３種裝備的數量，
取F為這些所有的h,l的最大值，當然如果這樣的h,l都找不到，則标記為函數值為-1
即不可行
最後得到F(n,x,y)
使用這個結果即可得到題目的解答
所有車輛中裝x,y件１裝備，２裝備的時候還能夠裝下多少的３裝備為F(n,x,y)
這些裝備可以組成的組合裝備套數可以馬上得到，能夠達到的最大防禦裡也可得到
周遊所有可能的x,y即可得到題目所求答案
ZOJ 1022 Parallel Expectations 還是一道麻煩的題，首先要翻譯成機器語言，然後開二維數組，存放雙方運作到目前狀态的值。因為隻有加減，直覺（？）上感覺可以存放平均值，那麼此題就可解了。
ZOJ 1037 首先和容易就想到找規律，如果可以一筆畫，則直線距離，否則要走一個斜線。但是沒有很好的動态規劃算法。
ZOJ 1039 Number Game 覺得是搜尋題，每一個數加入後，要去掉所有他的倍數，以及他與所有不允許的數的和（？），或者考慮動态規劃，一共２^２０的狀态，模拟遊戲，算出所有狀态的解。即構造解樹。有一個假設，每個狀态應該隻有一個可行的出現狀态。不然的話結會不唯一。不知道這種方法算不算搜尋樹構造動态規劃的解？
ZOJ 1052 題目讀的好不容易啊！我感覺會用一個while(flag){ up() ；}的算法，計算每次各個容器裡還能有什麼。然後更新，最後再看看能否變化。得出解。感覺類似于模拟。
ZOJ 1058 Currency Exchange感覺不是動态規劃，更像模拟，隻要注意舍入就行。
ZOJ 1076 Gene Assembly 首先要定義struct，其次定義排序，可以先按大數正序，再按小數反序排序。從小至大，如果兩個大數相同，則舍去小數小的（即後者）。然後利用基因位置，遞推，計算到達某一位置時的最大值，可以先賦以前者的值，如果有基因以次為尾，則比較更新。利用struct的排序數組，可以加快速度。
ZOJ 1092 Arbitrage 可以抽象為仁兩點之間的最短距離，用三層for循環實作即可，最短距離==最大換算
ZOJ 1093 Monkey and Banana 由于一塊可以看成三個不同的塊，是以擴充方塊，簡化題目，使規模成為90，其實進行排序，首先是長，其次是寬。每增加一個計算其放在前面每一個上的最大值。複雜度n*n，這道題也可以反着做，似乎能更快點。
ZOJ 1094 Matrix Chain Multiplication 似乎又不是動态規劃，重點隻是求值，利用堆棧，即可實作。利用函數模拟也行，遇見左括号，加深一層，遇見右括号傳回。
ZOJ 1100 Mondriaan s Dream 被稱為簡單題？引用一下别人的講解吧
Assume you could calculate the number of different paintings for a rectangle with c columns and r rows where the first r-1 rows are completely filled and the last row has any of 2c possible patterns. Then, by trying all variations of filling the last row where small rectangles may be spilled into a further row, you can calculate the number of different paintings for a rectangle with r+1 rows where the first r rows are completely filled and the last row again has any pattern.
This straightforwardly leads to a dynamic programming solution. All possible ways of filling a row part of which may already be occupied and spilling into the next row creating a new pattern are genrated by backtracking over a row. Viewing these as transitions from a pattern to another pattern, their number is given by the recursive equation Tc = 2 Tc-1 + Tc-2. Its solution is asymptotically exponential with a base of sqrt(2)+1, which is not a problem for c<=11.
If both h and w are odd, the result is 0. Since the number of paintings is a symmetric function, the number of columns should be chosen as the smaller of the two input numbers whenever possible to improve run-time behaviour substantially.
Judges test data includes all 121 legal combinations of h and w.
ZOJ 1103 Hike on a graph寬度搜尋，50*50*50的複雜度,從一個狀态，察看能否分成的狀态。
ZOJ 1107 Fat Mouse and Cheese 從起點開始，更新其所能到達的點的move值，取較大值，然後每次都選取一個最小的值，讓他去更新。或者直接按照cheese的大小排序，按照這樣的順序更新。複雜度100*100*k
ZOJ 1134 Strategic Game 使用backtrack算法，從葉節點開始，一步一步計算，每上升到一個父節點，分開考慮以下情況：任一個位元組點選中的最小值，父節點選中的最小值。
ZOJ 1136 Multiple 寬度搜尋來構造除法，從起始最小數開始，做除法，保留餘數，利用餘數構造新數來進行計算。
ZOJ 1147 Formatting Text 隻需要記錄前ｋ個單詞儲存為行，并且最後一個在最後所能得到的最小值，擴充時，令新加的在最後，前面添加，中間距離為平均值。
ZOJ 1148 The Game 算出可以一步到達的點對，然後用兩點之間距離的算法，或者僅僅用寬度搜尋。
ZOJ 1161 Gone Fishing 假設隻用前ｋ個，則先将移動時間減去，然後再貪心，比較所有解。
ZOJ 1180 Self Numbers 從前往後計算，要開一個大的bool數組，如果為０則計算
ZOJ 1192 It’s not a Bug，It’s a Feature. 2^20個狀态，寬度搜尋。
ZOJ 1196 Fast Food 前n個點，開k家店，每新加一個，假設最後一個開在後L個中，其餘的k-1個在前n-L中。再利用在k個中開店，應把配置設定點放在中間則可。
ZOJ 1206 With the Bonus 對于每個位置，需要計算所有兩位的情況，狀态一共10000*100*10，得出最小的。中間可以部分優化，一定要從後往前推。這樣才能構造最優解！
ZOJ 1213 Lubmer Cutting 首先想到的是預處理，将每個部分加上切割的浪費，再将總長也加上，就成了背包問題。如果隻是１２個的話硬搜應該可以。
ZOJ 1227 Free Candies 如果隻有四堆的話，狀态數是40^4，是以可以用動态規劃解，每次考慮一個能被變化到的狀态，由于這時候所有被取出來的已經消掉了，那麼剩下來的是确定的，是以僅僅是寬度搜尋就行了。
ZOJ 1234 Chopsticks 這道題裡面有的筷子可以不用，似乎增加了難度。而解題最重要的訣竅就是先不要考慮選最長的筷子，那麼動态規劃的時候每增加一個筷子，可以有兩種方式，１ 和最近的構成一雙 ２ 不使用。感覺應該儲存的是由前ｘ個構成ｍ個所得的最小值。于是複雜度是n*k，最後再考慮最長的，從後往前選，逐次去掉最長的，一直要湊夠去掉的為止。
ZOJ 1245 Triangles 以前做的，但是居然看不懂自己寫的了：）不過有個n^3的算法，共有三種類型的三角，現僅考慮一種，每遞推新一行的時候，每多一個節點，找出它前面最長的鄉鄰位，再比較他上一排對應的點的值，取小值。存儲。如果能預處理的話。應該能減到n^2，具體的方式就是，尋找相鄰位的時候，與其前面的那個點比較！
ZOJ 1250 Always On the Run 首先可以利用整除來模拟構造每天的時刻表，動态規劃用來遞推每天可以到達的城市。
ZOJ 1255 The Path 不像是動态規劃，僅僅依靠搜尋就行，隻需要将螢幕的塊分類為１，２如果可以連，則輸出正确，如果加一塊能将１，２互連則輸出另外結果。不過如果隻是用簡單的動态規劃模拟，每加入一個，就判斷他的連通性，可能也能解題。
ZOJ 1276 Optimal Array Multiplication Sequence 基本的動态規劃，從兩兩算起，再三三，直到ｎ，每次分為兩部分求值。
ZOJ 1301 The New Villa 首先想到的就是寬度搜尋，燈狀态*所在的屋子=10*2^10，可以儲存，一步一步類推。即可得解。
ZOJ 1303 Jury Compromise首先将兩個值相減，最後求得就是絕對值最小的，利用層數遞推每次最多20(層)*20*20（數）*200，但可以剪枝，例如每層最大數紀錄，如果先排序的話，算到正的某個數，就會知道肯定是遞增的，以此剪枝。
是以要注意動态規劃的剪枝！
ZOJ 1345 Best Deal 題目有點不太明白，但是大意應該是從最底層開始向上遞推或者化成有向路。不知道是否會有環。選擇要支付最少的錢的？還是選擇能折合最多錢的？從所有點一起出發？路線長度可以換成支付錢數，但是路線要限制。還是不太了解題意。
ZOJ 1396 The Umbrella Problem 典型題，遞推的時候隻需要依據規則計算每一排能到達的位置，以此類推，得到結果。
ZOJ 1409 Communication System 首先還是排序，依據發射範圍從大到小，然後是價錢。從上向下遞推，每考慮一個的時候，如果價錢比以前的還高，排除，否則将其放入，并比較最優值（這裡要注意隻有當所有的都選擇了以後才能比較更新），最後得出最優值。
ZOJ 1425 Crossed Matchings 由[i，j]再推新的[i，j+1]時，賦初值[i，j],然後讓第j+1個與前面的比對，由貪心原則知，在其枚舉時，另一行的隻有與與其最近的可以得最優值。n^4的複雜度。如果考慮到資料的預處，則可能更優。
ZOJ 1438 Asteroids 很簡單的寬度搜尋，但主要是3維，注意一下就行。
ZOJ 1459 String Distance and Transform Process 很典型的題，主要比較前m個與後n個的最優值，隻是紀錄一下中間的變化就行，再構造出來結果。
ZOJ 1462 Team Them Up 沒有太多想法，感覺是從人數開始遞增，但是狀态很多，無法确定狀态集。如果能事先找到所有的互相認識的集合就好了。但似乎又是有很多，如何才能簡化？如果狀态不過，可以記錄前k個人的分發，依次遞推。
ZOJ 1479 Dweep 确實很無聊的題，很簡單但又麻煩的寬度搜尋。
ZOJ 1499 Increasing Sequences 儲存到ｋ位時所能求出的最小值。
ZOJ 1520 Duty Free Shop 值需要記錄分完前k個，第一種巧克力還剩多少（因為可以推出第二中還剩多少），以此類推得出結果。
ZOJ 1524 Supermarket 儲存購物數組，記錄目前時刻如果購買各種物品所需花費的最少錢。當然得到一個新的數，然後更新目前數組。即可得解。
ZOJ 1536 Labyrinth 由初始圖開始進行計算，每次都得到一個更新圖，在每次疊代，以次考慮每個點，以及其每個可行的路線，如果可以，就進行累加，的新圖，推知答案。
ZOJ 1556 Heroes Of Might And Magic 共要走50步，每一刻的狀态集是：100(HP)*N(位置)*10(MP)*10(NM), 是以可以解。
ZOJ 1587 UP 100 不知道寬度搜尋行不行。題是看起來太麻煩了。
ZOJ 1066 Squire Ice 據說很難，想了想，類似于點燈問題，從上到下計算，第一行至少有一個1，是以根據這個算出第一行的情況，然後一行一行遞推，得解。
POI VI Stage 1 Problem 1 Musketeers 首先要将環拆成鍊，判斷一個人能否最終勝利，關鍵在于使其為首位的鍊能夠首尾相接，一種方法就是[i.j]=1 if and only if exist [i,k]==1&&[k,j]==1 &&(i win k || j win k) 僅判斷一個人是n^3複雜度，n^2 空間，但如果是所有人則要n^3複雜度了。
ACM/ICPC Shanghai 2000. Problem C. Dance Dance Revolution 首先分析狀态空間，雙腳位置5*5=25 依此類推時，隻要考慮将已有的狀态擴充為新的狀态，比較存儲最優值。
CEOI 2001 Day 2 Problem 2 WildCard Patterns 通配符的比對問題 最重要的是考慮*的問題，有以下情況
1 a b false
2 a a (i+1,j+1)
3 a * (i+1,j) (i+1,j+1)
4 * a (i,j+1) (i+1,j+1)
5 * * (i+1,j) (i,j+1) (i+1,j+1)
中間有許多重複狀态，要注意一下，而且感覺筆記本式比較好寫
至于問題二，隻要得出所有中途記錄的所有解，去掉重複的就行。
對于問題三，兩兩比較看看有沒有重複的。但是我不能保證最小。
ACM/ICPC Finals 2002. Problem B. Undecodable Codes 初始的想法是 由長度遞推，考慮已有的構成新有的，如果有重複，則比較字典序輸出。但是這樣的話就沒有用到公共的字首。
每一步肯定是要比對一個串和一個空串，即求ans[string]=?由于前後是不同的，是以有兩個ans。求ans1[string]時，要找出b中所有可以比對串，逐一嘗試的最小值，反之亦然。這就是一個類似于動态規劃加搜尋的算法了，但是如果長度到了10就可能會用上2^10的空間。查找效率是其次。關鍵是添加效率。而且用的是二進制的，就沒有用上他本身的性質了。
其次，這裡面既然至少要用上第一組與第二組各一個，那麼就隻需要搜尋以第一組開始的就行了。
CEOI 2002 Day 1 Problem 1 Bugs Integrated, Inc. 非常可怕的動态規劃題，用了我兩天的的時間。随意總結一下
1 狀态編碼 由于遞推要考慮到與最後相關的後兩排的情況，是以要進行編碼，但是由于至于最後一個占用有關，是以簡化編碼為3。
2 賦初值，在由已有狀态推位置狀态時，首先賦以一定的初值，中間要用上貪心政策。好像不太對。
3 狀态轉移，枚舉前一個中的每個狀态，貪心政策選擇，更新。
4 終值，要對最後中的每一個狀态比較，來得到最大值。
Balkan Olympiad in Informatics 2003. Day 2 Problem 2. Euro 感覺類似矩陣乘法的算法，如果想求出[i，j]的最大值，要枚舉[i，k]+[k，j]的所有值。
2003 廣州賽區b題 很酷的動态規劃，從上向下，用n^3的動态規劃算法，每算到一個新節點i，要考慮所有可能的後一次的停放地點。在每次停放地點中，要找出最長的，然後在所有中選最小的。
04.8.10-04.8.16
By fennec
I will try to use English to write my sentences. Forgive any of my mistakes.
I will also use some color to mark the problem.
Red: I haven’t thought it out.
Pink: Very good problem.
Brown: I can’t make sure of this problem, for example: these may be some other better algorithm. Blue: I have thought out it, but I haven’t write it out.
Black: I have finished it perfectly.
1. UVA 108 Maximum Sum
In this problem, you should enumerate the able range of row (also you can choose line), the do the longest maximum subsequence algorithm to get the answer, and choose the maximum of all the case. So the complexity is n^3 if you pre-dealing the data.
2. UVA 111 History Grading
At first, this problem is about the order with special value. Noting this, the problem is just a longest subsequence problem. I just have O(n*k) algorithm. And in this problem, you can have a exchange way to pretreat your data.
3. UVA 116 Unidirectional TSP
Easy problem, you should just from left to right, and update the value from the three positions, and care up-down connection.
4. UVA 136 Ugly Number
Open a big boolean matrix. Use multiple 2, 3, 5 to cut it, and count it. And I think it will have a combination way to work it out. Use bin-search.
Some one’s Dynamic Programming:
Build a list of ugly numbers bottom up, example:
if we know that 1 is the first ugly number and the only prime factors are 2,3,5, then the next ugly number will be min(2*1,3*1,5*1) which is 2.When we know that 1 and 2 are the first 2 ugly numbers, the next ugly number will be min(2*2,3*1,5*1) which is 3. Note that factor 2 is now multiplied with 2 whereas the rest are still multiplied with 1 .
5. UVA 147 Dollars
First, all number should divide 5 to predigest the problem number, then from small to big, sum all the possible values.
You should pay attention to the change of float to int, use int(x+0.5) instead of int(x).
6. UVA 164 String Computer
Easy problem, operate the minimum of string[i][j], when it comes to string[i][j+1], just check if they are the same sting[i-1][j], or use three ways.
7. UVA 231 Testing the CATCHER
The longest decreasing subsquence.
Writen by fennec
JLU JOJer
附錄2：（部分uva題目總結）
題号 名稱 類型 算法簡述
10600 ACM CONTEST AND BLACKOUT 圖算法 第二最小生成樹，每次去掉最小生成樹種的一條邊，然後找到一個構成連通
10601 CUBES POLAY (Z1^8+3*Z2^6+6*Z4^3+6*Z1^2*Z2^5+8*Z3^4)/24,然後要單獨計算每一個的展開式
10602 EDITOR NOTTOBAD 貪心 每一步選取與目前字元串有最長相同子串的字元串
10603 FILL 寬度搜尋 用目前狀态構造新狀态，需要堆結構，但是可以用set模拟！
10604 CHEMICAL REACTION 動态規劃 筆記簿式的動态規劃，有一點最重要，不要清除筆記簿的内容，即使是fill也太費時間，你隻需要重新申請一個就行了
10605 Mines 搜尋 首先枚舉點的排列情況，每選擇一個點，使用深度搜尋選擇離其最近的牆和最近的已經連到牆上的點。
10606 Opening Doors 數學 大數開放再乘方
10607 Siege 圖算法 首先求出中間得鄰接圖形，然後化減為獨立的點，加上外圍點，求他們的最小生成樹
10608 Friends 并查集 求出最大的并查集
10609 Fractal 函數疊代 算至範圍即可，問題在于點排序的有效範圍的處理
10610 Gopher and Hawks 最短路經 典型算法
10611 The Playboy Climp 二分查找 簡單的二分查找，可以利用庫函數
10612 Paper Folding 貪心 每次選擇保留在外面的最小方式，但是注意最後一次！
10613 Mushroom Misery 構造掃描 維持一個樹型結構，将圓化為矩形，再化為線段，最後成為點
10614 Dreadful Vectors 表達式計算 計算帶向量的表達式
10615 Rooks 比對算法 将圖中點二分，利用定理
10616 Divisible Group Sums 動态規劃 算出前k個選x(0<=x<=k&&x<=m)個，所能構成的除以d各種餘數的組合方式的個數
10617 Again Palindromes 動态規劃 類似于矩陣乘法O(n^3)，對每一種情況考慮第一個元素是保留，删去，或者配對
10618 Tango Tango Insurrection 動态規劃 保留上一步可以到達的各種狀态，根據目前節拍選擇比較更新狀态
10619 Advanced Causal Measurements 二分查找 将節點分别按斜率為+1，-1排序，然後對最小高度二分查找
10620 A flea on a chessboard 模拟 從起始點模拟，直到走回起始狀态，或者走出棋盤
10621 Jack and Jill 寬度搜尋 每次選擇距離最遠的兩個點擴充，要注意兩點細節 1 數組清零；2 可以回家！
10622 Perfect Pth Powers 數學 預處理質數，因數分解，求各因數的最大公約數，如果是負數，則需将答案轉換成奇數
10623 Thinking Backward 數學 計算出公式後，枚舉小數，然後解方程判斷
10624 Super Number
10625 GNU = GUN sNotUnix
10626 Buying Coke 貪心,動态規劃 注意10+3=8+5，n10+n5/2>=c，直接購買，n10+n5<c 每個5和10與1配對，否則用10與1購買，然後盡可能由2個5購買
10627 Infinite Race
10653 Bombs! NO they are Mines!! 寬度搜尋 很典型
10654 The Uxuhul Voting System 動态規劃 逆推，每到一個人，根據上層結果在三者中選擇，構造自身狀态集
10655 Contemplation!Algebra 數學 利用數學推出log級的遞歸公式
10656 Maximum Sum II 基本 輸出非零數
10657 Prince Frog II
10658 ReArrange 動态規劃 居然要用unsigned long long 才行，類似于漢諾塔，找出公式
10642 Can You Solve It? 數學 找到規律（1+x+y)*(x+y)+1+x
10650 Determinate Prime 數學 預求質數，注意了解題意，隻有完全一組都能輸出才輸出，此外沒有告訴輸入是前小後大
10670 Work Reduction
10671 Grid Speed 圖算法？
10672 Marbles on a tree 樹 構造樹去處理，如果是動态規劃，要注意特殊情況
10673 Play with Floor and Ceil
10674 Tangents
10675 Revenge of Faucet Flow
10676 Grid Points 枚舉 考慮複雜性可知7*10*2*k
10677 Base Equality 進制轉換 有10進制轉成b1進制在轉成b2進制
10678 The Grazing Cow 計算幾何 根據表述可以推出就是求橢圓面積
10679 I Lovs Strings!! 字元樹 非常的動态規劃，但是可以用AC算法進一步計算
10680 LCM 數學 質數計算，需要算出隻用一種質因數的數
10681 Teobaldo s Trip 動态規劃 由第i天可以到達的地方，推第i+1天可以到達的地方
10682 Forro Party 圖算法 寬度搜尋，用鄰接表比較好
10683 The decadary watch 模拟 簡單的計算可以使用setfill和setw
10684 The jackpot 動态規劃
10685 Nature 資料結構 并查集，題目有些誤解，就是求一個最大的并查集
10686 SQF Problem 字元串處理 比較繁瑣的題，題目說得很不清楚，要一個一個讀，然後處理，還要考慮變态資料
10687 Monitoring the Amazon 圖算法 根據最近原則構造鄰接表（不用開方),然後就是搜尋
10688 The Poor Giant 動态規劃 可以根據n,n遞推得到n^3的算法，更可以用n,k遞推得到不依賴資料的n^2*k算法,利用單調性範圍可以繼續減到1s以内
10689 Yet Another Number Sequence 動态規劃 注意到F(n)=f(n-1)*b+f(n)*b，首先預處理fibonacci數列，還有一種矩陣乘法可以使用。
10690 Expression Again 動态規劃 典型的分數算法，但要注意優化，選擇較小數，再算出所有可能值以後枚舉即可。可以+50預處理
10691 Sub Way 幾何+貪心 将每個點預處理，算出對其的可達角度範圍，并排序（要注意去掉能包含原點的點），然後貪心選擇
10692 Huge Mode 遞歸+數學 将最外層的取餘，遞歸為内層取餘,每一層要考慮循環長度與循環起點。
10693 Traffic Volume 數學分析 求導，求極值sqrt(2*L*F) 與 sqrt(F/2/L)
10694 Combinatorial Summation 組合數學 可以找規律，前面的數分别是0 1 7 14 26 46 79 … 仔細觀察fibonacci數列有關，然後大數計算。
10695 Find the Point 計算幾何
10696 f91 數學 找規律，或者動态規劃
10697 Fireman barracks 計算幾何 求三點的中點
10698 Football Sort 模拟排序 注意格式
10699 Count the factors 數論 預處理所有素數
10700 Camel Trading 動态規劃 非常典型的類似于矩陣乘法
10701 Pre, in and post 圖論 其實隻是找到規律，比較幾個值就可以了，但是挺有啟發性的
10702 Travelling Salesman
10703 Free Spots 模拟 建立數組，模拟覆寫
10704 Traffic!
10705 The Fun Number System 模拟+數學 從低位到高位處理，注意其中的正負關系，同時注意到餘數不為零的不變性
10706 Number Sequence 枚舉+剪枝 枚舉不同狀态，即前兩個點的分割位置。以此類推。
10707 2-D Nim 模拟 首先掃描出各種類型的區域，然後将其儲存成一個字元串。它可以有8種形式，儲存值最最大的，最後比較即可
10708 Cheetah 計算幾何 構造出三角形，求三邊長
10709 Intersection is not that Easy 計算幾何
10710 Chinese Shuffle 群論
10711 Stitching 動态規劃 分兩種情況，一種是向上，一種是向下，任一種情況都要平移旋轉指派。最後比較最優者。
10712 Count the Numbers 數學
10739 String to Palindrome 動态規劃 O(n^2)的複雜度
10740 Not the Best 圖算法 第二最小生成樹，每次去掉最小生成樹種的一條邊，然後找到一個構成連通
10741 Magic Cube
10742 New Rule in Euphomia 數學 預處理質數，本文求的就是将一個數分為兩個和比他小的質數的分法，也可以開個加速數組
10743 Blocks On Blocks
10744 The Optimal Super Highway 數學 求距離排序的中間點
10745 Dominant Strings 枚舉 枚舉各種情況，之前可以将點轉化成數字，利用整除
10746 Crime Wave - The Sequel
10747 Maximum Subsequence 數學 兩種排序，一種是絕對值，一種是大小
10748 Knights Roaming 預處理+排序 預處理50步情況，然後對各個點枚舉，排序，去掉重複的
附錄3：（joj題目分類）
被删除：）
JLU.jojer.fennec
--
隻管走過去，不必逗留着采了花朵來儲存，因為一路上花朵自會繼續開放的。
Do not linger to gather flowers to keep them, but walk on,
for flowers will keep themselves blooming all your way.
有一條小路，穿過田野，通向新南蓋特，我經常獨自一人到那裡去看落日，
并想到自殺。然而，我終于不曾自殺，因為我想更多的了解數學。
——B.Russell
※ 來源:．吉林大學牡丹園站 bbs.jlu.edu.cn [FROM: 10.60.26.*]
