背景
可能是因為新的一年藍橋杯報名開始了,所以最近有很多小伙伴私聊我,問該如何訓練,訓練到什么地步可以拿獎,所以我想再補充一些關于具體訓練內容的東西來幫助大家訓練.我也是第二次參加藍橋杯了,第一次也是拿到了國家二等獎(B組),對這部分內容有興趣的同學也可以去看看我之前寫的一篇博客.
考點
既然要參加藍橋杯那對它的考試內容當然要相當了解了.這一部分可以在藍橋杯官網查看我這里也會為大家進行一個總結,其實藍橋杯作為演算法競賽考點與ACM差不多,主要包括但不限于以下三個部分
1.計算機演算法：列舉、排序、搜索、計數、貪心、動態規劃、圖論、數論、博弈論、概率論、計算幾何、字串演算法、數論等
2.資料結構：陣列、物件/結構、字串、佇列、堆疊、樹、圖、堆、平衡樹/線段樹、復雜資料結構、嵌套資料結構等，
3.計算機基礎知識
這三塊內容與語言無關,語言只是為了方便大家來實作這兩塊內容.那么了解完需要學習的東西,什么才是作為新手來入手的演算法與資料結構,什么是準備沖刺國一(B組)、國獎(A組)所需要的內容呢?其優先級又如何呢?每種演算法又包括什么呢?如果你是身經百戰的ACM選手對這些名詞或多或少都有了解,但是作為大一、大二沒有參與過多演算法競賽的小白來說,這一部分內容應該是大家比較關心的,接下來就詳細的來分析應對不同人群在有限的時間內所要學習的內容.
前置知識
比賽形式
形式：閉卷、OI賽制
OI賽制：每道題提交之后都沒有任何反饋，每道題都有多個測驗點，根據每道題通過的測驗點的數量獲得相應的分數，每道題不限制提交次數，如果提交錯誤沒有任何懲罰，僅以最后一次提交為準，比賽程序中看不到實時排名，賽后按照總得分來排名，（賽中無法得知自己的得分所以輸入輸出不當是會0分的這樣建議不懂得同學可以補一下這方面內容標準輸入輸出）
題型：
填空題
編程大題（一般來說各五道）
省賽
如果你是從未接觸過演算法競賽的小白,那你首先要考慮的內容是如何面對省賽,畢竟拿到省一等獎才有資格去參加國賽嘛,那你所需要準備的內容以及難度不算太難.
1.計算機基礎知識(填空 5分)
作業系統、計算機網路、計算機組成
這一部分大家其實不必過分緊張,只是考的大家一個常識的問題,也是近兩年才剛剛新出的題型,包括上次模擬賽也出了一道常識題,可以預見省賽與國賽也是會涉及的,主要是考計算型題型,這里給大家的建議是不用過分糾結
2.演算法（序號表示優先級）
1.列舉
掌握列舉思想,就是寫暴力,省賽會寫暴力加一點點演算法就能出線了,這里的列舉主要包括,回圈遍歷、BFS、DFS
2.排序
一般配合著列舉使用，速成來說會Sort就好了，當然作為學習來說手寫一下冒泡、選擇、歸并、快排、堆排等都是可以的，（掌握sort、 priority_queue）
訓練題單
3.雙指標、前綴和、二分、差分、遞推
常用得基本演算法思想用來優化演算法復雜度的入門演算法（大量刷題、這是基本分）
4.最大公約數、最小公倍數、素數
掌握其中關系、素數篩（歐拉篩、埃氏篩）
5.動態規劃（學到這就有機會省一了）
01背包問題、線性dp、區間dp
6.圖論、字串演算法（去年學到這就國二了）
最短路徑（Dijktra、spfa、Floyd）、最小生成樹（prim、Kruskal）、BFS、DFS、KMP、字典樹
3.資料結構（無先后順序）
其實在第二部分的內容里就會學到相關的內容了，主要配合著演算法使用、作為一種思想
1.堆疊
單調堆疊
2.佇列（BFS）
單調佇列
3.堆（堆排序 priority_queue）
4.鏈表（鄰接表的思想）
5.哈希表
6.并查集（Kruskal）
其實資料結構的實作在各種語言中都有封裝好現成的可以使用（C++STL是必須要會用的）
具體訓練
首先是根據要學的內容去刷題,一題一題刷,這里首推洛谷題單整理的很好,只要跟著寫就好了.建議把入門也刷了,可以練一下基本功,否則要是被一些奇怪的輸出輸入卡了就不好了.其次呢可以去牛客,有條件的買課只推Acwing跟著練就完了.(可以關注我的ACM入門教程這個專欄、會根據上述內容緩慢更新)
國賽
其實如果是沖刺國賽相信大家都有自己的訓練計劃了，我這里就根據自己的訓練計劃來給大家分享拙見了，由于藍橋杯是閉卷的所以考的演算法相對來說不會很偏，當我們拿下暴力分后就應該想想改如何進行優化了，常見的優化手段就是套資料結構/dp優化/數學分析，針對這部分內容我認為比較好想的分數應該是資料結構，以及更加熟練的掌握的搜索，
DP
1.各類背包
2.狀壓DP
3.斜率優化DP
4.數位DP
搜索
1.DFS剪枝優化
2.迭代加深
3.雙向BFS
4.A*、IDA*
5.雙向廣搜
圖論
1.差分約束
2.二分圖
3.拓撲排序
4.最近公共祖先
資料結構
1.線段樹
2.樹狀陣列
3.平衡樹
4.AC自動機
數學
1.概率與數學期望
2.組合數
3.矩陣乘法
基礎演算法
1.RMQ.ST表
總結
簡要的寫了寫所需要學的演算法，發現還蠻多的，演算法之路漫慢，日常做題就是上CF或者牛客月賽之類的，計劃著根據這份演算法路線寒假繼續鞏固，每個模塊都用自己的理解來表達，希望大家都好好加油，取得個好成績！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/384161.html
標籤：其他