今天又是模拟题（还是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为边权，即边的长度）。

      第四步：输出即可。