【python语言】第十四届蓝桥杯国赛 c/c++b组_蓝桥杯国赛c++b组

1. 考点：质因子分解

2. 难度：⭐⭐

3. 要点分析：

①在双层循环中，若不增加一些“筛选条件”，或是从start~end开始循环，时间复杂度都会比较大。

import math
 
def check(x):
    for i in range(2,int(math.sqrt(x))+1):
        if x%i==0:
            return 0
    return 1
 
"""将x开方 变为p*q的数 找到其中的p和q"""
start = int(math.sqrt(2333))
end = int(math.sqrt(23333333333333))
 
prime = [2,]
for i in range(3,end+1):
    if check(i):
        prime.append(i)
 
vis = [0]*(end+1)
for p in range(len(prime)):
    for q in range(p+1,len(prime)):
        x = prime[p]*prime[q]
        if x>end:
            break
        if x<start:
            continue
        vis[x] = 1
print(sum(vis[start:]))

②尽管本次不需要对“素数的判断”进行优化，但还是记住“欧拉筛”比较好，说不定下次能够用上。其基本思想是，素数的倍数不是素数。

def ouler(r):
    primes = []
    check = [True for i in range(r+1)]
    for i in range(2,r+1):
        if check[i]:
            primes.append(i)
        for j in primes:
            if i * j > r:
                break
            check[i*j] = False
            if i % j == 0:
                break
    return primes

n = int(input())
numbers = list(map(int, input().split()))
ds = dict()
 
"""
有可能会出现同一数字出现多次的情况
每个数字只能出现两次 多于两次则需要更改
"""
 
# 统计次数
for t in numbers:
    if t not in ds.keys():
        ds[t] = 1
    else:
        ds[t] += 1
 
x = 0   #待分配id的学生
y = 0   #id重复的学生
for t in list(ds.keys()):
    if ds[t] == 1:
        x += 1
    elif ds[t] > 2:
        y += ds[t]-2
 
# x<=y 只需要改变id重复的学生即可
if x<=y:
    print(y)
# x>y 1.改变id重复的学生以适配；2.剩余待分配学生两两配对
else:
    print((x-y)//2+y)

n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
 
p=0;q=0
sumA=0;sumB=0
ans = 0
while p<n and q<m:
    if sumA==sumB:
        sumA += a[p]
        sumB += b[q]
        p+=1;q+=1
    elif sumA<sumB:
        sumA += a[p]
        p += 1
        ans += 1
    elif sumA>sumB:
        sumB += b[q]
        q += 1
        ans += 1
print(ans+n+m-p-q)

import math
 
n = int(input())
dots = []
for i in range(n):
    x, y = map(int, input().split())
    dots.append([x,y])
    
ans = 0
# 以p点为圆心，记录不同点与点p的距离
for p in range(n):
    dockers = {}
    for q in range(n):
        if p==q:
            continue
        x1,y1 = dots[p]
        x2,y2 = dots[q]
        dis = math.sqrt((x1-x2)**2+(y1-y2)**2)
        if dis not in dockers:
            dockers[dis] = [q]
        else:
            dockers[dis].append(q)
    
    for dis in dockers:
        if len(dockers[dis])>=2:
                # 判断是否能组成三角形
                for i in range(len(dockers[dis])):
                    for j in range(i+1,len(dockers[dis])):
                        x1,y1 = dots[dockers[dis][i]]
                        x2,y2 = dots[dockers[dis][j]]
                        tmp = math.sqrt((x1-x2)**2+(y1-y2)**2)
                        if tmp < 2*dis:
                            ans += 1
print(ans)