若水而净万物

B Mountains pku3227

题目意思就是你站在一个点上看一座连续的山，求可看到山的总长度。
我们可以把山的每一条线段分开考虑，分别求出每一条线段能看到的长度，累加起来即可。
精度也没什么要求，时间复杂度也不必考虑。可惜比赛时没看此题。。。

C Gold Transportation pku3228

题目意思就不讲了（虽然本人看成了最小费用最大流），算法就是二分+最大流，二分最长路，如果两点之间的路小于或等于二分的值，则这两点连两条相反的有向 边，且容量为无穷大。在建一个源和一个汇，分别与有黄金的村庄和储存黄金的村庄相连，容量为该村庄的拥有量或储量。求最大流判断即可。

D The Best Travel Design pku3229

考虑到n很小，可以用状态压缩的Dp(即炮兵阵地)。

G Accelerator pku3232

此题又是看错。。郁闷。
只要二分结束时间即可。。。还有要注意用int64。



这四题应该都能做出来。可惜老是理解错题目。。还是要多分析样例，以验证自己的理解是否正确。总得来说这次赛得不够理想，下次再加油吧。

考得不怎么样。才AC4道。。

先讲下AC的题

A String's Puzzle pku3226
题目大意是给一个长度为n的仅a..z组成的字符串，求这个字符串的编号。
比如：n=3时，
ABC 0
ABD 1
…… 　
ZYX 15599

简单题。算法就不细讲了。主要思路就是从前往后扫，边扫边加。
刚比赛的时候看到已有很多人AC了此题，所以先做了这道。。虽然高精度比较恶心，但还是一遍AC。。

D Travel pku3230
题目意思是说n个城市，m天，每天必须呆在一个城市，呆在某个城市可以赚到一些钱，从城市i到城市j需要一

些花费，问最多得多少钱。
看了一下数据范围，n,m<100,晕。简单的Dp。状态表示是opt[m,n]表示第m天在第n个城市最多能赚到的钱。这道题也是一次AC。


F FlashGet pku3231

这题关键要能够弄懂题目意思就不难做出来。题目意思是说有一些文件要下载。
给出每个文件的大小，初始下载速度和最大下载速度，求每个文件什么时候下载完。题目还有一个带宽限制，

即所有正在下载的文件速度总和不能大于带宽。关键要理解他那个HINT。
我就把HINT用人类的语言翻译出来吧。

HINT 提醒

当一个文件下载完成之后，多下来的带宽是这样分发的：
每一个没下载完并且没有达到最大速度的文件分到同样多的带宽（就是说带宽在没下载完并且没有达到最大速度的文件中平均分配），大家就要问了，万一平均分配下来有的文件超过了最大速度怎么办？那就不行，一定要以能分配的最大速度为准。 比如剩下6个带宽，还有2个文件没下完，第一个文件速度是1，可下的最快速度是3，第二个文件速度是1，刻下的最快速度是10。那么一开始只能以第一个文 件为基准，每个文件分配3-1=2个带宽，还剩6-2*2=2个带宽。剩下的2个带宽怎么分呢？继续按照上述规则分，直到不能分为止。这个例子中，这两个 带宽就全给第二个文件了。。


这道题第一遍交没有理解题意。。第二遍居然TLE。。原来是精度不够，循环跳不出来。。加了个特判之后第三遍才勉强AC。。。

H Pushing Boxes pku1475

题目大意就是大家熟知的推箱子游戏，可惜看错题目，耗了不少时间。推箱子是要使人推箱子的步数最少，而不是人走的步数和推箱子的步数的加和。。
但还是那么做，即不断BFS,不断迭代加深，直到不能扩展为止，而且已经扩展过的节点还是要扩展。。据说lrj的某篇论文已经证明这是NP-complete --！。所以队列尽量开大点吧。。所幸测试数据很弱，没有TLE或暴队列。。。