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 次操作以後的溶液質量和濃度。