题目背景
注意:本题为上古 NOIP 原题,不保证存在靠谱的做法能通过该数据范围下的所有数据。
题目描述
单词接龙是一个与我们经常玩的成语接龙相类似的游戏,现在我们已知一组单词,且给定一个开头的字母,要求出以这个字母开头的最长的“龙”(每个单词都最多在“龙”中出现两次),在两个单词相连时,其重合部分合为一部分,例如 beast 和 astonish,如果接成一条龙则变为 beastonish,另外相邻的两部分不能存在包含关系,例如 at 和 atide 间不能相连。
输入格式
输入的第一行为一个单独的整数 nn 表示单词数,以下 nn 行每行有一个单词,输入的最后一行为一个单个字符,表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在。
输出格式
只需输出以此字母开头的最长的“龙”的长度。
输入输出样例
输入 #1
5
at
touch
cheat
choose
tact
a
输出 #1
23
以下为我用python做的代码,但是在洛谷中全部显示RE
在IDLE中将测试点1和题目测试点带入答案是正确的
在牛客上的此题已AC
stack,v,a,max_x=[],[],[],[]
tt={}
def next_s(s):
n_s=[]
for i in range(1,len(s)):
for j in a :
if j[:i]==s[-i:] and stack.count(j)<a.count(j)*2:
tt[s+"-"+j]=tt.get(s+"-"+j,i)
n_s.append(j)
return n_s
def s_len(li):
long_1=len(li[0])
for i in range(1,len(li)):
long_1+=(len(li[i])-tt[li[i-1]+"-"+li[i]])
return long_1
def Dfs(s):
stack.append(s)
flag,cnt,maxx=0,0,0
v.append([])
while len(stack) > 0:
flag = 0
vertex = stack[-1]
nodes = next_s(vertex)
for w in nodes:
if w not in v[cnt]:
v.append([])
v[cnt].append(w)
cnt+=1
flag = 1
stack.append(w)
break
if flag == 0:
if s_len(stack)>maxx:
maxx=s_len(stack)
cnt-=1
v.pop(cnt+1)
stack.pop()
return maxx
n=int(input())
head=[]
for i in range(n):
a.append(input())
ch=input()
for i in a:
if i[0]==ch:
head.append(i)
for i in head:
max_x.append(Dfs(i))
print(max(max_x))