华为德科OD笔试

素数之积

给定一个整数 $n \in (0, 2^{31}-1]$ ，求该数是否为两素数之积。

一开始我试图用筛选法打表把所有素数打出来，因为我觉得直接暴力枚举并检测素数肯定会超时。结果发现光是打出来的表就直接爆内存了（
因为两个因子必定一个是小于等于 $\sqrt n$ ，另一个大于等于 $\sqrt n$ ，于是就把打表范围降到 $(0,2^{15.5}]$ ，表长度 $4792$ 。
然后在表中枚举小于等于 $\sqrt n$ 的因子，判断另一个因子是否素数。
判断另外一个因子是否素数时也可以利用打表信息，当该因子小于等于 $2^{15.5}$ 是可以利用二分法直接查找是否在表中。
大于 $2^{15.5}$ 时，记该因子为 $f$ ，因为 $f < n \le 2^{31}-1$ ，所以 $\sqrt f < 2^{15.5}$ ，因此可枚举表中 $(0,\sqrt f]$ 判断是否包含 $f$ 的因子，没有则为素数。
因此最坏时间复杂度为 $O(\frac{1}{2}\times 4792^2 \approx 10^7)$ 。

其实后来想了想，枚举 $n$ 的因子需要 $O(\sqrt n)$ ，检测该因子是否素数需要 $O(\sqrt[4]{n})$ ，整体时间其实也是 $O(n^\frac{3}{4} \approx 2^{23.25} \approx 10^7)$ 。
实际测试 $n = 2^{31}-1$ 时打表大概 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)

工厂流水线

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

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

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)

#华为笔试##外企德科人力资源服务##华为OD#