素数之积

给定一个整数 ，求该数是否为两素数之积。

一开始我试图用筛选法打表把所有素数打出来，因为我觉得直接暴力枚举并检测素数肯定会超时。结果发现光是打出来的表就直接爆内存了（
因为两个因子必定一个是小于等于 ，另一个大于等于 ， 于是就把打表范围降到 ，表长度 。
然后在表中枚举小于等于 的因子，判断另一个因子是否素数。
判断另外一个因子是否素数时也可以利用打表信息，当该因子小于等于 是可以利用二分法直接查找是否在表中。
大于 时，记该因子为 ，因为 ，所以，因此可枚举表中 判断是否包含 的因子，没有则为素数。
因此最坏时间复杂度为 。

其实后来想了想，枚举 的因子需要 ，检测该因子是否素数需要 ，整体时间其实也是 。
实际测试 时打表大概 2ms，枚举 10ms，完全不会超时。

n = int(input())

#### 打表 ####

import bisect

primes = [...]  #表略

sqrt = n ** 0.5

for p in primes:
    if p > sqrt:
        print(-1, -1)
        break
    if n % p == 0:
        div = n // p
        if div <= primes[-1]:
            if primes[bisect.bisect_left(primes, div)] == div:
                print(p, div)
                break
        else:
            is_prime = True
            sqrt2 = div ** 0.5
            for p2 in primes:
                if p2 > sqrt2:
                    break
                if div % p2 == 0:
                    is_prime = False
                    break
            if is_prime:
                print(p, div)
                break            
else:
    print(-1, -1)

#### 枚举 ####

def is_prime(n):
    if n == 1:
        return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

for i in range(2, int(n ** 0.5) + 1):
    if n % i == 0:
        if is_prime(i) and is_prime(n // i):
            print(i, n // i)
            break
else:
    print(-1, -1)

工厂流水线

给定 条流水线与 个作业，每个作业的作业时间 。流水线总是优先选取作业时间最短的作业进行工作。求总工作时长。

堆就完事了。不过输入数据巨坑， 的数量会多于 ，卡了我半天。

import heapq

m, n = map(int, input().split())
t = list(map(int, input().split()))[:n]

t.sort()

h = t[:m]

heapq.heapify(h)

for i in range(m, n):
    heapq.heapreplace(h, h[0] + t[i])

print(max(h))

完全波形信号

给定一个由 0 和 1 组成的字符串。一个信号定义为由 0 开头和结尾，中间不会有连续两个 0 的一个子串。求输入中最长的 0、1 交替的波形信号。

直接正则替换，能一行解决的绝对不写第二行（

import re

s = '0' + input() + '0'

waves = re.sub(r'0{2,}', '0|0', s).split('|')[1:-1]

ans = ''

for w in waves:
    if all(w[i] != w[i + 1] for i in range(len(w) - 1)):
        ans = max(ans, w, key=len)

print(ans or -1)