Posted on 2009-02-12 23:08
hello_world 閱讀(1643)
評(píng)論(0) 編輯 收藏 引用
Waterloo local 2001.09.22
題目分類
|
| Average Speed |
簡(jiǎn)單題 |
| Subway |
圖論，最短路 |
| Babelfish |
Map |
| Bounding box |
幾何 |
A multiplication game
|
博弈，局面
|
Subway：
把n個(gè)地鐵站抽象為點(diǎn)，起點(diǎn)為家，終點(diǎn)為學(xué)校！一共n+2個(gè)點(diǎn)，僅當(dāng)兩個(gè)地鐵站在一條線路上且相鄰他們的距離才是實(shí)際距離的1/4, 各個(gè)點(diǎn)之間的距離就為實(shí)際距離，然后求起點(diǎn)到終點(diǎn)的最短距離即可，然后換算成時(shí)間，注意的是雖然題目沒有說(shuō)但是每條線路上的站點(diǎn)是各不相同的！不用考慮得太麻煩！
Babelfish：
此題偷懶做可以用C++中的map，不過(guò)效率不是很高。如果想加快效率，可以用Trie樹來(lái)做。
bounding box：
求出圓心然后不斷旋轉(zhuǎn)
a multiplication game：
找必勝局與必負(fù)局，遞規(guī)求解
疲勞ing~~