李開(kāi)復(fù)說(shuō)算法

算法李開(kāi)復(fù)：算法的力量算法是計(jì)算機(jī)科學(xué)領(lǐng)域最重要的基石之一，但卻受到了國(guó)內(nèi)一些程序員的冷落。許多學(xué)生看到一些公司在招聘時(shí)要求的編程語(yǔ)言五花八門(mén)就產(chǎn)生了一種誤解，認(rèn)為學(xué)計(jì)算機(jī)就是學(xué)各種編程語(yǔ)言，或者認(rèn)為，學(xué)習(xí)最新的語(yǔ)言、技術(shù)、標(biāo)準(zhǔn)就是最好的鋪路方法。其實(shí)大家都被這些公司誤導(dǎo)了。編程語(yǔ)言雖然該學(xué)，但是學(xué)習(xí)計(jì)算機(jī)算法和理論更重要，因?yàn)橛?jì)算機(jī)算法和理論更重要，因?yàn)橛?jì)算機(jī)語(yǔ)言和開(kāi)發(fā)平臺(tái)日新月異，但萬(wàn)變不離其宗的是那些算法和理論，例如數(shù)據(jù)結(jié)構(gòu)、算法、編譯原理、計(jì)算機(jī)體系結(jié)構(gòu)、關(guān)系型數(shù)據(jù)庫(kù)原理等等。在“開(kāi)復(fù)學(xué)生網(wǎng)”上，有位同學(xué)生動(dòng)地把這些基礎(chǔ)課程比擬為“內(nèi)功”，把新的語(yǔ)言、技術(shù)、標(biāo)準(zhǔn)比擬為“外功”。整天趕時(shí)髦的人最后只懂得招式，沒(méi)有功力，是不可能成為高手的。算法與我當(dāng)我在1980年轉(zhuǎn)入計(jì)算機(jī)科學(xué)系時(shí)，還沒(méi)有多少人的專業(yè)方向是計(jì)算機(jī)科學(xué)。有許多其他系的人嘲笑我們說(shuō)：“知道為什么只有你們系要加一個(gè)'科學(xué)'，而沒(méi)有'物理科學(xué)系'或'化學(xué)科學(xué)系'嗎？因?yàn)槿思沂钦娴目茖W(xué)，不需要畫(huà)蛇添足，而你們自己心虛，生怕不'科學(xué)'，才這樣欲蓋彌彰?！逼鋵?shí)，這點(diǎn)他們徹底弄錯(cuò)了。真正學(xué)懂計(jì)算機(jī)的人（不只是'編程匠”）都對(duì)數(shù)學(xué)有相當(dāng)?shù)脑煸?，既能用科學(xué)家的嚴(yán)謹(jǐn)思維來(lái)求證，也能用工程師的務(wù)實(shí)手段來(lái)解決問(wèn)題——而這種思維和手段的最佳演繹就是“算法”。記得我讀博時(shí)寫(xiě)的Othello對(duì)弈軟件獲得了世界冠軍。當(dāng)時(shí)，得第二名的人認(rèn)為我是靠?jī)e幸才打贏他，不服氣地問(wèn)我的程序平均每秒能搜索多少步棋，當(dāng)他發(fā)現(xiàn)我的軟件在搜索效率上比他快60多倍時(shí)，才徹底服輸。為什么在同樣的機(jī)器上，我可以多做60倍的工作呢？這是因?yàn)槲矣昧艘粋€(gè)最新的算法，能夠把一個(gè)指數(shù)函數(shù)轉(zhuǎn)換成四個(gè)近似的表，只要用常數(shù)時(shí)間就可得到近似的答案。在這個(gè)例子中，是否用對(duì)算法才是能否贏得世界冠軍的關(guān)鍵。還記得1988年貝爾實(shí)驗(yàn)室副總裁親自來(lái)訪問(wèn)我的學(xué)校，目的就是為了想了解為什么他們的語(yǔ)音識(shí)別系統(tǒng)比我開(kāi)發(fā)的慢幾十倍，而且，在擴(kuò)大全大詞匯系統(tǒng)后，速度差異更有幾百倍之多。他們雖然買了幾臺(tái)超級(jí)計(jì)算機(jī)，勉強(qiáng)讓系統(tǒng)跑了起來(lái)，但這么貴的計(jì)算資源讓他們的產(chǎn)品部門(mén)很反感，因?yàn)椤鞍嘿F”的技術(shù)是沒(méi)有應(yīng)用前景的。在與他們探討的過(guò)程中，我驚訝地發(fā)現(xiàn)一個(gè)O(n*m)的動(dòng)態(tài)規(guī)劃(dynamicprogramming)居然被他們做成了O(n*n*m)。更驚訝的是，他們還為此發(fā)表了不少文章，甚至為自己的算法起了一個(gè)很特別的名字，并將算法提名到一個(gè)科學(xué)會(huì)議里，希望能得到大獎(jiǎng)。當(dāng)時(shí)，貝爾實(shí)驗(yàn)室的研究員當(dāng)然絕頂聰明，但他們?nèi)际菍W(xué)數(shù)學(xué)、物理或電機(jī)出身，從未學(xué)過(guò)計(jì)算機(jī)科學(xué)或算法，才犯了這么基本的錯(cuò)誤。我想那些人以后再也不會(huì)嘲笑學(xué)計(jì)算機(jī)科學(xué)的人了吧！網(wǎng)絡(luò)時(shí)代的算法有人也許會(huì)說(shuō)：“今天計(jì)算機(jī)這么快，算法還重要嗎？”其實(shí)永遠(yuǎn)不會(huì)有太快的計(jì)算機(jī)，因?yàn)槲覀兛倳?huì)想出新的應(yīng)用。雖然在摩爾定律的作用下，計(jì)算機(jī)的計(jì)算能力每年都在飛快增長(zhǎng)，價(jià)格也在不斷下降?？晌覀儾灰?，需要處理的信息量更是呈指數(shù)級(jí)的增長(zhǎng)。現(xiàn)在每人每天都會(huì)創(chuàng)造出大量數(shù)據(jù)(照片，視頻，語(yǔ)音，文本等等)。日益先進(jìn)的紀(jì)錄和存儲(chǔ)手段使我們每個(gè)人的信息量都在爆炸式的增長(zhǎng)。互聯(lián)網(wǎng)的信息流量和日志容量也在飛快增長(zhǎng)。在科學(xué)研究方面，隨著研究手段的進(jìn)步，數(shù)據(jù)量更是達(dá)到了前所未有的程度。無(wú)論是三維圖形、海量數(shù)據(jù)處理、機(jī)器學(xué)習(xí)、語(yǔ)音識(shí)別，都需要極大的計(jì)算量。在網(wǎng)絡(luò)時(shí)代，越來(lái)越多的挑戰(zhàn)需要靠卓越的算法來(lái)解決。再舉另一個(gè)網(wǎng)絡(luò)時(shí)代的例子。在互聯(lián)網(wǎng)和手機(jī)搜索，如果要找附近的咖啡店，那么搜索引擎該怎么處理這個(gè)請(qǐng)求呢？最簡(jiǎn)單的辦法就是把整個(gè)城市的咖啡館都找出來(lái)，然后計(jì)算出它們的所在位置與你之間的距離，再進(jìn)行排序，然后返回最近的結(jié)果。但該如何計(jì)算距離呢？圖論里有不少算法可以解決這個(gè)問(wèn)題。這么做也許是最直觀的，但絕對(duì)不是最迅速的。如果一個(gè)城市只有為數(shù)不多的咖啡館，那么這么做應(yīng)該沒(méi)什么問(wèn)題，反正計(jì)算量不大。但如果一個(gè)城市里有很多咖啡館，又有很多用戶都需要類似的搜索，那么服務(wù)器所承受的壓力就大多了。在這種情況下，我們?cè)撛鯓觾?yōu)化算法呢？首先，我們可以把整個(gè)城市的咖啡館做一次“預(yù)處理”。比如，把一個(gè)城市分成若十個(gè)“格子(grid)”，然后根據(jù)用戶所在的位置把他放到某一個(gè)格子里，只對(duì)格子里的咖啡館進(jìn)行距離排序。問(wèn)題又來(lái)了，如果格子大小一樣，那么絕大多數(shù)結(jié)果都可能出現(xiàn)在市中心的一個(gè)格子里，而郊區(qū)的格子里只有極少的結(jié)果。在這種情況下，我們應(yīng)該把市中心多分出幾個(gè)格子。更進(jìn)一步，格子應(yīng)該是一個(gè)“樹(shù)結(jié)構(gòu)”，最頂層是一個(gè)大格——整個(gè)城市，然后逐層下降，格子越來(lái)越小，這樣有利于用戶進(jìn)行精確搜索——如果在最底層的格子里搜索結(jié)果不多，用戶可以逐級(jí)上升，放大搜索范圍。上述算法對(duì)咖啡館的例子很實(shí)用，但是它具有通用性嗎？答案是否定的。把咖啡館抽象一下，它是一個(gè)“點(diǎn)”，如果要搜索一個(gè)'面”該怎么辦呢？比如，用戶想去一個(gè)水庫(kù)玩，而一個(gè)水庫(kù)有好幾個(gè)入口，那么哪一個(gè)離用戶最近呢？這個(gè)時(shí)候，上述'樹(shù)結(jié)構(gòu)”就要改成“r-tree”，因?yàn)闃?shù)中間的每一個(gè)節(jié)點(diǎn)都是一個(gè)范圍，一個(gè)有邊界的范圍。通過(guò)這個(gè)小例子，我們看到，應(yīng)用程序的要求千變?nèi)f化，很多時(shí)候需要把一個(gè)復(fù)雜的問(wèn)題分解成若干簡(jiǎn)單的小問(wèn)題，然后再選用合適的算法和數(shù)據(jù)結(jié)構(gòu)。并行算法：Google的核心優(yōu)勢(shì)上面的例子在Google里就要算是小case了！每天Google的網(wǎng)站要處理十億個(gè)以上的搜索，GMail要儲(chǔ)存幾千萬(wàn)用戶的2G郵箱，GoogleEarth要讓數(shù)十萬(wàn)用戶同時(shí)在整個(gè)地球上遨游，并將合適的圖片經(jīng)過(guò)互聯(lián)網(wǎng)提交給每個(gè)用戶。如果沒(méi)有好的算法，這些應(yīng)用都無(wú)法成為現(xiàn)實(shí)。在這些的應(yīng)用中，哪怕是最基本的問(wèn)題都會(huì)給傳統(tǒng)的計(jì)算帶來(lái)很大的挑戰(zhàn)。例如，每天都有十億以上的用戶訪問(wèn)Google的網(wǎng)站，使用Google的服務(wù)，也產(chǎn)生很多很多的日志(Log)。因?yàn)長(zhǎng)og每份每秒都在飛速增加，我們必須有聰明的辦法來(lái)進(jìn)行處理。我曾經(jīng)在面試中問(wèn)過(guò)關(guān)于如何對(duì)Log進(jìn)行一些分析處理的問(wèn)題，有很多面試者的回答雖然在邏輯上正確，但是實(shí)際應(yīng)用中是幾乎不可行的。按照它們的算法，即便用上幾萬(wàn)臺(tái)機(jī)器，我們的處理速度都根不上數(shù)據(jù)產(chǎn)生的速度。那么Google是如何解決這些問(wèn)題的？首先，在網(wǎng)絡(luò)時(shí)代，就算有最好的算法，也要能在并行計(jì)算的環(huán)境下執(zhí)行。在Google的數(shù)據(jù)中心，我們使用的是超大的并行計(jì)算機(jī)。但傳統(tǒng)的并行算法運(yùn)行時(shí)，效率會(huì)在增加機(jī)器數(shù)量后迅速降低，也就是說(shuō)，十臺(tái)機(jī)器如果有五倍的效果，增加到一千臺(tái)時(shí)也許就只有幾十倍的效果。這種事半功倍的代價(jià)是沒(méi)有哪家公司可以負(fù)擔(dān)得起的。而且，在許多并行算法中，只要一個(gè)結(jié)點(diǎn)犯錯(cuò)誤，所有計(jì)算都會(huì)前功盡棄。那么Google是如何開(kāi)發(fā)出既有效率又能容錯(cuò)的并行計(jì)算的呢？Google最資深的計(jì)算機(jī)科學(xué)家JeffDean認(rèn)識(shí)到，Google所需的絕大部分?jǐn)?shù)據(jù)處理都可以歸結(jié)為一個(gè)簡(jiǎn)單的并行算法：MapandReduce(/papers/mapreduce.html)。這個(gè)算法能夠在很多種計(jì)算中達(dá)到相當(dāng)高的效率，而且是可擴(kuò)展的(也就是說(shuō)，一千臺(tái)機(jī)器就算不能達(dá)到一千倍的效果，至少也可以達(dá)到幾百倍的效果)。MapandReduce的另外一大特色是它可以利用大批廉價(jià)的機(jī)器組成功能強(qiáng)大的serverfarm。最后，它的容錯(cuò)性能異常出色，就算一個(gè)serverfarm宕掉一半，整個(gè)fram依然能夠運(yùn)行。正是因?yàn)檫@個(gè)天才的認(rèn)識(shí)，才有了MapandReduce算法。借助該算法，Google幾乎能無(wú)限地增加計(jì)算量，與日新月異的互聯(lián)網(wǎng)應(yīng)用一同成長(zhǎng)。算法并不局限于計(jì)算機(jī)和網(wǎng)絡(luò)舉一個(gè)計(jì)算機(jī)領(lǐng)域外的例子：在高能物理研究方面，很多實(shí)驗(yàn)每秒鐘都能幾個(gè)TB的數(shù)據(jù)量。但因?yàn)樘幚砟芰痛鎯?chǔ)能力的不足，科學(xué)家不得不把絕大部分未經(jīng)處理的數(shù)據(jù)丟棄掉。可大家要知道，新元素的信息很有可能就藏在我們來(lái)不及處理的數(shù)據(jù)里面。同樣的，在其他任何領(lǐng)域里，算法可以改變?nèi)祟惖纳睢＠缛祟惢虻难芯?，就可能因?yàn)樗惴ǘl(fā)明新的醫(yī)療方式。在國(guó)家安全領(lǐng)域，有效的算法可能避免下一個(gè)911的發(fā)生。在氣象方面，算法可以更好地預(yù)測(cè)未來(lái)天災(zāi)的發(fā)生，以拯救生命。所以，如果你把計(jì)算機(jī)的發(fā)展放到應(yīng)用和數(shù)據(jù)飛速增長(zhǎng)的大環(huán)境下，你一定會(huì)發(fā)現(xiàn)；算法的重要性不是在日益減小，而是在日益加強(qiáng)。 轉(zhuǎn)自計(jì)算機(jī)科學(xué)論壇注:算法是計(jì)算機(jī)科學(xué)的核心，是程序的靈魂，它的基礎(chǔ)性地位遍布計(jì)算機(jī)科學(xué)的各個(gè)分支領(lǐng)域.原文作者介紹：李開(kāi)復(fù)博士現(xiàn)google中國(guó)總裁1998年7月加盟微軟，當(dāng)年11月出任微軟中國(guó)研究院（現(xiàn)微軟亞洲研究院）院長(zhǎng)。李開(kāi)復(fù)在語(yǔ)音識(shí)別、人工智能、三維圖形及網(wǎng)絡(luò)多媒體等領(lǐng)域享有很高的聲譽(yù)。在他的帶領(lǐng)下，微軟中國(guó)研究院以新一代多媒體、新一代用戶界面和新一代信息處理技術(shù)為主要方向開(kāi)展基礎(chǔ)研究。后升任微軟副總裁。加盟微軟公司前，李博士曾擔(dān)任SGI公司的多媒體軟件子公司——CosmoSoftware的總裁，負(fù)責(zé)多平臺(tái)、互聯(lián)網(wǎng)三維圖形和多媒體軟件方面的研發(fā)工作。此前他還曾在蘋(píng)果公司工作了六年，主管該公司的多媒體部門(mén)。李博士在蘋(píng)果公司任職六年中的最后一個(gè)職務(wù)是其交互式多媒體部門(mén)的副總裁，他們后來(lái)開(kāi)發(fā)出QuickTime，QuickDraw3D，QuickTimeVR等產(chǎn)品。在加入蘋(píng)果公司之前，李博士曾就讀于美國(guó)卡內(nèi)基梅隆大學(xué)，獲計(jì)算機(jī)科學(xué)博士學(xué)位。后擔(dān)任副教授。在他的博士課題研究工作中，首次創(chuàng)造性的提出基于統(tǒng)計(jì)學(xué)的語(yǔ)音識(shí)別方法，并在此基礎(chǔ)上開(kāi)發(fā)出了世界上第一個(gè)“非特定人連續(xù)語(yǔ)音識(shí)別”系統(tǒng)，使識(shí)別率由原來(lái)的百分之三十提高到百分之九十六，該方法今天已成為計(jì)算機(jī)語(yǔ)音識(shí)別的技術(shù)主流，也奠定了李博士在該領(lǐng)域的權(quán)威地位。1988年，商業(yè)周刊授予該系統(tǒng)“最重要科學(xué)創(chuàng)新獎(jiǎng)”。在校期間，李博士還開(kāi)發(fā)了“奧賽羅”人機(jī)對(duì)弈系統(tǒng)，因?yàn)樵?988年擊敗了國(guó)際象棋世界冠軍而名噪一時(shí)。李開(kāi)復(fù)同時(shí)還是美國(guó)電氣電子工程協(xié)會(huì)的院士。常用算法&數(shù)據(jù)結(jié)構(gòu)浙江大學(xué)微軟技術(shù)俱樂(lè)部彭鵬ACM競(jìng)賽競(jìng)賽中常見(jiàn)的16種題型3,競(jìng)賽中基本的數(shù)據(jù)結(jié)構(gòu)與算法時(shí)空復(fù)雜度的分析0,如何建立一支強(qiáng)隊(duì)如何建立一支強(qiáng)隊(duì)個(gè)人的能力理論（幾何，數(shù)論，動(dòng)態(tài)規(guī)劃，圖論等）技術(shù)（編程）隊(duì)員能力上的互補(bǔ)某論壇，一無(wú)聊男yy的中國(guó)"夢(mèng)之隊(duì)"錢文杰（）反應(yīng)奇快，擅長(zhǎng)隨機(jī)化，貪心,NOI貪心王劉汝佳or吳嘉之見(jiàn)多識(shí)廣,做過(guò)的題必別人見(jiàn)過(guò)的題多趙爽上海交大的"割題手"一支強(qiáng)隊(duì)需要的角色Leader/Coordinato（協(xié)調(diào)比賽進(jìn)程）Reader（發(fā)現(xiàn)題目隱諱的涵義）Thinker（邏輯能力強(qiáng)，收集其他隊(duì)員意見(jiàn)）Programmer/Debugger（反應(yīng)快/穩(wěn),細(xì)心）Helper（協(xié)助比賽，查錯(cuò)，驗(yàn)證數(shù)據(jù)等）參考書(shū)籍主要參考書(shū)籍《C++Primer》《C++標(biāo)準(zhǔn)程序庫(kù)》《算法導(dǎo)論》《算法藝術(shù)與信息學(xué)競(jìng)賽》《組合數(shù)學(xué)》《計(jì)算幾何》歷屆國(guó)家集訓(xùn)隊(duì)論文時(shí)空復(fù)雜度的分析時(shí)間復(fù)雜度的分析空間復(fù)雜度的分析函數(shù)增長(zhǎng)和運(yùn)行時(shí)間引用劉汝佳《序列和字符串》常見(jiàn)題型DynamicProgramming（動(dòng)態(tài)規(guī)劃）Greedy（貪心）CompleteSearch（窮舉）FloodFill（種子填充）常見(jiàn)題型ShortestPath（最短路徑）RecursiveSearchTechniques（回溯）MinimumSpanningTree（最小生成樹(shù)）Knapsack（背包）常見(jiàn)題型ComputationalGeometry（計(jì)算幾何）NetworkFlow（網(wǎng)絡(luò)流）EulerianPath（歐拉回路）Two-DimensionalConvexHull（二維凸包）常見(jiàn)題型BigNums（大數(shù)）HeuristicSearch（啟發(fā)式搜索）ApproximateSearch（近似搜索）AdHocProblems（雜題）枚舉法又叫窮舉法，它利用了計(jì)算機(jī)計(jì)算速度快且準(zhǔn)確的特點(diǎn)，是最為樸素和有效的一種算法.不是辦法的辦法但有時(shí)卻是最好的辦法PizzaAnyone(ZOJ1219)題目大意：你需要為你和你的朋友們訂一個(gè)皮薩.每個(gè)朋友都會(huì)告訴你他們想和不想放進(jìn)皮薩里的東西.你是否能訂一個(gè)皮薩，讓他滿足每個(gè)人至少一個(gè)條件.假設(shè)一共有16種東西可以放進(jìn)皮薩.是個(gè)對(duì)計(jì)算機(jī)很小的數(shù)貪心法(Greedy)矩陣胚理論(詳情請(qǐng)參考算法導(dǎo)論)枚舉法的時(shí)間效率很低,貪心法恰恰與其相反.并且貪心法的程序也很好實(shí)現(xiàn).無(wú)數(shù)論文都指責(zé)貪心法往往得不到問(wèn)題的最優(yōu)解.絕世高手與普通高手的差距所在.棧和隊(duì)列棧:后進(jìn)先出(LIFO)隊(duì)列:先進(jìn)先出(FIFO)字符串的輸入與輸出或chars[100];scanf("%s",s);stringa(s);Stringa;cin>>a;C++常用頭文件字符串的讀入哪種讀入更快在輸入數(shù)據(jù)達(dá)到1M時(shí),cin,cout將比scanf,printf在速度上有明顯的劣勢(shì)排序排序的種類：交換排序，選擇排序，插入排序,堆排序希爾排序，快速排序，歸并排序,桶排序用C++實(shí)現(xiàn)排序#include數(shù)組asort(a,a+5);vectorasort(a.begin(),a.end());并查集并查集是一種樹(shù)型的數(shù)據(jù)結(jié)構(gòu),用于處理一些不相交集合的合并問(wèn)題.并查集的主要操作有合并兩個(gè)不相交集合判斷兩個(gè)元素是否屬于同一個(gè)集合路徑壓縮Parity(ceoi99)有一個(gè)01序列，長(zhǎng)度＜=1000000000，現(xiàn)在有n條信息，每條信息的形式是-abeven/odd.表示第a位到第b位元素之間的元素總和是偶數(shù)/奇數(shù).你的任務(wù)是對(duì)于這些給定的信息，輸出第一個(gè)不正確的信息所在位置-1.信息的數(shù)目不超過(guò)5000.如果信息全部正確,即可以找到一個(gè)滿足要求的01序列，那么輸出n.Parity(ceoi99)從整個(gè)01序列肯定是無(wú)法入手的，因?yàn)樗拈L(zhǎng)度高達(dá)109.從范圍比較小的n入手.也就是說(shuō)我們需要對(duì)信息進(jìn)行一些特殊的處理.abeven/odd,那么將元素b指向a-1，邊的權(quán)值是even/odd.下面我們由樣例來(lái)說(shuō)明一下這個(gè)處理方法.Parity(ceoi99)(肖天)建立sum數(shù)組,sum[i]表示從1到i之和是奇(true)還是偶(false),sum[0]=false.這樣題目中給的任意問(wèn)題(a,b)的答案都可以用sum[b]xorsum[a-1]表示.開(kāi)始我們并不知道sum[1..n]的值，不妨設(shè)為false，這時(shí)任意sum[a],sum[b]都是獨(dú)立的.對(duì)于每對(duì)問(wèn)答（a,b,c），都可以知道sum[b]xorsum[a-1]=c，由此把sum[b]和sum[a-1]聯(lián)系起來(lái).這步操作可以用并查集完成，對(duì)于問(wèn)答（a,b,c）如果sum[a-1],sum[b]不屬于一個(gè)集合就把它們并起來(lái)，否則如果sum[a-1]xorsum[b]不等于c則說(shuō)明出現(xiàn)矛盾,輸出總句數(shù),退出.對(duì)于不出現(xiàn)矛盾的sum數(shù)組,對(duì)于每個(gè)集合分為兩個(gè)部分，我們指定其中一個(gè)部分為true，另一個(gè)部分為false，則可以確定sum數(shù)組，利用sum[i]xorsum[i-1]可以求出第i位的數(shù)字，由于不同集合之間沒(méi)有問(wèn)答出現(xiàn)，所以此數(shù)列是一可行解，證明算法正確.堆（優(yōu)先隊(duì)列）優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單動(dòng)態(tài)維護(hù)一組數(shù)據(jù)中最?。ù螅┑囊粋€(gè)數(shù)組維護(hù)例題：積水一個(gè)長(zhǎng)方形網(wǎng)格包含了n*m塊地,每塊地上面有1個(gè)長(zhǎng)方體.每一個(gè)長(zhǎng)方形蓋住了一塊地，地的面積是1平方英寸.相鄰的地上的長(zhǎng)方體之間沒(méi)有空隙.一場(chǎng)大雨降臨了這個(gè)建筑物,在建筑物的某些區(qū)域有積水產(chǎn)生.給各方格高度，求積水總量分析定義每塊地上的長(zhǎng)方體的高度稱為原始高度積滿水時(shí)的水面高度稱為積水高度（高于積水高度的水一定會(huì)流走,低于積水高度的水一定流不走）積水高度與原始高度之差為積水深度如果一個(gè)長(zhǎng)方體上不可能有積水,那么它的積水高度就等于它的原始高度.最外圈不能積水，積水高度等于原始高度分析由外而內(nèi)計(jì)算.每次選取外圍的格子中積水高度最低的一個(gè)格子4考慮它周圍所有在網(wǎng)格內(nèi)部的格子y想象不斷的往x和y里注水，但是x的積水高度固定(想象該高度處有一個(gè)小孔),因此如果y的原始高度不小于x的積水高度，那么它的積水高度就是它的原始高度如果y的原始高度小于x的積水高度，那么它的積水高度就等于x的積水高度每次用堆取出x進(jìn)行計(jì)算,O(mnlogmn).哈希表(Hash)理論上查找速度最快的數(shù)據(jù)結(jié)構(gòu)之一缺點(diǎn)：需要大量的內(nèi)存需要構(gòu)造KeyHash表的實(shí)現(xiàn)數(shù)組沖突解決法開(kāi)散列法閉散列法C++sgistl實(shí)現(xiàn)HashKey的選取數(shù)值：方法一:直接取余數(shù)(一般選取質(zhì)數(shù)M最為除數(shù))方法二:平方取中法,即計(jì)算關(guān)鍵值的平方，再取中間［位形成一個(gè)大小為的表是多少字符串：intELFhash(char*key){unsignedinth=0;while(*key){h=(h<>24;h&=-g；}returnh%M;}方法二:ELFhash函數(shù)方法一：折疊法:即把所有字符的ASCII碼加起來(lái)二分搜索樹(shù)普通的二分搜索樹(shù)時(shí)間復(fù)雜度：缺點(diǎn)：容易出現(xiàn)不平衡的情況AVLTree,Splaytree,紅黑樹(shù)樹(shù)堆(Treap)Treap=Tree+heap每次插入/刪除結(jié)點(diǎn)的時(shí)候,給結(jié)點(diǎn)隨機(jī)分配一個(gè)優(yōu)先級(jí)，讓Treap關(guān)于優(yōu)先級(jí)形成一個(gè)堆的同時(shí)，關(guān)于關(guān)鍵碼形成BST跳躍表,B樹(shù)跳躍表(Skiplists)線段樹(shù)在一類問(wèn)題中，我們需要經(jīng)常處理可以映射在一個(gè)坐標(biāo)軸上的一些固定線段，例如說(shuō)映射在OX軸上的線段.由于線段是可以互相覆蓋的，有時(shí)需要?jiǎng)討B(tài)地取線段的并，例如取得并區(qū)間的總長(zhǎng)度，或者并區(qū)間的個(gè)數(shù)等等.一個(gè)線段是對(duì)應(yīng)于一個(gè)區(qū)間的，因此線段樹(shù)也可以叫做區(qū)間樹(shù).Atlantis(ZOJ1128)一個(gè)平面被很多矩形覆蓋,矩形之間會(huì)相互疊加.輸出矩形覆蓋的總面積.Atlantis(ZOJ1128)線段樹(shù)矩形切割矩形切割字典樹(shù)(Trie)當(dāng)關(guān)鍵字是串的時(shí)候，理論上查找最快的數(shù)據(jù)結(jié)構(gòu)定義:保存字符串用的樹(shù)型數(shù)據(jù)結(jié)構(gòu)(多叉樹(shù))，其中每個(gè)節(jié)點(diǎn)表示一個(gè)公共前綴，單詞信息保存在相應(yīng)的頁(yè)節(jié)點(diǎn)里面.給如下幾個(gè)單詞，構(gòu)造的單詞樹(shù)：An,Ant,All,AllotAlloy,Aloe,Are,Atebe版權(quán)歸浙江大學(xué)ACM領(lǐng)隊(duì)徐串所有轉(zhuǎn)載需保留此字樣T9(ZOJ1038)題目描述:手機(jī)有智能英文輸入法，他根據(jù)自己已有的詞匯表，即使你每個(gè)數(shù)字只按一次也可以猜出你要按的是哪個(gè)單詞(方法就是從所有可能的串中選出出現(xiàn)概率最高的一個(gè)).詞匯表：hell3hello4idea8next8super3按435561是的響應(yīng)顯示iidhelhellhello動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃的時(shí)間效率極高.動(dòng)態(tài)規(guī)劃的算法簡(jiǎn)潔，一般只用邊界和狀態(tài)轉(zhuǎn)移方程就可清晰地表示出進(jìn)行規(guī)劃的步驟;而因?yàn)橛辛诉@些用數(shù)學(xué)語(yǔ)言描述的天然材料，編程也較為方便.最重要的一點(diǎn):動(dòng)態(tài)規(guī)劃不單是一種思想，也不單是一類算法，它是思想方法和具體算法的混合物.摘自徐靜《動(dòng)態(tài)規(guī)劃的算法與實(shí)現(xiàn)》動(dòng)態(tài)規(guī)劃無(wú)后效性遞推法和記憶化搜索深度優(yōu)先搜索(DFS)按照深度優(yōu)先的順序遍歷狀態(tài)空間，通常用遞歸或者棧來(lái)實(shí)現(xiàn).voiddfs(state,depth){if(state==結(jié)束狀態(tài))退出；枚舉所有可行狀態(tài){更新全局變量；dfs(newstate,depth+1);還原全局變量}}寬度優(yōu)先搜索(BFS)如果代價(jià)和搜索樹(shù)深度成正比,那么可以通過(guò)廣度優(yōu)先搜索得到解.由于空間占用大,BFS用處不是很廣，一般只用在路徑尋找問(wèn)題中，但是一旦使用,將比深度優(yōu)先搜括看得多雙向?qū)挾葍?yōu)先搜索深度優(yōu)先和寬度優(yōu)先搜索比較PrimeRingProblem(ZOJ1457)Aringiscomposeofncirclesasshownindiagram.Putnaturalnumber1,2,...,nintoeachcircleseparately,andthesumofnumbersintwoadjacentcirclesshouldbeaprime.Note:thenumberoffirstcircleshouldalwaysbe1.n(0<n<20)while(!deque.empty()){state=deque[0];deque.pop();枚舉所有可行狀態(tài){tempstate=狀態(tài)改變(state);deque.push_back(tempstate);}}寬度優(yōu)先搜索(BFS)寬度優(yōu)先搜索的框架Winlinez(ZOJ1591)Nowwehaveaboardof9*9grids,onwhichthereareseveralbeads.Thesebeadshaveonlysevencolors,wenumberthem1-7.Wedefinetheemptygridtobezero.Eachturnyoucanmoveanybeadontheboardtothedestinationwherethereisaroutebetweenthem.Theroutemeansthatthebeadcanmoveup,down,leftorrighttotheadjacentemptygridandmaygoonuntilitreachesthedestination.Afterthemoving,iftherearefiveormoresame-coloredbeadsinaline(row,column,diagonal),theywillallbeeliminated.博弈問(wèn)題給定一個(gè)有向無(wú)環(huán)圖(X,F),其中X是一個(gè)非空的點(diǎn)集(每個(gè)點(diǎn)表示一個(gè)位置),F是一個(gè)在集合X上的函數(shù)，對(duì)于集合X中的任意一個(gè)元素x,F(x)返回一個(gè)集合X的子集，即,F(x)表示了由一個(gè)位置x可以到達(dá)的位置.如果F(x)是空集，則稱x是一個(gè)結(jié)束位置.現(xiàn)在兩個(gè)人在這樣的一個(gè)有向圖上玩游戲，首先在一個(gè)初始位置x0上放置了一個(gè)棋子，然后他們將按照如下規(guī)則進(jìn)行游戲：首先由選于I從初始位置x0進(jìn)行移動(dòng).兩個(gè)選手交替移動(dòng).在一個(gè)位置x,選手可以將棋子移到位置y上，其中yex.如果輪到某一個(gè)選手移動(dòng)時(shí)棋子處在一個(gè)結(jié)束位置,那么這個(gè)選手就會(huì)因?yàn)闊o(wú)法繼續(xù)移動(dòng)棋子而被判輸?shù)暨@局游戲.對(duì)于給定的有向圖和初始位置，請(qǐng)你判斷出選手I與選于II誰(shuí)會(huì)獲勝.樓天城《淺談一類博弈問(wèn)題的解法》局面Max局面Min局面終結(jié)局面局面估價(jià)函數(shù)Alpha-Beta剪枝AMultiplicationGame(ZOJ1893)Stan和Ollie一起做游戲.游戲的內(nèi)容是將一個(gè)整數(shù)p乘上2到9中的任一個(gè)數(shù).Stan總是從p=1開(kāi)始,然后兩個(gè)人交替相乘.在游戲開(kāi)始前,兩個(gè)人訂了一個(gè)數(shù)n(1<N最大公約數(shù)最小公倍數(shù)歐幾里得輾轉(zhuǎn)相除intgcd(inta,intb){returnbgcd(b,a%b):a;}intlcm(inta,intb){returna/gcd(a,b)*b;}篩選法求質(zhì)數(shù)表Eratosthenes(埃拉托色尼)篩選法：每次求出一個(gè)新的素?cái)?shù)，就把n以內(nèi)的它的所有倍數(shù)都篩去.在實(shí)現(xiàn)的時(shí)候,對(duì)于-個(gè)素?cái)?shù)p,只需要篩去等就可以了，因?yàn)橐呀?jīng)在q的第一個(gè)素因子被找到的時(shí)候被篩去了#defineN100#defineM100intp[M],plist=0;intinit(){memset(p,0,sizeof(p));for(inti=2;i<=N;i++)if(!p[i]){p[plist++]=i;intdel=i*i;while(dela[i+1]&&i>=0)i--;if(i<0)return0;for(Min=i+1,j=i+2;ja[i]&&a[j]<a[Min])Min=j;swap(a[i],a[Min]);for(intj=i+1;j<n;j++)for(intk=j+1;ka[k])swap(a[j],a[k]);return1;}Catalan數(shù)將正n邊形用對(duì)角線剖分成三角形的方法數(shù)通項(xiàng)公式Fibonacci數(shù)Fibonacci數(shù)的O(lgn)實(shí)現(xiàn)彩票大街上到處在賣彩票，一元錢一張.購(gòu)買撕開(kāi)它上面的錫箔,你會(huì)看到一個(gè)漂亮的圖案.圖案有n種，如果你收集到所有n種彩票，就可以得大獎(jiǎng).請(qǐng)問(wèn)，在平均情況下,需要買多少?gòu)埐势辈拍艿玫酱螵?jiǎng)呢分析總結(jié)已有0個(gè)圖案：拿1次就可以多搜集一個(gè)已有1個(gè)圖案：平均拿n/(n-1)次就可多搜集一個(gè)已有k個(gè)圖案：平均拿n/(n-k)次就可多搜集一個(gè)所以總次數(shù)為:n(1+1/2+1/3+???+1/n)數(shù)值分析定積分計(jì)算(Romberg)多項(xiàng)式求根(牛頓法)線形方程組(高斯消元法)生成樹(shù)問(wèn)題最小生成樹(shù)(MST)最大生成樹(shù)Prim算法Kruskal算法兩種算法的使用范圍最短路問(wèn)題單源最短路徑問(wèn)題Dijkstra多源最短路徑問(wèn)題Floyd-WarshallBellman-ford第n短路徑第二最短路徑:枚舉最短路徑上的每條邊,每次刪除一條，然后求新圖的最短路徑，取這些圖的最短路徑.最短的一條即為第二最短路徑第n最短路徑可以在求解第n-1最短路徑的基礎(chǔ)上求解Arbitrage(ZOJ1092)題目大意：有很多很多種貨幣，每?jī)煞N貨幣之間都有一個(gè)匯率，問(wèn)是否能找到一種套匯()的方法網(wǎng)絡(luò)流問(wèn)題特點(diǎn)：較高的編程復(fù)雜度較死板的構(gòu)造方法1.較廣的使用范圍由于后面的兩個(gè)特點(diǎn)，網(wǎng)絡(luò)流算法已經(jīng)逐步淡出了高中信息學(xué)舞臺(tái).但在ACM/ICPC競(jìng)賽中，網(wǎng)絡(luò)流算法仍占據(jù)著一席之地網(wǎng)絡(luò)流模型若有向圖G=(V,E)滿足下列條件：有且僅有一個(gè)頂點(diǎn)S,它的入度為零，即d-(S)=0,這個(gè)頂點(diǎn)S便稱為源點(diǎn)，或稱為發(fā)點(diǎn)八、\?有且僅有一個(gè)頂點(diǎn)T,它的出度為零，即d+(T)=0,這個(gè)頂點(diǎn)T便稱為匯點(diǎn),或稱為收點(diǎn).每一條弧都有非負(fù)數(shù)，叫做該邊的容量.邊(vi,vj)的容量用cij表示.則稱之為網(wǎng)絡(luò)流圖，記為G=(V,E,C)最大流最大流的定義求有向帶權(quán)圖G=(V,E,C)的一個(gè)流,它滿足容量限制條件，且原點(diǎn)提供的流量最大最大流解法Ford-FulkersonmethodPush-relabelalgorithmRelabel-to-frontalgorithm算法導(dǎo)論第26章最小費(fèi)用最大流給定網(wǎng)絡(luò)G=(V,E,C,W),求網(wǎng)絡(luò)上的一個(gè)流f,使得f是網(wǎng)絡(luò)的最大流,且每條弧的流量與費(fèi)用的乘積加起來(lái)的總合帶上下界的最小費(fèi)用最大流最小費(fèi)用路算法消圈算法網(wǎng)絡(luò)流算法(金愷)難點(diǎn):網(wǎng)絡(luò)流在具體問(wèn)題中的應(yīng)用，最具挑戰(zhàn)性的部分是模型的構(gòu)造，其次是算法的優(yōu)化.構(gòu)造沒(méi)有現(xiàn)成的模式可依，只能根據(jù)題目的具體條件來(lái)分析.這需要對(duì)各種網(wǎng)絡(luò)流的性質(zhì)了如指掌，并且歸納總結(jié)一些經(jīng)驗(yàn),發(fā)揮我們的創(chuàng)造性.一般來(lái)說(shuō),用得最多的方法是拆點(diǎn)法.優(yōu)化是算法的重要環(huán)節(jié)，它并非朝夕之功就能提高的,必須靠經(jīng)驗(yàn)的積累.二分圖匹配問(wèn)題二分圖是一類很重要的圖,它的頂點(diǎn)可以分成兩個(gè)集合X和Y,圖的所有邊一定是有一個(gè)頂點(diǎn)屬于集合X,另一個(gè)頂點(diǎn)屬于集合Y.二分圖的最大匹配同類結(jié)點(diǎn)不鄰接.圖的一個(gè)匹配是一些邊的集合，任意兩條邊沒(méi)有公共端點(diǎn).圖中包含邊數(shù)最多的匹配稱為圖的最大匹配匈牙利算法網(wǎng)絡(luò)流解法(Hopcroft)二分圖的最小覆蓋定理:二分圖中點(diǎn)對(duì)邊的最小覆蓋等于其最大匹配數(shù).M個(gè)是足夠的.只需要讓它們覆蓋最大匹配的M條邊,則其它邊一定被覆蓋(如果有邊e不被覆蓋，把e加入后得到一個(gè)更大的匹配)M個(gè)是必須的.僅考慮形成最大匹配的這M條邊，由于它們兩兩個(gè)無(wú)公共點(diǎn)，因此至少需要M個(gè)點(diǎn)才能把它們覆蓋二分圖的匹配二分圖的最佳匹配二分圖的完美匹配二分圖的完備匹配穩(wěn)定婚姻問(wèn)題獨(dú)立集考慮圖G=(V,E).S是V的一個(gè)子集,如果在S中任意兩個(gè)頂點(diǎn)在G中都不是鄰接的，那么S就是G的一個(gè)獨(dú)立集.如果在G中不存在具有IS1I〉ISI，則稱S為G的最大獨(dú)立集誘導(dǎo)子圖頂點(diǎn)-導(dǎo)出子圖另V1是圖G=(V,E)的頂點(diǎn)集V的子集，如果E1是E的子集，且邊(vi,vj)屬于E1,當(dāng)且僅當(dāng)vi和vj屬于V1,那么子圖G1=(V1,E1)就叫做G在頂點(diǎn)集V1上的導(dǎo)出子圖.如果vi和vj屬于V1,那么E中任何一條以vi和vj為端點(diǎn)的邊都屬于E1弦圖定理:如果一個(gè)圖的任何誘導(dǎo)子圖都不是K階環(huán)(K>=4),那么該圖稱為弦圖FishingNet(ZOJ1015)判斷一個(gè)圖是否是弦圖計(jì)算幾何判兩條線斷相交判點(diǎn)在多邊性內(nèi)部二維凸包叉乘OJ是什么OnlineJudge的簡(jiǎn)稱一種通過(guò)網(wǎng)絡(luò)信息交互在線判題的系統(tǒng)它模擬了ICPC比賽真實(shí)的情況當(dāng)前世界上規(guī)模比較大的OJUVAZOJURALUSACOZhejianguniversityonlinejudge推薦使用：gcc+vivs2003/vs2005SubmissionError--提交使用了不正確的隊(duì)名，題號(hào)等.NoSuchProblem--檢查題號(hào)有沒(méi)有填錯(cuò)CompileError--程序不能通過(guò)編譯.RunTimeError--程序運(yùn)行過(guò)程中出現(xiàn)非正常中斷.Memory