備戰(zhàn)ACM資料一知識點數據結構1，單，雙鏈表及循環(huán)鏈表2，樹的表示與存儲，二叉樹（概念，遍歷）二叉樹的應用（二叉排序樹，判定樹，博弈樹，解答樹等）3，文件操作（從文本文件中讀入數據并輸出到文本文件中）4，圖（基本概念，存儲結構，圖的運算）數學知識1，離散數學知識的應用（如排列組合、簡單的圖論，數理邏輯）2，數論知識3，線性代數4，組合代數5，計算幾何二算法1，排序算法（冒拋法，插入排序，合并排序，快速排序，堆排序）2，查找（順序查找，二分發(fā)）3，回溯算法4，遞歸算法5，分治算法6，模擬法7，貪心法8，簡單搜索算法（深度優(yōu)先，廣度優(yōu)先），搜索中的剪枝，A算法9，動態(tài)規(guī)劃的思想及基本算法10，高精度運算三、ACM競賽的題型分析競賽的程序設計一般只有16種類型，它們分別是DYNAMICPROGRAMMING（動態(tài)規(guī)劃）GREEDY（貪心算法）COMPLETESEARCH（窮舉搜索）FLOODFILL（不知該如何翻譯）SHORTESTPATH（最短路徑）RECURSIVESEARCHTECHNIQUES（回溯搜索技術）MINIMUMSPANNINGTREE（最小生成樹）KNAPSACK（背包問題）COMPUTATIONALGEOMETRY計算幾何學NETWORKFLOW（網絡流）EULERIANPATH（歐拉回路）TWODIMENSIONALCONVEXHULL（不知如何翻譯）BIGNUMS（大數問題）HEURISTICSEARCH（啟發(fā)式搜索）APPROXIMATESEARCH（近似搜索）ADHOCPROBLEMS（雜題）四ACM競賽參考書實用算法的分析與程序設計（吳文虎，王建德著，電子工業(yè)出版社，競賽類的黑寶書）青少年國際和全國信息學（計算機）奧林匹克競賽指導）組合數學的算法和程序設計（吳文虎，王建德著，清華大學出版社，參加競賽組合數學必學）計算機算法設計與分析（王曉東編著，最好的數據結構教材）數據結構與算法（傅清祥，王曉東編著，我所見過的最好的算法教材）信息學奧林匹克競賽指導19971998競賽試題解析（吳文虎，王建德著，清華大學出版社）計算機程序設計技巧DEKRUTH著，算法書中最著名的葵花寶典，大師的作品，難度大）計算幾何周陪德著ACM國際大學生程序設計競賽試題與解析（一）（吳文虎著，清華大學出版社）數學建模競賽培訓教材共三本葉其孝主編數學模型第二版姜啟源隨機規(guī)劃模糊數學數學建模入門徐全智計算機算法設計與分析國防科大五常見的幾個網上題庫常用網站1）信息學初學者之家HTTP/OIBHIOIFORUMORG/（2）大榕樹編程世界HTTP/WWWFJSDFZORG/DRS/PROGRAM/DEFAULTASP（3）中國教育曙光網HTTP/WWWCHINASCHOOLORG/AOSAI/（4）福建信息學奧林匹克HTTP/WWWCFCSCOMCN/FJAS/INDEXHTM（5）第20屆全國青少年信息學奧林匹克競賽HTTP/WWWNOI2003ORG/（6）第15屆國際青少年信息學奧林匹克競賽HTTP/WWWIOI2003ORG/（7）全美計算機奧林匹克競賽HTTP/ACEDELOSCOM/USACOGATE（8）美國信息學奧林匹克競賽官方網站HTTP/WWWUSACOORG/（9）俄羅斯URAL州立大學HTTP/ACMTIMUSRU/（10）西班牙VALLADOLID大學HTTP/ACMUVAES/PROBLEMSET（11）ACMICPCHTTP/ICPCBAYLOREDU/ICPC/（12）北京大學HTTP/ACMPKUEDUCN/JUDGEONLINE/INDEXACM（13）浙江大學HTTP/ACMZJUEDUCN/（14）IOIHTTP/OLYMPIADSWINTUENL/IOI/（15）2003年江蘇省信息學奧林匹克競賽夏令營HTTP/JSOICZYZCOMCN（16）HTTP/ACMZJUEDUCN（17）HTTP/ACMZSUEDUCN（18）WWWSHUMOCOM（19）HTTP/WWWBEPARKCOM/DOWNLDMANAG/INDEXASP（20）HTTP/WWWYH01COMCOLIN_FOX/COLIN_FOX五如何備戰(zhàn)ACM/ICPC1，個人準備（算法書，習題集，網上做題和討論）2，1000題亞洲冠軍世界決賽3，做好資料收集和整理工作實驗一遞歸與分治1二分查找2合并排序3快速排序實驗二回溯101背包問題2裝載問題3堡壘問題（ZOJ1002）4翻硬幣問題58皇后問題6素數環(huán)問題7迷宮問題8農場灌溉問題（ZOJ2412）9求圖像的周長（ZOJ1047）10骨牌矩陣11字母轉換（ZOJ1003）12踩氣球（ZOJ1004）實驗三搜索1FLOODFILL2電子老鼠闖迷宮3跳馬4獨輪車5皇宮小偷6分酒問題7找倍數88數碼難題實驗四動態(tài)規(guī)劃1最長公共子序列2計算矩陣連乘積3凸多邊形的最優(yōu)三角剖分4防衛(wèi)導彈5石子合并6最小代價子母樹7旅游預算8皇宮看守9游戲室問題10基因問題11田忌賽馬實驗五貪心與隨機算法1背包問題2搬桌子問題3照亮的山景4用隨即算法求解8皇后問題5素數測試實驗一遞歸與分治實驗目的理解遞歸算法的思想和遞歸程序的執(zhí)行過程，并能熟練編寫遞歸程序。掌握分治算法的思想，對給定的問題能設計出分治算法予以解決。實驗預習內容編程實現講過的例題二分搜索、合并排序、快速排序。對本實驗中的問題，設計出算法并編程實現。試驗內容和步驟1二分查找在對線性表的操作中，經常需要查找某一個元素在線性表中的位置。此問題的輸入是待查元素X和線性表L，輸出為X在L中的位置或者X不在L中的信息。程序略2合并排序程序略3快速排序程序略實驗總結及思考合并排序的遞歸程序執(zhí)行的過程實驗二回溯算法實驗目的熟練掌握回溯算法實驗內容回溯算法的幾種形式A用回溯算法搜索子集樹的一般模式VOIDSEARCHINTMIFMN/遞歸結束條件OUTPUT/相應的處理輸出結果ELSEAM0/設置狀態(tài)0表示不要該物品SEARCHM1/遞歸搜索繼續(xù)確定下一個物品AM1/設置狀態(tài)1表示要該物品SEARCHM1/遞歸搜索繼續(xù)確定下一個物品B用回溯算法搜索子集樹的一般模式VOIDSEARCHINTMIFMN/遞歸結束條件OUTPUT/相應的處理輸出結果ELSEFORIMIVOIDREADDATAVOIDSEARCHINTVOIDCHECKMAXVOIDPRINTRESULTINTC35,N10/C背包容量；N物品數INTW10,V10/WI、VI第I件物品的重量和價值INTA10,MAX/A數組存放當前解各物品選取情況；MAX記錄最大價值/AI0表示不選第I件物品，AI1表示選第I件物品INTMAINREADDATA/讀入數據SEARCH0/遞歸搜索PRINTRESULTVOIDSEARCHINTMIFMNCHECKMAX/檢查當前解是否是可行解，若是則把它的價值與MAX比較ELSEAM0/不選第M件物品SEARCHM1/遞歸搜索下一件物品AM1/不選第M件物品SEARCHM1/遞歸搜索下一件物品VOIDCHECKMAXINTI,WEIGHT0,VALUE0FORI0IMAX/且價值大于MAXMAXVALUE/替換MAXVOIDREADDATAINTIFORI0INNCHECKMAX/檢查當前解是否是可行解，若是則把它的價值與MAX比較ELSESEARCHM1/該位置不放堡壘遞歸搜索下一個位置IFCANPLACEM/判斷第M個格子是否能放堡壘PLACEM/在第M個格子上放置一個堡壘SEARCHM1/遞歸搜索下一個位置TAKEOUTM/去掉第M個格子上放置的堡壘4翻硬幣問題把硬幣擺放成329的矩陣，你可以隨意翻轉矩陣中的某些行和某些列，問正面朝上的硬幣最多有多少枚提示（1）任意一行或一列，翻兩次等于沒有翻；（2）對于9列的任何一種翻轉的情況，每一行翻與不翻相互獨立。58皇后問題在一個的棋盤里放置個皇后，要求這8個皇后兩兩之間互相都不“沖突”。INCLUDEINCLUDEVOIDSEARCHINTVOIDPRINTRESULT/打印結果INTCANPLACEINT,INT/判斷該位置能否放置皇后VOIDPLACEINT,INT/在該位置能否放置皇后VOIDTAKEOUTINT,INT/把該位置放置皇后去掉INTA8/AI存放第I個皇后的位置INTMAINSEARCH0/遞歸搜索VOIDSEARCHINTMINTIIFM8/當已經找出一組解時PRINTRESULT/輸出當前結果ELSEFORI0IINCLUDEVOIDSEARCHINTVOIDINIT/初始化VOIDPRINTRESULT/打印結果INTISPRIMEINT/判斷該數是否是素數VOIDSWAPINT,INT/交換AM和AIINTA21/A數組存放素數環(huán)INTMAININITSEARCH2/遞歸搜索INTISPRIMEINTNUMINTI,KKSQRTNUMFORI2I20/當已經搜索到葉結點時IFISPRIMEA1A20/如果A1A20也是素數PRINTRESULT/輸出當前解RETURNELSEFORIMIINCLUDEVOIDSEARCHINT,INTINTCANPLACEINT,INTVOIDREADDATA/讀入數據VOIDPRINTRESULT/打印結果INTA2020/A數組存放迷宮INTS,TINTMAININTROW,COLREADDATAROWS/20COLS20SEARCHROW,COL/遞歸搜索PRINTRESULTVOIDSEARCHINTROW,INTCOLINTR,CAROWCOL1RROW/左CCOL1IFCANPLACER,C/判斷R,C位置是否已經走過SEARCHR,C/遞歸搜索R,CRROW1/下CCOLIFCANPLACER,C/判斷R,C位置是否已經走過SEARCHR,C/遞歸搜索R,CRROW/右CCOL1IFCANPLACER,C/判斷R,C位置是否已經走過SEARCHR,C/遞歸搜索R,CRROW1/上CCOLIFCANPLACER,C/判斷R,C位置是否已經走過SEARCHR,C/遞歸搜索R,CVOIDPRINTRESULTINTI,JFORI0I0/讀入數據VOIDINIT/初始化INTSEARCH/廣搜，并在每一個可到達的每一個空格出填上最小步數INTEMPTYOPEN/判棧是否為空空1；非空0。INTTAKEOUTOFOPEN/從棧中取出一個元素，并把該元素從棧中刪除INTCANMOVETOINT,INT,INT,INT,INT/判能否移動到該方向，并帶回坐標R,CINTISAIMINTROW,INTCOL/判斷該點是否是目標INTUSEDINT,INT/判斷該點是否已經走過VOIDADDTOOPENINT,INT/把該點加入到OPEN表INTA1212/A存放迷宮，0表示空格，2表示墻。/廣搜時，未找到目標以前到達的空格，填上到達該點的最小步數INTN/N為迷宮邊長，注若大于12，必須修改一些參數，如A的大小INTOPEN20,HEAD,TAIL,OPENLEN20/OPEN表INTS,T/起點和終點INTMAININTNUMBERREADDATA/讀取數據INIT/初始化NUMBERSEARCH/廣搜并返回最小步數PRINTF“D“,NUMBER/打印結果INTSEARCHINTU,ROW,COL,R,C,I,NUMWHILEEMPTYOPEN/當棧非空UTAKEOUTOFOPEN/從棧中取出一個元素，并把該元素從棧中刪除ROWU/N/計算該點的坐標COLUNNUMAROWCOL/取得該點的步數FORI0IN|CN/如果越界返回0RETURN0IFARC0/如果是空格返回1RETURN1RETURN0/其余情況返回0INTISAIMINTROW,INTCOLIFROWNCOLTRETURN1ELSERETURN0INTUSEDINTROW,INTCOLIFAROWCOL0/0表示空格RETURN0ELSERETURN1VOIDADDTOOPENINTROW,INTCOLINTUUROWNCOLOPENTAILUTAILTAILOPENLENVOIDREADDATAINTI,J,ROW,COLCHARSTR20SCANF“D“,SCANF“DD“,/起點坐標SROWNCOLSCANF“DD“,/終點坐標TROWNCOLGETSSTRFORI0IVOIDREADDATA/讀入數據VOIDINIT/初始化INTSEARCH/廣度優(yōu)先搜索INTEMPTYOPEN/判棧是否為空空1；非空0。LONGTAKEOUTOFOPEN/從棧中取出一個元素，并把該元素從棧中刪除INTCANMOVETOINT,INT,INT,INT,INT/判能否移動到該方向，并帶回坐標R,CINTISAIMINTROW,INTCOL/判斷該點是否是目標INTUSEDINT,INT/判斷該點是否已經走過VOIDADDTOOPENINT,INT/把該點加入到OPEN表INTA200200,N200/A存放棋盤，N為迷宮邊長LONGOPEN2000,HEAD,TAIL,OPENLEN2000/OPEN表1367LONGS,T/起點和終點INTSEARCHLONGUINTROW,COL,R,C,I,NUMWHILEEMPTYOPEN/當棧非空UTAKEOUTOFOPEN/從棧中取出一個元素，并把該元素從棧中刪除ROWU/N/計算該點所在的行COLUN/計算該點所在的列NUMAROWCOL/取得該點的步數FORI0ISTRUCTCOLORNODEINTROW/該狀態(tài)的行INTCOL/列INTCOLOR/顏色INTDIRECTION/方向INTNUM/最小步數INTSEARCH/廣搜返回目標結點的最小步數VOIDREADDATA/讀入數據VOIDINIT/初始化STRUCTCOLORNODEMOVEAHEADSTRUCTCOLORNODEU/返回U向前走一格得到的結點INTUSEDSTRUCTCOLORNODEV/判斷該結點是否是到達過的結點VOIDADDTOOPENSTRUCTCOLORNODEV/加入到OPEN表INTISLEGALSTRUCTCOLORNODEV/如果該結點是合法的結點未越界且是空格INTISAIMSTRUCTCOLORNODEV/判斷該結點是否是目標結點STRUCTCOLORNODETAKEOUTOFOPEN/從OPEN表中取出一個結點并把該結點從OPEN表中刪除STRUCTCOLORNODETURNTOLEFTSTRUCTCOLORNODEU/U向左轉得到新結點VSTRUCTCOLORNODETURNTORIGHTSTRUCTCOLORNODEU/U向左轉得到新結點VSTRUCTCOLORNODES,T/S起始結點；T目標結點STRUCTCOLORNODEOPEN200/OPEN表INTHEAD,TAIL,OPENLEN200/OPEN表相關數據INTDIRECT420,1,1,0,0,1,1,0/向左、下、右、上四個方向轉時，行列的增加值INTA2020,N20/A數組表示迷宮；N為迷宮邊長INTB202054/B數組表示搜索時的所有狀態(tài)0未訪問；1已訪問INTMAININTNUMBERREADDATAINITNUMBERSEARCHPRINTF“DN“,NUMBERINTSEARCH/廣搜返回目標結點的最小步數STRUCTCOLORNODEU,VWHILEHEADTAILUTAKEOUTOFOPENVMOVEAHEADU/U向前走一格得到新結點VIFISLEGALV/如果該結點是合法的結點未越界且是空格IFISAIMV/判是否是目標結點RETURNVNUMIFUSEDV/如果是未到達過的結點ADDTOOPENV/加入到OPEN表VTURNTOLEFTU/U向左轉得到新結點VIFUSEDVADDTOOPENVVTURNTORIGHTU/U向右轉得到新結點VIFUSEDVADDTOOPENVINTUSEDSTRUCTCOLORNODEV/判斷該結點是否是到達過的結點IFBVROWVCOLVCOLORVDIRECTION0RETURN0ELSERETURN1VOIDADDTOOPENSTRUCTCOLORNODEV/加入到OPEN表OPENTAILVTAILTAILOPENLENBVROWVCOLVCOLORVDIRECTION1STRUCTCOLORNODETAKEOUTOFOPEN/從OPEN表中取出一個結點并把該結點從OPEN表中刪除STRUCTCOLORNODEVVOPENHEADHEADHEADOPENLENRETURNVVOIDINIT/初始化INTI,J,K,LFORI0IN|VCOLN/若越界RETURN0IFAVROWVCOL0/0表示空格RETURN1RETURN0STRUCTCOLORNODEMOVEAHEADSTRUCTCOLORNODEU/返回U向前走一格得到的結點STRUCTCOLORNODEVVROWUROWDIRECTUDIRECTION0VCOLUCOLDIRECTUDIRECTION1VCOLORUCOLOR15VDIRECTIONUDIRECTIONVNUMUNUM1RETURNVSTRUCTCOLORNODETURNTOLEFTSTRUCTCOLORNODEU/U向左轉得到新結點VSTRUCTCOLORNODEVVUVDIRECTIONVDIRECTION14VNUMVNUM1RETURNVSTRUCTCOLORNODETURNTORIGHTSTRUCTCOLORNODEU/U向左轉得到新結點VSTRUCTCOLORNODEVVUVDIRECTIONVDIRECTION34VNUMVNUM1RETURNV測試數據XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX11114815皇宮小偷有一個小偷要到皇宮里偷取寶物，經過仔細的偵察，他發(fā)現皇宮實際上是一個2020的迷宮，并且有一名衛(wèi)兵巡邏，衛(wèi)兵巡邏的路線是固定的，每單位時間移動一格，每4個單位時間循環(huán)一次。小偷每單位時間移動一格或在原地不動。任何時刻，小偷和衛(wèi)兵在同一格，或衛(wèi)兵能看到小偷，小偷將會被衛(wèi)兵殺死。現在小偷已經得到了皇宮的地圖，衛(wèi)兵巡邏的起點，衛(wèi)兵連續(xù)四次移動的方向和寶物的位置，請你設計一個程序判斷小偷能否偷得寶物。提示參考第3題、第4題6分酒問題有一酒瓶裝有8斤酒，沒有量器，只有分別裝5斤和3斤的空酒瓶。設計一程序將8斤酒分成兩個4斤，并以最少的步驟給出答案。7找倍數對于每個輸入的數字（如2），則要求給出一個由1，0構成的十進制整數，且該整數為輸入數字的某個倍數（如2對應的10，6的倍數100100100100100100）。88數碼難題由左圖變到右圖最少需要幾步，并演示移動過程。實驗四動態(tài)規(guī)劃實驗目的理解動態(tài)規(guī)劃的基本思想，理解動態(tài)規(guī)劃算法的兩個基本要素最優(yōu)子結構性質和子問題的重疊性質。熟練掌握典型的動態(tài)規(guī)劃問題。掌握動態(tài)規(guī)劃思想分析問題的一般方法，對較簡單的問題能正確分析，設計出動態(tài)規(guī)劃算法，并能快速編程實現。實驗內容編程實現講過的例題最長公共子序列問題、矩陣連乘問題、凸多邊形最優(yōu)三角剖分問題、電路布線問題等。本實驗中的問題，設計出算法并編程實現。習題1最長公共子序列一個給定序列的子序列是在該序列中刪去若干元素后得到的序列。確切地說，若給定序列X，則另一序列Z是X的子序列是指存在一個嚴格遞增的下標序列，使得對于所有J1,2,K有解答如下A最長公共子序列的結構若用窮舉搜索法，耗時太長，算法需要指數時間。易證最長公共子序列問題也有最優(yōu)子結構性質設序列X和Y的一個最長公共子序列Z，則I若XMYN，則ZKXMYN且ZK1是XM1和YN1的最長公共子序列；II若XMYN且ZKXM，則Z是XM1和Y的最長公共子序列；III若XMYN且ZKYN，則Z是X和YN1的最長公共子序列。其中XM1，YN1，ZK1。最長公共子序列問題具有最優(yōu)子結構性質。B子問題的遞歸結構由最長公共子序列問題的最優(yōu)子結構性質可知，要找出X和Y的最長公共子序列，可按以下方式遞歸地進行當XMYN時，找出XM1和YN1的最長公共子序列，然后在其尾部加上XMYN即可得X和Y的一個最長公共子序列。當XMYN時，必須解兩個子問題，即找出XM1和Y的一個最長公共子序列及X和YN1的一個最長公共子序列。這兩個公共子序列中較長者即為X和Y的一個最長公共子序列。由此遞歸結構容易看到最長公共子序列問題具有子問題重疊性質。例如，在計算X和Y的最長公共子序列時，可能要計算出X和YN1及XM1和Y的最長公共子序列。而這兩個子問題都包含一個公共子問題，即計算XM1和YN1的最長公共子序列。我們來建立子問題的最優(yōu)值的遞歸關系。用CI,J記錄序列XI和YJ的最長公共子序列的長度。其中XI，YJ。當I0或J0時，空序列是XI和YJ的最長公共子序列，故CI,J0。建立遞歸關系如下C計算最優(yōu)值由于在所考慮的子問題空間中，總共只有MN個不同的子問題，因此，用動態(tài)規(guī)劃算法自底向上地計算最優(yōu)值能提高算法的效率。計算最長公共子序列長度的動態(tài)規(guī)劃算法LCS_LENGTHX,Y以序列X和Y作為輸入。輸出兩個數組C0M,0N和B1M,1N。其中CI,J存儲XI與YJ的最長公共子序列的長度，BI,J記錄指示CI,J的值是由哪一個子問題的解達到的，這在構造最長公共子序列時要用到。最后，X和Y的最長公共子序列的長度記錄于CM,N中。程序如下INCLUDEINCLUDEINTLCS_LENGTHCHARX,CHARYINTMAINCHARX100,Y100INTLENWHILE1SCANF“SS“,X,YIFX00/約定第一個字符串以0開始表示結束BREAKLENLCS_LENGTHX,YPRINTF“DN“,LENINTLCS_LENGTHCHARX,CHARYINTM,N,I,J,L100100MSTRLENXNSTRLENYFORI0ILI1JLIJLIJ1ELSELIJLI1JRETURNLMN由于每個數組單元的計算耗費1時間，算法LCS_LENGTH耗時MN。思考空間能節(jié)約嗎2計算矩陣連乘積在科學計算中經常要計算矩陣的乘積。矩陣A和B可乘的條件是矩陣A的列數等于矩陣B的行數。若A是一個PQ的矩陣，B是一個QR的矩陣，則其乘積CAB是一個PR的矩陣。由該公式知計算CAB總共需要PQR次的數乘。其標準計算公式為現在的問題是，給定N個矩陣A1,A2,AN。其中AI與AI1是可乘的，I1,2,N1。要求計算出這N個矩陣的連乘積A1A2AN。遞歸公式程序如下INCLUDEINTMAININTP101,I,J,K,R,T,NINTM101101/為了跟講解時保持一致數組從1開始INTS101101/記錄從第I到第J個矩陣連乘的斷開位置SCANF“D“,FORI0I表示具有N條邊V0V1，V1V2，,VN1VN的一個凸多邊形，其中，約定V0VN。若VI與VJ是多邊形上不相鄰的兩個頂點，則線段VIVJ稱為多邊形的一條弦。弦將多邊形分割成凸的兩個子多邊形和。多邊形的三角剖分是一個將多邊形分割成互不重迭的三角形的弦的集合T。如圖是一個凸多邊形的兩個不同的三角剖分。凸多邊形最優(yōu)三角剖分的問題是給定一個凸多邊形P以及定義在由多邊形的邊和弦組成的三角形上的權函數。要求確定該凸多邊形的一個三角剖分，使得該三角剖分對應的權即剖分中諸三角形上的權之和為最小?？梢远x三角形上各種各樣的權函數W。例如定義VIVJVK|VIVJ|VIVK|VKVJ|，其中，|VIVJ|是點VI到VJ的歐氏距離。相應于此權函數的最優(yōu)三角剖分即為最小弦長三角剖分。注意解決此問題的算法必須適用于任意的權函數4防衛(wèi)導彈一種新型的防衛(wèi)導彈可截擊多個攻擊導彈。它可以向前飛行，也可以用很快的速度向下飛行，可以毫無損傷地截擊進攻導彈，但不可以向后或向上飛行。但有一個缺點，盡管它發(fā)射時可以達到任意高度，但它只能截擊比它上次截擊導彈時所處高度低或者高度相同的導彈。現對這種新型防衛(wèi)導彈進行測試，在每一次測試中，發(fā)射一系列的測試導彈（這些導彈發(fā)射的間隔時間固定，飛行速度相同），該防衛(wèi)導彈所能獲得的信息包括各進攻導彈的高度，以及它們發(fā)射次序。現要求編一程序，求在每次測試中，該防衛(wèi)導彈最多能截擊的進攻導彈數量，一個導彈能被截擊應滿足下列兩個條件之一A它是該次測試中第一個被防衛(wèi)導彈截擊的導彈；B它是在上一次被截擊導彈的發(fā)射后發(fā)射，且高度不大于上一次被截擊導彈的高度的導彈。輸入數據第一行是一個整數N，以后的N各有一個整數表示導彈的高度。輸出數據截擊導彈的最大數目。分析定義LI為選擇截擊第I個導彈，從這個導彈開始最多能截擊的導彈數目。由于選擇了第I枚導彈，所以下一個要截擊的導彈J的高度要小于等于它的高度，所以LI應該等于從I1到N的每一個J，滿足HJINTMAININTI,J,N,MAX,H100,L100SCANF“D“,FORI0I0IMAX0FORJI1JHJVOIDINITINTN,A100,B100,L100100INTMAININTI,JREADDATAINITFORIN2I0IFORJ1JBJLIJLI1J11ELSEIFLI1J11LIJ1LIJLI1J11ELSELIJLIJ1PRINTF“D“,L0N1VOIDREADDATAINTISCANF“D“,FORI0IINTMAINSTRUCTINTSTARTINTENDA100INTI,JINTN,M,MIN,NUM,TEMP,USED1000SCANF“DD“,FORI0ITEMPTEMPAIENDUSEDI1NUMMINPRINTF“D“,MIN4用隨即算法求解8皇后問題5素數測試附錄邏輯推理問題對于較難的邏輯推理問題，看上去難于解決，不知道該從哪里下手時，認真的讀題從最簡單最特殊的情況入手1月薪30K的面試題小明和小強都是張老師的學生，張老師的生日是M月N日，2人都知道張老師的生日是下列10組中的一天，張老師把M值告訴了小明，把N值告訴了小強，張老師問他們知道他的生日是那一天嗎3月4日3月5日3月8日6月4日6月7日9月1日9月5日12月1日12月2日12月8日小明說如果我不知道的話，小強肯定也不知道小強說本來我也不知道，但是現在我知道了小明說哦，那我也知道了提示做西服有的需要幾分鐘，有的需要幾百道工序。只要認真就能做好。此題做對的人很少，不是因為題目太難，而是因為不夠認真。2微軟面試題一個大院子里住了50戶人家，每家都養(yǎng)了一條狗，有一天他們接到通知說院子里有狗生病了，并要求所有主人在發(fā)現自己家狗生病的當天就要把狗槍殺掉。然而所有主人和他們的狗都不能夠離開自己的房子，主人與主人之間也不能通過任何方式進行溝通，他們能做的只是通過窗戶觀察別人家的狗是否生病從而判斷自己的狗病否。（就是說，每個主人只能看出其他49家的狗是不是生病，單獨看自己的狗是看不出來的）第一天沒有槍聲，第二天還是沒有槍聲，第三天傳出一陣槍聲，問有多少條狗被槍殺。提示上面的大字3海盜分金塊問題海盜，大家聽說過吧。這是一幫亡命之徒，在海上搶人錢財，奪人性命，干的是刀頭上舔血的營生。在我們的印象中，他們一般都瞎一只眼，用條黑布或者講究點的用個黑皮眼罩把壞眼遮上。他們還有在地下埋寶的好習慣，而且總要畫上一張藏寶圖，以方便后人掘取。不過大家是否知道，他們是世界上最民主的團體。參加海盜的都是桀驁不馴的漢子，是不愿聽人命令的，船上平時一切事都由投票解決。船長的唯一特權，是有自己的一套餐具可是在他不用時，其他海盜是可以借來用的。船上的唯一懲罰，就是被丟到海里去喂魚。現在船上有若干個海盜，要分搶來的若干枚金幣。自然，這樣的問題他們是由投票來解決的。投票的規(guī)則如下先由最兇猛的海盜來提出分配方案，然后大家一人一票表決，如果有50或以上的海盜同意這個方案，那么就以此方案分配，如果少于50的海盜同意，那么這個提出方案的海盜就將被丟到海里去喂魚，然后由剩下的海盜中最兇猛的那個海盜提出方案，依此類推。我們先要對海盜們作一些假設。1每個海盜的兇猛性都不同，而且所有海盜都知道別人的兇猛性，也就是說，每個海盜都知道自己和別人在這個提出方案的序列中的位置。另外，每個海盜的數學和邏輯都很好，而且很理智。最后，海盜間私底下的交易是不存在的，因為海盜除了自己誰都不相信。2一枚金幣是不能被分割的，不可以你半枚我半枚。3每個海盜當然不愿意自己被丟到海里去喂魚，這是最重要的。4每個海盜當然希望自己能得到盡可能多的金幣。5每個海盜都是現實主義者，如果在一個方案中他得到了1枚金幣，而下一個方案中，他有兩種可能，一種得到許多金幣，一種得不到金幣，他會同意目前這個方案，而不會有僥幸心理?？偠灾麄兿嘈哦B在林，不如一鳥在手。6最后，每個海盜都很喜歡其他海盜被丟到海里去喂魚。在不損害自己利益的前提下，他會盡可能投票讓自己的同伴喂魚?，F在，如果有10個海盜要分100枚金幣，將會怎樣提示同上4囚犯放風問題有100個無期徒刑囚徒，被關在100個獨立的小房間，互相無法通信。每天會有一個囚徒被隨機地抽出來放風，隨機就是說可能被抽到多次，也可能一次抽不到。放風的地方有一盞燈，囚徒可以打開或者關上，除囚徒外，沒有別人會去動這個燈。每個人除非出來放風，是看不到這個燈的。一天，全體囚徒大會，國王大赦，給大家一個機會如果某一天，某個囚徒能夠明確表示，所有的囚徒都已經被放過風了，而且的確如此，那么所有囚徒釋放；如果仍有囚徒未被放過風，那么所有的囚徒一起處死囚徒大會后給大家20分鐘時間討論，囚徒們能找到方法么除了那個燈以外，囚徒們不能以其他方式聯(lián)系提示說過了5天盟筆試的最后一道題目一段文章，中有逗號若干，現求一算法，搜尋某一逗號位置。要求1、只搜索文章一遍2、搜索過程中只能存儲一個逗號的位置3、對于每個逗號，被搜尋到的幾率是相等的提示書讀百遍其意自見6現有100個黑球和100個白球，每次從中任意取出兩個球，若顏色相同，則給這堆球中放入一個黑球，若顏色不同，則給這堆球中放入一個白球，這樣當這堆球中只剩下一個球時這個球是什么顏色，請證明你的結論。提示多讀仔細分析就能抓住關鍵。7下面用數學歸納法證明“所有的馬的顏色都相同”的證明是否正確，如不正確指出錯誤的原因。（1）基礎當N1時顯然正確。（2）歸納假設NK時命題成立，當NK1時，從中間取出一匹馬，這是只有K匹馬，根據假設，這K匹馬的顏色是相同的，再從中取出一匹馬，把剛才這匹馬放回，這是又是K匹馬，根據假設，這K匹馬的顏色是相同的，所以這K1匹馬的顏色是相同的。由以上兩步可知，所有的馬的顏色都是相同的。提示不需要什么，除了知識。8現在小明一家過一座橋，過橋時候是黑夜，所以必須有燈。現在小明過橋要秒，小明的弟弟要秒，小明的爸爸要秒，小明的媽媽要秒，小明的爺爺要秒。每次此橋最多可過兩人，而過橋的速度依過橋最慢者而定，而且燈在點燃后秒就會熄滅。問小明一家如何過橋（再加一點，如果是5個人，6個人呢）9小明早晨600從山腳下開始爬山，中午1200到達山頂；第二天早晨600從山頂開始下山，中午1200到達山腳下。上山的路只有一條沒有任何岔路，你能否證明小明在同一個時間經過了同一個點。10一男孩和一女孩分別在離家2千米和1千米且方向相反的兩所學校上學每天同時以4千米/時和2千米/時的速度步行上學一小狗以6千米/時的速度從男孩奔向女孩又從女孩處奔向男孩，如此往返當兩人到達學校時小狗在何處然后一步一步分析ACM競賽須掌握的知識圖論拓撲排序有向無環(huán)圖與動態(tài)規(guī)劃的關系二分圖匹配問題一般圖問題與二分圖問題的轉換思路最大匹配有向圖的最小路徑覆蓋0/1矩陣的最小覆蓋完備匹配最優(yōu)匹配穩(wěn)定婚姻網絡流問題網絡流模型的簡單特征和與線性規(guī)劃的關系最大流最小割定理最大流問題有上下界的最大流問題循環(huán)流最小費用最大流/最大費用最大流弦圖的性質和判定組合數學解決組合數學問題時常用的思想逼近遞推/動態(tài)規(guī)劃概率問題POLYA定理計算幾何/解析幾何計算幾何的核心叉積/面積解析幾何的主力復數基本形點直線，線段多邊形凸多邊形/凸包凸包算法的引進，卷包裹法GRAHAM掃描法水平序的引進，共線凸包的補丁完美凸包算法相關判定兩直線相交兩線段相交點在任意多邊形內的判定點在凸多邊形內的判定經典問題最小外接圓近似ON的最小外接圓算法點集直徑旋轉卡殼，對踵點多邊形的三角剖分數學/數論最大公約數EUCLID算法擴展的EUCLID算法同余方程/二元一次不定方程同余方程組線性方程組高斯消元法解MOD2域上的線性方程組整系數方程組的精確解法矩陣行列式的計算利用矩陣乘法快速計算遞推關系分數分數樹連分數逼近數論計算求N的約數個數求PHIN求約數和快速數論變換素數問題概率判素算法概率因子分解數據結構組織結構二叉堆左偏樹二項樹勝者樹跳躍表樣式圖標斜堆REAP統(tǒng)計結構樹狀數組虛二叉樹線段樹矩形面積并圓形面積并關系結構HASH表并查集路徑壓縮思想的應用STL中的數據結構VECTORDEQUESET/MAP動態(tài)規(guī)劃/記憶化搜索動態(tài)規(guī)劃和記憶化搜索在思考方式上的區(qū)別最長子序列系列問題最長不下降子序列最長公共子序列一類NP問題的動態(tài)規(guī)劃解法樹型動態(tài)規(guī)劃背包問題動態(tài)規(guī)劃的優(yōu)化四邊形不等式函數的凸凹性狀態(tài)設計規(guī)劃方向線性規(guī)劃常用思想二分最小表示法串KMPTRIE結構后綴樹/后綴數組LCA/RMQ有限狀態(tài)自動機理論排序選擇/冒泡快速排序堆排序歸并排序基數排序拓撲排序排序網絡/以下為POJ推薦/題目均為POJ上的HTTP/ACMPKUEDUCN個別題目的分類并不準確OJ上的一些水題可用來練手和增加自信POJ3299,POJ2159,POJ2739,POJ1083,POJ2262,POJ1503,POJ3006,POJ2255,POJ3094初期一基本算法1枚舉POJ1753,POJ29652貪心POJ1328,POJ2109,POJ25863遞歸和分治法4遞推5構造法POJ32956模擬法POJ1068,POJ2632,POJ1573,POJ2993,POJ2996二圖算法1圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷2最短路徑算法DIJKSTRA,BELLMANFORD,FLOYD,HEAPDIJKSTRAPOJ1860,POJ3259,POJ1062,POJ2253,POJ1125,POJ22403最小生成樹算法PRIM,KRUSKALPOJ1789,POJ2485,POJ1258,POJ30264拓撲排序POJ10945二分圖的最大匹配匈牙利算法POJ3041,POJ30206最大流的增廣路算法KM算法POJ1459,POJ3436三數據結構1串POJ1035,POJ3080,POJ19362排序快排、歸并排與逆序數有關、堆排POJ2388,POJ22993簡單并查集的應用4哈希表和二分查找等高效查找法數的HASH,串的HASHPOJ3349,POJ3274,POJ2151,POJ1840,POJ2002,POJ25035哈夫曼樹POJ32536堆7TRIE樹靜態(tài)建樹、動態(tài)建樹POJ2513四簡單搜索1深度優(yōu)先搜索POJ2488,POJ3083,POJ3009,POJ1321,POJ22512廣度優(yōu)先搜索POJ3278,POJ1426,POJ3126,POJ3087POJ34143簡單搜索技巧和剪枝POJ2531,POJ1416,POJ2676,1129五動態(tài)規(guī)劃1背包問題POJ1837,POJ12762型如下表的簡單DP可參考LRJ的書PAGE1491EJOPTDIWI,JPOJ3267,POJ1836,POJ1260,POJ25332EI,JOPTDI1,JXI,DI,J1YJ,DI1J1ZIJ最長公共子序列POJ3176,POJ1080,POJ11593CI,JWI,JOPTCI,K1CK,J最優(yōu)二分檢索樹問題六數學1組合數學1加法原理和乘法原理2排列組合3遞推關系POJ3252,POJ1850,POJ1019,POJ19422數論1素數與整除問題2進制位3同余模運算POJ2635,POJ3292,POJ1845,POJ21153計算方法1二分法求解單調函數相關知識POJ3273,POJ3258,POJ1905,POJ3122七計算幾何學1幾何公式2叉積和點積的運用如線段相交的判定,點到線段的距離等POJ2031,POJ10393多邊型的簡單算法求面積和相關判定點在多邊型內,多邊型是否相交POJ1408,POJ15844凸包POJ2187,POJ1113中級一基本算法1C的標準模版庫的應用POJ3096,POJ30072較為復雜的模擬題的訓練POJ3393,POJ1472,POJ3371,POJ1027,POJ2706二圖算法1差分約束系統(tǒng)的建立和求解POJ1201,POJ29832最小費用最大流POJ2516,POJ2516,POJ21953雙連通分量POJ29424強連通分支及其縮點POJ21865圖的割邊和割點POJ33526最小割模型、網絡流規(guī)約POJ3308,三數據結構1線段樹POJ2528,POJ2828,POJ2777,POJ2886,POJ27502靜態(tài)二叉檢索樹POJ2482,POJ23523樹狀樹組POJ1195,POJ33214RMQPOJ3264,POJ33685并查集的高級應用POJ1703,24926KMP算法POJ1961,POJ2406四搜索1最優(yōu)化剪枝和可行性剪枝2搜索的技巧和優(yōu)化POJ3411,POJ17243記憶化搜索POJ3373,POJ1691五動態(tài)規(guī)劃1較為復雜的動態(tài)規(guī)劃如動態(tài)規(guī)劃解特別的施行商問題等POJ1191,POJ1054,POJ3280,POJ2029,POJ2948,POJ1925,POJ30342記錄狀態(tài)的動態(tài)規(guī)劃POJ3254,POJ2411,POJ11853樹型動態(tài)規(guī)劃POJ2057,POJ1947,POJ2486,POJ3140六數學1組合數學1容斥原理2抽屜原理3置換群與POLYA定理POJ1286,POJ2409,POJ3270,POJ10264遞推關系和母函數2數學1高斯消元法POJ2947,POJ1487,POJ2065,POJ1166,POJ12222概率問題POJ3071,POJ34403GCD、擴展的歐幾里德中國剩余定理POJ31013計算方法10/1分數規(guī)劃POJ29762三分法求解單峰單谷的極值3矩陣法POJ3150,POJ3422,POJ30704迭代逼近POJ33014隨機化算法POJ3318,POJ24545雜題POJ1870,POJ3296,POJ3286,POJ1095七計算幾何學1坐標離散化2掃描線算法例如求矩形的面積和周長并,常和線段樹或堆一起使用POJ1765,POJ1177,POJ1151,POJ3277,POJ2280,POJ30043多邊形的內核半平面交POJ3130,POJ33354幾何工具的綜合應用POJ1819,POJ1066,POJ2043,POJ3227,POJ2165,POJ3429高級一基本算法要求1代碼快速寫成,精簡但不失風格POJ2525,POJ1684,POJ1421,POJ1048,POJ2050,POJ33062保證正確性和高效性POJ3434二圖算法1度限制最小生成樹和第K最短路POJ16392最短路,最小生成樹,二分圖,最大流問題的相關理論主要是模型建立和求解POJ3155,POJ2112,POJ1966,POJ3281,POJ1087,POJ2289,POJ3216,POJ24463最優(yōu)比率生成樹POJ27284最小樹形圖POJ31645次小生成樹6無向圖、有向圖的最小環(huán)三數據結構1TRIE圖的建立和應用POJ27782LCA和RMQ問題LCA最近公共祖先問題有離線算法并查集DFS和在線算法RMQDFSPOJ13303雙端隊列和它的應用維護一個單調的隊列,常常在動態(tài)規(guī)劃中起到優(yōu)化狀態(tài)轉移的目的POJ28234左偏樹可合并堆5后綴樹非常有用的數據結構,也是賽區(qū)考題的熱點POJ3415,POJ3294四搜索1較麻煩的搜索題目訓練POJ1069,POJ3322,POJ1475,POJ1924,POJ2049,POJ34262廣搜的狀態(tài)優(yōu)化利用M進制數存儲狀態(tài)、轉化為串用HASH表判重、按位壓縮存儲狀態(tài)、雙向廣搜、A算法POJ1768,POJ1184,POJ1872,POJ1324,POJ2046,POJ14823深搜的優(yōu)化盡量用位運算、一定要加剪枝、函數參數盡可能少、層數不易過大、可以考慮雙向搜索或者是輪換搜索、IDA算法POJ3131,POJ2870,POJ2286五動態(tài)規(guī)劃1需要用數據結構優(yōu)化的動態(tài)規(guī)劃POJ2754,POJ3378,POJ30172四邊形不等式理論3較難的狀態(tài)DPPOJ3133六數學1組合數學1MOBIUS反演POJ2888,POJ21542偏序關系理論2博奕論1極大極小過程POJ3317,POJ10852NIM問題七計算幾何學1半平面求交POJ3384,POJ25402可視圖的建立POJ29663點集最小圓覆蓋4對踵點POJ2079八綜合題POJ3109,POJ1478,POJ1462,POJ2729,POJ2048,POJ3336,POJ3315,POJ2148,POJ1263下面是另一版本POJ推薦，基本都比較難，很多題目與黑書配套推薦一些題目，希望對參與ICPC競賽的同學有所幫助。POJ上一些題目在HTTP/16210581202/COURSE/PROBLEMSOLVING/可以找到解題報告。算法藝術與信息學競賽的習題提示在網上可搜到一動態(tài)規(guī)劃參考資料劉汝佳算法藝術與信息學競賽算法導論推薦題目HTTP/ACMPKUEDUCN/JUDGEONLINE/PROBLEMID1141簡單HTTP/ACMPKUEDUCN/JUDGEONLINE/PROBLEMID2288中等，經典TSP問題HTTP/ACMPKUEDUCN/JUDGEONLINE/PROBLEMID2411中等，狀態(tài)壓縮DPHTTP/ACMPKUEDUCN/JUDGEONLINE/PROBLEMID1112中等HTTP/ACMPKUEDUCN/JUDGEONLINE/PROBLEMID1848中等，樹形DP。可參考算法藝術與信息學競賽動態(tài)規(guī)劃一節(jié)的樹狀模型HTTP/ACMZ