算法藝術(shù)與信息學(xué)競(jìng)賽

1、缺少的提示：2.4.1; 2.4.2; 2.4.7; 2.4.92.4.3 Gridland其實(shí)這道題目只需要考慮兩種情況。情況一：兩個(gè)邊長(zhǎng)至少有一個(gè)是偶數(shù)長(zhǎng)度為：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情況二：兩個(gè)邊長(zhǎng)都是奇數(shù)長(zhǎng)度為：Height*width 1 + sqrt(2)因?yàn)樯僖粭l直邊但是多一個(gè)斜邊。2.4.4 郵遞員首先讓把理清楚。如果期望值為 Wi 的村子是郵遞員第 Ki 個(gè)經(jīng)過(guò)的不Wi-Ki

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

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

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

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

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