SLPC 2004 repeatless问题Python代码超时求优化方案

你当前的两段代码超时核心原因是暴力枚举+低效的重复校验：

• 逐个数遍历判断，大量带有重复数位的无效数字占用了绝大多数运行时间，越高位的数无效占比越高
• 转字符串、转集合的校验方式本身开销远大于数值运算

方案1：直接生成无重复数位的数（最优） #

不要被动校验重复，主动按从小到大的顺序生成所有无重复数位的数，完全避免无效计算，本质是BFS生成组合数：

from collections import deque
import sys
sys.stdin = open('input.txt')

# 预生成所有无重复数位的数，按升序排列
res = []
q = deque()
# 初始化1位数，1-9，mask对应数位出现标记
for i in range(1, 10):
    q.append((i, 1 << i))

while q:
    num, mask = q.popleft()
    res.append(num)
    # 生成到满足1e6次查询的量级即可
    if len(res) >= 1000000:
        break
    # 追加下一位，只能用没出现过的数字
    for d in range(0, 10):
        if not (mask & (1 << d)):
            new_num = num * 10 + d
            new_mask = mask | (1 << d)
            q.append((new_num, new_mask))

# 处理查询
while True:
    n = int(sys.stdin.readline())
    if n == 0:
        break
    print(res[n-1])

该方案预生成过程只有不到200万次有效操作，完全不会超时，内存占用也远低于128MB限制。

方案2：优化现有校验逻辑 #

如果不想调整生成逻辑，可以把字符串转集合的校验替换为位运算，能提升3-5倍运行速度：

def has_duplicate(num):
    mask = 0
    while num:
        d = num % 10
        if mask & (1 << d):
            return True
        mask |= (1 << d)
        num = num // 10
    return False

把你原来的len(set(a)) != len(a)逻辑替换为调用该函数即可。

Python中可以用time模块统计运行时间：

import time
start = time.time()
# 你的代码逻辑
end = time.time()
print(f"运行耗时：{end - start}秒")

内容的提问来源于stack exchange，提问作者곽동현