文本文稿成果2352stars xiedi

1、2352 Stars謝 迪 .cn2352 Stars 題目描述Cartesian coordinatesLevel: an amount of the stars that are not higher and not to the right of the given star Task: Count the amounts of the stars of each level on a given mapxy 3 1 0 1 22352 Stars 輸入Number of stars：N(1 = N = 15000)Coordinates of stars： 0=Xi,Yi=32000

2、There can be only one star at one point of the plane. Stars are listed in ascending order of Y coordinate. Stars with equal Y coordinates are listed in ascending order of X coordinate. Input:NX1 Y1X2 Y2XN YNThis problem has huge input data,use scanf() instead of cin to read data to avoid time limit

3、exceed.2352 Stars 輸出The first line contains amount of stars of the level 0, the second does amount of stars of the level 1 and so on, the last line contains amount of stars of the level N-1. Output:C0C1Cn-12352 Stars StatisticsTotal Submits 274 Accepted 58 Time Limit Exceed 96 Wrong Answer 69 Runtim

4、e Error 10 Output Limit Exceed 8 Compile Error 33 算法一：原始想法題目意思很簡(jiǎn)單我們就照著它說的按部就班的做吧把它當(dāng)作模擬題for(i=0;in;i+) int tmp=0;for(j=0;ji;j+) if(xj=xi) / 統(tǒng)計(jì)不在右邊的星星：因?yàn)轭}目已經(jīng) tmp+; / 保證輸入的是按照y排好序的，因此numtmp+; / ji保證了統(tǒng)計(jì)的是不在上面的星星 算法一：原始想法for(i=0;in;i+) int tmp=0;for(j=0;ji;j+) if(xj=xi) / 統(tǒng)計(jì)不在右邊的星星：因?yàn)轭}目已經(jīng) tmp+; / 保證輸入的是按

5、照y排好序的，因此numtmp+; / ji保證了統(tǒng)計(jì)的是不在上面的星星 SubmitAccepted 208K 4653MS C+ 0.39K 2005-04-07 21:54:4710/JudgeOnline Time Limit Exceed C+ 0.39K 2005-04-07 22:51:26 /JudgeOnline Total Submits 274 Accepted 58 Time Limit Exceed 96 + 1Wrong Answer 69 Runtime Error 10 Output Limit Exceed 8 Compile Erro

6、r 33 算法二：另一種原始的想法題目意思很簡(jiǎn)單我們來換一個(gè)角度試試可能會(huì)有所收獲我們?cè)O(shè)置m個(gè)桶(Buckets)，m的范圍為星星的x坐標(biāo)的范圍：0-32000!然后將所有的星星按輸入順序扔入桶中：記錄在這個(gè)桶的位置上星星的個(gè)數(shù)扔入之前，先從0位置開始到這個(gè)星星的x位置，統(tǒng)計(jì)星星的個(gè)數(shù)，即求出了這個(gè)星星的level。算法二：另一種原始的想法這樣做效率顯然不高在算法一中，我們計(jì)算某個(gè)星星的level的時(shí)候，僅要考察它前面的全部星星，這樣做的效率是：O(N*(N+1)/2)，N的范圍是1-15000。而在這個(gè)算法中，計(jì)算某個(gè)星星的level的時(shí)候，需要考察它所有的前面位置。復(fù)雜度為O(N*M)。而

7、M的范圍是0-32000。比算法一還要爛！for (i = 0; i n; i+)scanf(%d%d, &x, &y);s = 0;for (j = 0; j x; j+)s += bucketj;levels+;buckety+;算法三：由算法二想起的這樣做效率顯然不高我們?cè)賮碛^察一下我們的算法二：我們每次計(jì)算一個(gè)星星的level的時(shí)候，總要對(duì)前面所有的位置都掃描一遍，時(shí)間都浪費(fèi)在這里了！如果前面減少幾個(gè)桶就好了！for (i = 0; i n; i+)scanf(%d%d, &x, &y);s = 0;for (j = 0; j x; j+)s += bucketj;levels+;bu

8、ckety+;算法三：由算法二想起的如果前面減少幾個(gè)桶就好了！我們可以把幾個(gè)桶合并成一個(gè)大桶！計(jì)算的時(shí)候我們先考察在當(dāng)前星星位置前面的大桶，再考察大桶和當(dāng)前星星位置之間的小桶（包括當(dāng)前位置）。圖中我們把每3個(gè)小桶合并為一個(gè)大桶則我們可以很容易計(jì)算紅色星星level為13112算法三：由算法二想起的則我們可以很容易計(jì)算紅色星星level為13我們花的代價(jià)只是：統(tǒng)計(jì)3個(gè)大桶和2個(gè)小桶！而以前要統(tǒng)計(jì)11個(gè)小桶！3 + 2 11這個(gè)辦法好！112算法三：由算法二想起的是不是就取個(gè)小桶合并成一個(gè)大桶?當(dāng)m達(dá)到30000時(shí)，大桶的個(gè)數(shù)也有10000了！顯然效率不高！那我們?nèi)?00個(gè)小桶合并成一個(gè)大桶，這樣

9、最多只有150個(gè)大桶。最壞情況下只用統(tǒng)計(jì)200+150=350次！112算法三：由算法二想起的其實(shí)為了使平均效率比較高，我們得要大桶的個(gè)數(shù)和每個(gè)大桶包含的小桶的個(gè)數(shù)相同！即都為sqrt(m)個(gè)為什么？這樣分散了“風(fēng)險(xiǎn)”！因?yàn)槲覀兘y(tǒng)計(jì)的次數(shù)為：當(dāng)前星星之前的所有大桶當(dāng)前星星和最后一個(gè)大桶之間的小桶（包括當(dāng)前位置）所以需要統(tǒng)計(jì)的次數(shù)不超過sqrt(m)+sqrt(m)112算法三：由算法二想起的#include #include const int CAPACITY = 200;const int MAX = 32000 + 1;const int BUCKET = MAX / CAPACITY

10、+ 1;const int N = 15000;short bucketBUCKET = 0;short aMAX = 0, levelN = 0;/每個(gè)大桶相當(dāng)于多少小桶，即大桶“容量”/最大位置/桶的個(gè)數(shù)/星星的個(gè)數(shù)/大桶/ a 表示小桶，level 表示各個(gè)等級(jí)星星的個(gè)數(shù)算法三：由算法二想起的int main() int i, j, n, x, y, big, s; scanf(%d, &n); for (i = 0; i n; i+) scanf(%d%d, &x, &y); big = x / CAPACITY; s = 0; for (j = 0; j big; j+) s +=

11、bucketj; for (j = CAPACITY * big; j = x; j+) s += aj; levels+; ax+; buckettmp+;/Big:當(dāng)前位置之前大桶的個(gè)數(shù) / s累計(jì)當(dāng)前星星的level /首先計(jì)算大桶/然后計(jì)算小桶/當(dāng)前星星所屬大桶小桶均加算法三：由算法二想起的搞定了！回顧一下：時(shí)間復(fù)雜度 O(n*sqrt(m)空間復(fù)雜度 O(m)Submit11 392257 xiedi 120K 90MS C+ 0.59K 2005-03-30 22:20:38 /JudgeOnline 算法四：有點(diǎn)點(diǎn)難度的我們?cè)倩仡櫼幌律弦活}的基本思想：實(shí)際上就是盡量減少統(tǒng)計(jì)的次數(shù)

12、！想想在我們所接觸的一些數(shù)據(jù)結(jié)構(gòu)中，二叉樹是一種比較高效的方法。那我們用二叉樹試試算法四：有點(diǎn)點(diǎn)難度的每個(gè)結(jié)點(diǎn)有一個(gè)它所涉及星星位置的范圍。如下圖根結(jié)點(diǎn)A表示的是0-3位置中的星星。而根結(jié)點(diǎn)的左子B表示的是0-1位置中的星星。C表示的是1-1，就是1位置的星星。0-30-12-30-01-12-23-3ACB算法四：有點(diǎn)點(diǎn)難度的每個(gè)結(jié)點(diǎn)我們記錄一個(gè)值f：對(duì)于非葉結(jié)點(diǎn)表示以它為根的子樹中，左子樹中星星的個(gè)數(shù)。對(duì)于葉結(jié)點(diǎn)則表示它表示的位置上的星星個(gè)數(shù)。以Sample Input中的數(shù)據(jù)來說明：圖中紅色數(shù)字即為f值。0-30-12-30-01-12-23-32211211算法四：有點(diǎn)點(diǎn)難度的則算法為

13、：從根結(jié)點(diǎn)開始向下遍歷，當(dāng)不是葉結(jié)點(diǎn)時(shí)：若星星位置在當(dāng)前結(jié)點(diǎn)的左側(cè)，則：當(dāng)前結(jié)點(diǎn)f值加1。訪問左子樹。若星星位置在當(dāng)前結(jié)點(diǎn)的右側(cè)，則：星星總數(shù)加上當(dāng)前結(jié)點(diǎn)的f值，訪問右子樹。0-30-12-30-01-12-23-32211211當(dāng)為葉結(jié)點(diǎn)時(shí)：星星總數(shù)加上當(dāng)前結(jié)點(diǎn)f值，然后當(dāng)前結(jié)點(diǎn)f值加1。算法四：有點(diǎn)點(diǎn)難度的舉一個(gè)具體的例子：我們要計(jì)算圖中紅星星的level。0-30-12-30-01-12-23-32211211Total=2+2+12非葉結(jié)點(diǎn)：左側(cè)：當(dāng)前結(jié)點(diǎn)f值加1。訪問左子樹。右側(cè)：星星總數(shù)加上當(dāng)前結(jié)點(diǎn)的f值，訪問右子樹。葉結(jié)點(diǎn)：星星總數(shù)加上當(dāng)前結(jié)點(diǎn)f值，當(dāng)前結(jié)點(diǎn)f值加1。算法四：有點(diǎn)

14、點(diǎn)難度的另外一個(gè)例子：我們要計(jì)算圖中紅星星的level。0-30-12-30-01-12-23-32211211Total=21+13非葉結(jié)點(diǎn)：左側(cè)：當(dāng)前結(jié)點(diǎn)f值加1。訪問左子樹。右側(cè)：星星總數(shù)加上當(dāng)前結(jié)點(diǎn)的f值，訪問右子樹。葉結(jié)點(diǎn)：星星總數(shù)加上當(dāng)前結(jié)點(diǎn)f值，當(dāng)前結(jié)點(diǎn)f值加1。算法四：有點(diǎn)點(diǎn)難度的怎樣實(shí)現(xiàn)二叉樹？由于本題中二叉樹是滿的，所以用數(shù)組實(shí)現(xiàn)就可以了。根結(jié)點(diǎn)標(biāo)號(hào)為1；第二層順次標(biāo)為2，3；0-30-12-30-01-12-23-32211211則若當(dāng)前結(jié)點(diǎn)為i，則其左子結(jié)點(diǎn)為i*2,其右子結(jié)點(diǎn)為i*2+1。1327654算法四：有點(diǎn)點(diǎn)難度的#include #include const

15、 int MAXX = 32000;/最大范圍int f(MAXX + 1) * 3;/f值int level15001;/記錄各個(gè)level的星星個(gè)數(shù)算法四：有點(diǎn)點(diǎn)難度的int main()int i, k, l, r, s, n, x, y, mid;memset(f, 0, sizeof(f);scanf(%d, &n);for (i = 0; i n; i+)scanf(%d%d, &x, &y);s = 0; k = 1; l = 0; r = MAXX;while (l 1;if (x mid)l = mid + 1; s += fk; k = 1; k+;elser = mid;

16、fk+;k = k 1;s += fk; fk+;levels+;算法四：有點(diǎn)點(diǎn)難度的scanf(%d%d, &x, &y);s = 0; k = 1; l = 0; r = MAXX;while (l 1;if (x mid)/ 如果在右側(cè)l = mid + 1; s += fk; k = 1; k+;else/ 否則在左側(cè)r = mid; fk+; k = k 1;s += fk; fk+;/ 葉結(jié)點(diǎn)levels+;非葉結(jié)點(diǎn)：左側(cè)：當(dāng)前結(jié)點(diǎn)f值加1。訪問左子樹。右側(cè)：星星總數(shù)加上當(dāng)前結(jié)點(diǎn)的f值，訪問右子樹。葉結(jié)點(diǎn)：星星總數(shù)加加上當(dāng)前結(jié)點(diǎn)f值，當(dāng)前結(jié)點(diǎn)f值加1。算法四：有點(diǎn)點(diǎn)難度的for (

17、i = 0; i n; i+)/輸出printf(%dn, leveli);return 0;算法四：有點(diǎn)點(diǎn)難度的復(fù)雜度分析：從前面的過程可以發(fā)現(xiàn)：如果要計(jì)算一個(gè)星星的level，我們只需要將這個(gè)樹從根結(jié)點(diǎn)向葉結(jié)點(diǎn)遍歷一次。只需要“二叉樹的深度”次的運(yùn)算。對(duì)于本題，即進(jìn)行l(wèi)og m次。而且在這一次遍歷中，就已經(jīng)將這個(gè)星星的有關(guān)信息都記錄下來了。因此總的時(shí)間復(fù)雜度為O( n log m )空間：需要存儲(chǔ)一個(gè)二叉樹，其中此二叉樹的葉結(jié)點(diǎn)個(gè)數(shù)為m個(gè)。因此總的空間需求為m*2。再加上統(tǒng)計(jì)level的一個(gè)數(shù)組：n總的空間復(fù)雜度為O( n + m * 2)算法四的推廣0-30-12-30-01-12-23

18、-3線段樹：描述單個(gè)或若干區(qū)間并的樹形結(jié)構(gòu)，屬于二叉平衡樹?？梢跃S護(hù)的信息有：并區(qū)間的總長(zhǎng)度，并區(qū)間的不連續(xù)線段的個(gè)數(shù)等等。這道題采用的是比較特殊的線段樹：線段互不相交，最后葉結(jié)點(diǎn)表示的是單個(gè)點(diǎn)。算法四的推廣：線段樹0-30-12-30-01-12-23-3線段樹：描述單個(gè)或若干區(qū)間并的樹形結(jié)構(gòu)，屬于二叉平衡樹?？梢跃S護(hù)的信息有：并區(qū)間的總長(zhǎng)度，并區(qū)間的不連續(xù)線段的個(gè)數(shù)等等?？匆粋€(gè)比較一般而且大一點(diǎn)的線段樹：線段樹的基本概念區(qū)間標(biāo)號(hào):如圖中的1,5,7,8,表示這個(gè)區(qū)間覆蓋的范圍左、右子結(jié)點(diǎn)：如果是用數(shù)組實(shí)現(xiàn)，就不用記錄了測(cè)度：等下要用到，表示當(dāng)前區(qū)域里所覆蓋的大小連續(xù)段數(shù)：指的是區(qū)間的并可以

19、分解為多少個(gè)獨(dú)立的區(qū)間。線段樹的基本操作建樹：插入線段：刪除線段：維護(hù)信息：線段樹的應(yīng)用經(jīng)典題目：IOI 1998 Picture ( POJ 1177)線段樹的應(yīng)用把豎線作為區(qū)間建立線段樹，從左向右掃描的時(shí)候，遇到左豎邊，插入線段樹，右豎邊從線段樹中刪除。在每?jī)蓚€(gè)豎線中間計(jì)算周長(zhǎng)：橫邊=2*連續(xù)段數(shù)*兩條豎線間距離豎邊=abs(掃描到i+1時(shí)候的測(cè)度-掃描到i時(shí)候的測(cè)度)，因?yàn)楦淖兊拈L(zhǎng)度是“露在外面”線段樹的應(yīng)用POJ 1151 Atlantisthe total explored area (the area of the union of all rectangles)n (1 = n

20、= 100) of available mapsx1;y1;x2;y2 (0 = x1 x2 = 1000000 = y1 y2 = 100000), not necessarily integers. The values (x1; y1) and (x2;y2) are the coordinates of the top-left resp. bottom-right corner of the mapped area. 線段樹的應(yīng)用把豎線作為區(qū)間建立線段樹，從左向右掃描的時(shí)候，遇到左豎邊，插入線段樹，右豎邊從線段樹中刪除。在每?jī)蓚€(gè)豎線中間計(jì)算周長(zhǎng)：橫邊=2*連續(xù)段數(shù)*兩條豎線間距離豎邊

21、=abs(掃描到i+1時(shí)候的測(cè)度-掃描到i時(shí)候的測(cè)度)，因?yàn)楦淖兊拈L(zhǎng)度是“露在外面”在每?jī)蓚€(gè)豎線中間計(jì)算面積：abs(掃描到i+1時(shí)候的測(cè)度-掃描到i時(shí)候的測(cè)度)*兩條豎線間距離注意！本題中的數(shù)據(jù)規(guī)模：1 = n = 100離散化以后最多只有200個(gè)不同坐標(biāo)不用線段樹就可以很快解決！線段樹的應(yīng)用剛剛利用線段樹求周長(zhǎng)也可以利用線段樹求面積擴(kuò)展：利用線段樹求體積線段樹的應(yīng)用POJ 1803 Box ArtFor a given three-dimensional axis aligned initial box B and a set S of three-dimensional axis ali

22、gned boxes, you have to compute the volume of the union of all parts of the boxes of S that lie within B. Make sure that you count the volume of overlapping parts of the boxes only once!Number m (m = 2000) of boxes in S whose colour was changed by the laser device,All coordinates are in the range fr

23、om 0 to 1000 線段樹的應(yīng)用POJ 1803 Box Art首先根據(jù)z將所有box離散化，即將所有box用平行于Oxy的box的面分成許多片。然后對(duì)每一塊：利用線段樹計(jì)算其面積，然后再乘以兩個(gè)面之間距離，即得其體積。如果不用線段樹，效率將很低。線段樹的應(yīng)用另外一個(gè)題：POJ 1151 Hotel1.The arrival of a new group of tourists Receive i which represents the start room of the sequence of the rooms that the group wants to occupy and M representing the number of members of the group. It is guaranteed that all the rooms i,i+1,.,i+M-1 are free a