PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[情報] Google Code Jam 2008 第一題解法

看板Prob_Solve (計算數學 Problem Solving)作者 (十三)時間16年前 (2008/07/17 23:38), 編輯推噓11(11推 0噓 3→)
留言14則, 10人參與, 最新討論串1/2 (看更多)
Google Code Jam 2008　第一題 前面的宇宙會被擠壓的廢話就不多說了 這題的大意是在N組測資內, 有S個搜尋引擎要依序搜索Q個字 第一個選定的引擎不列入計算(count=0) 開始搜索後, 如果碰到的字和引擎的名字是相同的話 可以換引擎繼續搜索 求依序搜索完所有的字後, 所換引擎次數最少為多少 解法： 依次建立每個引擎不包括相同字的起點和終點 然後找終點最遠的引擎來更換 範例： 5 Yeehaw NSM Dont Ask B9 Googol 10 Yeehaw Yeehaw Googol B9 Googol NSM B9 NSM Dont Ask Googol 起點(從1開始算) 終點 Yeehaw 3 10 NSM 1 5 7 7 9 10 Dont ask 1 8 10 10 B9 1 3 5 6 8 10 Googol 1 2 4 4 6 9 開始跑： 從1開始跑, 有4個引擎都有1, 但Dont ask終點到8為最大, 所以一開始選Dont ask 再來從9開始跑, 包含9的有Yeehaw, NSM, B9　因為都到10　所以任選一個皆可 而10就是case的終點 所以換的次數最少為1次 還有5小時　有報名的可以參考看看 Bleed -- ACM's PARADISE http://bleed1979.myweb.hinet.net/ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 122.116.16.70
→
07/18 00:27, , 1F
我是直接從頭開始跑，判斷哪邊需要switch就好了
07/18 00:27, 1F
→
07/18 00:27, , 2F
畢竟輸出不需要包含用哪個engine
07/18 00:27, 2F
推
07/18 03:43, , 3F
我在想 search從頭掃到尾, 一直很greedy
07/18 03:43, 3F
→
07/18 03:43, , 4F
engine 五個都出現表示要換, 這樣會有問題嗎@@?y
07/18 03:43, 4F
推
07/18 08:50, , 5F
我也是用 greedy mathod
07/18 08:50, 5F
推
07/18 09:36, , 6F
greedy 的基本題呀, 下一題也是
07/18 09:36, 6F
推
07/18 15:00, , 7F
greedy is ok
07/18 15:00, 7F
推
07/18 18:11, , 8F
我比較想知道第三題怎麼解..
07/18 18:11, 8F
推
07/18 20:39, , 9F
我比較想知道第二題怎麼解..
07/18 20:39, 9F
推
07/19 01:51, , 10F
greedy +1
07/19 01:51, 10F
推
07/19 14:37, , 11F
greedy +1
07/19 14:37, 11F
推
07/19 22:39, , 12F
我用DP來解 XD, 果真變遲鈍了
07/19 22:39, 12F
推
07/20 15:09, , 13F
樓上(握) 當下不知怎麼不敢用greedy...orz
07/20 15:09, 13F
推
07/21 10:10, , 14F
第二題就表全部建起來event-driven就好了
07/21 10:10, 14F
‣ 更多 bleed1979 的文章
文章代碼(AID): #18VsTTAf (Prob_Solve)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 bleed1979 的文章
文章代碼(AID): #18VsTTAf (Prob_Solve)