2021第十二届蓝桥杯国赛Python组

A带宽

2021第十二届蓝桥杯国赛Python组_第1张图片

考常识的,Mbps是兆比特每秒,MB是兆字节,1字节等于8比特,除以8就好

答案:25

print(200//8)
# 25

B纯质数

2021第十二届蓝桥杯国赛Python组_第2张图片

模拟即可,注意细节,自己是质数并且每个数位上也是质数

答案:1903

from math import *


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


def check(n):
    num = [2, 3, 5, 7]
    n = str(n)
    for i in n:
        if int(i) not in num:
            return False
    return True


n = 20210605
cnt = 0
for i in range(2, n+1):
    if check(i) and isPrime(i):
        cnt += 1
print(cnt)
# 1903

C完全日期

2021第十二届蓝桥杯国赛Python组_第3张图片

模拟即可,注意闰年

答案:977

from calendar import month
from math import *


def isPowed(n):
    tmp = int(sqrt(n))
    if tmp**2 == n:
        return True
    return False


def check(year, mon, day):
    date = str(year)+str(mon)+str(day)
    s = sum([int(i) for i in date])
    return isPowed(s)


months = [0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
cnt = 0
for year in range(2001, 2022):
    for mon in range(1, 13):
        if year % 4 == 0 and year % 100 != 0 or year % 400 == 0:
            months[2] = 29
        else:
            months[2] = 28
        for day in range(1, months[mon]+1):
            if check(year, mon, day):
                cnt += 1
print(cnt)
# 977

D最小权值

2021第十二届蓝桥杯国赛Python组_第4张图片

简单动规,用一个w数组表示有i个节点的二叉树的最小权值,转移时枚举左子树节点数,取最小的权值填进去即可

答案:2653631372

w = [0]*2022  # w[i]表示有i个节点的二叉树的最小权值
w[0] = 0
w[1] = 1
for i in range(2, 2022):
    minn = float('inf')
    # 枚举左子树节点个数,则右子树节点数为i-1-j
    for j in range(i):
        minn = min(minn, 1+2*w[j]+3*w[i-1-j]+pow(j, 2)*(i-1-j))
    w[i] = minn
print(w[2021])
# 2653631372

E大写

2021第十二届蓝桥杯国赛Python组_第5张图片

没啥好说的

print(input().upper())

F123

2021第十二届蓝桥杯国赛Python组_第6张图片

第一反应前缀和,一看数据规模前缀和也顶不住。看规律就知道要用等差数列。

将整个数列分段:第一段为1;第二段为1,2;第n段为1到n

根据数的位置序号,可以确定该数在第几段,段内是第几个(即该数是多少),也就是下面的locate函数的作用。

如果l和r在同一段内,一个等差数列就和即可;如果不在同一段,先把l所在段剩下的数(l-n)加进去,还有r所在段前面的数(1-r)加进去,剩下中间的都是整段整段的和,等差数列求出一整段循环加上去。代码如下:

def locate(x):
    i = 1
    while i*(i+1)//2 < x:
        i += 1
    return i, x-i*(i-1)//2


t = int(input())
for _ in range(t):
    l, r = map(int, input().split())
    posL, numL = locate(l)
    posR, numR = locate(r)
    if posL == posR:
        print((numL+numR)*(numR-numL+1)//2)
    else:
        s = (numL+posL)*(posL-numL+1)//2
        s += (1+numR)*numR//2
        for i in range(posL+1, posR):
            s += (1+i)*i//2
        print(s)

G冰山

2021第十二届蓝桥杯国赛Python组_第7张图片

只会模拟,也不知道能过多少

n, m, k = map(int, input().split())
v = list(map(int, input().split()))
mod = 998244353
for _ in range(m):
    x, y = map(int, input().split())
    a = []
    i = 0
    while i < len(v):
        v[i] += x
        if v[i] <= 0:
            del v[i]
            i -= 1
        if v[i] > k:
            a += [1]*(v[i]-k)
            v[i] = k
        i += 1

    v += a+[y]
    print(sum(v) % mod)

H和与乘积

2021第十二届蓝桥杯国赛Python组_第8张图片

长度为n 的数列总共有n(n-1)/2个不同的区间,如果每个区间内部再遍历的话时间复杂度太高,所以采用前缀和前缀积预处理,即使这样也仍然只能过一部分。

n = int(input())
a = list(map(int, input().split()))
adder = [0]  # 前缀和
multi = [1]  # 前缀积
for i in range(len(a)):
    adder.append(adder[i]+a[i])
    multi.append(multi[i]*a[i])
cnt = 0
for l in range(1, len(a)+1):
    for r in range(l, len(a)+1):
        if multi[r]//multi[l-1] == adder[r]-adder[l-1]:
            cnt += 1
print(cnt)

I二进制问题

2021第十二届蓝桥杯国赛Python组_第9张图片

暴力应该只能过30%

n, k = map(int, input().split())
cnt = 0
for i in range(1, n+1):
    s = bin(i)[2:]
    if s.count('1') == k:
        cnt += 1
print(cnt)

J翻转括号序列

2021第十二届蓝桥杯国赛Python组_第10张图片
利用栈的思想,遇到一个左括号入栈一次,遇到一个右括号出栈一次。不过要注意,如果栈空了,但序列还没遍历完,那么后面可能还有合法的括号对,递归一下继续求。

以下代码不保证正确性:

from queue import *


def change(s, l, r):
    for i in range(l-1, r):
        if s[i] == '(':
            s[i] = ')'
        else:
            s[i] = '('


def getLen(s, l):
    global n
    stack = LifoQueue()
    if s[l] == ')':
        return 0
    stack.put(s[l])
    while not stack.empty() and l < n-1:
        l += 1
        if s[l] == ')':
            stack.get()  # 出栈
        else:
            stack.put(s[l])  # 入栈
    if not stack.empty():
        return 0
    elif l < n-1:
        return max(l, getLen(s, l+1))
    else:
        return l


n, m = map(int, input().split())
s = list(input())
for _ in range(m):
    c = input().split()
    if c[0] == '1':
        change(s, int(c[1]), int(c[2]))
    else:
        res = getLen(s, int(c[1])-1)
        if res > 0:
            print(res+1)
        else:
            print(0)

你可能感兴趣的