圖論練習題 備用交換機 gd 題解

問題描述

n個城市之間有通訊網絡，每個城市都有通訊交換機，直接或間接與其它城市連接。因電子設備容易損壞，需給通訊點配備備用交換機。但備用交換機數量有限，不能全部配備，只能給部分重要城市配置。於是規定：如果某個城市由於交換機損壞，不僅本城市通訊中斷，還造成其它城市通訊中斷，則配備備用交換機。請你根據城市線路情況，計算需配備備用交換機的城市個數，及需配備備用交換機城市的編號。

【輸入格式】

輸入文件有若干行

第一行，一個整數n，表示共有n個城市(2<=n<=100)

下面有若干行,每行2個數a、b，a、b是城市編號，表示a與b之間有直接通訊線路。

【輸出格式】

輸出文件有若干行

第一行，1個整數m，表示需m個備用交換機，下面有m行，每行有一個整數，表示需配備交換機的城市編號，輸出順序按編號由小到大。如果沒有城市需配備備用交換機則輸出0。

OI練習題 溶液模擬器 simulator

小 Y 太失敗了，他雖然在化學實驗課上拿來了很多溶液，但是還是沒有辦法配成想要的溶液，萬一倒錯了就沒有辦法挽回了，小 Y 遲遲不敢下手。

於是小 Y 到網上下載了一個溶液配置模擬器。溶液配置模擬器是這樣的程序：模擬器在電腦中構造一種虛擬溶液，然後你可以虛擬地向當前虛擬溶液中加入一定濃度一定質量的這種溶液，模擬器會快速地算出倒入後虛擬溶液的濃度和質量。當然，計算機最可愛的地方就是當你倒錯了可以撤銷。

模擬器的使用步驟是這樣的：

1. 為模擬器設置一個初始質量和濃度 V0 ， C0% （ 0 ≤ C0≤100 ）。

2. 進行一系列操作，模擬器支持兩種操作：

P(v,c) 操作：表示向當前的虛擬溶液中加入質量為 v 濃度為 c 的溶液；

Z 操作：撤銷上一步 P 操作。

但是，小 Y 不小心把模擬器弄丟了……，眼看考試迫在眉睫，小 Y 只能依靠你了。

輸入格式：

第一行，兩個整數 V0 ， C0 。

第二行，一個整數 n ，表示操作數（ n ≤ 10000 ）。

接下來 n 行，每行一條操作，格式為：

P v c 或 Z 。

之間用一個空格隔開，當只剩初始溶液的時候，再撤銷就沒有用了。

任意時刻質量不會超過 2 31 -1 。

輸出格式：

n 行，每行兩個數 V i ， C i , 其中 V i 為整數， C i 為實數（保留 5 位小數），之間用一個空格隔開。其中，第 i 行表示第 i 次操作以後的溶液質量和濃度。

圖論練習題 圖的平方 ljb

【問題描述】

有向圖G=(V,E)的平方是圖G^2=(V,E^2)，該圖滿足下列條件：(u,w)∈E^2當且僅當對v∈V，有(u, v)∈E，且(v,w)∈E。亦即，如果圖G中頂點u和w之間存在著一條恰包含兩條邊的路徑時，則G^2必包含該邊(u,w)。

請編程序對於給定的有向圖G，查詢邊(u,w)是否存在於平方圖G^2中。

【輸入文件】

第一行有兩個整數，v(1<=v<=100000)，m(1<=m<=1000)，其中v表示圖G的頂點個數，（頂點按1~v編號）；

接下來有m行，每行包含4個整數u1,u2,v1,v2，表示在圖G中，頂點區間[u1,u2]中的每一個頂點至頂點區間[v1,v2]中的每一個頂點都有邊相連；

接下來有一行，一個整數n（1<=n<=1000），表示查詢的個數；

接下來有n行，每一行有4個整數，x1,x2,y1,y2，表示一個詢問，即詢問在平方圖G^2中，其頂點區間[x1,x2]中的每一個頂點至頂點區間[y1,y2]中的每一個頂點是否都有邊。

圖論練習題 摔跤 rassle 題解

【問題描述】

有兩種類型的職業摔跤手：一種是“好選手”，另一種是“差選手”。對於任何一對職業摔跤手來說，他們中可能有、也可能沒有比賽。假定有 n 位職業摔跤手，並且有一份清單，上面列出了 r 對參加比賽的摔跤手。寫一個程序,它能夠確定是否可能指定某些摔跤手為好選手，而將餘下的摔跤手指定為壞選手，從而使得每一場比賽都是在一個好選手與一個差選手之間進行。如果有可能做出這樣的指定，你的程序就應該將它產生出來，否則輸出無解“No”。

【輸入格式】

第1行有三個整數n，r。n是職業摔跤手的數量，r是比賽場數，它們之間用一個空格隔開。

接下來的r行，每行用兩個數V1，V2表示V1號摔跤手與V2號摔跤手比賽，選手從1開始編號。

【輸出格式】

輸出有兩行，第一行“好選手”的編號，第二行為“差選手”的編號，編號之間用一個空格隔開。

注意：為了鼓勵選手，使輸出答案唯一，請儘量多的將選手設為“好選手”，並且在可行條件下選擇編號小的選手為“好選手”。

如果無解，則輸出一行“No”。

動態規劃練習題 相似基因 gene 題解

問題描述

大家都知道，基因可以看作一個鹼基對序列。它包含了 4 種核苷酸，簡記作 A,C,G,T 。生物學家正致力於尋找人類基因的功能，以利用於診斷疾病和發明藥物。

在一個人類基因工作組的任務中，生物學家研究的是：兩個基因的相似程度。因為這個研究對疾病的治療有著非同尋常的作用。兩個基因的相似度的計算方法如下：

對於兩個已知基因，例如 AGTGATG 和 GTTAG ，將它們的鹼基互相對應。當然，中間可以加入一些空鹼基 - ，例如：

A	G	T	G	A	T	-	G
-	G	T	-	-	T	A	G

這樣 , 兩個基因之間的相似度就可以用鹼基之間相似度的總和來描述，鹼基之間的相似度如下表所示：

那麼相似度就是： (-3)+5+5+(-2)+(-3)+5+(-3)+5=9 。因為兩個基因的對應方法不唯一，例如又有：

A	G	T	G	A	T	G
-	G	T	T	A	-	G

相似度為： (-3)+5+5+(-2)+5+(-1)+5=14 。規定兩個基因的相似度為所有對應方法中，相似度最大的那個。

[搜索]ACM練習題：分球 ball 解題報告

題目來源：
1. 浙江理工大學 OnlineJudge 2584
2. 山東理工大學 OnlineJudge 1406

【問題描述】

在一個裝滿財寶的屋子裡，有2N個盒子排成一排。除了兩個相鄰的空盒外，其餘的每個盒子裡都裝有一個金球或者一個銀球，總共有N-1個金球和N-1個銀球。用圖6．3所示為一個N=5時的例子，G表示金球，S表示銀球。

G

S

S

G

G

S

G

S

任意兩個相鄰的非空的盒子裡的球可以移動到兩個相鄰的空盒中，移動不能改變這兩個球的排列順序。寫一個程序，用最少的移動次數把所有的金球都移到所有的銀球的左邊。