b839. 104北二3.朋友
Tags : LCS 分組最大團
Accepted rate : 83人/96人 ( 86% ) [非即時]
評分方式:
Tolerant

最近更新 : 2016-07-03 22:09

Content

3.朋友  (104北二區 桃竹苗 )

問題描述

當我們到一個新環境時,常常會從和我們有相同個性、喜好或來自相同故鄉的人們開始結交,我們也會對同姓交或名字相近的人感到熟悉或有好感。 在這道題目中,我們將假設朋友關係是這樣建立的:

(1)若兩個人的名字相似,則兩個人會結為朋友。

(2)若兩個人有共同朋友,則兩個人會結為朋友。

 

如何定義兩個人的名字相似呢?令兩個人的名字為 S 和 T ,我們說若S(長度為m)和T(長度為n)的最長共同子字串(Longest common subsequene,LCS)長度不小於min(m,n)/2.0,則S和T相似。  {LCS的定義就省略}

 

根據上上述的朋友關係,我們可以將一群人分成一個或數個團體,每個團體中的任意兩個人都是朋友,而兩個不同團體中的人則都不是朋友。現在,請你寫一個程式,輸出最大團體(人數最多)的人數個數。

  

Input

 輸入測資檔第一行有一正整數T(1<=T<=3),代表有T組資料,每組第1行正整數N(1<=N<=50)行,接著N行,每行有一個人的名字,全數讚小寫英文字母組成,長度為L(1<=L<=50)。

 

Output

每一組資料,輸出一行,最大團體的人數個數

Sample Input #1
3
5
abc
adb
xyzzzz
zzzxop
xompn
5
abc
adb
xyzzzz
zzzxop
xoapd
5
abc
adb
xyzzzz
zzzxop
xoape
Sample Output #1
3
5
3
測資資訊:
記憶體限制: 128 MB
公開 測資點#0 (25%): 1.0s , <1K
公開 測資點#1 (25%): 1.0s , <1K
公開 測資點#2 (25%): 1.0s , <1M
公開 測資點#3 (25%): 1.0s , <1M
Hint :

測資有誤,感謝 liouzhou_101 指正

Tags:
LCS 分組最大團
出處:
104北二區桃竹苗基資訊學科能力複賽 [管理者: p3a_owhj (阿普二信) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」