信息學(xué)競賽如何學(xué)習(xí)及準備攻略

　　信息學(xué)競賽要想考的好，靠前的準備當然也是必不可少的，以下是CN人才小編搜集并整理的有關(guān)內(nèi)容，希望對大家有所幫助！

　　溫馨提示，信息學(xué)的學(xué)習(xí)須具備的五大能力：

　　一是觀察、分析問題的能力；

　　二是數(shù)學(xué)建模的能力；

　　三是靈活運用算法的能力；

　　四是編寫代碼并且調(diào)試的能力；

　　五是檢測程序是否正確的能力。

　　除此之外，調(diào)試能力比編程能力更重要。很多學(xué)生之所以參加信息學(xué)競賽但拿不了獎，很大部分原因就在于調(diào)試環(huán)節(jié)出了差錯。具備算法功底、編程能力之外，還需要具備創(chuàng)造性思維以及團隊合作的能力。信息學(xué)與各個學(xué)科都密切相關(guān)，尤其是數(shù)學(xué)學(xué)科，信息學(xué)的本質(zhì)就是利用計算機來解決數(shù)學(xué)問題。

　　信息學(xué)競賽的比賽時間

　　每年10-11月份：全國奧林匹克信息學(xué)競賽聯(lián)賽NOIP，初賽和復(fù)賽；

　　來年7月份：全國奧林匹克信息學(xué)競賽NOI，信息競賽國決；

　　翻年1月份：國家隊選拔賽；

　　8月份：參加國際奧林匹克信息學(xué)競賽IOI。

　　信息學(xué)競賽考什么？考試的形式及流程

　　聯(lián)賽分兩個等級組：普及組和提高組。每組競賽分兩輪：初試和復(fù)試。

　　初試形式為筆試，側(cè)重考察學(xué)生的計算機基礎(chǔ)知識和編程的基本能力，并對知識面的廣度進行測試。初試為資格測試，各省初試成績在本賽區(qū)前15％的學(xué)生進入復(fù)賽。

　　復(fù)試形式為上機，著重考察學(xué)生對問題的分析理解力，數(shù)學(xué)抽象能力，編程語言的能力和編程技巧、想象力和創(chuàng)造性等。各省聯(lián)賽的等第獎在復(fù)試的優(yōu)勝者中產(chǎn)生。

　　初賽：初賽全部為筆試，滿分100分。試題由四部分組成：

　　1、選擇題：共20題，每題1.5分，共計30分。每題有5個備選答案，前10個題為單選題(即每題有且只有一個正確答案，選對得分)，后10題為不定項選擇題(即每題有1至5個正確答案，只有全部選對才得分)。

　　2、問題求解題：共2題，每題5分，共計10分。試題給出一個敘述較為簡單的問題，要求學(xué)生對問題進行析，找到一個合適的算法，并推算出問題的解�？忌�給出的答案與標準答案相同，則得分：否則不得分。

　　3、程序閱讀理解題：共4題，每題8分，共計32分。題目給出一段程序(不一定有關(guān)于程序功能的說明)，考生通過閱讀理解該段程序給出程序的輸出。輸出與標準答案一致，則得分；否則不得分。

　　4、程序完善題：共2題，每題14分，共計28分。題目給出一段關(guān)于程序功能的文字說明，然后給出一段程序代碼，在代碼中略去了若干個語句或語句的一部分并在這些位置給出空格，要求考生根據(jù)程序的功能說明和代碼的上下文，填出被略去的語句。填對則得分；否則不得分。

　　復(fù)賽：自2011年開始，提高組復(fù)賽分為一試和二試，各3題，每題100分，共計600分。

　　每一試題包括：題目、問題描述、輸入輸出要求、樣例描述及相關(guān)說明。測試時，測試程序為每道題提供了5-10組測試數(shù)據(jù)，考生程序每答對一組得10—20分，累計分即為該道題的得分。

　　測試的知識范圍

　　(一)初賽內(nèi)容與要求

　　1、計算機的基本常識

　　計算機和信息社會(信息社會的主要特征、計算機的主要特征、數(shù)字通信網(wǎng)絡(luò)的主要特征、數(shù)字化)

　　信息輸入輸出基本原理(信息交換環(huán)境、文字圖形多媒體信息的輸入輸出方式)

　　信息的表示與處理(信息編碼、微處理部件MPU、內(nèi)存儲結(jié)構(gòu)、指令，程序，和存儲程序原理、程序的三種基本控制結(jié)構(gòu))

　　信息的存儲、組織與管理(存儲介質(zhì)、存儲器結(jié)構(gòu)、文件管理、數(shù)據(jù)庫管理)

　　信息系統(tǒng)組成及互連網(wǎng)的基本知識(計算機構(gòu)成原理、槽和端口的部件間可擴展互連方式、層次式的互連結(jié)構(gòu)、互聯(lián)網(wǎng)絡(luò)、TCP／IP協(xié)議、HTTP協(xié)議、WEB應(yīng)用的主要方式和特點)

　　人機交互界面的基本概念(窗口系統(tǒng)、人和計算機交流信息的途徑(文本及交互操作))

　　信息技術(shù)的新發(fā)展、新特點、新應(yīng)用等。

　　2、計算機的基本操作

　　WINDOWS和LINUX的基本操作知識

　　聯(lián)網(wǎng)的基本使用常識(網(wǎng)上瀏覽、搜索和查詢等)

　　常用的工具軟件使用(文字編輯、電子郵件收發(fā)等)

　　3、程序設(shè)計的基本知識

　　數(shù)據(jù)結(jié)構(gòu)

　　程序語言中基本數(shù)據(jù)類型(字符、整數(shù)、長整數(shù)、浮點)

　　浮點運算中的精度和數(shù)值比較

　　一維數(shù)組(串)與線性表

　　記錄類型(PASCAL)／結(jié)構(gòu)類型(C)

　　程序設(shè)計

　　結(jié)構(gòu)化程序設(shè)計的基本概念

　　閱讀理解程序的基本能力

　　具有將簡單問題抽象成適合計算機解決的模型的基本能力

　　具有針對模型設(shè)計簡單算法的基本能力

　　程序流程描述(自然語言／偽碼／NS圖／其他)

　　基本算法處理

　　初等算法(計數(shù)、統(tǒng)計、數(shù)學(xué)運算等)

　　排序算法(冒泡法、插入排序、合并排序、快速排序)

　　查找(順序查找、二分法)

　　回溯算法

　　(二)復(fù)賽內(nèi)容與要求

　　在初賽的內(nèi)容上增加以下內(nèi)容

　　1、數(shù)據(jù)結(jié)構(gòu)

　　指針類型

　　多維數(shù)組

　　單鏈表及循環(huán)鏈表

　　二叉樹

　　文件操作(從文本文件中讀入數(shù)據(jù)，并輸出到文本文件中)

　　2、程序設(shè)計

　　算法的實現(xiàn)能力

　　程序調(diào)試基本能力

　　設(shè)計測試數(shù)據(jù)的基本能力

　　程序的時間復(fù)雜度和空間復(fù)雜度的估計

　　3、算法處理

　　離散數(shù)學(xué)知識的應(yīng)用(如排列組合、簡單圖論、數(shù)理邏輯)

　　分治思想

　　模擬法

　　貪心法

　　簡單搜索算法(深度優(yōu)先廣度優(yōu)先)搜索中的剪枝

　　動態(tài)規(guī)劃的思想及基本算法

　　信息學(xué)競賽必備書單匯總

　　基礎(chǔ)篇

　　1、《全國青少年信息學(xué)奧林匹克分區(qū)聯(lián)賽初賽培訓(xùn)教材》（推薦指數(shù)：4顆星）曹文，吳濤編著，知識點大雜燴，部分內(nèi)容由學(xué)生撰寫，但是對初賽知識點的覆蓋還是做得相當不錯的。語言是pascal的。

　　2、譚浩強老先生寫的《C語言程序設(shè)計（第三版）》（推薦指數(shù)：5顆星）針對零基礎(chǔ)學(xué)C語言的筒子，這本書是必推的。

　　3、《騙分導(dǎo)論》（推薦指數(shù)：5顆星）參加NOIP必看之經(jīng)典。

　　4、《全國信息學(xué)奧林匹克聯(lián)賽培訓(xùn)教程（一）》（推薦指數(shù)：5顆星）傳說中的黃書。吳文虎，王建德著，系統(tǒng)地介紹了計算機的基礎(chǔ)知識和利用Pascal語言進行程序設(shè)計的方法。

　　5、《全國青少年信息學(xué)奧林匹克聯(lián)賽模擬訓(xùn)練試卷精選》王建德著，傳說中的紅書。

　　6、《算法競賽入門經(jīng)典》（推薦指數(shù)：5顆星）劉汝佳著，算法必看經(jīng)典。

　　7、《算法競賽入門經(jīng)典:訓(xùn)練指南》（推薦指數(shù)：5顆星）劉汝佳著，《算法競賽入門經(jīng)典》的重要補充。

　　歷年真題必須做，這是絕對不能遺失的存在！

　　1、題庫方面首推USACO（美國的賽題），usaco寫完了一等基本上就沒有問題，如果悟性好的話甚至能在NOI取得不錯的成績。

　　2、除此之外Vijos也是一個不錯的題庫，有很多中文題。

　　3、國內(nèi)廣受NOIP級別選手喜歡的國內(nèi)OJ（Tyvj、CodeVs、洛谷、RQNOJ）。

　　4、BZOJ擁有上千道省選級別及以上的題目資源，但有一部分題目需要購買權(quán)限才能訪問。

　　NOIP初賽偏重于基礎(chǔ)知識，一部分是計算機的基礎(chǔ)知識，計算機基礎(chǔ)部分，內(nèi)容多而雜，多以選擇題形式出現(xiàn)，所以不必要花太多時間去背，而是平時多積累，有意識的去記憶，留下印象。內(nèi)容會包括計算機的特征（硬件和軟件）、網(wǎng)絡(luò)的特征和基本概念、信息的輸入輸出、信息的表示和處理、新興應(yīng)用等。另一部分是數(shù)學(xué)內(nèi)容，范圍很廣，永遠不知道會考到哪一部分的知識點，但試卷包括兩道數(shù)學(xué)題，所以不能忽視。比較重要的大概包括排列、組合、輾轉(zhuǎn)相除法、容斥原理等。還有數(shù)據(jù)結(jié)構(gòu)會考基本類型（整型、長整型、浮點型、字符等）和數(shù)組。比較容易在初賽中出現(xiàn)的數(shù)據(jù)類型有樹、棧、隊列等。

　　樹：二叉樹、完全樹等；棧：先進后出特點；隊列：先進先出特點。最后一部分是程序完成（也就是算法）。這部分完全是靠你的做題基礎(chǔ)，沒有捷徑，只能靠你平時多做題，掌握簡單算法。