解题报告_.doc

买彩票
此题最初可能想到用搜索，不过如果仔细分析题目会发现其实用贪心就可以解了。虽然中奖的概率会不断变化，但概率只和在该抽奖地点的抽奖次数有关，和抽奖的总次数以及时间无关。所以，我们可以枚举起始S和终点T的抽奖地点，则在路上花费的时间可以求出，那么在这个范围内的抽奖，可以看作bird能瞬间转移，那么我们只需将此范围内的抽奖概率排序，取前若干个，使得花费的时间不超过时限。很容易证明，这种方法是最优的。
此题的贪心关键是要先确定一个范围，然后针对具体的范围贪心。贪心法的隐秘性还是比较强的。

BuyLow,BuyLower
此题的实质就是求最长下降子序列。不过要求输出不同的方案总数。
如果直接套用经典的求最长不下降子序列的方程，那么方案数会出现重复。为了避免重复，我们将序列从大到小排序，那么我们计算的对象就变为标号，注意排序时如果两数相等就按照原来序列的位置的前后放置。设f[I]表示以第I为为结尾的最大长度，fn[I]表示方案数。那么当计算f[I]的时候，我们从I-1循环到1（不是从1循环到I-1），那么当遇到一个满足条件的j时，如果之前有遇到过等值的并且也符合条件的数k，那么就不用在fn[I]上加上fn[j]的值了，因为到达j的方案数在计算k时都已经记录过了，这样就可以避免重复了。最后求总方案数时也是一样。
这道题目在原来的经典题目上加以了一定的变化，不过总的说来，还是一道比较简单的题目。

Bird的烦恼
这是一道让人头痛的物理题目，数据范围很大，所以解决此题肯定有一个特殊的公式。
需要注意的是题目的条件——“包含了n只不同的安培表，和n只相同的伏特表”。既然伏特表是相同的，那么就意味着伏特表的内阻相同，这一点对于推导出公式很重要。
安培表A1测的是干路上的电流，容易知道a1=a2+I1，I1是伏特表1的电流值。所以I1=a1-a2，根据欧姆定律，可算出R1(R1是伏特表1的内阻值)。伏特表的读书之和tot=I1*R1+I2*R2……+In*Rn，由于R1=R2=……=Rn，所以tot=(I1+I2+……+In)*R1，又因为I1,I2,……,In都是支路上的电流，所以I1+I2+……+In=a1，所以tot=a1*v1/(a1-a2)。
解决此题要认真分析题目，当然也需要一定的物理知识。

城市公路网
这是一道求最少路径覆盖的题目。可以用经典的最大流或者二分图的最大匹配求解。
如果我们每次都重新求解，那么无疑会浪费很多时间，其实，每个新的图都是在前面已有的图的基础之上生成的，所以可以增量求解。每次找增广轨即可，避免重复计算，时间效率就提高了很多。
对于这类图论的题目，一般都采用增量求解，每次在已求得的基础上更新，例如CTSC99的家园，还有IOI2003的路径维护，都是类似的思想。