2016年2月24日 星期三

[HOJ 189]ABC聚餐 (題目備份)

HOJ生病惹QQ,因此在此悼念昔日光彩
題目備份,請參考~
題解在這裡
敬告:目前HOJ主機也許進入瀕死狀態了,常常無預警跳電。請看到這則公告的人能注意備份自己的資料,感謝。
至於主機壞掉以後會如何目前並沒有任何規劃.. 
Submit  Ranklist

Problem : 189 - ABC聚餐

Problem Statistics
Solved Member: 5  Submission: 59  User Tried: 14
Problem:
hh參加了一個有趣的下午茶聚會,那是一個有趣的聚會。

他們在一家名為東加衣吃下午茶,東加衣的食品提供是經由兩條迴轉道出來的!每條迴轉道只有一個出口與一個入口,一個食物只會出現在你眼前一次,錯過就無法在得到他。在兩條迴轉道上,有著來自東京的蘋果(Apple), 加勒比海的香蕉(Banana), 以及衣索比亞的咖啡(Coffee)。

在神祕的龍使傳說下,Double Eat是比7122(某種宗教儀式)還爽的事,也就是同時吃兩個蘋果或兩根香蕉或兩杯咖啡。但如果這兩個食品來自同一個地方,那吃起來味道就一樣了,所以有一個嚴苛的條件是他們必須來自不同地方(也就是兩條迴轉道各提供一個)。

hh透過神秘方法得到了兩條迴轉道依序出口的食品,所謂好馬不吃回頭草,兔子不吃窩邊草,一種食物過了就不再回頭,hh也無法再吃到。所以hh很想預先知道自己可以吃到幾次Double Eat。

我們以A,B,C代替三種食物,給你兩個由A,B,C組成的序列,代表兩個出口線出來的食物順序,問問hh可以吃到幾次Double Eat。

為了化簡問題,hh決定吃了B後便不再吃A,吃了C後便不再吃A與B,這樣應該有把問題化簡吧? (炸飛

簡單的說,現在給你兩個由ABC所組成的字串,你要找一個最長長度的字串屬於兩個字串的共同子序列(不一定要連續),且是由A*B*C*所構成。

其中A*表示由不定個數的A所組成的字串(可以是空字串)。
Input:
第一行為數字T,表示有T組測試資料。
每組測試資料有兩行由A,B,C所組成的字串,每個字串長度不超過200000,分別表示兩條出口線出口食物順序。
Output:
對於每一筆測試資料,請輸出在化簡問題後,hh能得到幾次Double Eat!
Sample Input:
3
AABCABCB
AABCABCB
ABC
AAAAA
ABABC
ABBCCA
Sample Output:
5
1
4
HINT:
後來hh才發現,兩個出口線的食物來自同一個廚房阿!故hh無法得到Double Eat的爽感。
Problem Setter
hanhan0912
Testdata:
TestTimeMemoryScore
01000ms65536kb
11000ms65536kb10
21000ms65536kb10
31000ms65536kb10
41000ms65536kb10
51000ms65536kb10
61000ms65536kb10
71500ms65536kb10
81500ms65536kb10
91700ms65536kb10
101700ms65536kb10

沒有留言:

張貼留言

歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原