其實在北京比賽完的時候，我就想寫了，不過還是早了點，直到上海比賽結束，大家的心中都不是太好受。郭老師有句話：你們這樣做也是對的，不成功就成仁。讓我的心也能安慰了不少。 我是從大一下學期開始接觸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*kZOJ 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，所以根據這個算出第一行的情況，然后一行一行遞推，得解

總結

以上是生活随笔為你收集整理的神牛笔记：吉林大学ACM总结（fennec）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。