acm競賽網路培訓課程

1. 關於ACM競賽

ACM 是一個國際科學教育計算機組織,它致力於發展在高 級藝術、最新科學、工程技術和應用領域中的信息技術。它強調在專業領域或在社會感興趣的領 域中培養、發展開放式的信息交換，推動高級的專業技術和通用標準的發展。

1947年，即世界第一台電子數字計算機(ENIAC)問世的第二年，ACM即成為第一個，也一直是世界上最大的科學教育計算機組織。它的創立者和成員都是數學家和電子工程師，其中之一是約翰.邁克利(John.Mauchly)，他是ENIAC的發明家之一。他們成立這個組織的初衷是為了計算機領域和新興工業的科學家和技術人員能有一個共同交換信息、經驗知識和創新思想的場合。幾十年的發展，ACM的成員們為今天我們所稱之為「信息時代」作出了貢獻。他們所取得的成就大部分出版在ACM印刷刊物上並獲得了ACM頒發的在各種領域中的傑出貢獻獎。例如：A.M.Turing獎和Grance Murr—ay Hopper獎。

ACM組織成員今天已達到九萬人之多，他們大部分是專業人員、發明家、研究員、教育家、工程師和管理人員；三分之二以上的ACM成員，又是屬於一個或多個SIGs(Special Interest Group)專業組織成員。他們都對創造和應用信息技術有著極大的興趣。有些最大的最領先的計算機企業和信息工業也都是ACM的成員。

ACM就像一個傘狀的組織，為其所有的成員提供信息，包括最新的尖端科學的發展，從理論思想到應用的轉換，提供交換信息的機會。正象ACM建立時的初衷，它仍一直保持著它的發展「信息技術」的目標，ACM成為一個永久的更新最新信息領域的源泉。

ACM 國際計算機組織有以下主要活動內容：

1. 出版各種有關計算機技術的雜志，日報和書共十大類；

- Communications of the ACM ACM通訊

- Interactions 交互技術

- Standard View 標准

- Multimedia Systems 多媒體系統

- Computing Surveys 計算技術調查

- Computing Reviews 計算技術回顧

- Journal of the ACM ACM日報

- Wireless Networks 無線網路技術

- ACM's Transactions Journals ACM科研項目日報

包括：Computer-Human Interaction 人機交互技術

Computer Systems 計算機系統

Database Systems 資料庫系統

Graphics 作圖

Information Systems 信息系統

Mathematical Software 數學軟體

Modeling and Computer Simulation 建模和計算機模仿

Networking 網路

Programming Languages and Systems 編程語言和系統

Software Engineering & Methodology 軟體工程和方法學

- The ACM Press Books Program ACM 出版書四十種

2. ACM 有下屬37個專業組織SIGs(Special Interest Group)

(1)、SIGACT: Algorithm & Computational Theory

計算機科學基礎理論專業組織

(2)、SIGAda: Ada Programming Language

計算機科學軟體專業組織

(3)、SIGAPL: APL Programming Language

計算機應用軟體專業組織

(4)、SIGAPP: Applied Computing

應用計算機技術專業組織

(5)、SIGARCH: Computer Architecture

計算機硬體結構技術專業組織

(6)、SIGART: Artificial Intelligence

人工智慧專業組織

(7)、SIGBIO: Biomedical Computing

生物醫學專業組織

(8)、SIGBIT: Business Information Technology

商業信息理論專業組織

(9)、SIGCAPH: Computers & the Physically Handicapped

計算機與殘疾人專業組織

(10)、SIGCAS: Computers and Society

計算機與社會專業組織

(11)、SIGCHI: Computer-Human Interaction

人機交互專業組織

(12)、SIGCOMM: Data Communication

數據通訊專業組織

(13)、SIGCPR: Computer Personnel Research

計算機個人研究專業組織

(14)、SIGCSE: Computer Science Ecation

計算機科學教育專業組織

(15)、SIGCUE: Computer Uses in Ecation

計算機教育應用專業組織

(16)、SIGDA: Design Automation

自動化設計專業組織

(17)、SIGDOC: Systems Documentation

文件系統專業組織

(18)、SIGFORTH: FORTH Programming Language

第四編程語言專業組織

(19)、SIGGRAPH: Computer Graphics

計算機圖形圖像專業組織

(20)、SIGICE: Indivial Computing Environments

小型計算機環境專業組織

(21)、SIGIR: Information Retrieval

信息存儲恢復專業組織

(22)、SIGLINK: Hypertext & Hypermedia

專業組織

(23)、SIGMETRICS: Measurement & Evaluation

測量與估評專業組織

(24)、SIGMICRO: Micro-architectural Research & Practice

微型建築研究與實踐專業組織

(25)、SIGMM: Multimedia

多媒體專業組織

(26)、SIGMOD: Management of Data

數據管理專業組織

(27)、SIGNUM: Numerical Mathematics

數字數學理論專業組織

(28)、SIGOIS: Office Information Systems

辦公信息系統專業組織

(29)、SIGOPS: Operating Systems

操作系統專業組織

(30)、SIGPLAN: Programming Languages

編程語言專業組織

(31)、SIGSAC: Security, Audit and Control

保密稽核控制專業組織

(32)、SIGSAM: Symbolic & Algebraic Manipulation

符號與代數變換專業組織

(33)、SIGSIM: Simulation and Modeling

模仿與建模專業組織

(34)、SIGSOFT: Software Engineering

軟體工程專業組織

(35)、SIGSOUND: Electronic Forum on Sound Technology

聲音技術電子會議專業組織

(36)、SIGUCCS : University & College Computing Services

大專院校計算機服務專業組織

(37)、SIG3C: Computing at Community Colleges

社區院校計算機專業組織

3. 舉行專業年會

ACM和它的各專業組織SIGs每年在世界范圍內舉行60多場年會和展覽會，吸引五萬多人次來參加；

會議的主題主要是信息技術工業，其中最大的年會是SIGGRAPH。

4. 舉行地方專業會議和各種SIGs活動。

5. 與有關院校合作，召集學生參加多種會議和舉辦各種活動。

6. ACM 電子團體

7. 與其它專業協會交往:

ACM經常與其它專業協會交往，並召集舉辦其它電子計算機會議。

8. 對有傑出貢獻的計算機科學家、工程師、教育家和專業人員頒發八種主要獎：

- A.M. Turing Award

- Grace Murray Hopper Award

- Distinguished Service Award

- Doctoral Dissertation Award

- Eckert-Maucbly Award
- Software System Award
- Karl V. Karlstrom Outstanding Ecator Award
- Alan Newell Award

2. 參加ACM競賽需要學習一些什麼知識啊…演算法什麼的…待解決

先學數據結構
之後多看書，給你推幾本
ACM入門經典 劉汝佳
程序設計與分析 王曉東
實用的演算法分析與程序設計 吳文虎
演算法導論 一群老外寫的
演算法藝術與信息學競賽 劉汝佳

3. ACM的競賽流程

1.參賽隊伍最多由三名參賽隊員組成。
2.競賽中一般命題10題左右，試題描述為英文，比賽時間為5個小時，前四個小時可以看到實時排名，最後一小時封榜，無法看到排名。
3.競賽可以使用的語言：C++、C、Java和Pascal。但final賽只有C/C++;
4.重點考察選手的演算法和程序設計能力，不考察任何Windows編程知識；
5.選手可攜帶任何非電子類資料，包括書籍和列印出來的程序等，部分賽區會對攜帶的資料進行限制；
6.評委負責將結果（正確或出錯的類型）通過網路盡快返回給選手，除此之外不提供任何額外幫助；
返回結果：
1.Accepted. ---通過！(AC)
2.Wrong Answer. ---答案錯。(WA)
3.RunTime Error. ---程序運行出錯，意外終止等。(RTE)
4.Time Limit Exceeded. ---超時。程序沒在規定時間內出答案。(TLE)
5.Presentation Error. ---格式錯。程序沒按規定的格式輸出答案。(PE)
6.Memory Limit Exceeded. ---超內存。程序沒在規定空間內出答案。(MLE)
7.Compile Error. ---編譯錯。程序編譯不過。(CE)

4. 網上有哪些比賽是適合ACM初級入門的人的呢

http://codeforces.com/
http://bestcoder.h.e.cn/
第一個都是英文，Div2的 A B 題還是很適合新手的，，每兩周大概3次比賽回吧，，對應一個rating。
具體網路codeforces，了解相關答規則。
第二個是中國的，杭州電子科技大學做的一個比賽，每周六晚上7點，，新手的只能做1001（也就是第一題了），，不過這個支持中文，題目中英文都有。。。隨你選擇，加油吧，，新手剛開始不要太著急比賽（可以做幾次把握把握）然後可以學習相關專題。。

5. 請問哪裡可以找到acm-icpc程序競賽的視頻全套培訓教程（網路上好像都找不到這類視頻QAQ）謝謝

全套教程。。。。哪有這種東西，最多是全套入門教程 來自Lumia830

6. 參加ACM競賽需要用的參考書

演算法導論 演算法藝術與信息學競賽 初等數論 具體數學 柔性字元串匹配

7. 大一學數學的以後可以參加ACM競賽嗎需要學習哪些課程 謝謝大佬。

確實需要，一般來說，在單純學習演算法到一定程度時大家的水平都差不多，但是想要更內進一步就需容要非常扎實的數學功底，數學並不一定指的是數論和組合數學，更為確切地說應該是一種剖析、思考的高效方式，於是很容易地發現問題的本質，就可以產生清晰的解題思路，在套用自己學過的演算法就成了，中級水平的acmer和高級水平的acmer的差距大概就在這里，這並不是時間和經驗就能彌補的
事實上，國際比賽中常有數學系的學生摘金奪銀，樓天成高中時除了詩歌oier，還是全國數學競賽一等獎,這都很能說明問題

8. 什麼是ACM培訓

ACM 即 ACM國際大學生程序設計競賽。
ACM國際大學生程序設計競賽標志ACM國際大學生程序設計競賽(英文全稱： International Collegiate Programming Contest（ACM-ICPC或ICPC）是由美國計算機協會（ACM）主辦的，一項旨在展示大學生創新能力、團隊精神和在壓力下編寫程序、分析和解決問題能力的年度競賽。經過近30多年的發展，ACM國際大學生程序設計競賽已經發展成為最具影響力的大學生計算機競賽。賽事目前由IBM公司贊助。
基本概況
ACM/ICPC（國際大學生程序設計競賽）是由ACM(，美國計算機協會)組織的 ACM競賽年度性競賽，始於1970年，是全球大學生計算機程序能力競賽活動中最有影響的一項賽事，是全球歷史最悠久、規模最大且最負盛名的程序設計競賽。競賽提倡創新和團隊協作，鼓勵學生在構建全新的軟體程序時盡情發揮創意，幫助學生檢驗自己在強壓力下的工作能力。 ACM國際大學生程序設計競賽(ICPC)的歷史可以上溯到1970年，當時美國德州A&M大學舉辦了首屆競賽，主辦方是UPE計算機科學榮譽協會Alpha分會。作為一種發現和培養計算機科學這一新興領域頂尖學生的全新方式，競賽很快得到了美國和加拿大多所大學的積極響應。
1977年，首屆ICPC總決賽在ACM計算機科學會議期間舉行，並由此演變成一項多級競賽。此後，ACM擔任競賽主辦方，並於1989年將大賽總部設在了美國德克薩斯州的貝勒大學。從此，該競賽逐漸發展成了一個舉辦區域預賽選拔參賽隊伍參加ACM-ICPC全球決賽的全球大學網路。
1997年，IBM成為競賽的贊助方。IBM的加盟促使競賽的規模擴大了七倍。參賽人數顯著增加，涉及來自六大洲83個國家1,821所大學數萬名計算領域的頂尖學生和教師。

9. ACM 關於ACM程序設計競賽，需要掌握哪些知識點，最好能詳細一點，謝謝高手們了。

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

中級:
一.基本演算法:
(1)C++的標准模版庫的應用. (poj3096,poj3007)
(2)較為復雜的模擬題的訓練(poj3393,poj1472,poj3371,poj1027,poj2706)
二.圖演算法:
(1)差分約束系統的建立和求解. (poj1201,poj2983)
(2)最小費用最大流(poj2516,poj2516,poj2195)
(3)雙連通分量(poj2942)
(4)強連通分支及其縮點.(poj2186)
(5)圖的割邊和割點(poj3352)
(6)最小割模型、網路流規約(poj3308, )
三.數據結構.
(1)線段樹. (poj2528,poj2828,poj2777,poj2886,poj2750)
(2)靜態二叉檢索樹. (poj2482,poj2352)
(3)樹狀樹組(poj1195,poj3321)
(4)RMQ. (poj3264,poj3368)
(5)並查集的高級應用. (poj1703,2492)
(6)KMP演算法. (poj1961,poj2406)
四.搜索
(1)最優化剪枝和可行性剪枝
(2)搜索的技巧和優化 (poj3411,poj1724)
(3)記憶化搜索(poj3373,poj1691)

五.動態規劃
(1)較為復雜的動態規劃(如動態規劃解特別的施行商問題等)
(poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)
(2)記錄狀態的動態規劃. (POJ3254,poj2411,poj1185)
(3)樹型動態規劃(poj2057,poj1947,poj2486,poj3140)
六.數學
(1)組合數學:
1.容斥原理.
2.抽屜原理.
3.置換群與Polya定理(poj1286,poj2409,poj3270,poj1026).
4.遞推關系和母函數.

(2)數學.
1.高斯消元法(poj2947,poj1487, poj2065,poj1166,poj1222)
2.概率問題. (poj3071,poj3440)
3.GCD、擴展的歐幾里德(中國剩餘定理) (poj3101)
(3)計算方法.
1.0/1分數規劃. (poj2976)
2.三分法求解單峰(單谷)的極值.
3.矩陣法(poj3150,poj3422,poj3070)
4.迭代逼近(poj3301)
(4)隨機化演算法(poj3318,poj2454)
(5)雜題.
(poj1870,poj3296,poj3286,poj1095)
七.計算幾何學.
(1)坐標離散化.
(2)掃描線演算法(例如求矩形的面積和周長並,常和線段樹或堆一起使用).
(poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)
(3)多邊形的內核(半平面交)(poj3130,poj3335)
(4)幾何工具的綜合應用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429)

高級:
一.基本演算法要求:
(1)代碼快速寫成,精簡但不失風格
(poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)
(2)保證正確性和高效性. poj3434
二.圖演算法:
(1)度限制最小生成樹和第K最短路. (poj1639)
(2)最短路,最小生成樹,二分圖,最大流問題的相關理論(主要是模型建立和求解)
(poj3155, poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446
(3)最優比率生成樹. (poj2728)
(4)最小樹形圖(poj3164)
(5)次小生成樹.
(6)無向圖、有向圖的最小環
三.數據結構.
(1)trie圖的建立和應用. (poj2778)
(2)LCA和RMQ問題(LCA(最近公共祖先問題) 有離線演算法(並查集+dfs) 和 在線演算法
(RMQ+dfs)).(poj1330)
(3)雙端隊列和它的應用(維護一個單調的隊列,常常在動態規劃中起到優化狀態轉移的
目的). (poj2823)
(4)左偏樹(可合並堆).
(5)後綴樹(非常有用的數據結構,也是賽區考題的熱點).
(poj3415,poj3294)
四.搜索
(1)較麻煩的搜索題目訓練(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)
(2)廣搜的狀態優化:利用M進制數存儲狀態、轉化為串用hash表判重、按位壓縮存儲狀態、雙向廣搜、A*演算法. (poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)
(3)深搜的優化:盡量用位運算、一定要加剪枝、函數參數盡可能少、層數不易過大、可以考慮雙向搜索或者是輪換搜索、IDA*演算法. (poj3131,poj2870,poj2286)
五.動態規劃
(1)需要用數據結構優化的動態規劃.
(poj2754,poj3378,poj3017)
(2)四邊形不等式理論.
(3)較難的狀態DP(poj3133)
六.數學
(1)組合數學.
1.MoBius反演(poj2888,poj2154)
2.偏序關系理論.
(2)博奕論.
1.極大極小過程(poj3317,poj1085)
2.Nim問題.
七.計算幾何學.
(1)半平面求交(poj3384,poj2540)
(2)可視圖的建立(poj2966)
(3)點集最小圓覆蓋.
(4)對踵點(poj2079)
八.綜合題.
(poj3109,poj1478,poj1462,poj2729,poj2048,poj3336,poj3315,poj2148,poj1263)

-----------------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------
以及補充
Dp狀態設計與方程總結
1.不完全狀態記錄
<1>青蛙過河問題
<2>利用區間dp
2.背包類問題
<1> 0-1背包，經典問題
<2>無限背包，經典問題
<3>判定性背包問題
<4>帶附屬關系的背包問題
<5> + -1背包問題
<6>雙背包求最優值
<7>構造三角形問題
<8>帶上下界限制的背包問題(012背包)
3.線性的動態規劃問題
<1>積木游戲問題
<2>決斗（判定性問題）
<3>圓的最大多邊形問題
<4>統計單詞個數問題
<5>棋盤分割
<6>日程安排問題
<7>最小逼近問題(求出兩數之比最接近某數/兩數之和等於某數等等)
<8>方塊消除游戲(某區間可以連續消去求最大效益)
<9>資源分配問題
<10>數字三角形問題
<11>漂亮的列印
<12>郵局問題與構造答案
<13>最高積木問題
<14>兩段連續和最大
<15>2次冪和問題
<16>N個數的最大M段子段和
<17>交叉最大數問題
4.判定性問題的dp(如判定整除、判定可達性等)
<1>模K問題的dp
<2>特殊的模K問題，求最大(最小)模K的數
<3>變換數問題
5.單調性優化的動態規劃
<1>1-SUM問題
<2>2-SUM問題
<3>序列劃分問題(單調隊列優化)
6.剖分問題(多邊形剖分/石子合並/圓的剖分/乘積最大)
<1>凸多邊形的三角剖分問題
<2>乘積最大問題
<3>多邊形游戲(多邊形邊上是操作符,頂點有權值)
<4>石子合並(N^3/N^2/NLogN各種優化)
7.貪心的動態規劃
<1>最優裝載問題
<2>部分背包問題
<3>乘船問題
<4>貪心策略
<5>雙機調度問題Johnson演算法
8.狀態dp
<1>牛仔射擊問題(博弈類)
<2>哈密頓路徑的狀態dp
<3>兩支點天平平衡問題
<4>一個有向圖的最接近二部圖
9.樹型dp
<1>完美伺服器問題(每個節點有3種狀態)
<2>小胖守皇宮問題
<3>網路收費問題
<4>樹中漫遊問題
<5>樹上的博弈
<6>樹的最大獨立集問題
<7>樹的最大平衡值問題
<8>構造樹的最小環

10. 參加ACM大賽應該准備哪些課程

課程：

（1）基本演算法: 二分,分治，貪心

（2） 離散數學離散數學動態規劃

（3） 搜索演算法：深度優先 搜索，廣度優先搜A*演算法 ，阿爾法貝塔剪枝

（4）數據結構:線段樹, 樹狀數組，並查集,Trie圖

（5）圖論問題：最小生成樹 最短路 強連通分量、橋和割點

（6）網路流演算法：基本的網路流演算法，Dinic演算法，帶上下界的網路流，最小費用流

（7）計算幾何：線與線求交，線與面求交，求凸包，半平面求交等

（8） 離散數學，高等數學，線性代數，初等數論，計算幾何

（9）計算機專業英語

（10）C++；基礎的遞歸、枚舉演算法

(10)acm競賽網路培訓課程擴展閱讀：

1.參賽隊伍最多由三名參賽隊員組成。

2.競賽中命題10題左右，試題描述為英文，比賽時間為5個小時，前四個小時可以實時看到排名，最後一小時封榜，無法看到排名。

3.競賽可以使用的語言：Java, C, C++, Kotlin 和 Python。

4.重點考察選手的演算法和程序設計能力，不考察實際工程中常用的系統編程，多線程編程等等；

5.選手可攜帶任何非電子類資料，包括書籍和列印出來的程序等，部分賽區會對選手攜帶的紙質資料做限制。

6.評委負責將結果（正確或出錯的類型）通過網路盡快返回給選手，除此之外不提供任何額外幫助；

7.每個題目對應一種顏色的氣球，通過該題目的隊伍會得到對應顏色氣球。每道題目第一支解決掉它的隊還會額外獲得一個「FIRST PROBLEM SOLVED」的氣球。