信息學集訓隊作業(yè)submit

1、申請人：孫方成申請數目：34* 申請1(報告已完成) *題目: 0107 Island時間復雜度： O(n3)基本思想：貪心算法描述：不斷選取距離最短的兩個點進行合并，同時修正其它各點到這個新點的距離。* 申請2(報告已完成) *題目: 9904 Polygons時間復雜度： O(1)基本思想：數學問題算法描述：當n為偶數時必然是tak，當奇數時，只有黑色方塊已經暴露時才是tak，否則為nie。* 申請3(報告已完成) *題目: 0008 Code時間復雜度： O(k2)基本思想：動態(tài)規(guī)劃（遞推）算法描述：這道題首先算出有n個節(jié)點的排序二叉樹的個數，然后通過計算得到每一棵子樹的根節(jié)點的字母。*

2、 申請4(已接受) *題目: 0103 Antiprime numbers時間復雜度： O()4)基本思想：雙向搜索算法描述：主要是由于大于23的質數是必然不會被取到的，所以實際上只有九個質數可能被取到。將這九個質數分成兩組，分別進行搜索，并將一部分的搜索結果存入表中。在對另一部分進行搜索時可以直接引用表中的結果。* 申請5(報告已完成) *題目: 0109 Travel時間復雜度： O(n2)基本思想：動態(tài)規(guī)劃算法描述：本題的題意理解較為復雜，我采用三維數組記錄不同時間兩點間的最短直接距離。由于所有的頻率都是60的約數，所以完全可以安分鐘數分類。這樣擴展每個點的時間是60n，在采用了最大堆和

3、哈希表的數據結構后，得到了較優(yōu)的時間效率。* 申請6(報告已完成) * 題目: 9808 Frogman時間復雜度： O(abn)基本思想：動態(tài)規(guī)劃算法描述：就是基本的動態(tài)規(guī)劃，以氣瓶為階段，氧氣和氮氣的體積為狀態(tài)。* 申請7(報告已完成) *題目: 9914 Primitivus時間復雜度： O(m)基本思想：圖論算法描述：主要是通過并查集對圖中的所有連通塊進行分類。最終的解就是所給的邊數加上每個連通塊中的系數。如果連通塊是一個Euler回路，則系數為1，否則為連通塊中所有點的入度出度差的絕對值的和的一半。* 申請8(報告已完成) *題目: 0115 Chain時間復雜度： O(n)基本思想

4、：遞推高精度計算算法描述：通過兩個函數的遞推可以的到結果，由于函數形式比較復雜，這里不便描述。* 申請9(報告已完成) *題目: 9711 Canoes時間復雜度： O(n)基本思想：貪心算法描述：就是經過排序后，從兩端取數，如果和大于可承載量則大的單獨一條船，否則兩個人一條船。一直繼續(xù)，取完為止。* 申請10(報告已完成) *題目: 9714 Monochromatic triangles時間復雜度： O(m)基本思想：數學問題算法描述：只要記錄和一個點相連的紅邊的條數，乘以與其相連的黑邊的條數就是這個點的系數。將所有點的系數相加，并將和除以二就得到顏色不相同的三角形的個數。最后用三角形的總

5、個數減就得到最后的解。* 申請11(報告已完成) *題目: 9807 How to pack containers?時間復雜度： O()基本思想：構造法算法描述：在匹配完所有容量為i的容器后，將剩余的大小為i的物品按權從小到大兩兩合并為大小為i+1的物品。依此類推。* 申請12(報告已完成) *題目: 0015 Promotion時間復雜度： O()基本思想：最大堆的應用算法描述：利用兩個最大堆（一個最大，一個最小），兩個散列（記錄元素在兩個堆中的位置）。不斷的找出最大最小數，刪除，維護。* 申請13(報告已完成) *題目: 0006 Automorphisms時間復雜度： O(nm)m為輪換

6、的個數基本思想：置換群算法描述：找出所有的輪換，然后分別討論環(huán)間和環(huán)內的關系。環(huán)間關系權為兩個輪換的長度的最大公約數，環(huán)內關系權為：如果長度為偶數無解，若為奇數則為L/2。最后將所有權相加為k。解為2k。同時2(k-3)*8=2(k-3)%500)*8。* 申請14(已接受) *題目: 9813 The lightest language時間復雜度： O(kn2)基本思想：動態(tài)規(guī)劃算法描述：用兩個函數進行互推。一個記錄有n個單詞的The lightest language的權，一個記錄用前k個字母有n個單詞的The lightest language的權。主要是建立一棵數，樹的葉結點樹為n。*

7、 申請15(報告已完成) *題目: 0102 Intervals時間復雜度： O(n)基本思想：模擬算法描述：由于a,b的范圍較小，可以用數組模擬坐標軸，進行區(qū)間合并。* 申請16(報告已完成) *題目: 0108 Ants and the ladybug時間復雜度： O()基本思想：最短路徑模擬算法描述：抓住樹結構的特殊性，按一定的順序模擬每一只螞蟻一次的行動。* 申請17(報告已完成) *題目: 0105 Weaker Goldbach時間復雜度： O(1)和數據規(guī)模沒有明顯關系基本思想：貪心、構造算法描述：解是很多的，所以差不多按照一定規(guī)律隨便拆拆都可以得到解。* 申請18(報告已完成)

8、 *題目: 9703 Cheap Travels時間復雜度： O(n2)基本思想：動態(tài)規(guī)劃算法描述：最基本的動態(tài)規(guī)劃，沒什么可說的。* 申請19(報告已完成) *題目: 9801 Painters Studio時間復雜度： O(n)基本思想：數學算法動態(tài)規(guī)劃算法描述：以數學推理為主。將坐標用二進制表示，然后按照進位的情況進行動態(tài)規(guī)劃。* 申請20(報告已完成) *題目: 9910 Three-coloring of binary trees時間復雜度： O(n)基本思想：動態(tài)規(guī)劃算法描述：每一個點將被拆做三個顏色的三種狀態(tài)，表示為這個結點染成該顏色時最多（最少）有多少個綠色結點。同時，每個點都

9、記錄以其為根的子樹的最后一個結點的位置，這樣父結點就可以迅速的找到兩個子結點。* 申請21(報告已完成) *題目: 9915 Water時間復雜度： O(mnlogmn)基本思想：迭代算法描述：不斷找出高度最小的柱子，如果其旁有一個柱子的最高水位已確定（必然低于它），則將其周圍所有其它柱子的水位抬高至和其相平（可以證明這是他們的最高水位）。由于每個柱子只進行一次水位抬高，所以時間復雜度集中在查找高度最小的柱子上。* 申請22(報告已完成) *題目: 9912 Map時間復雜度： O(n2)基本思想：動態(tài)規(guī)劃算法描述：就是ioi2000的郵局問題，讀入所有的人口數，排序，然后就可以動態(tài)規(guī)劃了！*

10、 申請23(報告已完成) *題目: 9909 Bitmap時間復雜度： O(mn)基本思想：動態(tài)規(guī)劃算法描述：從四個方向動態(tài)規(guī)劃，Dab=1則Fab=0，否則Fab=min(Fab,min(fa+dxb,fab+dy)+1)。* 申請24(已接受) */沒有測試數據，但我覺得算法是對的，所以也交了。題目: 0010 Lollobrigida時間復雜度： O(nlogn)基本思想：構造算法描述：將所有的柱子按高度從小到大排序后，從中間分成兩部分。如果這兩部分可以兩兩相間的構成序列則為tak，否則為nie。* 申請25(報告已完成) *題目: 9816 Rectangles時間復雜度： O(n2)

11、基本思想：集合合并算法描述：判斷兩個矩形是否相交，若是則將兩個矩形所在的集合合并。最后檢查集合的個數。* 申請26(報告已完成) *題目:9810 Assemler circuits 時間復雜度： O(n2)基本思想：動態(tài)規(guī)劃模擬算法描述：首先判斷哪些操作是不必要的，即如果操作結果還沒有被使用就被刷新則該操作是無效的，可以舍棄。然后建立一個表記錄判斷一個寄存器中是第幾個操作的結果。如果兩次操作選用的被操作數相同則，該操作可以和以前的操作合并。* 申請27(報告已完成) *題目:9815 Flat broken lines時間復雜度： O(nlogn)基本思想：構造算法描述：首先旋轉坐標系，然后

12、貪心。具體實現上可以采用二分查找。* 申請28(報告已完成) *題目:0112 City tour時間復雜度： O(n)基本思想：圖論算法描述：只要總的權是正的，則必然可以構造出一個滿足要求的旅行路線。所以主要算法是求歐拉回路。由于歐拉回路算法的時間復雜度為O(m)，m=2n。所以時間復雜度為O(n)。* 申請29(報告已完成) *題目:0113 Bank時間復雜度： O(16)基本思想：構造算法描述：首先構造貨幣1，滿足使用貨幣1的數量最少，并可以兌換出所有的貨幣1。然后在貨幣1的量不變的情況下，構造貨幣2。經過4次構造后可以得到最優(yōu)解。每一次構造使用貪心算法，不斷尋找短缺較少的客戶，直到兌

13、換完所有的客戶。* 申請30(尚未接受) *題目:9811 ATMs時間復雜度： O()其中為高精度計算的時間復雜度基本思想：構造算法描述：貸款時，首先確定第0位的狀態(tài)，然后將輸入數據除2。接著，將處理后的數據轉換成4進制數，每k位上的數字對應了第2k+1位和第2k+2位的狀態(tài)。如果最后的結果超過99位則無解。還款時的算法與之相似。* 申請31(尚未接受) *題目:0014 Repetitions時間復雜度： O(mn)基本思想：模式匹配算法描述：先將第一個字符串作為待匹配串，求出最大匹配數。然后刪去該串的第一個字符，繼續(xù)操作，直到刪空為止。采用模式匹配的KMP算法。* 申請32(尚未接受) *題目:9902 Monodigital representations時間復雜度：最大不超過107?；舅枷耄焊F舉算法描述：對于一個數字，計算出對所有ai的解。求解過程采用寬度搜索。* 申請33(尚未接受