P6491 [COCI 2010/2011 #6] ABECEDA - 洛谷 数据比较弱，因为内存较小Python语言的话使用Python3提交
LCR 114. 火星词典 - 力扣 数据较强
CF510C - CodeForces
这类题的技巧是图建模。如果是非数字和非连续数字作为节点的话，选择字典进行存图是最好的选择。
-
先记录出现过的字符，再根据这些字符进行建图。
chars = set(''.join(text)) g = {c: set() for c in chars}din = {c: 0 for c in chars} # 入度统计 -
相邻单词对比较，比较遇到的第一个不同字母
s1[i]和s2[i]，建立有向边s1[i] -> s2[i]。 -
如果两串是前缀关系，那么根据字典序定义，前面长后面短的一定不合法。
-
最后正常判唯一性和环即可。
题目虽然没有说明无解
!和多解?的优先级，但这类题目一般优先输出无解的情况
具体代码为
import sys
from collections import deque
if 1:inp = lambda: sys.stdin.readline().strip()II = lambda: int(inp())MII = lambda: map(int, inp().split())LII = lambda: list(MII())Max = lambda x, y: x if x > y else yMin = lambda x, y: x if x < y else ydef main():n = II()text = [inp() for _ in range(n)]chars = set(''.join(text)) g = {c: set() for c in chars}din = {c: 0 for c in chars} for i in range(n - 1):cur = text[i]nxt = text[i + 1]for j in range(Min(len(cur), len(nxt))):if cur[j] != nxt[j]:u = cur[j]v = nxt[j]if v not in g[u]: # 注意这里度数要与边绑定g[u].add(v)din[v] += 1breakelse: # 遍历到最后没有触发 break 会进入这个 elseif len(cur) > len(nxt): # 前面更长一定不合法print("!")return dq = deque([c for c in chars if din[c] == 0])topo = []possible = Falsewhile dq:if len(dq) > 1:possible = Trueu = dq.popleft()topo.append(u)for v in g[u]:din[v] -= 1if din[v] == 0:dq.append(v)if len(topo) != len(chars):print("!")elif possible:print("?")else:print(''.join(topo))if __name__ == "__main__":main()