Posted on 2009-02-12 23:08
hello_world 閱讀(1656)
評論(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：
求出圓心然后不斷旋轉(zhuǎn)
a multiplication game：
找必勝局與必負局，遞規(guī)求解
疲勞ing~~