自選題解題報(bào)告積木游戲

1、積木解題江蘇蘇州中學(xué)1，題目描述【問(wèn)題描述】在玩一個(gè)俄羅斯方塊：在初始狀態(tài)，地面上是空的。假設(shè)所有積木都是長(zhǎng)方形的，且積木不能旋轉(zhuǎn)或翻轉(zhuǎn)。在每個(gè)時(shí)刻都會(huì)選擇一個(gè)位置將一塊積木落下，當(dāng)積木在落下的過(guò)程中碰到地面或另一塊積木時(shí)，它會(huì)停留在地面上或那塊積木上。落到另一塊積木上意味著：上面的積木的下邊界與下面積木的上邊至少有一條線段重合(一個(gè)點(diǎn)不算)，如圖一所示。在俄羅斯方塊中，如果某個(gè)時(shí)刻積木間形成了一個(gè)洞，那么看起來(lái)就很不優(yōu)美。于是想知道，每落下一塊積木之后，會(huì)形成幾個(gè)新的洞。一個(gè)洞是指由積木的邊界或地面組成的一塊面積大于 0 的封閉的區(qū)域。如圖 2(a)和圖 2(b)所示。要注意的是：當(dāng)出現(xiàn)圖

2、3 所示的情況時(shí)，因?yàn)榉e木 1 和積木 2 緊緊地愛在一起，所以當(dāng)積木 3 落下的時(shí)候，不會(huì)形成新的洞?，F(xiàn)在告訴你她依次落下的積木的高度 Hi 以及落下位置的左邊界和右邊界Li 與Ri，1in，而她想知道每次積木落下時(shí)會(huì)形成結(jié)果新的洞？1【輸入文件】輸入文件的第一行包含一個(gè)正整數(shù) n，表示落下的積木的總數(shù)。接下來(lái)有n 行，每行有用一個(gè)空格隔開的三個(gè)整數(shù)，分別表示 Li、Ri 和Hi，即積木落下的左右邊界和積木的高度?！据敵鑫募枯敵鑫募?n 行，每行只有一個(gè)整數(shù)。第 i 行表示第 i 個(gè)積木落下只有形成的新的洞的數(shù)目?！据斎霕永?18 11 26 8 32【輸出樣例】001002【樣例說(shuō)

3、明】【數(shù)據(jù)規(guī)模和約定】100%的數(shù)據(jù)中 N100000【來(lái)源】HNOI2009，day2 第四題。2，觀察一個(gè)積木掉下來(lái)后很容易知道它會(huì)掉到哪個(gè)位置，這可以用線段樹。下面觀察一下新增的洞是如何產(chǎn)生的。一個(gè)新增的洞必定是由原來(lái)的積木的若干條邊和當(dāng)前積木的一些邊的一個(gè)封閉圖形。一個(gè)新增的洞大體上來(lái)看有 3 種情況：1， 原來(lái)的積木與新積木的左邊界2， 原來(lái)的積木與新積木的右邊界3， 原來(lái)的積木與新積木的底邊界的新洞的新洞的新洞3，進(jìn)一步分析首先考慮底邊界的“規(guī)范”新洞：3底邊界“規(guī)范”新洞：新掉落積木的底邊界和兩塊原有積木的底邊界重合，在這兩塊原有積木中間產(chǎn)生的洞。在上圖中，紅色積木是新掉落的。由

4、底邊界那么，的“規(guī)范”新洞有 1 個(gè)，右邊那個(gè)洞。如何來(lái)計(jì)數(shù)這種類型的洞呢？可以用線段樹來(lái)一個(gè)線段，如果，這個(gè)線段樹需要支持的操作有 3 個(gè)：它后和某條線段緊鄰，那么合并這兩條線段1，2， 詢問(wèn)l,r，回答有多少線段與l-1,r+1相交。3， 詢問(wèn)某個(gè)點(diǎn)是否被某條線段覆蓋建立 3 種線段樹，Up，Left，Right。新掉下一個(gè)方塊(x1,x2,y1,y2)就4 條線段：1， 在Upy2中 2， 在Leftx1中 3， 在Rightx2中一個(gè)線段x1,x2一個(gè)線段y1,y2一個(gè)線段y1,y2對(duì)于上面這個(gè)例子只需要對(duì) Up2的線段樹詢問(wèn)一次4,9即可知道有多少個(gè)底邊界“規(guī)范”新洞了。當(dāng)然，是不同

5、的線段數(shù)目減一。考慮完底邊界“規(guī)范”新洞以后，自然還有左邊界“規(guī)范”新洞和右邊界“規(guī)范” 新洞。這個(gè)與底邊界“規(guī)范”新洞比較類似，一次即可。同樣是只需要對(duì)對(duì)應(yīng)的線段樹詢問(wèn)考慮完所有的“規(guī)范”洞以后，要考慮一些特殊的洞了。接下來(lái)考慮底邊界左邊洞。還是這，這有一個(gè)底邊界左邊洞。對(duì)于上圖，底邊界左邊洞的存在條件是：1， 在Up2中，第 3 個(gè)格子沒有被覆蓋42， 在Up2中，第 4 個(gè)格子沒有被覆蓋3， 在Right3中，第 2 個(gè)格子被覆蓋了這些都只需在對(duì)應(yīng)的線段樹中詢問(wèn)即可?？紤]完底邊界左邊洞后，還有底邊界右邊洞，這個(gè)和左邊洞是類似的，也是需要滿足三個(gè)條件。下面左邊界下邊洞。圖中紅色積木是新掉下

6、來(lái)的，有一個(gè)左邊界下邊洞。對(duì)于上圖，左邊界下邊洞的存在條件是：1， 在Right4中，第 1 個(gè)格子沒有被覆蓋2， 在Right4中，第 2 個(gè)格子沒有被覆蓋3， 在Up1中，第 4 個(gè)格子被覆蓋了4， 因?yàn)檫@個(gè)洞必須是封閉的，所以對(duì)Right4詢問(wèn)一次3,5的必須非 0，即這個(gè)洞上面還有積木和新掉下來(lái)的積木的右邊界一起把右邊界下邊洞封閉起來(lái)?？紤]完左邊界下邊洞以后，還有右邊界下邊洞，這個(gè)和左邊界下邊洞是類似的，也是需要滿足 4 個(gè)條件。那么，在下圖：完以上這些洞以后，是不是就結(jié)束了呢？不！還有特殊情況，見圖中紅色積木時(shí)新掉下來(lái)的，這里產(chǎn)生了一個(gè)新洞，但是它不屬于之前的任何類型的洞。過(guò)在這里，

7、稱它為左下角洞。左下角洞存在的條件比較復(fù)雜：1， 紅色積木不能直接碰到地面2， 在Up2中，第 4 個(gè)格子沒有被覆蓋3， 在Right4中，第 2 個(gè)格子沒有被覆蓋54， 由于左下角洞必須封閉，所以對(duì)Right4詢問(wèn)一次3,5必須非 0。另外，還需要滿足以下兩個(gè)條件之一(只需要滿足其中任意一個(gè)即可)：條件一：在Up2中，第 5 個(gè)格子沒有被覆蓋條件二：在Right4中，第 3 個(gè)格子沒有被覆蓋完左下角洞以后，類似的還有右下角洞。右下角洞和左下角洞的處理方式是類似的。4，偽代碼for i:=1 to n找到積木i 掉落的位置(x1,x2,y1,y2)分 9 種情況統(tǒng)計(jì)各種洞的數(shù)目：左邊界“規(guī)范”洞右邊界“規(guī)范”洞底邊界“規(guī)范”洞底邊界左邊洞底邊界右邊洞左邊界下邊洞右邊界下邊洞左下角洞右下角洞在Upy2中在Leftx1中在Rightx2中線段x1,x2線段y1,y2線段y1,y25，時(shí)間復(fù)雜度找到每個(gè)積木掉落的位置可以用線段樹來(lái)，總的復(fù)雜度為 O(nlogn)統(tǒng)計(jì)各類洞的數(shù)目，也只需進(jìn)行 O(n)次線段樹操作，總的復(fù)雜度為 O(nlogn)故總的時(shí)間復(fù)雜度為 O(nlogn)需要注意的一點(diǎn)是，每行每列直接開線段樹肯定會(huì) MLE，現(xiàn)線段樹的功能，然后動(dòng)態(tài)開內(nèi)存即可?？?/p>