信息學(xué)奧賽教程指導(dǎo)

1、信息學(xué)奧賽教程指導(dǎo)第1頁，共227頁，2022年，5月20日，16點36分，星期一6、2002、2003年分區(qū)聯(lián)賽復(fù)賽試題解析1、高精度運算2、圖的運算3、搜索算法4、構(gòu)造算法5、動態(tài)程序設(shè)計第2頁，共227頁，2022年，5月20日，16點36分，星期一2002、2003年全國分區(qū)聯(lián)賽復(fù)賽試題解析 第3頁，共227頁，2022年，5月20日，16點36分，星期一題 型題 目與課內(nèi)知識相關(guān)自由落體、級數(shù)求和、乒乓球、麥森數(shù) 字符串處理字符近似查找貪心法均分紙牌、傳染病控制 回溯法選數(shù)、字串變換、棧、神經(jīng)網(wǎng)絡(luò)、偵探推理 動態(tài)程序設(shè)計方法過河卒、數(shù)字游戲、加分二叉樹 幾何計算矩形覆蓋 雖然2002

2、、2003年全國奧林匹克信息學(xué)復(fù)賽中含許多可“一題多解” 的試題，但如果按照較優(yōu)算法標(biāo)準(zhǔn)分類的話，大致可分為 第4頁，共227頁，2022年，5月20日，16點36分，星期一特 點 1、凸現(xiàn)信息學(xué)知識和學(xué)科知識整合的趨勢。為了考核學(xué)生運用學(xué)科知識的能力，激發(fā)學(xué)生的創(chuàng)造力，2002、2003年全國奧林匹克信息聯(lián)賽(NOIP)中學(xué)科類的試題增加，并且首次出現(xiàn)了計算幾何類的試題(矩形覆蓋)。這說明信息學(xué)與學(xué)科的依賴關(guān)系日益凸現(xiàn)，學(xué)科基礎(chǔ)好、尤其是數(shù)學(xué)素質(zhì)好的人雖然不一定會編程，但希望學(xué)習(xí)編程的人愈來愈多；編程解題能力強的人勢必有數(shù)學(xué)的潛質(zhì)和愛好，他們中愈來愈多的人也希望深造數(shù)學(xué)。各門學(xué)科的交融和整合

3、是奧林匹克信息學(xué)聯(lián)賽活動發(fā)展的一個大趨勢（按照2005年國家教改方案，數(shù)學(xué)教材增加算法內(nèi)容，信息科技教材摻入語言知識）。2、“構(gòu)造法” 或貪心策略類試題的引入，使得算法知識的不確定性和不穩(wěn)定性增加。這正體現(xiàn)了科學(xué)的本質(zhì)知識是不斷推陳出新的。第5頁，共227頁，2022年，5月20日，16點36分，星期一3、試題的綜合性增加，并不一定隨知識的分類而發(fā)生變化，有時幾乎找不到一個單一的經(jīng)典算法(字串變換回溯法中有字符串處理)，也找不到一個純粹的數(shù)據(jù)結(jié)構(gòu)問題（級數(shù)求和需要為表達(dá)式的計算結(jié)果設(shè)計合適的數(shù)據(jù)類型），關(guān)鍵是你從哪個角度去分析，也就是說能不能綜合所學(xué)的知識，應(yīng)用自如地解決問題。選手的綜合素質(zhì)愈

4、高，得勝的機率愈大； 4、經(jīng)常面對著不知道算法的試題，面對著誰都不知如何處置的情境（經(jīng)常出現(xiàn)許多選手在一題中得0分、優(yōu)秀選手表現(xiàn)失常的情況），因此必須使學(xué)生正確地理解問題、深入問題的空間并形成解決問題的意識、習(xí)慣和能力。能不能創(chuàng)造性地應(yīng)答沒有遇到過的挑戰(zhàn)，成為培訓(xùn)的基本要求和目標(biāo)。第6頁，共227頁，2022年，5月20日，16點36分，星期一 1、培養(yǎng)問題意識和問題能力。創(chuàng)造始于問題?！坝辛藛栴}才會思考，有了思考才有解決問題的方法，才有找到獨立思路的可能（陶行知）”。有問題雖然不一定有創(chuàng)造，但沒有問題一定沒有創(chuàng)造（想一想當(dāng)前的解法有沒有缺陷，有沒有更好的算法，它與哪些問題有聯(lián)系，與哪些知識相

5、關(guān)聯(lián)，還可以拓延出哪些問題，要解決這些問題還需要哪些知識）；啟 示2、處理好前沿性與基礎(chǔ)性、直線培訓(xùn)和散點培訓(xùn)、循序漸進(jìn)與跳躍式的矛盾。如果恪守按部就班的培訓(xùn)程序，不謀求跳躍式學(xué)習(xí)，將離全國和國際奧林匹克信息學(xué)活動的前沿、離世界程序設(shè)計知識的前沿愈來愈遠(yuǎn)。因此在進(jìn)行基礎(chǔ)課程學(xué)習(xí)的同時，必須有追逐前沿的選擇性學(xué)習(xí)。這里，有時候心理的障礙比科學(xué)上的障礙更難跨越，敢不敢的問題比能不能的問題更突出。其實在學(xué)習(xí)中或多或少地都有必要的跳躍，不少人還能夠?qū)崿F(xiàn)比較大的跳躍（ 愛笛生小學(xué)三年級退學(xué)、比爾.蓋茨大學(xué)三年級退學(xué)）第7頁，共227頁，2022年，5月20日，16點36分，星期一學(xué)生必須學(xué)會從浩如煙海的

6、信息中選擇最有價值的知識，構(gòu)建個性化（符合自己能力結(jié)構(gòu)和興趣結(jié)構(gòu)）和競爭需要的知識結(jié)構(gòu)培訓(xùn)內(nèi)容要有選擇性，因為除了出題者，誰也說不清楚在未來競賽中究竟什么知識是必要的（對基礎(chǔ)的理解是主觀的選擇。例如中國、美國和俄羅斯的理科教材大不相同，有的同年級同學(xué)科的教材相差三分之二），因此不可能把所有重要的東西都選擇好了給學(xué)生，而是應(yīng)該將直線培訓(xùn)與散點培訓(xùn)相結(jié)合，選擇部分重要的東西交給學(xué)生，讓他們自己去探索若干知識點之間的聯(lián)系，補充自己認(rèn)為需要補充的知識。 3、參與活動的學(xué)生應(yīng)由競爭關(guān)系和獨立關(guān)系（你做你的，我干我的，程序和算法互相保密，彼此津津樂道于對方的失敗和自己的成功）轉(zhuǎn)向合作學(xué)習(xí)的關(guān)系（通過研討算

7、法、集中編程、互測數(shù)據(jù)等互相合作的方式完成學(xué)習(xí)任務(wù)）第8頁，共227頁，2022年，5月20日，16點36分，星期一學(xué)生的心理調(diào)適：我掌握的知識僅不過是滄海一粟(進(jìn)取心)；固守錯誤的概念比一無所知更可怕（明智）；三人之行必有我?guī)煟ㄖt虛）；知識生產(chǎn)社會化條件下人的基本素質(zhì)之一是合作精神（現(xiàn)在的重大科學(xué)發(fā)明需要成百上千科學(xué)家進(jìn)行長期甚至跨國的合作，例如制作windows，人類基因工程）（現(xiàn)代意識）；前提條件：水平相當(dāng)?shù)耐|(zhì)成員或各有所長（包括數(shù)學(xué)知識、編程能力和思維方式等解題所需的各種因素）的異質(zhì)成員是開展合作學(xué)習(xí)的組織基礎(chǔ)；合作學(xué)習(xí)的效應(yīng)：集思廣益容易出好的算法；群體設(shè)計的測試數(shù)據(jù)相對全面；在群

8、體活動中能比較客觀的反映自己能力情況；每個學(xué)生在付出與給予中可提高合作精神和編程能力，成功者往往是那些相容性好、 樂于幫助他人，并且善于取他人之長的學(xué)生（符文杰、張一飛等）。第9頁，共227頁，2022年，5月20日，16點36分，星期一4、選手面對從未遇到過的挑戰(zhàn)應(yīng)調(diào)整好心態(tài)，不要急功近利，要只管耕耘、不問收獲、潛心鉆研、其樂無窮。那怕是一兩次失誤，也是砥礪之石，可從中汲取有益的經(jīng)驗和教訓(xùn)?！安皇且环畯毓?，哪得梅花撲鼻香”。第10頁，共227頁，2022年，5月20日，16點36分，星期一題5、均分紙牌題6、字串變換題7、自由落體題8、 矩形覆蓋題 1、字符近似查找題2、級數(shù)求和題3、選數(shù)

9、題4、過河卒9、乒乓球 10、數(shù)字游戲 11、棧 12、麥森數(shù) 13、神經(jīng)網(wǎng)絡(luò) 14、偵探推理 15、加分二叉樹 16、傳染病控制 第11頁，共227頁，2022年，5月20日，16點36分，星期一第一題：字符近似查找設(shè)有n個單詞的字典表（1n100）。計算某單詞在字典表中的四種匹配情況（字典表中的單詞和待匹配單詞的長度上限為255）： i：該單詞在字典表中的序號； Ei：在字典表中僅有一個字符不匹配的單詞序號； Fi：在字典表中多或少一個字符（其余字符匹配）的單詞序號； N：其他情況 當(dāng)查找時有多個單詞符合條件，僅要求第一個單詞的序號即可。輸入文件 輸入文件名為a.in，文件的格式如下： n

10、（字典表的單詞數(shù)） n行，每行一個單詞 待匹配單詞第12頁，共227頁，2022年，5月20日，16點36分，星期一輸出文件 輸出文件名a.out，格式如下： i Ei Fi其中i為字典表中符合條件的單詞序號（1in），若字典表中不存在符合條件的單詞，則對應(yīng)的i=0。若上述三種情況不存在，則輸出N。輸入輸出樣例輸入1:5abcdeabcasdfasfdabcdaacdabcd輸出1:4E5F1輸入2:1ab輸出2:0E0F0N第13頁，共227頁，2022年，5月20日，16點36分，星期一我們將字典表中的單詞分成3類： 第1類：單詞與待匹配單詞多或少一個字符，其余字符匹配； 第2類：單詞僅有

11、一個字符與待匹配單詞不匹配； 第3類：單詞與待匹配單詞完全匹配；設(shè)constnote :array1.3 of string=(F,E,)； 匹配情況的標(biāo)志var want:string； 待匹配單詞list:array1.100 of string； 字典表。其中l(wèi)isti為字典ians ：array1.100 of integer；單詞的類別序列。其中ansi= 第14頁，共227頁，2022年，5月20日，16點36分，星期一1、匹配情況的計算計算兩個等長字串中不同字符的個數(shù)function find(a,b:string):integer；輸入兩個等長字串a(chǎn),b，計算和返回不同字符的個

12、數(shù)vari,tot:integer；begintot0；for i1 to length(a) do if aibi then inc(tot)；findtot；end； find 第15頁，共227頁，2022年，5月20日，16點36分，星期一判別一個字串是否比另一個字串多一個字符（其余字符匹配）我們不知道長度大1的字串究竟在哪個位置上多出一個字符，無奈，只能將該字串的每一個字符試插在另一個字串的對應(yīng)位置上。如果插入后使得兩串相同，則說明猜想成立。否則猜想不成立。function check(a,b:string):integer；輸入字串a(chǎn),b。若b能夠在a的基礎(chǔ)上添加一個字符得到的話，

13、則返回1；否則返回0vari:integer；begincheck0；for i0 to length(a) do begin acopy(a,1,i)+bi+1+copy(a,i+1,255)；在ai后插入bi+1if a=b 若插入后兩串相同，則成功退出then begin check1；exit；end；thendelete(a,i+1,1)； 刪去a中的插入字符end；forend；check第16頁，共227頁，2022年，5月20日，16點36分，星期一2、計算字典表中的每一類單詞首先，我們依次計算每一個單詞的類別序號在單詞i與待匹配單詞等長的情況下，若兩串相同，則單詞i的類別記為

14、3；若兩串僅有一個字符不同，則單詞i的類別記為2；若單詞i比待匹配單詞多或少一個字符（其余字符匹配），則單詞i的類別記為1；否則單詞i的類別記為0；然后根據(jù)ans序列在字典表中依次搜索類別3類別1的單詞，輸出對應(yīng)的單詞序號。如果在字典表中不存在上述3種類別的單詞，則輸出N。fillchar(ans,sizeof(ans),0)； 單詞的類別序列初始化for i1 to n do begin 對字典中的每個單詞進(jìn)行分類 if length(listi)=length(want) 若單詞i與待匹配單詞等長 then begin kfind(listi,want)；計算單詞i與待匹配單詞的不同字符個

15、數(shù) if k=0 then ansi 3； 記下類別序號 if k=1 then ansi 2； end；then第17頁，共227頁，2022年，5月20日，16點36分，星期一若單詞i比待匹配單詞多或少一個字符（其余字符匹配），則單詞i的類別記為1；否則單詞i的類別記為0 if length(listi)+1=length(want) then ansi check(listi,want)； if length(listi)=length(want)+1 then ansi check(want,listi)；end；forhavefalse； 匹配情況存在的標(biāo)志初始化for i3 dow

16、nto 1 do begin 依次輸出每一類別的單詞在字典表最先出現(xiàn)的序號 k0； for j1 to n do if ansj=i then begin kj；break；end；thenhavehave or (k0)；writeln(notei,k)；end；for第18頁，共227頁，2022年，5月20日，16點36分，星期一 第二題：級數(shù)求和 已知：Sn=1+1/2+1/3+.+1/n。顯然當(dāng)n.非常大的時候，Sn可大于任何一個整數(shù)K。現(xiàn)給出一個整數(shù)K（1K15），要求計算出一個最小的n，使得SnK。輸入 鍵盤輸入k輸出 屏幕輸出n輸入輸出樣例輸入:1輸出:2第19頁，共227頁，

17、2022年，5月20日，16點36分，星期一算法分析 該題考核選手的并不是編程能力，而是選擇變量類型的能力。由于該數(shù)列是遞減的，而k的上限為15，因此項數(shù)很大，即便是longint也容納不下。但未必非高精度運算不可。只要啟動浮點數(shù)運算（$n+），將項數(shù)設(shè)為extended類型，便可以得出正確解。$n+ 啟動浮點數(shù)運算vars,b,k:extended； 數(shù)列的和、項數(shù)、最接近sn(大于sn)的整數(shù)值begins0； 數(shù)列的和初始化b0； 項數(shù)初始化readln(k)； 讀最接近sn(大于sn)的整數(shù)值kwhile s=k do 若目前數(shù)列的和小于k，則項數(shù)b+1，計算sb beginbb+1；

18、ss+1/b； end；while 輸出項數(shù)round(b)；end.main第20頁，共227頁，2022年，5月20日，16點36分，星期一第三題：選數(shù) 已知n個整數(shù) x1,x2,.xn, 以及一個整數(shù)k (kn)。從 n 個整數(shù)中任選k個整數(shù)組合相加，可分別得到一系列的和。例如當(dāng) n=4, k=3，4個整數(shù)分別為3，7，12，19 時，可得全部的組合為： 3+7+12=22 3+7+19=29 7+12+19=38 3+12+19=34。 現(xiàn)在，要求你計算出和為素數(shù)的組合數(shù)有多少種。例如上例，只有一種組合的和為素數(shù)：（3+7+19=29）。第21頁，共227頁，2022年，5月20日，1

19、6點36分，星期一輸入 輸入文件名為c.in。文件格式n, k（1n20，ka，則說明a不可能分解出比primei大的素數(shù)了，a本身為素數(shù)。由于primei表的最大素數(shù)接近10000，其平方遠(yuǎn)大于xi的上限5000000，因此是一個比較可行的方法：function check(a:longint):boolean； 判斷a是否是素數(shù)beginchecktrue； 素數(shù)標(biāo)志初始化for i1 to tot do begin 搜索素數(shù)表 if primei*primeia then exit；若超出搜索范圍的上限，則說明a是素數(shù)，返回true if a mod primei=0 then begi

20、n checkfalse；exit；end；thenend；forend； check 第24頁，共227頁，2022年，5月20日，16點36分，星期一2、遞歸搜索方案數(shù) 由于數(shù)列是隨機和無序的，因此只能通過搜索的辦法求解。設(shè) 狀態(tài)(left,now,all)：目前組合為all，還需要從xnowxn中選出left個數(shù)； 約束條件(leftn-now+1)：xnowxn中數(shù)的個數(shù)大于等于left； 邊界條件（(left=0) and (now=n+1)）和目標(biāo)狀態(tài)（check(all)=true）：從x1xn中選出k個數(shù)為邊界。在這種情況下，若k個數(shù)的和為素數(shù)，則滿足條件的種數(shù)+1。到達(dá)邊界后

21、，應(yīng)回溯； 搜索范圍為兩種選擇： 當(dāng)前組合不選xnow,遞歸計算子狀態(tài)(left,now+1,all)； 在還有數(shù)需要選的情況下（left0），xnow選入組合，遞歸計算子狀態(tài)(left-1,now+1,all+listnow)；由此得出子程序第25頁，共227頁，2022年，5月20日，16點36分，星期一Procedure solve(left,now,all:longint)；遞歸計算選數(shù)情況beginif (leftn-now+1)then exit；若xnowxn中不足left個數(shù)，則回溯 if (left=0) and (now=n+1) 若從x1xn中選出了k個數(shù) then be

22、gin if check(all) then inc(ans)；若k個數(shù)的和為素數(shù)，則滿足條件的種數(shù)+1 exit； 回溯 end；then solve(left,now+1,all)；當(dāng)前組合不選xnow,遞歸計算子狀態(tài)if left0 在還有數(shù)需要選的情況下，xnow選入組合，遞歸計算子狀態(tài) then solve(left-1,now+1,all+listnow)；end； solve顯然，遞歸調(diào)用solve(k,1,0)后得出的ans即為問題的解。第26頁，共227頁，2022年，5月20日，16點36分，星期一過河卒如圖，A點有一個過河卒，需要走到目標(biāo)B點。卒行走的規(guī)則：可以向下、或者

23、向右。第27頁，共227頁，2022年，5月20日，16點36分，星期一 同時在棋盤上的任一點有一個對方的馬（如上圖的C點）,該馬所在的點和所有跳躍一步可達(dá)的點稱為對方馬的控制點。例如上圖C點上的馬可以控制8個點（圖中的P1，P2.P8）。卒不能通過對方馬的控制點。 棋盤用坐標(biāo)表示，A點（0，0）、B點（n，m）(n,m為不超過20的整數(shù),并由鍵盤輸入)，同樣馬的位置坐標(biāo)是需要給出的（約定：CA，同時CB）?，F(xiàn)在要求你計算出卒從A 點能夠到達(dá)B點的路徑的條數(shù)。輸 入： 鍵盤輸入B點的坐標(biāo)(n,m)以及對方馬的坐標(biāo)（X，Y）輸 出： 屏幕輸出一個整數(shù)（路徑的條數(shù)）。輸入輸出樣例： 輸入：3 3

24、2 2 輸出：0第28頁，共227頁，2022年，5月20日，16點36分，星期一1、計算對方馬的控制點 按照題意，對方的馬所在的點和所有跳躍一步可達(dá)的點稱為對方馬的控制點，卒不能通過對方馬的控制點。在卒出發(fā)之前，必須計算對方馬的所有控制點。顯然，若（0，0）或（n,m）為控制點，則輸出路徑數(shù)為0。設(shè)const move:array1.8,1.2ofinteger=(1,-2),(1,2),(2,1),(2,-1),(-1,2),(-1,-2),(-2,1),(-2,-1)； movek，1.2為馬沿k方向跳躍一步的水平增量和垂直增量var list:array-1.20,-1.20 of c

25、omp；路徑數(shù)序列，其中l(wèi)isti,j為卒從(0,0)到(i,j)的路徑數(shù) can:array0.20,0.20 of boolean； 點(i,j)允許卒通行的標(biāo)志馬的初始位置為（x,y）。我們按照下述方式計算can序列：canx,y false； 對方馬所在的點為控制點for i1 to 8 do begin從（x，y）出發(fā)，沿8個跳馬方向計算控制點 jx+movei,1； 計算i方向的跳馬位置(j，k) ky+movei,2； if (j=0) and (k=0) and (j=n) and (k=m) 若（j,k）在界內(nèi)，則為控制點 then canj,k false；end；fori

26、f (not can0,0)or(not cann,m) 若卒的起點和終點為控制點，則輸出路徑數(shù)0 then writeln(0) else begin 計算和輸出卒從（0，0）走到（n,m）點的路徑數(shù)listn,m；end；else第29頁，共227頁，2022年，5月20日，16點36分，星期一2、計算和輸出卒從（0，0）走到（n,m）點的路徑條數(shù) 我們按照由上而下、由左而右的順序，將卒可能到達(dá)的每一個位置（i,j）(0in，0jm)設(shè)為階段,顯然這樣做，可以取消對狀態(tài)的枚舉。 首先，將卒的出發(fā)點（0，0）的路徑數(shù)設(shè)為1（list0,01），并將該位置設(shè)為控制點（can0,0 fals）。

27、然后從（0，0）出發(fā)，按照由上而下、由左而右的順序計算卒經(jīng)過每一個可行點的路徑數(shù)。若（i，j）為可行點，則卒可由上側(cè)的（i-1,j）和左側(cè)的（i,j-1）進(jìn)入該點。將這兩點的路徑數(shù)加起來，即為從（0，0）走到（i，j ）的路徑數(shù)，即 listi,j=listi-1,j+listi,j-1（i，j）非控制點依次類推，最后得出的listn,m即為問題的解。由此得出算法： fillchar(list,sizeof(list),0)； 路徑數(shù)序列初始化 list0,01；卒從（0，0）出發(fā)的路徑數(shù)為1，該位置不再允許卒通行 can0,0 false； for i0 to n do對于每個可行點,小兵要

28、么從左側(cè)、要么從上方走到,由此計算從(0,0)到(i,j)的路徑數(shù) for j0 to m do if cani,j then listi,jlisti-1,j+listi,j-1；輸出卒從（0，0）走到（n,m）點的路徑條數(shù)listn,m；第30頁，共227頁，2022年，5月20日，16點36分，星期一題一 均分紙牌問題描述 有N堆紙牌，編號分別為1，2，.N。每堆上有若干張， 但紙牌總數(shù)必為N的倍數(shù)?？梢栽谌我欢焉先∪舾蓮埣埮疲缓笠苿?。移牌規(guī)則為：在編號為1堆上取的紙牌，只能移到編號為2的堆上；在編號為N的堆上取的紙牌，只能移到編號為N-1的堆上；其他堆上取的紙牌，可以移到相鄰左邊或右

29、邊的堆上?，F(xiàn)在要求找出一種移動方法，用最少的移動次數(shù)使每堆上紙牌數(shù)都一樣多。例如N=4，4堆紙牌數(shù)分別為： 9 8 17 6移動3次可達(dá)到目的：從取4張牌放到（9 8 13 10）從取3張牌放到（9 11 10 10）從取1張牌放到（10 10 10 10）。 輸 入 ： N （ N 堆紙牌，1N100） A1，A2，.An (N 堆紙牌，每堆紙牌初始數(shù)，1Ai10000) 輸 出 ：所有堆均達(dá)到相等時的最少移動次數(shù)。輸入輸出樣例第31頁，共227頁，2022年，5月20日，16點36分，星期一輸入： 4 9 8 17 6 輸出： 3設(shè)list為紙牌序列，其中l(wèi)isti為第i堆紙牌的張數(shù)（1i

30、n），ave為均分后每堆紙牌的張數(shù)，即 ；ans為最少移動次數(shù)。我們按照由左而右的順序移動紙牌。若第i堆紙牌的張數(shù)listi超出平均值，則移動一次(ans+1)，將超出部分留給下一堆，既第i+1堆紙牌的張數(shù)增加listi-ave；若第i堆紙牌的張數(shù)listi少于平均值，則移動一次(ans+1)，由下一堆補充不足部分，既第i+1堆紙牌的張數(shù)減少ave-listi； 右鄰堆取的牌第32頁，共227頁，2022年，5月20日，16點36分，星期一問題是，在從第i+1堆中取出紙牌補充第i堆的過程中，可能會出現(xiàn)第i+1堆的紙牌數(shù)小于零(listi+1-(ave-listi)xu ud-yy-yzA.ou

31、t文件： 3第35頁，共227頁，2022年，5月20日，16點36分，星期一1、分析變換規(guī)則設(shè)規(guī)則序列為rule，其中第i條規(guī)則為rulei，1rulei，2；當(dāng)前串為now，其中tmp為now的一個待匹配子串。由于匹配過程的由左而右進(jìn)行的，因此設(shè)j為now的指針，即從now的第j個字符開始匹配rulei,1。now適用第i條規(guī)則的條件是now中的子串被第i條規(guī)則替換后的長度小于255，即 length(now)+length(rulei,2)-length(rulei,1)255rulei,1是now的一個子串（k=pos(rulei,1,tmp)0）在使用了第i條規(guī)則后，now變換為no

32、w= copy(now,1,j+k-1)+rulei,2+copy(now,j+k+length(rulei,1),255)由于now中可能有多個子串被第i條規(guī)則替換，因此每替換一次后，為了方便地找出下一個替換位置，我們將當(dāng)前被替換串前（包括被替換串）的子串刪除。 第36頁，共227頁，2022年，5月20日，16點36分，星期一2、使用回溯法計算最少替換次數(shù)由于原串a(chǎn)、目標(biāo)串b和規(guī)則rule是隨機輸入的，因此不可能找出直接計算最少替換次數(shù)best的數(shù)學(xué)規(guī)律，只能采用回溯搜索的辦法。設(shè) 狀態(tài)（need,now）:替換次數(shù)為need，替換結(jié)果為now； 邊界條件（needbest）和目標(biāo)狀態(tài)（n

33、ow=b）：替換次數(shù)達(dá)到或超過目前得出的最小值為邊界；已經(jīng)替換出目標(biāo)串為目標(biāo)狀態(tài)； 搜索范圍i：嘗試每一條規(guī)則,即1i規(guī)則數(shù)n；約束條件（length(now)+length(rulei,2)-length(rulei,1)255）：now中的子串被第i條規(guī)則替換后的長度小于255；由此得出計算過程： 第37頁，共227頁，2022年，5月20日，16點36分，星期一procedure solve(need；now)；從當(dāng)前串now出發(fā)，遞歸第need次替換vari,k,j:integer；tmp:string；beginif need=best then exit； 若到達(dá)邊界，則回溯if

34、now=b then begin若達(dá)到目標(biāo)狀態(tài)，則記下替換次數(shù)，并回溯 bestneed； exit； end；thenfor i1 to n do 搜索每一條規(guī)則 第38頁，共227頁，2022年，5月20日，16點36分，星期一if length(now)+length(rulei,2)-length(rulei,1)0 do 反復(fù)在tmp 中尋找子串rulei,1 begin solve(need+1，copy(now,1,j+k-1)+rulei,2+copy(now，j+k+length(rulei，1)，255)； 遞歸下一次替換 delete(tmp,1,k)；將當(dāng)前被替換串前（

35、包括被替換串）的子串刪除 jj+k； 右移匹配指針 kpos(rulei,1,tmp)； 繼續(xù)嘗試第i條規(guī)則 end；while end；thenend； solve 第39頁，共227頁，2022年，5月20日，16點36分，星期一由此得出主程序：讀入初始串a(chǎn)和目標(biāo)串；讀入替換規(guī)則rule；best31； 設(shè)定替換次數(shù)的上限solve(0,a)； 回溯搜索最少的替換次數(shù)if best=30 輸出最少替換次數(shù) then writeln(best) else writeln(ERROR!)；、第40頁，共227頁，2022年，5月20日，16點36分，星期一題三 自由落體問題描述: 在高為H 的

36、天花板上有n個小球，體積不計，位置分別為0，1，2，n-1。在地面上有一個小車(長為L，高為K，距原點距離為S1)。已知小球下落距離計算公式為 S=1/2*g*t2，其中 g=10， t為下落時間。地面上的小車以速度 V 前進(jìn)。如下圖： 小車與所有小球同時開始運動，當(dāng)小球距小車的距離0.00001時，即認(rèn)為小球被小車接受（小球落到地面后不能被接受）。請你計算出小車能接受到多少個小球。輸入：H，S1，v，L，k，n （1H，S1，v，L，k，n100000）輸出：小車能接受到的小球個數(shù)。 這是分區(qū)聯(lián)賽最容易失誤的一道試題，關(guān)鍵是弄清小車行程的物理意義和計算的精度誤差！第41頁，共227頁，202

37、2年，5月20日，16點36分，星期一算法分析由題意可知，車頂與天花板的距離為h-k，小球由天花板落至車頂所花費的時間為t1= ，由天花板落至地面的時間為t2= 。小車與所有小球同時開始運動，當(dāng)小球距小車的距離0.00001時，即認(rèn)為小球被小車接受（小球落到地面后不能被接受）。顯然，若n1n2，則小車接受的小球數(shù)為n1-n2+1；否則小車未接受任何一個小球。 小車在行駛了t1*v-0.00001路程后接受了第一個小球，其編號為n1=minn-1, 小車在行駛了t2*v+0.00001路程后小球落地，小車接受最后一個小球的編號為n2=max0， 。為什么在n1的公式中加上L？為什么在n2的公式中

38、加上0.5？為什么n1取下整、n2取上整？第42頁，共227頁，2022年，5月20日，16點36分，星期一矩形覆蓋問題描述：在平面上有n個點 (n100)，每個點用一對整數(shù)坐標(biāo)表示。例如：當(dāng)n=4 時，4 個點的坐標(biāo)分別為： p1(1，1)， p2(2，2)， p3 (6，3)， p4(7，0)這些點可以用 k 個矩形( k4) 全部覆蓋，矩形的邊平行于坐標(biāo)軸。如圖一，當(dāng) k=2時，可用如圖二的兩個矩形s1，s2覆蓋， s1，s2面積和為4。問題是當(dāng) n個點坐標(biāo)和 k 給出后，怎樣才能使得覆蓋所有點的k個矩形的面積之和為最小呢。約定： 覆蓋一個點的矩形面積為0；覆蓋平行于坐標(biāo)軸直線上點的矩形

39、面積也為0；各個矩形間必須完全分開（邊線也不能重合）；本試題是高中組復(fù)賽中最難的一道試題，對選手的幾何基礎(chǔ)和編程能力是一個比較嚴(yán)峻的考驗。 第43頁，共227頁，2022年，5月20日，16點36分，星期一算法分析 1、點和矩形的描述和關(guān)系 平面上的點由坐標(biāo)（x,y）表示。由于計算過程是按照由下而上、由左而右進(jìn)行的，因此我們按照x坐標(biāo)遞增的順序和y坐標(biāo)遞增的順序?qū)個點存入a序列。矩形由2條平行于x軸的邊界線和2條平行于y軸的邊界線圍成。為了計算最小矩形的方便，我們將空矩形的左邊界設(shè)為、右邊界為設(shè)-、下邊界設(shè)為、上邊界設(shè)為-。 第44頁，共227頁，2022年，5月20日，16點36分，星期一

40、2、計算覆蓋所有點的一個最小矩形設(shè)目前最小矩形的四條邊界為maxx，maxy，minx，miny。如何按照面積最小的要求將a點加入矩形呢？顯然需要調(diào)整邊界線，使a點位于對應(yīng)的邊界線上。初始時，我們設(shè)最小矩形為空，即左邊界left為、右邊界right為-、下邊界top為、上邊界bottom為-。然后由左而右，依次往矩形放入n個點，調(diào)整對應(yīng)的邊界線。最后得出的矩形為最小矩形，其面積為（右邊界-左邊界）*（上邊界-下邊界）第45頁，共227頁，2022年，5月20日，16點36分，星期一3、計算覆蓋所有點的兩個面積和最小的獨立矩形 我們稱彼此完全分開的矩形是獨立的。兩個覆蓋所有點的獨立矩形有兩種形態(tài)

41、： 我們將覆蓋x軸左方點集a1,1.j的最小獨立矩形存入tac1,j；將覆蓋x軸右方點集a1,j.n的最小獨立矩形存入tdc1,j；將覆蓋y軸下方點集a2,1.j的最小獨立矩形存入tac2,j；將覆蓋y軸上方點集a2,j.n的最小獨立矩形存入tdc2,j（注意：當(dāng)k=3時，對應(yīng)的點集不包括被矩形1覆蓋的點（1j n ）。 Tac1,j-1Tdc1,jTac2,j-1Tdc2,j為什么一定要考慮兩個軸向,如果僅考慮一個軸向的話,有什么反例?第46頁，共227頁，2022年，5月20日，16點36分，星期一問題是面積和最小的兩個獨立矩形究竟取哪一個形態(tài)，區(qū)分兩個矩形的分界線j為何值，我們無法確定。

42、不得已，只能將所有可能的情況枚舉出來。設(shè)var best，now:longint；兩個獨立矩形的最小面積和、當(dāng)前方案中兩個獨立矩形的面積和枚舉過程如下： 計算tac和tdc序列； bestmaxlongint； 最小矩形面積初始化 for i1 to 2 do begin 依次分析x軸向和y軸向 k=3時順序?qū)ふ襥軸向上第一個未被矩形1覆蓋的點j； while jn do枚舉i軸向上所有可能的兩個獨立矩形，從中找出最佳方案 begin 記下i軸向上點j的坐標(biāo)h； 順序?qū)ふ襥軸向上最接近h點(k=3時，該點未被矩形1覆蓋)的點j； 第47頁，共227頁，2022年，5月20日，16點36分，星期

43、一if 點j存在并且k=2，或者k=3時以點j為分界線的左矩形和右矩形與矩形1沒有交集 then begin now(taci，j-1，1-taci，j-1，3)*(taci，j-1，2-taci，j-1，4)+(tdci，j，1-tdci，j，3)*(tdci，j，2-tdci，j，4)；則計算兩個獨立矩形的面積和 if nowbest then bestnow； 若面積和為目前最小，則記下 end；thenend；whileend；for if best=maxlongint 若找不到的兩個獨立矩形 then返回失敗標(biāo)志-1 else返回兩個矩形的最小面積和best；end；getans第

44、48頁，共227頁，2022年，5月20日，16點36分，星期一4、計算覆蓋所有點的三個面積和最小的獨立矩形 我們先枚舉第一個矩形，該矩形覆蓋x軸向上的點1、點i、點j、點h（1in, ijn, jhn）,求出覆蓋它們的最小矩形。該矩形的上邊界、下邊界、左邊界和右邊界分別記為bottom、top、left、right。顯然其面積為(bottom-top)*(right-left)。我們將該矩形稱為矩形1。那么，平面上還有哪些點未在矩形1內(nèi)，這些點將被另外兩個獨立的矩形所覆蓋。 判斷（x,y）是否在矩形1內(nèi)的條件 (xleft) and (xright) and (ybottom) and (y

45、top) 判斷矩形是否與矩形1相交的條件(min(x1,right) max(x2,left) and (min(y1,bottom) max(y2,top)第49頁，共227頁，2022年，5月20日，16點36分，星期一我們在得出矩形1的基礎(chǔ)上，直接調(diào)用上述算法計算與矩形1分開的另外兩個獨立矩形的面積和，加上矩形1的面積便是三個獨立矩形的面積和。問題是矩形1究竟覆蓋了哪些點才能得出最優(yōu)解呢？我們無法得知。無奈之下，只能通過枚舉法搜索所有的可能情況for i1 to n do 枚舉x軸向上三個點（點i、點j、點h）的所有可能組合 for ji to n do for hj to n do b

46、egin 計算覆蓋點1、點i、點j、點h的最小矩形（矩形1）的四條邊界right、bottom、left、top； now(bottom-top)*(right-left)； 計算矩形1的面積 計算未被矩形1覆蓋的點集u； 計算覆蓋u且與矩形1不相交的兩個獨立矩形的最小面積和g； if (g0) and (g+now1)），則輸出當(dāng)前局的比分a：b。請注意，如果輸入的字符為E，則標(biāo)志比賽結(jié)束，11分制計算完畢；否則，繼續(xù)讀下一個字符，計算新一局的比分。然后，對當(dāng)前輸入行計算21分制下每一局比賽的比分。計算方法基本如上。有所不同的是，若華華得分a或者對方得分b達(dá)到21分且雙方的分?jǐn)?shù)差值大于1（(

47、a21) or(b21)and (abs(a-b)1)），則輸出當(dāng)前局的比分a：b。 按照上述方法對每一輸入行計算11分制和21分制的比賽結(jié)果，直至文件讀完（eof(input)）為止。第54頁，共227頁，2022年，5月20日，16點36分，星期一assign(input,inp); reset(input);輸入文件讀準(zhǔn)備 assign(output,out);rewrite(output);輸出文件寫準(zhǔn)備 a:=0;b:=0; 當(dāng)前局雙方的比分初始化 while not eof (input) do若文件未讀完，則循環(huán) begin while not eoln(input) do若當(dāng)前

48、行處理完，則11分制的比賽結(jié)束 begin read(ch);讀一個字符 case ch of根據(jù)字符的種類分情形處理 E: begin若比賽結(jié)束，則輸出雙方比分 writeln(a,:,b); break;退出11分制的計算過程 end; E W,L: begin華華或?qū)Ψ降靡环?if ch=Wthen inc(a)else inc(b); if(a=11)or(b=11) and (abs(a-b)1) then若有一方得分達(dá)到11分且雙方的分?jǐn)?shù)差值大于1，則輸出雙方比分 begin writeln(a,:,b); 第55頁，共227頁，2022年，5月20日，16點36分，星期一a:=0

49、;b:=0;新一局的比分初始化 end;then end; W,L end;case end;while readln; end; while a:=0; b:=0; 新一局的比分初始化 writeln; reset(input);重新讀輸入行 while not eof(input) do若文件未讀完且比賽未結(jié)束，則循環(huán) begin while not eoln(input) do若當(dāng)前行處理完，則21分制的比賽結(jié)束 begin read(ch);讀一個字符 第56頁，共227頁，2022年，5月20日，16點36分，星期一case ch of根據(jù)字符的種類分情形處理 E: begin若比賽

50、結(jié)束，則輸出雙方比分，退出21分制的計算過程 writeln(a,:,b); break; end; E W,L: begin華華或?qū)Ψ降靡环?if ch=Wthen inc(a) else inc(b); if (a=21)or(b=21) and (abs(a-b)1) 若有一方得分達(dá)到21分且雙方的分?jǐn)?shù)差值大于1，則輸出雙方比分 then begin writeln(a,:,b); a:=0;b:=0;新一局的比分初始化 end;then end; W,L end;case end;while readln; end;while close(input); close(output);關(guān)

51、閉輸入文件和輸出文件 第57頁，共227頁，2022年，5月20日，16點36分，星期一數(shù)字游戲（Game.pas） 丁丁最近沉迷于一個數(shù)字游戲之中。這個游戲看似簡單，但丁丁在研究了許多天之后卻發(fā)覺原來在簡單的規(guī)則下想要贏得這個游戲并不那么容易。游戲是這樣的，在你面前有一圈整數(shù)（一共n個），你要按順序?qū)⑵浞譃閙個部分，各部分內(nèi)的數(shù)字相加，相加所得的m個結(jié)果對10取模后再相乘，最終得到一個數(shù)k。游戲的要求是使你所得的k最大或者最小。例如，對于下面這圈數(shù)字（n=4，m=2）：第58頁，共227頁，2022年，5月20日，16點36分，星期一當(dāng)要求最小值時，(2-1) mod 10)(4+3) mo

52、d 10)=17=7，要求最大值時，為(2+4+3) mod 10)(-1 mod 10)=99=81。特別值得注意的是，無論是負(fù)數(shù)還是正數(shù)，對10取模的結(jié)果均為非負(fù)值。丁丁請你編寫程序幫他贏得這個游戲?！据斎敫袷健枯斎胛募谝恍杏袃蓚€整數(shù)，n（1n50）和m（1m9）。以下n行每行有個整數(shù)，其絕對值不大于104，按順序給出圈中的數(shù)字，首尾相接?！据敵龈袷健枯敵鑫募袃尚?，各包含一個非負(fù)整數(shù)。第一行是你程序得到的最小值，第二行是最大值。第59頁，共227頁，2022年，5月20日，16點36分，星期一算法分析 設(shè)圓周上的n個數(shù)字為a1、a2、an。按照模運算的規(guī)則（a1+a2+ +ak）mod

53、 10=(a1 mod 10+a2 mod 10+ ak mod 10)mod 10；gi，j為ai、ai+1、aj的數(shù)和對10的模，即 gi，j=（ai+ai+1+ +aj）mod 10顯然 gi，i=（ai mod 10+10）mod 10 gi，j= (gi,j-1+gj,j) mod 10 (1in，i+1jn)當(dāng)m=1時，程序得到的最小值和最大值為g1,n；第60頁，共227頁，2022年，5月20日，16點36分，星期一fmax1p,I,j為ai、ai+1、aj分為p個部分，各部分內(nèi)的數(shù)字相加，相加所得的p個結(jié)果對10取模后再相乘，最終得到最大數(shù)。顯然，fmax11,i,j= gi

54、，j；fmin1p,I,j為ai、ai+1、aj分為p個部分，各部分內(nèi)的數(shù)字相加，相加所得的p個結(jié)果對10取模后再相乘，最終得到最小數(shù)。顯然，fmin11,i,j= gi，j；(1pm)問題是當(dāng)ai、ai+1、aj劃分成的部分?jǐn)?shù)p大于1時，怎么辦。我們采用動態(tài)程序設(shè)計的方法計算。第61頁，共227頁，2022年，5月20日，16點36分，星期一設(shè) 階段p：劃分成的部分?jǐn)?shù),2pm-1； 狀態(tài)（i，j）:將ai、ai+1、aj劃分成p個部分，1in，ijn； 決策k: 將ai、ai+1、ak劃分成p-1個部分，ak+1、aj為第p部分，ikj-1；顯然，狀態(tài)轉(zhuǎn)移方程為 fmin1p,i,j= fm

55、in1p-1,i,k*gk+1,j fmax1p,i,j= fmax1p-1,i,k*gk+1,j2pm-1第62頁，共227頁，2022年，5月20日，16點36分，星期一max=min= 由于p-1階段僅和p階段發(fā)生聯(lián)系，因此我們將p-1階段的狀態(tài)轉(zhuǎn)移方程fmin1p-1,i,j設(shè)為fmin1i,j、fmax1p-1,i,j 設(shè)為fmax1i,j，將p階段的狀態(tài)轉(zhuǎn)移方程fmin1p,i,j設(shè)為fmini,j、fmax1p,i,j設(shè)為fmaxi,j。 第63頁，共227頁，2022年，5月20日，16點36分，星期一 read(n,m);讀數(shù)字個數(shù)和劃分的部分?jǐn)?shù) fillchar(fmax1

56、,sizeof(fmax1),0); fillchar(fmin1,sizeof(fmin1),$FF);狀態(tài)轉(zhuǎn)移方程初始化 fillchar(g,sizeof(g),0); for i:=1 to n do依次讀入每個數(shù)，一個數(shù)組成一部分 begin read(gi,i); gi,i:=(gi,imod mask+mask) mod mask; min1i,i:=gi,i;fmax1i,i:=gi,i; end;for for i:=1 to n do計算一部分內(nèi)的數(shù)和對10的模的所有可能情況 for j:=i+1 to n do begin gi,j:=(gi,j-1+gj,j) mod

57、mask; fmax1i,j:=gi,j; fmin1i,j:=gi,j;end;forfor p:=2 to m-1 do階段：遞推計算劃分2部分m-1部分的結(jié)果值beginfillchar(fmax,sizeof(fmax),0); 劃分p部分的狀態(tài)轉(zhuǎn)移方程初始化fillchar(fmin,sizeof(fmin),$FF); 第64頁，共227頁，2022年，5月20日，16點36分，星期一for i:=1 to n do狀態(tài)：枚舉被劃分為p部分的數(shù)字區(qū)間 for j:=i to n do for k:=i to j-1 do決策：aiak被劃分為p-1部分 begin if fmax1

58、i,k*gk+1,jfmaxi,j 計算將ai、ai+1、aj劃分成p個部分的狀態(tài)轉(zhuǎn)移方程 then fmaxi,j:=fmax1i,k*gk+1,j; if(fmin1i,k=0)and(fmin1i,k*gk+1,jfmini,j)or(fmini,j0)then fmini,j:=fmin1i,k*gk+1,j; end;for fmin1:=fmin;fmax1:=fmax; end;formax:=0;min:=maxlongint;將a1、a2、an劃分成m個部分的最大值和最小值初始化if m=1 計算n個數(shù)劃分成一部分的最大值和最小值 then begin max:=g1,n;m

59、in:=g1,n;endthen 第65頁，共227頁，2022年，5月20日，16點36分，星期一else for i:=1 to n do將a1ai-1、aj+1an設(shè)為第m部分，計算最大值和最小值 for j:=i to n do if (i1) or (jn) then begin if(g1,i-1+gj+1,n) mod mask*fmax1i,jmaxthen max:=(g1,i-1+gj+1,n) mod mask*fmax1i,j; if(fmin1i,j=0) and (g1,i-1+gj+1,n) mod mask*fmin1i,jmin)then min:=(g1,i

60、-1+gj+1,n) mod mask*fmin1i,j; end;then writeln(min); writeln(max);輸出最小值和最大值第66頁，共227頁，2022年，5月20日，16點36分，星期一棧（Stack.pas） 【問題背景】棧是計算機中經(jīng)典的數(shù)據(jù)結(jié)構(gòu)，簡單的說，棧就是限制在一端進(jìn)行插入刪除操作的線性表。棧有兩種最重要的操作，即pop（從棧頂彈出一個元素）和push（將一個元素進(jìn)棧）。棧的重要性不言自明，任何一門數(shù)據(jù)結(jié)構(gòu)的課程都會介紹棧。寧寧同學(xué)在復(fù)習(xí)棧的基本概念時，想到了一個書上沒有講過的問題，而他自己無法給出答案，所以需要你的幫忙。【問題描述】第67頁，共227