信息學(xué)復(fù)賽備考總結(jié)課件

信息學(xué)復(fù)賽備考總結(jié)復(fù)賽注意事項1、認真審題，尤其要注意問題的規(guī)模（數(shù)據(jù)范圍），從某種意義上說，問題規(guī)模也暗示了你可能的算法。數(shù)據(jù)小，也許是搜索派上用場的時候；數(shù)據(jù)大了，可能只能考慮動態(tài)規(guī)劃，數(shù)學(xué)方法等高算法了。2、正確的估計題目的難度和自己的水平。拿到試題后先從總體上分析一下題目，做到心中有數(shù)！注意：題目的難易對所有人是公平的，只要最大限度地發(fā)揮自己的水平，不要有包袱，考出自己的最佳成績。3、正確地選擇題目去做（最擅長、最簡單的先完成），合理地安排時間和解題順序。4、復(fù)賽中：一定提高正確率！?。〗忸}速度是其次。

復(fù)賽考查的算法并不困難，建議大家：1）充分利用草稿紙，不要對自己的“心算能力”太自信！編程熟練的同學(xué)喜歡“一氣呵成”，拿到題目就開始編碼。我認為這樣不好，做信息學(xué)競賽題的思維過程是豐富而曲折多變的，考慮問題必須全面，僅憑一時的“感覺”來編程往往是漏洞百出。比如初學(xué)者常常忘記做一些初始化工作（遠不止變量賦初值這種最簡單的），即使有經(jīng)驗的同學(xué)也難免因一時疏忽寫出幾個錯誤的語句。最要命的是“第一感覺”的算法是錯誤的或者效率太低（命題者的陷阱），而程序編了大半才發(fā)現(xiàn)，時間浪費了不說，還影響了信心和發(fā)揮。題目名稱算法參考難度1997-c1數(shù)矩形數(shù)學(xué)（乘法原理）*1997-c2數(shù)字三角形窮舉*1997-c3數(shù)路徑遞推（迭代）+加法原理+高精度***1997-g1素數(shù)方陣遞歸回溯+構(gòu)造**1997-g2表達式判錯字符串+棧**1997-g3騎士游歷寬搜+遞推**1998-c11:2:3窮舉*1998-c2S!高精度*1998-c32的冪次方遞歸+二進制***1998-g1上下車問題遞推或者枚舉*1998-g2連接多位數(shù)貪心+字符串**1998-g3加法表遞歸+直接判斷***1999-c1Cantor表數(shù)學(xué)*1999-c2/g2回文數(shù)字符串**1999-c3/g3旅行家的預(yù)算貪心***1999-g1導(dǎo)彈攔截動態(tài)規(guī)劃、貪心**1999-g4郵票面值設(shè)計搜索+優(yōu)化***2000-c1計算器的改良字符串*2000-c2稅收與補貼問題數(shù)學(xué)或窮舉**2000-c3/g2乘積最大動態(tài)規(guī)劃+高精度***2000-c4/g3單詞接龍回溯**2000-g1進制轉(zhuǎn)換類比+窮舉**2000-g4方格取數(shù)動態(tài)規(guī)劃***2001-c1數(shù)的計數(shù)遞歸或遞推或動態(tài)規(guī)劃*2001-c2最大公約數(shù)與最小公倍數(shù)窮舉+優(yōu)化+乘法原理**2001-c3二*樹的先序序列遞歸或窮舉，構(gòu)造**2001-c4裝箱問題寬搜+hash表，或動態(tài)規(guī)劃***2001-g1一元三次方程求解窮舉或隨機化+迭代**2001-g2數(shù)的劃分遞推或動態(tài)規(guī)劃**2001-g3統(tǒng)計單詞個數(shù)貪心或隨機化或動態(tài)規(guī)劃***2001-g4Car的旅行路線圖論（Dijkstra算法）***2002-c1級數(shù)求和高精度*2002-c2選數(shù)搜索（遞歸）***2002-c3產(chǎn)生數(shù)乘法原理+圖論***2002-c4過河卒遞推+加法原理+高精度**2002-g1均分紙牌數(shù)學(xué)**2002-g2字串變換廣搜（雙向）+剪枝***2002-g3自由落體物理題**2002-g4矩形覆蓋搜索（全國沒有1人對）*****歸納：遞推、動態(tài)規(guī)劃、貪心、搜索、數(shù)學(xué)（物理）、圖論、高精度、回溯、窮舉、字符串網(wǎng)上總結(jié)的一些心得一、認真審題審題對于信息學(xué)競賽來說尤其重要。同一個題目如果數(shù)據(jù)限制差異大的話，可能難度差異也很不同。例如：輸入A,B,輸出A+B的值。如果題目說0<=A,B<=10000,這道題目無疑是一道很簡單的題目，但如果題目說0<=A,B<=10000000000000000000000000000000000000000000000顯然就要用到高精度數(shù)的處理了。從某種意義上說，數(shù)據(jù)限制也暗示了你可能的算法。數(shù)據(jù)小，也許是搜索派上用場的時候，數(shù)據(jù)大了，可能只能考慮動態(tài)規(guī)劃，數(shù)學(xué)方法等高效的算法了。

二、編碼和調(diào)試的能力去年復(fù)賽的時候，我身邊的那個選手，打鍵盤的聲音特別大，引得我轉(zhuǎn)過頭去看他。這時，我正在寫第一題，他已經(jīng)寫完開始調(diào)試了。我暗想，可能這是個極有競爭力的選手吧。當(dāng)我完成第三題是不由自主的又去看他，竟發(fā)現(xiàn)他還在調(diào)試第一題。如此調(diào)試能力，試問如何能得高分？復(fù)賽考查的算法并不困難，選手在實現(xiàn)上的問題往往還要大一些。建議大家：一，充分利用草稿紙，不要對自己的“心算能力”太自信了。編程熟練的同學(xué)喜歡“一氣呵成”，拿到題目就開始編碼。我認為這樣不好。做信息學(xué)競賽競賽題的思維過程是豐富而曲折多變的，考慮問題必須全面。僅憑一時的“感覺”來編程往往是漏洞百出。初學(xué)者常常忘記做一些初始化工作（遠不止變量賦初值這種最簡單的），即使有經(jīng)驗的同學(xué)也難免因一時疏忽寫出幾個錯誤的語句。最要命的是“第一感覺”的算法是錯誤的或者效率太低，而程序編了大半才發(fā)現(xiàn)...做一些復(fù)雜的題目（以前復(fù)賽的題目其實沒有特別復(fù)雜的，但今后可說不準），大多數(shù)人多會在一分心的時候突然短了思路，不知道下一步該寫什么了。3.評分的唯一標準是測試數(shù)據(jù)我不是鼓勵大家“投機取巧”，我的意思是，一道困難的題目如果無法下手，在時間允許的情況下一定要寫一個能解一些特殊情況的程序。例如去年分區(qū)聯(lián)賽《旅行家的預(yù)算》一題，無解的數(shù)據(jù)和沒有加油站的數(shù)據(jù)各一個，難道對于這兩個情況的程序你還不會編嗎？得一些分算一些嘛。還有“導(dǎo)彈追蹤”一題有一個數(shù)據(jù)是升序排列的，難道你不知道這種情況是一次只能打一個嗎？很多最優(yōu)化題目，不要一個字都不寫，根據(jù)你的“直覺”算法（例如貪心），雖然得不了滿分，也能得