若水而净万物

版权声明：转载时请以超链接形式标明文章原始出处和作者信息及本声明
http://iuaaui.blogbus.com/logs/5254480.html

考得不怎么样。才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或暴队列。。。