【文章內(nèi)容簡介】 .................................... 25 1121 最短路徑★ ........................................................................................................... 25 1123 球鐘 ...................................................................................................................... 25 1124 回文數(shù) II .............................................................................................................. 26 1125 愷撒的規(guī)劃 ........................................................................................................... 26 1128 控制棋 .................................................................................................................. 26 1133 Billiard★ ................................................................................................................ 26 1134 One Person The Price is Right★ ............................................................................. 26 1136 Factoring Large Numbers .......................................................................................... 27 1138 Wall ....................................................................................................................... 27 1139 Flip Game★ ........................................................................................................... 27 1140 Buffer Manager ....................................................................................................... 27 1142 Binary Search .......................................................................................................... 27 1145 Disk Tree★ ............................................................................................................. 27 1147 Equipment Box ........................................................................................................ 28 1153 Play on Words ......................................................................................................... 28 1154 Simple Arithmetics ................................................................................................... 28 1162 IKeyboard★★ ....................................................................................................... 28 1163 Cash Machine .......................................................................................................... 29 1167 Game★★ ............................................................................................................... 29 1168 Manager ................................................................................................................. 30 1169 Networking ............................................................................................................. 31 1184 Symbolic Derivation................................................................................................. 31 1185 Rectangles............................................................................................................... 31 1189 P,MTHBGWB ......................................................................................................... 31 1197 Multiplication Puzzle................................................................................................ 31 1001 A + B Problem 幾乎每個 Online Judge 的第一道題目都是這個（好像 UVA除外 ^_^）。用于試驗服務(wù)端環(huán)境的題目，主要考查 scanf 的用法。 1002~1004 Big integer calculation 主要考查高精度運算的知識 ，并沒有太多的技術(shù)含量。 1005 Move cards★★ 首先要判斷點數(shù)總和能否被堆數(shù)整除，如果不能，就沒有必要進行下面的操作了。 由于隊列兩端的卡片只能移到相鄰的一個方向，這樣我們在進行卡片移動操作的 時候不得不考慮端點的情況，于是，程序變得不夠統(tǒng)一，不統(tǒng)一的程序往往是沒有通用性和不穩(wěn)定的。 為了構(gòu)造統(tǒng)一的程序，我只 考慮每個卡片堆右邊的情況。 基于以上考慮，我將隊列分為兩個部分：一堆卡片與這堆卡片右邊的部分。顯然，這里的“一堆卡片”不包括最右邊的那堆。表示如下 P R 分別表示 Pile Right 我定義 Average 為達到平衡的時候每堆卡片的張數(shù)，于是出現(xiàn)三種情況： 一、 Pile = Average，此時不需要動這堆卡片。 二、 Pile Average，此時需要將這堆卡片中比 Average 多的部分移走，由于 我只考慮向右的情況，所以 Pile 將 (Pile – Average)張卡片移給 Right（只能移給 Right 而不是Right + 1 或是其他是由規(guī)則決定的）。 三、 Pile Average, 此時需要從別的卡片中移一些卡片給 Pile，讓 Pile = Average，顯示，需要 (Average – Pile)張卡片。這種情況與 [情況二 ]不一樣，情況二只是把 Pile 多余的卡片分給右邊，但 [情況三 ]也許需要將多堆卡片中多余的部分一起分為 Pile。 于是，當出現(xiàn)這種情況時，需要從 Pile 的右邊開始搜索。顯然，對于張數(shù) 小于或等于 Average 的堆是不能夠分卡片給 Pile 的，所以，需要從所有張數(shù)大于 Average的堆中分卡片給 Pile，直到 Pile 張數(shù)等于 Average，也就是說，搜索的最后一堆也許不會將所有的多余卡片分給 Pile。 由于我的操作是從左至右進行的，所以，當出現(xiàn)這種情況的時候，一定可以從 Pile的右邊找到多余的卡片，使 Pile = Average。 重復(fù)考慮這三種情況，直到達到平衡為止。 1006 The Hardest Problem Ever 很簡單的一道題，原理就是查密碼表。 注意讀入的時候不要用 scanf(“%s”, … )讀入，用 gets。 另外就是注意輸入數(shù)據(jù)的格式。 1007 Rubik39。s Cube Solver 題目很簡單，但程序很麻煩，主要操作在于寫出魔方在各種操作下的變換，沒有什么算法。 1008 Climbing Trees★ 給定一顆樹，然后再給出兩個結(jié)點，要求得到這兩個結(jié)點的關(guān)系。這個問題主要是基于樹結(jié)構(gòu)的操作，基本操作是先找出兩個結(jié)點的最近的公共祖先，再根據(jù)兩個結(jié)點與它們的公共祖先的關(guān)系來判斷兩個結(jié)點的關(guān)系。 這道題的關(guān)鍵在于找出兩個結(jié)點的公共祖先，我用的方法是： 假設(shè)兩個結(jié)點是 A和 B，先找出從根到 A的路徑，再找到從根到 B的路徑，再找到兩條路徑中離根最遠的公共點即可。兩個結(jié)點一定會有公共祖先（至少是根）。 1009 Dollars★ “生成類”動態(tài)規(guī)劃的題目。從 0 元開始，不斷地生成，直到生成到 元。在實際操作的時候，先將浮點數(shù)乘以 100，轉(zhuǎn)換為整數(shù)，這樣再進行后面的運算便不會出現(xiàn)精度問題。 這道題在剛開始的時候會遇到精度問題，即在將讀入的錢數(shù)乘以 100得到整數(shù)的時候會出現(xiàn)得到的結(jié)果 N % 5 = 1 或 N % 5 = 4 的問題。在這道題里，我通過以下的方法避免此問題：判斷 N是否能被 5 整除，如果不能，則考慮 N + 1 和 N – 1哪個能被 5 整除，則取哪個（ N + 1 和 N – 1 中只可能有一個被 5 整除）。 1010 Mutant Flatworld Explorers★ 模擬題。關(guān)鍵在于理解題意：機器人在一個位置 fall off 之前，會在該位置留下標記，后面的機器人在走到該位置，如果下一條指令會導(dǎo)致它 fall off，它會忽略掉該指令。注意，這里的 fall off 并不包含對方向的限制，也就是說，機器人留下的標記只是說明該位置有機器人 fall off 過，并沒有記錄是在哪個方向 fall off 的。 1011 The Skyline Problem 又是一道模擬題。 先按矩形的左坐標排序會簡化程序的操作。排序后，從最小的坐標開始掃描，發(fā)現(xiàn)高度變化，就記錄下來，最后將這些“變化點”打印出來就行了。 1013 The Cat in the Hat★ 數(shù)學(xué)題。為了敘述方面，我定義 Cat 帽子里的 Cat 為 ChildCat。 根據(jù)題意，每只 Cat 有 N 只 ChildCat， ChildCat 的高度為 Cat 的 1/(N+1)。 題目的輸入告訴了 initial Cat 的高度和 worker cat 的數(shù)目，也就是說，告訴了最大 的那只貓的高度和最小的貓的數(shù)目?；?Cat 和 ChildCat 的高度、數(shù)量關(guān)系，假設(shè)所有的貓堆起來有 n 層，則有： (N + 1) ^ n = initial Cat 的高度 N ^ n = worker cat 的數(shù)目 搜索到第一個滿足條件的 n 后，再進行以后的計算。 題目要求得出 nonworker cat 的數(shù)目和貓疊起來的高度。得到 n 值以后，這兩個值就很容易算了。 Nonworker cat 的數(shù)目就是 cat 的總數(shù)目 – worker cat 的數(shù)目（已經(jīng)在輸入中告訴了） 算貓疊起來的高度利用等比數(shù)列的求和公式就 行了。 1014 Maximum Sum 最大子矩陣和的問題，動態(tài)規(guī)劃的的經(jīng)典題目。 1015 History Grading★ 模擬 ＋ 最長公共子序列。關(guān)鍵還是在于理解題意 ，也就是得分的兩種情況：一種是數(shù)字相同，位置也相同；另