自动搬运

查看原文

来自洛谷，原作者为

	KomeijiReimu **

搬运于2025-08-24 23:13:22，当前版本为作者最后更新于2025-04-30 21:41:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

https://www.luogu.com.cn/problem/P12171

长度为 $1$ 的字符串自动变成优美字符串，因此一定是从长度小的字符串开始升序更新，于是把整个字符串组按照长度排序。

考虑题目中说只要字符相同，就算次序不一致也能匹配。于是在比对是否一致的时候，把每个字符串用字典序排序，这样就不用管次序，直接匹配即可。

从头到尾枚举每个字符串，每次判断这个字符串是否为优美字符串，方法是将当前字符串去掉末尾一个字符后按字典序重新组合，判断排序后的字符串是否在优美字符串库内，如果是则把当前字符串入库，并且更新最长的优美字符串。 值得注意的是，在把优美字符串入库时，也要对该字符串进行重新排序，因为不排序就没法与下一个去掉末尾字符的字符串进行直接比较。

import sys


def solve():
    with open("words.txt", "r") as f:
        words = [line.strip() for line in f.readlines()]

    # 排序：首先按长度排序，长度相同则按字典序排序
    words.sort(key=lambda x: (len(x), x))

    # set存储所有优美字符串
    Bs = set()

    # 查找最长的优美字符串
    longestBs = ""

    for word in words:
        # 排序去掉末尾的字符串
        newsub = list(word[:-1])
        newsub.sort()
        # 排序整个字符串，为入库做准备
        news = list(word)
        news.sort()

        # 检查当前单词是否可以成为优美字符串
        if len(word) == 1 or str(newsub) in Bs:
            Bs.add(str(news))
            # 更新最长的优美字符串
            if len(word) > len(longestBs):
                longestBs = word
            # 一样长找字典序最小的
            elif len(word) == len(longestBs):
                longestBs = min(longestBs, word)

    return longestBs


sys.stdout.write(solve())