题解：P12171 [蓝桥杯 2025 省 Python B] 最长字符串【缺少 words.txt】

Ag2WO4 · 2025-04-13 14:59:01 · 题解

根据题意给每个字符串一个统计属性，dfs 即可。由于长度递增无需设置 vis 数组，集合合并优化即可。

import sys,time;t=time.time();a={};c={(0,)*26};d=set();sys.stdin=open('words.txt','r')
for i in range(50000):
    s=input();b=[0]*26
    for i in s[:-1]:b[ord(i)-97]+=1
    b=tuple(b)
    if b in a:a[b].append(s)
    else:a[b]=[s]
while c:
    e='~'
    for i in c:
        for j in a[i]:
            e=min(e,j);k=list(i);k[ord(j[-1])-97]+=1;k=tuple(k)
            if k in a:d.add(k)
    c,d=d,set()
print(e,time.time()-t)

上述程序输出正确答案和用时（防止 TLE 做法的出现）。答案为字符串 afplcu，本地用时为 232\text{ms}，在 O(\sum|s|) 的复杂度下常数可以接受。