备战蓝桥杯大赛：Python必刷题单之算法训练

题目链接

n, b = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
for x in a:
  if x % b == 0:
    continue
  if x >= ord('A') and x <= ord('Z'):
    print(chr(x), end = " ")
  else:
    print(x, end = " ")

题目链接

# 质数判断
def is_prime(n):
    i = 2
    while i * i <= n:
        if n % i == 0:
            return 0
        i += 1
    else:
        return 1

a, b = map(int, input().split())

for n in range(a, b + 1):
	# 如果n为质数，直接输出，否则会TLE
    if is_prime(n):
        print("%d=%d" % (n, n))
        continue
    #质因数分解
    p = 2
    print("%d=" % n, end = "")
    while n > 1:
        while n % p == 0:
            print(p, end = "")
            n //= p
            if n > 1:
                print("*", end = "")
            else:
                print("")
        p = p + 1

题目链接

# 获取不超过n的所有质数
def get_primes(n):
  # 遍历2到n的所有数
  for i in range(2, n + 1):
      # 如果该数没有被筛除
      if st[i] == 0:
        # 添加到质数列表中
        p.append(i)
        # 将i的倍数筛除
        j = 2 * i
        while j <= n:
            st[j] = 1
       	    j = j + i
  # 返回质数个数
  return len(p)
p = []
n = int(input())
# 标记数组，没有筛除时状态为0
st = [0] * (n + 10)
print(get_primes(n))

题目链接

a = [0] * 20
c = [0] * 20
u = [0] * 20
v = [0] * 20
ans = []
n = 8
def dfs(t):
    global n
    if t == n:
        b = [str(a[i]) for i in range(n)]
        ans.append("".join(b))
        return
    for i in range(n):
        if c[i] == 1 or u[i + t] == 1 or v[i - t + n] == 1:
            continue
        c[i] = u[i + t] = v[i - t + n] = 1
        a[t] = i + 1
        dfs(t + 1)
        c[i] = u[i + t] = v[i - t + n] = 0

dfs(0)      
m = int(input())
while m > 0:
    n = int(input())
    print(ans[n - 1])
    m -= 1

题目链接

# 输入
g = []
n = int(input())
ans = 0
for i in range(n):
    g.append(list(map(int, input().split())))

# 初始化黑白皇后的列、对角线状态
cw = [0] * (n + 10)
uw = [0] * (n * 3)
vw = [0] * (n * 3)
cb = [0] * (n + 10)
ub = [0] * (n * 3)
vb = [0] * (n * 3)
# 搜索白皇后的情况
def dfs_w(t):
    global n
    if t == n:
    	# 成功放置n个白皇后，再搜索黑皇后的情况
        dfs_b(0)
        return
    for i in range(n):
        if cw[i] == 1 or uw[i + t] == 1 or vw[i - t + n] == 1:
            continue;
        if g[t][i] == 0:
            continue;
        g[t][i] = 0
        cw[i] = uw[i + t] = vw[i - t + n] = 1
        dfs_w(t + 1)
        g[t][i] = 1
        cw[i] = uw[i + t] = vw[i - t + n] = 0
# 搜索黑皇后的情况
def dfs_b(t):
    global ans
    global n
    if t == n:
    	# 成功放置后，方案总数加1
        ans += 1
        return
    for i in range(n):
        if cb[i] == 1 or ub[i + t] == 1 or vb[i - t + n] == 1:
            continue;
        if g[t][i] == 0:
            continue;
        cb[i] = ub[i + t] = vb[i - t + n] = 1
        dfs_b(t + 1)
        cb[i] = ub[i + t] = vb[i - t + n] = 0
# 搜索白皇后的情况
dfs_w(0)
print(ans)