2016年2月24日 星期三

[HOJ 179][Codeforces #121]爆炸的期中考 (題目備份)

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

Problem : 179 - 爆炸的期中考

Problem Statistics
Solved Member: 24  Submission: 61  User Tried: 24
Problem:
有一天,hh國國王Seven One Two Two For Life命令史記官整理王族歷屆來的祖譜。如你所見hh國國王的名字非常長,這是歷屆以來的傳統,也是國家強大的秘方,這讓史記官十分的苦惱,因為這樣記錄起來十分的不方便,所以史記官總是會為這些名字長的國王縮寫!縮短的方法是只取出所有的第一個字母,他便會變成SOTTFL,既不失王者風範,也可以方便紀載hh國的歷史。

hh國的歷史非常長,根據王國的傳統,繼承者的首名,必須跟前任國王的尾名一樣,因此在史記官的神奇縮寫下,你會發現繼承者的開頭字母會與前任國王的結尾字母一樣。

難過的是,再強大的王國也有滅亡的一天,傳說,在隕石砸落後,hh國便滅亡了...

身為hh國的後裔hanhan,聰明的找到自己的祖譜,打算將所有名字串起來,並將其取為新名字,此時hanhan意外的發現,hh國第一任國王的第一個字母,與最後一任國王的最後一任字母一樣(縮寫後),並在其中找出了一翻奧妙,開了一門The name of HanHan's Dynasty Algorithm。

在數十年後,hanhan也因此成名,現在你正在期中考,hanhan依照年份給了你一堆國王與親屬的名字,根據他祖先的命名方法,你要從裡面選出一些名字做為歷屆國王,問此新名字最長可能為多長。
Input:
第一個數字T代表你有T題題目要寫。每題題目的第一個數字n(1≤n≤500000)代表全部有多少個名字,接下來有n行,每行有一個字串Si,代表按照時間點所寫下來的名字,其中名字的長度不會超過十個字元,且全為小寫字母。
Output:
對於每一題題目輸出一個數字代表此王國的歷屆名字最長的可能長度。若hh國並不存在,請輸出0。
Sample Input:
3
3
abc
ca
cba
4
vvp
vvp
dam
vvp
3
ab
c
def
Sample Output:
6
0
1
HINT:
題目1:"abccba"比"abcca"還長

題目2:不可能存在hh王朝

題目3:只有一個國王,名字是"c"
Source:
Codeforces #121
Problem Setter
hanhan0912
Testdata:
TestTimeMemoryScore
0500ms131072kb
1-1500ms131072kb10
1-2500ms131072kb
1-3500ms131072kb
2-1500ms131072kb10
2-2500ms131072kb
2-3500ms131072kb
3-1700ms131072kb10
3-2700ms131072kb
3-3700ms131072kb
4-1700ms131072kb10
4-2700ms131072kb
4-3700ms131072kb
5-1700ms131072kb10
5-2700ms131072kb
5-3700ms131072kb
6-1700ms131072kb10
6-2700ms131072kb
6-3700ms131072kb
7-11000ms131072kb10
7-21000ms131072kb
7-31000ms131072kb
8-13000ms131072kb10
8-23000ms131072kb
8-33000ms131072kb
9-14000ms131072kb10
9-24000ms131072kb
9-34000ms131072kb
10-15000ms131072kb10
10-25000ms131072kb
10-35000ms131072kb

沒有留言:

張貼留言

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