如何有效自己訓練 ACM?

如果是在一個計算機專業不被看好的學校,如何通過自己的努力來提高ACM水平,以達到參賽,甚至是拿獎的水平。

如果是自己組建的話,是不是只是到網上找一個在線測試平台了然後漫無目的的刷題?


從我認識的頂尖的 ACMer 中來看,大部分人走的都不是在 OJ 盲目刷題的路。這裡也有少數特例,前提是他們在某方面的基礎或智商本身已經達到較高水平。不盲目刷題,主要一個原因就是 OJ 題目的質量良莠不齊,訓練的效果不會太好。具體來說,OJ 的題目來源大多數是比賽,而比賽套題的特點是:有防止人吃蛋的水題,也有可以防止人 AK 的神題(刻意刁難,不是真正意義的難),有些賽區命題人水平有限整套都是廢題,有些賽區還流行論文題、結論題、模板題,這些題目都不具備多少訓練價值。另外還有一種情況就是,盲目刷題容易讓人沉迷於虛榮的解題數排名,一入此坑萬劫不復。

要有效地刷題,一般分兩種情況:

  1. 嚴格按照比賽的條件來模擬刷套題 → 找比賽的感覺,給自己定位
  2. 按照前人的總結,刷知識點專題 → 鞏固基礎知識

兩種練習方式需要獨立開,不要混在一起。

除了刷題,更重要的一件事是做比賽。建議常去 TopCoder Codeforces 比賽。這些地方題目質量有保障,大家的代碼是公開的。同時很關鍵的是,這樣的平台可以讓你對題目的難度、比賽的進度、國內外頂級選手的實力做到心中有數,培養在大型比賽中所需要的大局觀和節奏感。

另外,你可以嘗試忘掉拿獎的事情。只要你真的有興趣,拿獎是小 case,這個比賽還沒到拼死拼活的地步。


  1. ACM本來就是靠自己的努力來提高,參賽,拿獎的。這點到哪個學校都一樣,當然好的學校訓練環境上要好一點。
  2. 對於你的問題,首先,你要找到靠譜的隊友。這點很重要,ACM是3個人的事情,要找到2個志同道合,能夠一起堅持每天訓練,做題,學習演算法,參加比賽。保持狀態2年左右的人,很不容易的。我是軟體學院的,08級整個4個班,我才找到了一個人。另一個隊友是在計算機學院找到的。大一開始我們一直堅持了3年。沒有他們,根本無法參賽。所以這是你首先要解決的問題。
  3. 找到隊友啦!那麼恭喜你了,你們學校應該也有參加比賽的集訓隊,和他們取得聯繫,加入進去,如果學校本來就有這個隊伍的話,隊友可以在隊伍中尋到。如果沒有,那麼。。。從你們3個開始吧!
  4. 如果是創始人,聯繫你們計算機啊軟體學院的領導,表示要參賽,爭取得到支持。比如所訓練用的機房,參賽的經費。。。等等
  5. 如果不是創始人,那麼進隊伍之後跟著訓練就好。具體如何訓練可以參考一下:
  6. http://wenku.baidu.com/view/49d1e416866fb84ae45c8da0.html
  7. 經典的弱校acm奮鬥史。。。真的很有毅力啊!表示我沒人家勤奮。
  8. http://www.zhihu.com/question/19719698/answer/13045301
  9. 我之前答過的問題。
  10. 初期參加區域級別的比賽,比如所省級,然後賽區級別,然後每年的9月開始中國的5大賽區開始了,可以在網上預選賽上試試能不能進去,競爭相當激烈,300多個大學900多隊伍要進前70才行。進去的話就可以進入現場賽了。
  11. 平時訓練的話,題量是第一位的。多做題吧,不會的就去找資料搜,弄會,再做......
  12. 沒有老師教沒關係,我們這老師也是不教的,但是我們這老師資源提供的好,有機房,有辦公室,有高速的網路,有空調,有假,有經費。作為回報我們多拿獎,多拿獎。
  13. 你的具體情況沒有說清楚,期待你能補充具體情況,如果你們真的是第一屆搞,可以給你更多的計劃。
  14. ACM啊,好懷念參賽的日子,我的青春啊~~~~

組隊的事情我不多談,我著重從個人的角度來說兩句。主要分成兩部分:

1. 理論部分

初學階段要做的就是熟悉語言基礎;熟悉基本數據結構和常見簡單演算法。

這些內容,書本里都有。推薦的書籍,《演算法導論》。至於語言入門書太多了,不列舉。

進階階段,看一下圈內的論文,學習進階的演算法和數據結構,比如變種的平衡樹SBT;比如線性的素數篩法,中國剩餘定理;比如dinic,預留推進,最高頂標;亦或者是快速的半平面交,凸包的交,高維凸包;又比如龍貝格積分,拉格朗日插值。

這裡面有個重要的分類,就是動態規劃。其實動態規劃在學術界,我就用呵呵來形容好了。因為你根本就遇不到OI/ACM中那麼複雜繞人的問題和模型,即使遇到了,直接建模,剩下的交給cplex就好。但是,在ACM界你會遇到很多很多的DP問題,變種,卡空間、卡時間,各種卡。所以得多看論文,培養解題的感覺是很重要的。

前一部分還是可以找到一些好看的書籍的,比如網路流,數論(初等數論、計算數論),數值分析,計算幾何等。至於DP則沒有啥好書了,作為一個剛上路的人,你會覺得理論和現實,差距真的好遠好遠。(但回過頭來會發現其實理論真的描述了一切)

高級階段,如果說初學階段要做的是打基礎,進階階段是加深深度,那麼高級階段就是加大廣度。你需要涉獵許多理論,系統性的學習。比如你只知道dinic,只知道dijkstra,只知道bellman-ford是不行的,你需要知道整個圖論它大概講的是啥,你需要知道還有什麼你是不懂的,不會的;再比如你只知道孫子定理,只知道丟番圖方程是不行的,你需要系統地學習數論知識,你要深刻理解歐拉函數,要深刻理解莫比烏斯函數,要深刻理解擴展歐幾里德,要深刻理解原根,等等等等。這樣你才能知道原來擴展歐幾里德可以輕鬆解出線性丟番圖方程,你才能知道原來解二次丟番圖方程要先解一下佩爾方程,你才能知道解高次同餘方程就是質因數分解+擴展歐幾里德+中國剩餘定理。

在你涉獵了足夠多的知識之後,再選擇性的深入學習。為什麼說是選擇性的深入學習呢?因為一個人的精力始終有限,方方面面不能都照顧到,剩下的就要交給隊友了,不然ACM為啥是個三人的比賽呢?

2. 實踐部分

其實實踐部分才是重中之重。

首先要知道ACM的代碼是個什麼樣的水平。

1. 代碼不多,大多在100行左右,多的在300行左右。當然,這些都是普遍的,也不排除有很長很長的代碼。或者換種說法,大多數代碼在1KBit左右,長的代碼在3K,打表的代碼不算。

2. 編程風格極「差」。這其中的代表有:

(1)幾乎所有變數都是全局變數,因為平時練習中有內存限制,而靜態變數區的大小足以應付。並且我們都知道,靜態區的速度是要優於堆區的速度的,所以一般是不用new或者malloc的。

(2)代碼怎麼簡單怎麼寫,以效率第一,犧牲部分代碼可讀性,犧牲安全性。

舉個例子,比如用C++的選手,在沒有特殊情況下,一般使用scanf而不用cin,這是因為前者效率比後者高許多,但scanf是有很多安全漏洞的,但是我們不管,因為我們正確的使用是不會導致問題的。

再舉個例子,比如你用scanf讀數據讀到文件尾(EOF),一般的想法是用EOF != scanf(...)作為循環判斷條件,而ACMer可能會寫成~scanf(...)。總之,代碼簡寫,效率第一。

3. ACM里的代碼大多數是結構化編程,面向對象的絕對不用,基於對象的可以用一點。這是由於代碼長度和效率優先的思想綜合導致的。

好了,接下來是實踐的正文。

ACM最重要的是什麼,是代碼控制力。要做到寫代碼跟你講話一樣,不說錯字(編譯錯誤),不說錯話(運行錯誤),表意正確(代碼邏輯正確)。樓上說的做TC、CF的比賽當然是好的,但是這些並不適合初學者。

(待續)


學好數學。。。


除了真正努力,無他

首先,想像摸象樣的參加regional,不被切的太難看,要訓練基本的能力,該想到的都想到,大家都會的演算法你也要會

然後,要避免切水題,切一些稍稍高過自己水平的較難題,自虐提高難度

TC div2 500-1000, div1都是鍛煉思維的神器

spoj的數據結構題要切一些

還有sgu,不過切不動...

ACM本身沒有止境,如果所有東西都會,感到胸有成竹,建議看看演算法書...一定會有新發現的


codeforces, topcoder,常有競賽,賽後有解體報告和別人的代碼,可以參考學習提高。實戰出真知呀。

演算法導論》 //好書,非常值得啃下來。acm入門之後,個人覺得對演算法的理解是很重要的!

挑戰程序設計競賽》//很有趣味的一本書,很有趣


匿了,貼張圖。

不要告訴我你不知道他是誰。


題主如果高中信息學競賽有集訓隊的話,可以爭取回去旁聽,我們高中是出過IOI國際金牌的,所以在訓練上會更加系統、更加科學,會更有效地幫助你提高水平。


1.多多和自己的隊友交流是促進小隊競爭力的最有效方法

2.相信團隊更需要相信自己,個人能力的提升才是最重要的

3.不斷的刷題吧,codeforces很好的一個訓練站(可惜我接觸的不多 orz)


做題做題做題


推薦閱讀:

手腕扭傷怎麼進行康復訓練?
如何快速訓練畫畫能力?

TAG:演算法 | 訓練 | 演算法設計 | ACM競賽 |