今天又是模擬題（還是2005年的），這次的題目普遍偏難（至少對我這個菜鳥來說）

題目共4道，如下：

****************

第一題：

建設圍墻 (wall.pas)
保定一中要為一棟教學樓建圍墻
為了美觀，圍墻離樓的距離不能小于一個常數L，求如何建造圍墻最節省材料
?
Input (wall.in)
第一行兩個整數N和L，N 表示教學樓的頂點個數
接下來N行按順時針順序給出教學樓的N 個頂點坐標Xi,Yi 用一個空格隔開
頂點不會重合 不會有邊在除頂點之外的地方相交,Xi Yi在[-10000,10000]內
Output (wall.out)
輸出最小的圍墻長度 四舍五入保留整數

第二題：

植樹運動 (tree.pas)
保定一中有T棵銀杏樹排成一列，依次編號為1~T
為美化校園 學校決定在T棵銀杏樹的空隙中栽種若干棵梧桐樹
信息學競賽小組負責規劃栽樹方案……
Einstein提出了n條形如 a b c (a<b) 的建議，即a b 兩棵銀杏之間的梧桐不能少于c
Erwin提出了m條形如 b a -c (a<b)的建議，即a b 兩棵銀杏之間的梧桐不能多于c
請你設計出一個方案，滿足所有Einstein和Erwin的建議，并且使需要的梧桐樹最少。
Input (tree.in)
第一行3 個整數T n m,用空格隔開
以下n行，每行3 個數，表示Einstein的一條建議
以下m行，每行3 個數，表示Erwin的一條建議
Output (tree.out)
輸出T-1行
第i行有一個非負整數表示第i棵和第i+1棵銀杏之間種了多少棵梧桐
如果多解，輸出任意一組
如果無解，輸出"No solution."(注意".")

第三題：

飯票 (bticket.pas)
保定一中的食堂在使用飯卡之前使用飯票
飯票并不向飯卡一樣方便。比如你有1 張5 元飯票和3 張1 元飯票，則你無法付4 元的
飯費。
某天小x 去食堂吃飯，手里有n種飯票，面值分別為A1～An,數量分別為C1～Cn
請你計算小x 的飯票能組成多少在[1,m]區間內的面值。
Input (bticket.in)
第一行2 個數n m，用空格隔開。
以后n個數，分別為A1..An
以后n個數，分別為C1..Cn
Output (bticket.out)
一個數，即問題的答案

第四題：

平均距離 (ave.pas)
給定一個含n個點的無向連通圖，任意兩點間有且僅有一條路徑，求兩點間距離的平均
值，即 Σdisij/(n*n-n) (1≤i≤n,1≤j≤n)
Input (ave.in)
第一行一個正整數n
隨后n-1行每行3個正整數a b c，表示a b兩點間有一條長度為c的邊
Output (ave.in)
輸出兩點間平均距離，保留兩位小數。

*****************

?

My Solution:

第一題：

????? 此題從數學角度說，非初三畢業人士可為之試題。

????? 首先一點，也是最難的一點，就是要通過給出的每個點的坐標求出凸多邊形每個點連接的循序，求出凸多邊形（好似稱為“凸包”）

??????因此，此題先被歸類為不可解。

第二題：

????? 空。

第三題：

????? 此題為一道經典問題，即選硬幣的問題（硬幣即為此處的飯票）。

????? 下面引用題解中的一段文字：

**************

解題思路：
?最容易想到的算法是O(m*n*max(ci)).
?我們用O(m*n)的算法。設已經考慮了前i-1個A了，現在要把第i個A加進去。依次考慮1-m中每個數，如果還沒有標記過（設為x）,則考慮x-Ai是否已被標記過。如果沒有，則x也不用考慮，否則，看看x-Ai是不是由x-2*Ai生成的。如果不是，則x可以由x-Ai生成，同時記錄下來，x最后一步是加了Ai生成的，并且已經用過了1個；如果是，則考慮x-Ai是用了幾個Ai之后生成的，如果超過了Ci，則x不能生成，否則可以，標記x可被生成，最后一步是加了Ai生成的，并且Ai用過的次數比x-Ai多1。
?最后統計一下1-m中有多少個生成即可。

**************

?????? 再談談我對題解的理解：

?????????? O(m*n)的算法和普通的算法的最大不同在于：普通算法的實際意義為，通過已知可以拼得的價值加上當前選定的一枚硬幣，再將得出的新值標記，一般需要3層循環；效率更高的算法的實際意義為，枚舉當前可能的未拼出情況，看看是否能用有限的當前種類硬幣拼得，在實際實現過程中，可減少為2層循環，時間復雜度大大減少。

第四題：

????? 題目給的很明確，由于每兩個點之間有且僅有一條路徑，路徑數為n-1。以上，表明了所給的圖其實既是一棵生成樹，或者說應該是一棵無根樹。下面的問題似乎明朗起來了：

????? 數據結構：邊集數組（很顯然，數據規模不允許臨接矩陣的存在；使用臨接表也無疑增加了這道題的編寫難度。邊集數組的優越性在后面還會有所體現）

????? 第一步：完成構造這棵樹，這里采用直接記錄每個點的根節點的方法，即講一次輸入的兩個節點，前者記為后者的父親。

????? 下面，我有兩種思路，1、通過“最近公共祖先”的方法,枚舉所有組合，求出所有兩點間路徑的長度；2、用數學方法，求出所有邊的使用次數（因為每兩個節點間的路徑是唯一的）。

????? 不用我多說，后者的效率一定大大高于前者（經試驗，前者可通過4-6個點）。

????? 下面就討論后者方法的實現問題：

????? 我們發現，對于每一條邊，在期前端的每一個節點都需要通過這條邊才能到達它后端（以及其后）的節點，所以這條邊必然被使用? 其前端的節點數*其后端的節點數(次） 。這樣通過對邊的搜索，就可以得到總路徑的和。

????? 這時，對于每一個節點，我們需要記錄一個新的量，即以每個節點為根的子樹所包含的節點數。（方法很簡單，遞歸搜索即可，見程序）

????? 第二步：以每個節點為根的子樹所包含的節點數。

????? 第三步：循環每一個邊，這條邊所產生的路徑長即為 a*(n-a)*w (注：a為這條邊兩端節點的記錄量的較小值；w為邊權，即邊的長度）。

????? 第四步：輸出即可。