C語言基礎，簡單數據結構，

ACM入門講座

搜索部分Bjut：mark0632010.10.301C語言是什么forwhileif…else…switch,case函數調用變量，數組，結構體聲明&,*,->,||,&&,==,++,+=輸入輸出scanf,printf,freopen(“in.txt”,”r”,stdin);2ACM/ICPCACM-ICPC以團隊的形式代表各學校參賽，每隊由3名隊員組成。每位隊員必須是在校學生，有一定的年齡限制，并且最多可以參加2次全球總決賽和5次區域選拔賽。比賽期間，每隊使用1臺電腦需要在5個小時內使用C、C++或Java中的一種編寫程序解決7到10個問題。程序完成之后提交裁判運行，運行的結果會判定為正確或錯誤兩種3其他比賽Topcoder，Codeforces平均每周一次，還定期有其他形式的比賽，要求快速準確的構造算法寫代碼能力有道難題，百度之星，每年5，6月份數學建模，校內賽4，5月，全國9月4參考書目圖書館有關acm的書網上OJ5天津賽區哈爾濱賽區6POJ2027NoBrainerTimeLimit:1000MSMemoryLimit:30000KTotalSubmissions:15196Accepted:10314DescriptionZombieslovetoeatbrains.Yum.InputThefirstlinecontainsasingleintegernindicatingthenumberofdatasets.

Thefollowingnlineseachrepresentadataset.Eachdatasetwillbeformattedaccordingtothefollowingdescription:

Asingledatasetconsistsofaline"XY",whereXisthenumberofbrainsthezombieeatsandYisthenumberofbrainsthezombierequirestostayalive.OutputForeachdataset,therewillbeexactlyonelineofoutput.Thislinewillbe"MMMBRAINS"ifthenumberofbrainsthezombieeatsisgreaterthanorequaltothenumberofbrainsthezombierequirestostayalive.Otherwise,thelinewillbe"NOBRAINS".SampleInput3453343SampleOutputNOBRAINSMMMBRAINSMMMBRAINS7DescriptionZombieslovetoeatbrains.Yum.InputThefirstlinecontainsasingleintegernindicatingthenumberofdatasets.

Thefollowingnlineseachrepresentadataset.Eachdatasetwillbeformattedaccordingtothefollowingdescription:

Asingledatasetconsistsofaline"XY",whereXisthenumberofbrainsthezombieeatsandYisthenumberofbrainsthezombierequirestostayalive.OutputForeachdataset,therewillbeexactlyonelineofoutput.Thislinewillbe"MMMBRAINS"ifthenumberofbrainsthezombieeatsisgreaterthanorequaltothenumberofbrainsthezombierequirestostayalive.Otherwise,thelinewillbe"NOBRAINS".8ACM題型分類1，基本算法2，圖算法3，數據結構4，搜索5，動態規劃6，貪心7，數學8，計算幾何9，模擬9搜索概論搜索被稱為“通用解題法”，在算法和人工智能中占據重要地位。但由于它巨大的局限性和自身靈活性，也被認為是最難學難用的算法之一。本節目標：希望同學們對于任意一個問題，

1.很快建立狀態空間 2.提出一個合理算法 3.簡單估計時空性能10搜索分類盲目搜索：按預定的控制策略進行搜索，在搜索過程中獲得的中間信息不用來改進控制策略。啟發式搜索：在搜索中加入了與問題有關的啟發性信息，用以指導搜索朝著最有希望的方向發展，加速問題的求解過程并找到最優解。11搜索算法盲目搜索：1.廣度優先搜索（BreadthFirstSearch）2.深度優先搜索（DepthFirstSearch）3.純隨機搜索、重復式搜索、迭代加深搜索、迭代加寬搜索、柱型搜索啟發式搜索：1.A*算法2.IDA*算法12DFS&BFS深搜例子：走迷宮，你沒有辦法用分身術來站在每個走過的位置。不撞南山不回頭。廣搜例子:你的眼鏡掉在地上以后，你趴在地板上找。你總是先摸最接近你的地方，如果沒有，再摸遠一點的地方……13狀態空間明確以下概念：狀態：問題在某一時刻進展狀況的數學描述。狀態轉移：問題從一種狀態到另一種或幾種狀態的操作。狀態空間：一個“圖”，圖結點對應于狀態，點之間的邊對應于狀態轉移。搜索：尋找一種可行的操作序列，從起始狀態經過一系列狀態轉移，達到目標狀態。14搜索基礎搜索是常人最容易想到的解題辦法，可以說所有題都可以用搜索解決，但是沒有剪枝搜索可以看成是窮舉法，時間上無法忍受158皇后問題給定8*8棋盤，要在上邊放子，要求各棋子在同一行，同一列，同

一斜邊上不能有兩個或兩個以上的子，找到所有的放子方法，并輸出放子過程與種類數。16深搜：可運行代碼在備注中17

一個從起始狀態到達目標狀態包含多步操作，而每一步操作又有幾種可能，只有正確的操作才能達到目標（如八皇后問題），這樣的問題可以看做是一個樹。

如果按照1-2-4-5-3-6-7的順序，叫深度優先(DFS)

如果按照1-2-3-4-5-6-7的順序，叫廣度優先(BFS)1234567概述18voidDFS(intk)//處理第k步{if(k==n)//已經處理到第n步，到達目的狀態

輸出結果

else//處理第k步

for(inti=1;i<=m;i++)//第k步中有m種可能

{處理第k步

DFS(k+1)；//進入第k+1步

}}深度優先(DFS)模板：19幫助小明小明參加一個搶東西的電視節目。這個節目很有意思，一共有n個東西可以拿(n<50)每個參加活動的人不能拿重量超過m(m<2000)的東西，而每個東西都有它的價值v，有的高有的低，幫助小明安排要拿的東西，使總價值最高。輸入 512

35 46 53 89 108 00樣例輸出：1520幫助小明這是一個0-1背包問題。對于每件物品，有兩種選擇：1）拿這件物品（條件是最大重量不超過m）2）不拿這件物品下面程序給出0-1背包的dfs解法，效率無法忍受，但是理解簡單。下一次會介紹動態規劃的0-1背包解法效率會提升很大（備注中給出0-1背包動態規劃解法）。2122POJ1088滑雪Michael喜歡滑雪百這并不奇怪，因為滑雪的確很刺激。可是為了獲得速度，滑的區域必須向下傾斜，而且當你滑到坡底，你不得不再次走上坡或者等待升降機來載你。Michael想知道載一個區域中最長底滑坡。區域由一個二維數組給出。數組的每個數字代表點的高度。下面是一個例子

12345

161718196

152425207

142322218

131211109

一個人可以從某個點滑向上下左右相鄰四個點之一，當且僅當高度減小。在上面的例子中，一條可滑行的滑坡為24-17-16-1。當然25-24-23-...-3-2-1更長。事實上，這是最長的一條。23POJ1088滑雪Input輸入的第一行表示區域的行數R和列數C(1<=R,C<=100)。下面是R行，每行有C個整數，代表高度h，0<=h<=10000。Output輸出最長區域的長度。24這個搜的重復的過程太多了，交到OJ上給個TLE25記憶化搜索26BFS廣搜例子:你的眼鏡掉在地上以后，你趴在地板上找。你總是先摸最接近你的地方，如果沒有，再摸遠一點的地方……27BFS程序基本結構定義一個隊列;起始點加入隊列;while(隊列不空){取出隊頭結點;若它是所求的目標狀態,跳出循環;否則，從它擴展出子結點,全都添到隊尾;}若循環中找到目標,輸出結果;否則輸出無解;28POJ2243KnightMoves國際象棋棋盤上有一個馬，要從起點跳到指定目標，最少跳幾步？輸入：a1h8輸出：Togetfroma1toh8takes6knightmoves.

abcdefgh12345678h8a129跳馬規則abcdefgh12345678在2×3的矩形里：30例如：從a1到e4當目標出現在所擴展出的結點里，結果就找到了。Togetfroma1toe4takes3knightmoves.

abcdefgh1234567803321322312332233323333333233332313233雙向BFSabcdefgh123456780212212122211112012從起點、終點同時開始雙向BFS,有效地提高了時空效率。從起點找2步能跳到的點從終點找1步能跳到的點34POJ1745Divisibility輸入N、K,然后輸入N個整數，N個整數可列出若干加減運算式；若存在一個算式，它的值能被K整除,輸出“Divisible”，否則輸出“Notdivisible”.輸入：247

175-211545

175-2115輸出：Divisible

Notdivisible35{17，5，-21，15}1755-21-21-21-211515151515151515+++17+5+-21+15++++-------17-5+-21-1536最壞情況N=10000，二叉樹有10000層，結點總數210000-1。不可能枚舉所有表達式本題的目標：判斷葉子結點上是否有值能被k整除=>判斷是否有值，除以k的余數為零。計算中間值取余，不影響結果。

(a+b)%k=(a%k+b%k)%k因此只需記錄對k的余數。2<=k<=100，每層結點最多100個，不是指數級增加。3747175-2115每層最多7個結點(定義數組)：首先加入起點，17%7=3擴展第2層結點(3+5)%7=1(3–5+7)%7=51234560+-擴展第3層結點(1+-21)%7=1(1–-21)%7=1(5+-21)%7=5(5–

-21)%7=51234560擴展