Posted on 2009-02-12 23:08
hello_world 阅读(1616)
评论(0) 编辑 收藏 引用
Waterloo local 2001.09.22
题目分类
|
| Average Speed |
简单题 |
| Subway |
图论，最短路 |
| Babelfish |
Map |
| Bounding box |
几何 |
A multiplication game
|
博弈，局面
|
Subway：
把n个地铁站抽象为点，起点为家，终点为学校！一共n+2个点，仅当两个地铁站在一条线路上且相邻他们的距离才是实际距离的1/4, 各个点之间的距离就为实际距离，然后求起点到终点的最短距离即可，然后换算成时间，注意的是虽然题目没有说但是每条线路上的站点是各不相同的！不用考虑得太麻烦！
Babelfish：
此题偷懒做可以用C++中的map，不过效率不是很高。如果想加快效率，可以用Trie树来做。
bounding box：
求出圆心然后不断旋转
a multiplication game：
找必胜局与必负局，递规求解
疲劳ing~~