算法藝術與信息學競賽

1、缺少的提示：2.4.1; 2.4.2; 2.4.7; 2.4.92.4.3 Gridland其實這道題目只需要考慮兩種情況。情況一：兩個邊長至少有一個是偶數(shù)長度為：2*(height-1)+2*(width-1)+(height-2)*(width-2)= 2*height-2+2*width-2+height*width-2*height-2*width+4= height*width情況二：兩個邊長都是奇數(shù)長度為：Height*width 1 + sqrt(2)因為少一條直邊但是多一個斜邊。2.4.4 郵遞員首先讓把理清楚。如果期望值為 Wi 的村子是郵遞員第 Ki 個經(jīng)過的不Wi-Ki

2、元；同時在郵遞員走過所有 M 條路后，他會從郵局那里同村子，那么他會得到得到 m 元，所以無論郵遞員怎么走，只要他完成了任務，都是而由于是最小負權，所以在從起點到這個點的這段路徑中所有點的權都大于-a。換句話說，如果將這個權最小的點作為新起點，則從原起點到這個點的路徑上的所有點的權均大于 0。同時，由于這個點的權最小，所以在從這個點到起點的路徑中所有的點的權也都大于 0。滿足題目要求。所以，只要構造出一條回路，就總能在這條回找到一個點作為起點，滿足題目要求。2.4.6機來分析一下機器失敗的苛刻條件。首先抽象模型：機是圖（稱為圖 T1）中的頂點，如果機 x 的集合中有一個數(shù) y，那么向圖中添加一

3、條從 x 指向 y 的有向邊。僅當此圖一個頂點 1 出度比入度大一，頂點 n 入度比出度大一，其余頂點入度等于出度的歐拉路時，機器才有可能失敗。所以下面只針對此種情況進行：路徑如果機器沒有失敗，那么圖中剩余邊殘留圖 T3，機器圖 T2，T2 是一個頂點 1 出度比入度大一，頂點 n 入度比出度大一，其余頂點入度等于出度的路。因為T1-T2=T3，所以 T3 是頂點 n 入度出度皆為 0 其余所有頂點入度等于出度的回路。既然是回路就必然包含圈，事實上，只要殘留圖 T3 是個圈而非沒有邊的空圖，機器就不會失敗。從每個頂點出發(fā)，找尋不包含頂點 n 的圈。如果找不到，那么機器失??；如果找到了，那么把這

4、個圈從圖 T1 中刪除，剩下的圖便是使得機器獲勝的路徑，而這個路徑仍然是個頂點 1 出度比入度大一，頂點 n 入度比出度大一，其余頂點入度等于出度的路。2.4.8通信例子給出的方案是怎樣找到的呢？ 可以這樣來分析：對于 Bornholm 端口 2、Gotland端口 1、 Gotland 端口 4，由于沒有其它端口以它們?yōu)槟康亩丝?，所以它們必須被設置成發(fā)送模式，因此一一對應的 Gotland 端口 5、Bornholm 端口 4、Bornholm 端口 1 必須為接收模式。刪除由 Gotland 端口 5、Bornholm 端口 4、Bornholm 端口 1 發(fā)出的有向邊。結果發(fā)現(xiàn)，由于邊的

5、刪除，Gotland 端口 3、Bornholm 端口 3 也成為只有發(fā)送模式?jīng)]有接受模式的端口，所以它們必須被設置成發(fā)送模式，相應的 Gotland 端口 2 為接受模式。參照樣例的解題方法，對于任意待匹配的通訊圖，不斷找出只有發(fā)送（接受）模式的端口 x，確定它們以及相應接受（發(fā)送）端口 y 的運行方式，將點 x、y 及相關邊從圖中刪除。如此迭代，直至無點、邊可刪?？紤]當前剩余通訊圖，圖有 a+b 個點，a+b 條有向邊，每個點入度出度皆為 1。這樣的圖只能由若干個有向環(huán)。倘若某個有向環(huán)頂點個數(shù)為奇數(shù)，那么此通訊圖無合法匹配方案；否則對于每個環(huán)任意確定某個端口為發(fā)送模式，其余端口的運行模式也

6、就相應確定了。2.4.10 龍穴迷宮圖中部分點是重復的，于是想到不斷把重復的點合并，以求出最少的點數(shù)。按 F1 的定義進一步定義 Fk：描述以點 k 為起點到點 n 的路徑，其中 1kn，有：有向無環(huán)圖層次分明，定義 de：表示點 i 到點 n 的最大步數(shù)，顯然有：這里 R 和 X 都在樹上，所以 R 和 X 到樹上的點的路線都是唯一的。所以，用寬度優(yōu)先搜索來判斷究竟是 A 能率先到達安全點還是 B 能搶先一步卡住咽喉要道?？梢允紫纫页鏊械陌踩c。從點 1 開始做寬度優(yōu)先搜索。每出現(xiàn)一條橫向邊，就表示找到了一個環(huán)。找出這個環(huán)上的所有點，然后把它們都記為安全點。接著，用寬度優(yōu)先搜索分別計算每一回合后 A、B 兩人可以到達的格子。先搜 B 的，再搜 A 的（這和題中兩人走棋的順序相反）。對于一個點，如果 B 已經(jīng)到達過了，那么 A 就不能再去了，否則就一定會被抓住。如果 A 能安全到達一個安全點，那么 B 就再也抓不到 A 了，程序就應該馬上終止。當 B 能到達所有 A 能到達的格子后，那么A 就無路可走了。這時所用的步數(shù)就是 B 抓到 A 所需要的步數(shù)。要開一個型數(shù)組，每個點是否為安全點。在寬度優(yōu)先搜索中還需要開幾個數(shù)組。在解題的過程