信息學(xué)集訓(xùn)隊作業(yè)submit

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

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

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

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

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

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

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

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

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

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

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

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

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