USACO Feb12 Bronze Rope Folding 折繩子 題解

USACO 2012 February Contest, Bronze Division

Problem 1. Rope Folding

Problem 1: Rope Folding [Brian Dean, 2012] 
Farmer John has a long rope of length L (1 <= L <= 10,000) that he uses for various tasks around his farm. The rope has N knots tied into it at various distinct locations (1 <= N <= 100), including one knot at each of its two endpoints. 

FJ notices that there are certain locations at which he can fold the rope back on itself such that the knots on opposite strands all line up exactly with each-other:
  
Please help FJ count the number of folding points having this property. Folding exactly at a knot is allowed, except folding at one of the endpoints is not allowed, and extra knots on the longer side of a fold are not a problem (that is, knots only need to line up in the areas where there are two strands opposite each-other). FJ only considers making a single fold at a time; he fortunately never makes multiple folds. 

PROBLEM NAME: folding
INPUT FORMAT:
 * Line 1: Two space-separated integers, N and L.
 * Lines 2..1+N: Each line contains an integer in the range 0...L specifying the location of a single knot. Two of these lines will always be 0 and L. 

並查集練習題 島國 jx 題解

【題目描述】
很久很久很久很久很久很久以前......

有一個島國。

這個國家的領地是一塊座標從(1,1)到(K,K)的正方形（包括領海和領陸，座標(x,y)是指(x,y)這塊土地，並非一個點）

衛星資訊會告訴你這個國家的土地情況，希望你能根據給出的資訊計算出這個國家有多少個島。

衛星給出的資訊形如x1 y1 x2 y2，表示左下角座標為x1,y1,右上角座標為x2,y2的這一個矩形區域是陸地

輸入格式：

第一行一個整數n，表示衛星會傳送給你n條資訊

下面n行每行有4個整數，x1,y1,x2,y2，含義如上

輸出格式：

第一行，一個整數Sum，表示這個國家的島的數量

注，只有一個公共點的兩塊陸地不算是一塊區域，具體如樣例

OI練習題 式子 recursion

【問題描述】

動態規劃 DP 的實現形式之一是遞推，因此遞推在 oi 中十分重要。在某資訊學的分支學科中， LC 學會瞭如何求一階線性遞推數列。由於他現在正在學習主幹學科，因此希望知道求出 N 階線性遞推數列。為此，他瞭解到了以下的內容：

一個 N 階線性遞推式是這樣的式子：

也就是說，這個數列的每一項都是由他之前連續 N 項加權相加所得。其中還包括一個常數 an 。

例如，當 N=2 ， a0=a1=1 ， a2=0 時，這個式子就是我們熟悉的斐波那契數列。當然，作為這界條件， f0 、 f1…f n-1 都是已知的。

LC 對這如何去求這個式子一籌莫展，因此請你來幫助他。你的任務就是對於一個給定的 N 階線性遞推式，求出它的第 K 項是多少。

【輸入文件】

第一行兩個整數： N ， K ，其中 N 表示這個式子是 N 階線性遞推式， K 表示你需要求得那一項。

第二行有 N+1 個整數： A0,A1,… ， An ，表示這個遞推式的係數。

第三行有 N 個整數： F0 ， F1 ， …. ， Fn-1 ，表示數列的初始值。

【輸出文件】

只有一行，其中只有一個整數，表示這個數列第 K 項的值。由於資料較大，你只需輸出結果 mod 9973 的值。

ACM/ICPC 小球鐘——時間與運動

問題描述

時間是運動的一種方式，所以常常用運動來度量時間。如圖所示的小球鍾就是一個通過不斷在軌道上移動小球來度量時間的簡單設備。

每分鐘，一個轉動臂將一個小球從小球隊列的底部擠走，將它上升到鐘的頂部並安置在一個表示分鐘， 5 分鐘和小時的軌道上。這裡可以顯示從 1:00 到 12:59 範圍內的時間，但無法表示 “a.m.” 和 “p.m.” 。若有 2 個球在分鐘軌道， 6 個球在 5 分鐘軌道及 5 個球在小時軌道上，就顯示時間 5:32 。

不幸的是，大多數市場上提供的小球鍾無法顯示日期，儘管只需要簡單地加上一些軌道就可以了。當小球通過鐘的機械裝置被移動後，它們就會改變其初始次序。仔細研究它們隨著時間的流逝發生的次序的改變，可以發現相同的次序會不斷出現。由於小球的初始次序最後遲早會被重複，所以這段時間的長短是可以被度量的，這完全取決於所提供小球的總數。

每分鐘，最近最少使用的那個小球從位於球鍾底部的小球隊列被移走，並將上升安置於顯示分鐘的軌道上，這裡可以放置 4 個小球。當第 5 個小球滾入該軌道，它們的重量使得軌道傾斜，原先在軌道上的 4 個小球按照與它們原先滾入軌道相反加入到鍾底部的小球隊列。引起傾斜的第 5 個小球滾入顯示 5 分鐘的軌道，該軌道可以放置 11 個球。當第 12 個小球滾入該軌道，它們的重量使得軌道傾斜，原先 11 個小球同樣以相反的次序加入鍾底部的小球隊列。而這第 12 個小球滾入了顯示小時的軌道。該軌道同樣可以放置 11 個球，但這裡有一個外加的固定不能被移動的小球，這樣小時的值域就變為 1 到 12 。從 5 分鐘軌道滾入的第 12 個小球將使小時軌道傾斜，這 11 個球同樣以相反的次序加入鍾底部的小球隊列，然後第 12 個小球同樣加入鍾底部的小球隊列。

輸入小球的個數，輸出該時鐘在經過多少天的運行可以回到它的初始小球序列。例如有 45 個小球的鐘經過 378 天會回到初始狀態。

圖論練習題 備用交換機 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

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

【拓撲排序練習題】課程安排問題 curriculum

【問題描述】

一個軟體專業的學生必須學習一系列基本課程，其中有些課程是基礎課，它獨立於其它課程，如《高等數學》、《計算引論》；而另一些課程必須在學完作為它的基礎的先修課程才能開始。如，在《程序設計基礎》和《離散數學》學完之前就不能開始學習《資料結構》。這些先決條件定義了課程之間的領先（優先）關係。請你在符合上述領先（優先）條件的前提下，給出所有課程的一個有序序列，以方便學校排課。

【輸入格式】

輸入文件有若干行

第一行，一個整數n，表示共有n(0<n<=100)門課程

第2--n+1行分別表示第1--n門課程的先修課程資訊，每行有若干個整數m,s1,s2,...,sm

m表示該門課程有m門先修課程，s1,s2,...,sm分別表示m門先修課的編號，如果該門課沒有先修課程，則m為0。

【輸出格式】

一行，n個整數，表示n門課程編號的有序序列(如果這樣的序列不存在，則輸出no;如果有多個這樣的序列，輸出字典序最小的)

【強連通分量】四面楚歌 virus 解題報告

【題目描述】

公元2008年10月31日星期五，篤志者所在的整個機房由於猖獗的病毒一片恐慌。經查證，病毒是由A1機器散播開來的。。這要追溯到29日，篤志者由於病毒被迫從A1機器撤離。

一想到病毒是從自己的機器傳開的，篤志者就心神不寧。他決定搞清楚病毒是怎麼散播開來的。事實上，機房內的機器並不是全部都能夠互相感染的。篤志者（ceeji）好不容易經過測試得到了機房中各機器間是否連通的圖表，就在他馬上就要得出結果的時候，大腦突然亂了！問題的嚴重性在於：如果他不在1s內搞清楚這個問題，機房就會整體癱瘓。現在篤志者求助於你，他需要知道病毒從未感染機房開始，最少入侵幾臺機器之後，機房就會整體感染。

【輸入格式】

文件的第一行為一個整數n，第二行至第n+1行為n*n的矩陣（若第i行第j列為1，則機器i能對機器j進行ARP攻擊（即感染機器j），若第i行第j列為0，則機器i不能感染機器j）。

文件名為“2.in”。

【輸出格式】

輸出文件只有一行，為篤志者想知道的最少感染機器數。

文件名為“2.out”。