信息學奧賽,你準備好了嗎?

編者按：新的一年，“高手論技”繼續伴隨大家前行，身處一線的你，就那些技術上最常遇到的故障、最需要解決的難題、最成熟的應用……都可以在此暢所欲言，各抒己見。是繼續圍觀還是現身說法，新浪微群http://q.t.sina.com.cn/264976，期待您的共同參與。

● 信息學奧賽的意義

全國青少年信息學奧林匹克聯賽和全國中學生生物學聯賽、全國中學生物理競賽、全國高中數學聯賽、全國高中學生化學競賽，被稱為國內影響力最大的“五大奧賽”。由于參加“五大奧賽”獲得省賽區一等獎的考生可以享受大學保送或加分資格，因此每年報考“五大奧賽”的考生總是樂此不疲，被稱為“小高考”。目前，教育部已經出臺政策，從2011年開始，入學的高中學生將取消奧賽省級一等獎保送和加分，奧賽的功利性將消失，回歸興趣和愛好。

信息學奧賽是“五大奧賽”中唯一非高考科目，雖然對高考沒有直接幫助，但參加奧賽學習，能達到使大多數青少年在智力上有所發展、在能力上有所提高的目標。CCF理事長李國杰院士在NOI2009開幕式和NOI25周年紀念會上曾講到：“給那些學有余力的中學生提供學習計算機科學的機會，提高他們的邏輯思維能力和用計算機解決問題的能力。競賽本質上是面向問題的算法設計和計算機編程，這就要求學生有分析問題和設計算法的能力，還要有通過編寫程序用計算機實現的能力。有了這種訓練，不管將來是否從事計算機專業工作，對學生都有好處?！?

計算機科學技術究竟是一門什么學問？計算機科學教給人們什么樣的思維？中學生參加信息學奧林匹克競賽究竟能增長什么能力？這些問題都值得我們深思。

● 讀名詞縮寫，了解信息學奧賽

CCF：中國計算機學會。這是我國信息學奧林匹克競賽的主辦者。

NOIP：全國青少年信息學奧林匹克分區聯賽。分為初賽和復賽兩部分，其中初中學生可以參加普及組的競賽，高中學生和初中學生都可以參加提高組的競賽。

NOI：全國青少年信息學奧林匹克競賽。這是全國決賽，每個省根據規則選派一定數量的選手參加，其中至少要有一名女選手。前20名選手獲得金牌，并進入國家集訓隊。

NOI冬令營：冬令營培訓內容包括授課、講座、討論、測試等。參加中國隊選拔賽隊員的成績將作為選拔賽成績的一部分記入檔案。

CTSC：中國代表隊選拔賽暨全國信息學精英賽。由國家集訓隊和其他80～100人參加，是中國代表隊人選決定的最重要比賽。

APIO：亞洲與太平洋地區信息學奧林匹克競賽。是一個面向亞太地區在校學生的信息學科競賽。旨在給青少年提供更多的賽事機會，推動亞太地區的信息學奧林匹克發展。該競賽性質為區域性的網上準同步賽，每年五月的第一或第二個星期六舉辦。

IOI：國際信息學(計算機)奧林匹克競賽。這是面向全球中學生的信息學頂級賽事，每個國家可以選派4名選手參加。

大多數省還會舉辦省隊選拔賽，以選拔參加NOI的省隊隊員。

其他競賽如Topcoder、百度之星、網易有道難題等是面向所有人的，獲獎者將獲得豐厚的獎金，中學生也可以參加。

● 信息學奧林匹克競賽形式與內容

從競賽形式上說，只有NOIP初賽采用筆試，題型分為選擇題（20分）、問題求解（10分）、讀程序寫結果（32分）、程序填空（38分）。選擇題和問題求解涉及計算機硬件、軟件、網絡基礎及數據結構與算法、組合數學等知識。

其他競賽都是上機編程，采用黑盒測試的方法評定成績。比如，NOIP復賽要在3小時內解決4道編程題，每道題在測試時有10個測試點（個別題會有更多），只要使用給定的輸入數據得出和輸出結果一致的，就能得到相應分數。當然，競賽的另一個特點是每道題都有時間限制和空間限制，大多數題要求在1秒之內得到結果，不同競賽對空間的要求會有差別，目前NOIP復賽每道題允許使用的空間是128MB。即使答案正確，如果超時或超空間，也會是0分。

信息學奧賽涉及的知識面非常廣泛，有些難度達到大學本科甚至研究生的課程。因為內容繁雜深奧，通常要經過四到五年的刻苦學習才能達到較高的水平。

● 如何評測你的程序

因為競賽基本上都是采用上機編程、黑盒測試的形式，那么平時如何評測學生的成績呢？我們可以為每道題編寫一個批處理文件，以此對程序的輸入輸出和標準輸入輸出相對比。這個方法比較原始，但在沒有評測軟件提供的環境下還是一個不錯的方法。平時練習時，我們可以使用Cena或清澄評測軟件評定學生成績。

Cena是開放源程序的信息學競賽評測系統，能滿足大多數的評測需求。它能通過局域網自動收取選手程序，但每臺學生機都必須安裝Cena客戶端，有一定的麻煩。我使用的方法是在教師機上安裝FTP軟件，學生通過FTP上傳相應的程序，然后在教師機上統一評測，以下是主要的操作步驟。

首先在教師機上安裝Cena。然后在某個分區，如D盤下建立一個文件夾專門存放測試程序，我將其命名為test。在test下再建一個文件夾，名為期末考查。打開Cena軟件，自動彈出“新建或打開”窗口。單擊“新建”頁，在“競賽標題”下輸入期末考查，然后在“保存在”下面選擇D盤下的“test\期末考查”文件夾，再按確定。在彈出的警告窗口中按“確定”。

現在在文件夾D:\test\期末考查下將自動建立兩個文件夾，其中data文件夾里面是放測試數據的，把期末考查用到的四道題復制到data文件夾下。另一個文件夾src是用來存放待測試程序的。打開FTP軟件，建立一個新的用戶，用戶目錄指向D:\test\期末考查\src，將權限設置為可讀可寫可修改可刪除。學生在做完題目以后，用這個用戶名把源程序上傳。按照NOIP復賽的要求，在src文件夾下先建立以學生名字命名的文件夾，然后以題目的英文名字為名在自己的文件夾下建立四個文件夾，分別把源程序放在這四個文件夾下。

回到Cena進行配置。單擊菜單“工具－選項”，在“選項”窗口中“默認內在限制”原來為2560KB，現在NOIP復賽的空間限制為128MB，我們可以把值修改一下。值修改完后將在以后所有的考試中起作用。

在Cena主窗口中單擊“試題”頁，在“綱要”下右擊，選“添加試題”。比如，第一題文件名為music，則在試題標題后輸入music，源文件后輸入“music\music”。注意文件名后面一定不能添加擴展名，否則將出現錯誤。如果源程序是放在自己的根目錄下，那么在源文件里只要輸入music就可以了?！拜斎胛募焙竺孑斎腩}目中要求使用的名字，一般是題目名.in，如這里是music.in，輸出文件則為music.out。一般的題目不用改動比較方式。

添加完題目以后，再在試題1下右擊，選“添加測試點”。在右邊的窗口輸入文件后單擊，如果data下相應題目的測試數據所建文件夾和題目的名字是相同的，將會自動列出來。我們選擇序號最小的一個輸入文件，如music0.in，輸出文件位置選擇“music0.out”。我們還可以對這道題的分值、時間限制、內存限制進行修改。再在“試題1”下右擊，選“添加其他測試點”，軟件將自動按序號把其他測試點添加上去。

用同樣的方法把其他三道題添加進來，單擊“選手”頁，按“全部評測”按鈕，軟件將對已經上交的程序進行評測，給出最后的得分和用時等信息。在“統計與分析”頁，可以對某些題或某些選手的做題情況進行分析。

要注意的是，NOIP復賽提高組必須經過CCF最終評測，這個評測是在Linux下用北京航天航空大學編寫的評測軟件完成的，與在Windows下評測的結果可能會出現一些差異，特別是Linux下文件名大小寫是敏感的，大家一定要注意。另外，NOIP提高組復賽CCF推薦在Linux下進行，有部分省市已經開始實施了，而NOI是必須在Linux下進行的，所以參加競賽的選手要預先熟悉Linux環境。

● 語言的選擇

競賽規定可以使用Pascal、C、C++三門語言。在如何選擇語言方面，許多人都很糾結。每種語言都有自己的優劣，我們只針對競賽中語言的特點進行一些分析。

1.語言特點

Pascal具有嚴格的結構化形式、豐富完備的數據類型、運行效率高、查錯能力強等特點，可以方便用于描述各種算法和數據結構。對于程序設計的初學者，Pascal語言有益于培養良好的程序設計風格和習慣。C語言的優點是簡潔、緊湊、使用方便、靈活、易于學習和應用，程序的書寫形式也很自由，適合初學者使用。C語言的弱點也很明顯：非強制類型；語法限制不嚴格，使得編程者無法過多地依賴C編譯程序去查錯；缺少實時檢查，如數組越界等。因為C++是C的擴展，所以也具有C的特點。C++在C的基礎上，加入了面向對象編程思想。

2.參考資料

需要大量的參考資料，也是奧賽學習的一個特點。因為Pascal在競賽中使用的時間更長，市面上可以買到的參考書大多以Pascal或類Pascal寫成。當然，現在的一個趨勢是用C/C++寫的參考書越來越多，網絡上各大題庫的題解以C++占絕對主流。

3.運行速度

對于三門語言的運行速度，到底誰最快？筆者分別以三門語言計算一千萬次加法，以cena反復測試，結果基本穩定如圖1。一千萬次除法（整除）的評測結果如圖2。在上兩次的測試中，Pascal的劣勢就比較明顯了。再來看看一千萬次求模運算，C/C++和Pascal的差異更加明顯了（如圖3）。

雖然對浮點數運算、邏輯運算、指針運算等沒有繼續進行全面測試，但基本上可以得出如下結論：C++和C語言的速度基本上處于同一級別；而C/C++和Pascal相比，確實在運行速度上有一定優勢。當然，從出題時通常以標程的1/10作為時間限制的角度來說，只要算法一致，C/C++能在規定時間內出解，Pascal也是可以的，在這方面大家不用過于擔心。只有當三者算法都不是最優，解題時間接近時間限制時，C/C++可能會顯示出它一定的優勢。

要注意的是，不同硬件配置的機器，運行同一程序所用的時間是不同的。同一臺機器多次測試同一程序，運行時間也會略有差異。但它們三者的相對關系是基本不變的。

4.其他方面

C/C++語言簡約，同樣的程序，它們比Pascal要少打不少字母和符號。C++在競賽中可以使用STL中的模板，其中含有大量比較實用的函數，在競賽時使用可以提高程序的正確性和速度。

從近幾年NOIP的報名情況來看，使用Pascal的還是占絕大多數，但C++語言的使用者在逐漸增多。如果只從競賽的角度來看，C++有一定優勢。個人建議，對小學高年級、初中低年級的入門者來說，最好選擇Pascal；對初中高年級和高中學生來說，可以選擇C++；特別是進入大學以后，如果參加ACM/ICPC，那么只能使用C/C++/Java語言，學習Pascal的學生要在適當的時候轉學另外的語言。

信息學奧林匹克，教給學生的不僅僅是一種語言、幾種算法，競賽對學生的學習方法、思維能力、性格培養等方面的影響是非常深刻的。對愛好計算機而又學有余力的學生，信息學奧賽將展現出一個精彩的世界。