2016年2月24日 星期三

[HOJ 182][COCI 2011/2012 #5]hh盜墓記 (題目備份)

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

Problem : 182 - hh盜墓記

Problem Statistics
Solved Member: 7  Submission: 58  User Tried: 13
Problem:
在hh看完盜墓筆記後,很喜歡主角天真無邪與胖子與悶油瓶小哥在古墓的歷險,因此帶了他收服的龍前往他們去過的古墓。

書中都說要準備黑驢子蹄,以防有粽子突然蹦蹦蹦地跳出咬你,但hh並不需要,他有的是觸手與龍可以幫他對付「血劇死」(一種血粽子的進化版本,喜歡用觸手攻擊路過的盜墓者),於是hh很開心的帶著他的龍出發了。

古墓裡有許多機關,但在魔法威能的龍使面前都不堪一擊,直到出現了一個散發出神秘力量氣息的門,這是一扇用什麼魔法都無法摧毀的門。


想得到我的祕寶嗎,去追尋吧,我全都放到門的後面。
注:要打開這扇門就要解開此密碼。


門上突然顯現出這幾個字。

之後便出現一串長度為N,全由小寫英文字母所組成的字串S,接著眼前也出現了M個字串卡,奇怪的是每種字串卡怎麼拿也拿不完,看來被施了很強大的魔法,莫非這裡是... ...

此時神秘男子的聲音再度響起。


想通過這扇門,就先破解密碼吧!一個字串卡Li如果是S的子字串,便能覆蓋那段區間,當你把所有可能被覆蓋的字母覆蓋後,密碼就出來了...


這應該是那位偉大的龍使弗利茲的棺木吧!喔喔喔,這真是令人興奮的一件事,請你幫hh解出密碼吧!
Input:
第一行有一個數字N ( 1 ≤ N ≤ 300000 )
第二行有一長度為N的字串S
第三行有一個數字M ( 1 ≤ M ≤ 5000 )
接下來M行,每行一個字串Li,其中長度不超過5000
Output:
請輸出一個數字代表密碼長度。
Sample Input:
Sample A:
6
abcbab
2
cb
cbab

Sample B:
4
abab
2
bac
baba

Sample C:
6
abcabc
2
abca
cab
Sample Output:
Sample A:
2

Sample B:
4

Sample C:
1
HINT:
最後hh解出的密碼在經過一連串加密後是 7122
hh興奮得進去後,發現裡面一無所有... so sad...
前往下一個目的地 (?)
Source:
COCI 2011/2012 #5
Problem Setter
hanhan0912
Testdata:
TestTimeMemoryScore
0-1500ms524288kb
0-2500ms524288kb
0-3500ms524288kb
1500ms524288kb8
2500ms524288kb8
31000ms524288kb8
4-11500ms524288kb14
4-21500ms524288kb
5-11500ms524288kb14
5-21500ms524288kb
6-18000ms524288kb16
6-212000ms524288kb
6-310000ms524288kb
6-48000ms524288kb
7-18000ms524288kb16
7-212000ms524288kb
7-310000ms524288kb
7-48000ms524288kb
8-18000ms524288kb16
8-212000ms524288kb
8-310000ms524288kb
8-48000ms524288kb

沒有留言:

張貼留言

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