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

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

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

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

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

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

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

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

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

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

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

12、數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的字串究竟在哪個位置上多出一個字符，無奈，只能將該字串的每一個字符試插在另一個字串的對應位置上。如果插入后使得兩串相同，則說明猜想成立。否則猜想不成立。function check(a,b:string):integer；輸入字串a,b。若b能夠在a的基礎上添加一個字符得到的話，

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；然后根據ans序列在字典表中依次搜索類別3類別1的單詞，輸出對應的單詞序號。如果在字典表中不存在上述3種類別的單詞，則輸出N。fillchar(ans,sizeof(ans),0)； 單詞的類別序列初始化for i1 to n do begin 對字典中的每個單詞進行分類 if length(listi)=length(want) 若單詞i與待匹配單詞等長 then begin kfind(listi,want)；計算單詞i與待匹配單詞的不同字符個

15、數 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； 匹配情況存在的標志初始化for i3 dow

16、nto 1 do begin 依次輸出每一類別的單詞在字典表最先出現的序號 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分，星期一 第二題：級數求和 已知：Sn=1+1/2+1/3+.+1/n。顯然當n.非常大的時候，Sn可大于任何一個整數K。現給出一個整數K（1K15），要求計算出一個最小的n，使得SnK。輸入 鍵盤輸入k輸出 屏幕輸出n輸入輸出樣例輸入:1輸出:2第19頁，共227頁，

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

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

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

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

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

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

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

24、2 2 輸出：0第28頁，共227頁，2022年，5月20日，16點36分，星期一1、計算對方馬的控制點 按照題意，對方的馬所在的點和所有跳躍一步可達的點稱為對方馬的控制點，卒不能通過對方馬的控制點。在卒出發之前，必須計算對方馬的所有控制點。顯然，若（0，0）或（n,m）為控制點，則輸出路徑數為0。設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；路徑數序列，其中listi,j為卒從(0,0)到(i,j)的路徑數 can:array0.20,0.20 of boolean； 點(i,j)允許卒通行的標志馬的初始位置為（x,y）。我們按照下述方式計算can序列：canx,y false； 對方馬所在的點為控制點for i1 to 8 do begin從（x，y）出發，沿8個跳馬方向計算控制點 jx+movei,1； 計算i方向的跳馬位置(j，k) ky+movei,2； if (j=0) and (k=0) and (j=n) and (k=m) 若（j,k）在界內，則為控制點 then canj,k false；end；fori

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

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

28、么從左側、要么從上方走到,由此計算從(0,0)到(i,j)的路徑數 for j0 to m do if cani,j then listi,jlisti-1,j+listi,j-1；輸出卒從（0，0）走到（n,m）點的路徑條數listn,m；第30頁，共227頁，2022年，5月20日，16點36分，星期一題一 均分紙牌問題描述 有N堆紙牌，編號分別為1，2，.N。每堆上有若干張， 但紙牌總數必為N的倍數。可以在任一堆上取若干張紙牌，然后移動。移牌規則為：在編號為1堆上取的紙牌，只能移到編號為2的堆上；在編號為N的堆上取的紙牌，只能移到編號為N-1的堆上；其他堆上取的紙牌，可以移到相鄰左邊或右

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

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

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

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

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

34、now=b then begin若達到目標狀態，則記下替換次數，并回溯 bestneed； exit； end；thenfor i1 to n do 搜索每一條規則 第38頁，共227頁，2022年，5月20日，16點36分，星期一if length(now)+length(rulei,2)-length(rulei,1)0 do 反復在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)；將當前被替換串前（

35、包括被替換串）的子串刪除 jj+k； 右移匹配指針 kpos(rulei,1,tmp)； 繼續嘗試第i條規則 end；while end；thenend； solve 第39頁，共227頁，2022年，5月20日，16點36分，星期一由此得出主程序：讀入初始串a和目標串；讀入替換規則rule；best31； 設定替換次數的上限solve(0,a)； 回溯搜索最少的替換次數if best=30 輸出最少替換次數 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 前進。如下圖： 小車與所有小球同時開始運動，當小球距小車的距離0.00001時，即認為小球被小車接受（小球落到地面后不能被接受）。請你計算出小車能接受到多少個小球。輸入：H，S1，v，L，k，n （1H，S1，v，L，k，n100000）輸出：小車能接受到的小球個數。 這是分區聯賽最容易失誤的一道試題，關鍵是弄清小車行程的物理意義和計算的精度誤差！第41頁，共227頁，202

37、2年，5月20日，16點36分，星期一算法分析由題意可知，車頂與天花板的距離為h-k，小球由天花板落至車頂所花費的時間為t1= ，由天花板落至地面的時間為t2= 。小車與所有小球同時開始運動，當小球距小車的距離0.00001時，即認為小球被小車接受（小球落到地面后不能被接受）。顯然，若n1n2，則小車接受的小球數為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)，每個點用一對整數坐標表示。例如：當n=4 時，4 個點的坐標分別為： p1(1，1)， p2(2，2)， p3 (6，3)， p4(7，0)這些點可以用 k 個矩形( k4) 全部覆蓋，矩形的邊平行于坐標軸。如圖一，當 k=2時，可用如圖二的兩個矩形s1，s2覆蓋， s1，s2面積和為4。問題是當 n個點坐標和 k 給出后，怎樣才能使得覆蓋所有點的k個矩形的面積之和為最小呢。約定： 覆蓋一個點的矩形面積為0；覆蓋平行于坐標軸直線上點的矩形

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

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

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（注意：當k=3時，對應的點集不包括被矩形1覆蓋的點（1j n ）。 Tac1,j-1Tdc1,jTac2,j-1Tdc2,j為什么一定要考慮兩個軸向,如果僅考慮一個軸向的話,有什么反例?第46頁，共227頁，2022年，5月20日，16點36分，星期一問題是面積和最小的兩個獨立矩形究竟取哪一個形態，區分兩個矩形的分界線j為何值，我們無法確定。

42、不得已，只能將所有可能的情況枚舉出來。設var best，now:longint；兩個獨立矩形的最小面積和、當前方案中兩個獨立矩形的面積和枚舉過程如下： 計算tac和tdc序列； bestmaxlongint； 最小矩形面積初始化 for i1 to 2 do begin 依次分析x軸向和y軸向 k=3時順序尋找i軸向上第一個未被矩形1覆蓋的點j； while jn do枚舉i軸向上所有可能的兩個獨立矩形，從中找出最佳方案 begin 記下i軸向上點j的坐標h； 順序尋找i軸向上最接近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返回失敗標志-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內，這些點將被另外兩個獨立的矩形所覆蓋。 判斷（x,y）是否在矩形1內的條件 (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的基礎上，直接調用上述算法計算與矩形1分開的另外兩個獨立矩形的面積和，加上矩形1的面積便是三個獨立矩形的面積和。問題是矩形1究竟覆蓋了哪些點才能得出最優解呢？我們無法得知。無奈之下，只能通過枚舉法搜索所有的可能情況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)），則輸出當前局的比分a：b。請注意，如果輸入的字符為E，則標志比賽結束，11分制計算完畢；否則，繼續讀下一個字符，計算新一局的比分。然后，對當前輸入行計算21分制下每一局比賽的比分。計算方法基本如上。有所不同的是，若華華得分a或者對方得分b達到21分且雙方的分數差值大于1（(

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

48、行處理完，則11分制的比賽結束 begin read(ch);讀一個字符 case ch of根據字符的種類分情形處理 E: begin若比賽結束，則輸出雙方比分 writeln(a,:,b); break;退出11分制的計算過程 end; E W,L: begin華華或對方得一分 if ch=Wthen inc(a)else inc(b); if(a=11)or(b=11) and (abs(a-b)1) then若有一方得分達到11分且雙方的分數差值大于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若文件未讀完且比賽未結束，則循環 begin while not eoln(input) do若當前行處理完，則21分制的比賽結束 begin read(ch);讀一個字符 第56頁，共227頁，2022年，5月20日，16點36分，星期一case ch of根據字符的種類分情形處理 E: begin若比賽

50、結束，則輸出雙方比分，退出21分制的計算過程 writeln(a,:,b); break; end; E W,L: begin華華或對方得一分 if ch=Wthen inc(a) else inc(b); if (a=21)or(b=21) and (abs(a-b)1) 若有一方得分達到21分且雙方的分數差值大于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);關

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

52、d 10)=17=7，要求最大值時，為(2+4+3) mod 10)(-1 mod 10)=99=81。特別值得注意的是，無論是負數還是正數，對10取模的結果均為非負值。丁丁請你編寫程序幫他贏得這個游戲。【輸入格式】輸入文件第一行有兩個整數，n（1n50）和m（1m9）。以下n行每行有個整數，其絕對值不大于104，按順序給出圈中的數字，首尾相接。【輸出格式】輸出文件有兩行，各包含一個非負整數。第一行是你程序得到的最小值，第二行是最大值。第59頁，共227頁，2022年，5月20日，16點36分，星期一算法分析 設圓周上的n個數字為a1、a2、an。按照模運算的規則（a1+a2+ +ak）mod

53、 10=(a1 mod 10+a2 mod 10+ ak mod 10)mod 10；gi，j為ai、ai+1、aj的數和對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)當m=1時，程序得到的最小值和最大值為g1,n；第60頁，共227頁，2022年，5月20日，16點36分，星期一fmax1p,I,j為ai、ai+1、aj分為p個部分，各部分內的數字相加，相加所得的p個結果對10取模后再相乘，最終得到最大數。顯然，fmax11,i,j= gi

54、，j；fmin1p,I,j為ai、ai+1、aj分為p個部分，各部分內的數字相加，相加所得的p個結果對10取模后再相乘，最終得到最小數。顯然，fmin11,i,j= gi，j；(1pm)問題是當ai、ai+1、aj劃分成的部分數p大于1時，怎么辦。我們采用動態程序設計的方法計算。第61頁，共227頁，2022年，5月20日，16點36分，星期一設 階段p：劃分成的部分數,2pm-1； 狀態（i，j）:將ai、ai+1、aj劃分成p個部分，1in，ijn； 決策k: 將ai、ai+1、ak劃分成p-1個部分，ak+1、aj為第p部分，ikj-1；顯然，狀態轉移方程為 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階段發生聯系，因此我們將p-1階段的狀態轉移方程fmin1p-1,i,j設為fmin1i,j、fmax1p-1,i,j 設為fmax1i,j，將p階段的狀態轉移方程fmin1p,i,j設為fmini,j、fmax1p,i,j設為fmaxi,j。 第63頁，共227頁，2022年，5月20日，16點36分，星期一 read(n,m);讀數字個數和劃分的部分數 fillchar(fmax1

56、,sizeof(fmax1),0); fillchar(fmin1,sizeof(fmin1),$FF);狀態轉移方程初始化 fillchar(g,sizeof(g),0); for i:=1 to n do依次讀入每個數，一個數組成一部分 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計算一部分內的數和對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部分的結果值beginfillchar(fmax,sizeof(fmax),0); 劃分p部分的狀態轉移方程初始化fillchar(fmin,sizeof(fmin),$FF); 第64頁，共227頁，2022年，5月20日，16點36分，星期一for i:=1 to n do狀態：枚舉被劃分為p部分的數字區間 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個部分的狀態轉移方程 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個數劃分成一部分的最大值和最小值 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設為第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） 【問題背景】棧是計算機中經典的數據結構，簡單的說，棧就是限制在一端進行插入刪除操作的線性表。棧有兩種最重要的操作，即pop（從棧頂彈出一個元素）和push（將一個元素進棧）。棧的重要性不言自明，任何一門數據結構的課程都會介紹棧。寧寧同學在復習棧的基本概念時，想到了一個書上沒有講過的問題，而他自己無法給出答案，所以需要你的幫忙。【問題描述】第67頁，共227