NOIP資訊學奧賽普及組備戰攻略|奧林程式設計
考前須知
NOIP普及組比賽日程和題型
▷初賽:每年
10月份第二個週末 14:30-16:00
題型:選擇題,問題求解,程式填空、程式結果運算
▷複賽:每年
11月份第二個週六 14:30-18:00
題型:編寫程式(共 4道題)
NOIP 2018年獲獎情況
由於國家人工智慧戰略和各高校的優惠政策,
自主招生
向資訊學奧賽靠攏的趨勢,資訊學奧賽歷年的報名人數呈30%的遞增趨勢。2018年
初賽參賽人數是55851人
,篩選後進入
複賽有11909人
。進入複賽後,
總獲獎率高達到72%,其中一等獎22%二等獎46%三等獎5.2%。
實際初賽的難度不高,但透過率僅為1/4。一方面原因是篩選掉的學生多是0基礎型選手,另外CCF官方對比賽的規模、組織、成本控制也有考量,比如以往考試場地對計算機的容納數量是巨大的挑戰,
預計今年場地問題會被最佳化,初賽進入複賽的比例會有所增加。
NOIP省賽的特點註定了省間差異十分大,省賽參賽人數(普及組+提高組)超過5000的省份只有8個,分別是
山東、四川、江蘇、安徽、浙江、福建、廣東、河北
,而普及組的總參賽人數是5W多,
平均下來某些省份的參賽人數在2000左右,甚至幾百人,對考生來說競爭環境良好。
對資訊學競賽賽程賽制有疑問可以回看往期全面解讀C++資訊學奧賽,家長必讀
題型分析
我們統計了2000-2018年所有複賽程式編寫的76道考題後,從普及組20大門類問題中整理出了
8種常見題型
:
1。
列舉
。列舉是程式設計最簡單樸素的演算法,可以理解為窮舉或搜尋演算法,也是典型的拿分題。
2。
簡單動態規劃
;
3。
數學、數論
。比如質數、素數、漢諾塔、數列,這些數學知識在程式設計裡需要用程式的方式表現,而這些數學知識相對奧數難度低了很多;
4。
排序
。在十大排序演算法中其中又以快速排序、冒泡、堆排序最為常見;
5。
模擬
。當無法規則化解題時可以用模擬演算法嘗試;
6。
字串
。程式設計常用型別,規範性強,是歷年出題的搶手題,也是拿分題,有時字串會和其他問題結合在一起出現;
7。
搜尋
。從簡單搜尋到深度搜索各種型別都有出現;
8。
貪心演算法
。例如歷史上的排座椅、紀念品問題。
其他如圖論、
揹包問題
、數論、分支都是偏向提高組的題型,在普及組是低頻題、拉分題。按5星最難,1星最簡單作程度分類,常見8種題型難度都是在1~3星,搞定這些題目可以達到普及組二等獎的水準;一等獎水準對應的是大部分4星難度能掌握,個別5星問題能攻克;
NOIP長期備戰四個策略
▶ DO or NOT DO
C++語言很強大,但坑多藏得又深,比如迴圈越界,考生自己難以發現,在寫入操作中迴圈越界會影響後續
變數值
,因此要熟練掌握C++規則和模型,既要懂做什麼,也要懂不要做什麼;
▶
練習
◆大量做題練習,培養“碼感”,熟練套路;
◆針對具體要做多少道題,這裡給出一個
量化參考
,考生可以根據自己的情況規劃練習頻率,比如一週10道題的練習積累,一年可以衝刺普及組一等獎;也可以依此判斷準備時間,
比如對於大部分強省考生,提高組衝獎需要準備2年的時間
。
▶
掌握演算法,熟練資料結構
資料結構就是清楚資料的輸入、儲存、變換、輸出整個流向。這裡引用一個公式“
程式設計 = 演算法+資料結構
”。演算法和資料結構是程式設計的一體兩面這點是技術界的共識,然而
資訊奧賽
歷史過於強調演算法導致部分考生容易偏頗的理解這兩者,忽略資料結構的重要性。
▶
建立 “庫存優勢!“
這裡的“庫存”指可以拿來即用的“程式設計庫”。掌握 STL(標準庫) ,特別是vector、string、list、stack、queue、 map、 set 、 tree 等常用資料結構和 algorithm 中的常用演算法可以大大提升效率。
臨考五大方針
▶ 花時間審題,
選擇對自己最簡單的題目
。題目不一定是按照難易程度排列的。
▶ 選中優先做的題後,不要急著寫程式碼,
先勾劃一下演算法流程+資料結構
▶ 對於約束、邊界條件,可以先不考慮,
不要讓這些攔住演算法的整體思維
。
▶
不鑽牛角尖
,如果某一種方法不work,跳出思維,換一種方式。
▶不會的題目,特殊的邊界,
最後階段暴力解決
(樸素演算法)“騙分”,即獲得樸素分。“騙分”,其實是非完美演算法(NOIP判題策略是機器輸入10組左右資料檢驗工作) 。暴力也有含金量!
避免低階錯誤
▶未包含標頭檔案——
編譯檢查自己的標頭檔案!
▶Linux 和 Win有區別——
使用萬能標頭檔案 #include<bits/stdc++.h>
注意”/“方向
▶主函式沒有 return 0 ——
寫演算法前先寫好return 0!
▶未按規範寫檔名,未使用檔案輸入輸出——
寫演算法前先寫好輸入輸出
。
▶數值溢位,浮點精度丟失——
儘量使用儲存空間大的型別。
▶陣列記憶體不夠、越界——
熟練陣列!
▶字
符串
、字元、8位、16位、大小寫 搞混淆——
熟練字串!
▶注意空間和時間複雜度限制!——
掌握複雜度判斷!
NOIP十問十答
▶剛剛開始學習,能夠打2019年資訊學奧賽嗎?
可以,但不要對一等獎抱有幻想,目標設定到三等獎或二等獎,對於10月份的初賽,需要規劃
每週3-6小時的學習時間以及每週精練10道題
。
▶語言選擇如何?選擇C語言是不是簡單點?
C語言和PASCAL目前仍是NOIP考試可使用的語言,但從2022年開始,
NOIP競賽也將不再支援Pascal語言和C語言,C++將成為唯一推薦使用語言
。C語言雖然相對簡單,但不使用C++是一個巨大的損失。首先使用其他語言,STL標準庫裡很多拿來即用的函式無法使用,另外C語言過於老套,比如C語言沒有string這個型別,而用
字元陣列
或字元指標代替,複雜性大大增加,在C++裡面寫字串比在C語言裡簡單很多。
▶如何報名資訊學奧賽?
初賽一般都是以學校為單位
透過指導教師報名(每年9月份開始報名)
。若學校因故不能統一報名,家長可
直接聯絡特特派員報名
(各省特派員聯絡方式見
http://www。
noi。cn/newsview。html?
id=81&hash=C6F26A&type=9
),由省特派員在報名截止日期前統一提交至中國計算機學會(CCF)。NOIP初賽時間是每年10月份,複賽為每年11月份。透過NOIP初賽的考生可以在10月末報名複賽。另外也可選擇
透過我們代報名
。
▶初賽基礎知識如何學習?
初賽的基礎知識比如常見邏輯、
二進位制
等等,我們會在課程中穿插講解,對於0基礎的學生,
初賽的基礎知識在比賽前突擊一兩週即可掌握
。
▶既然做題很重要,如何科學刷題?
科學刷題要做到三點:
a.做題要有反饋。
對哪裡出錯,哪裡已掌握要有明確認知。
b.做題要包含獨立思考過程,
不能照本宣科。
c.對常見題型要有一定覆蓋量
(詳見”題型分析部分“)
▶ 對自學和報班分別有什麼建議?
自學要科學,要有規劃有反饋,資源和題目的把握是對自學的很大考驗,而報班級學習就節省了很多時間。
▶
聽說可以騙分,老師教我怎麼騙分!
”
騙分“實際是指樸素演算法,而樸素演算法是程式設計的基本素養。真正能寫出好的”騙分“的都是高手。
▶資訊學奧賽什麼時候開始學?有什麼學習規劃?
▶
臨考前怎麼突擊提高?
練習時在
8大類高頻題
上多花時間,有難度的題型比如
動態規劃
可以適當放過。
▶
我能獲獎嗎?有什麼秘訣?(★★★)
由於時間已經臨近比賽了,這個時間衝刺獲獎的可能性是要因人而異的,這裡奧林為衝刺今年NOIP的考生送上限量福利——
賽前真人測評
,在一個小時的時間裡透過題目測試+
導師1V1問答互動判斷考生水平,題目涵蓋初賽複賽所有題型範圍,並給出考生能力水平報告
。
認識奧林
奧林程式設計
是溫故知新(上海)教育科技有限公司旗下青少兒程式設計教育品牌。奧林程式設計承襲母公司 Boolan 在 IT 職業教育領域技術、資源優勢,奧林程式設計教研顧問團隊主要負責奧林程式設計的課程研發及資源支援。
研究院與加州大學伯克利分校、斯坦福大學、舊金山大學、華東師範大學深入合作
,為奧林程式設計提供科學、嚴謹的課程研發與教學效果支援。
我們的課程安排遵循以下六步:能力測試,瞭解學生基礎——多元導學,針對性教學方案——互動教學,趣味式啟發寓教於樂——練習作業,輸出檢驗輸入——線上輔導,隨時隨地自由便捷——智慧題庫,AI智慧教學練題更高效。
微信關注“奧林程式設計”回覆“NOIP”獲取2004-2018年真題資料
回覆“講座”,參與8月8日提高組備戰講座