2021第十二届蓝桥杯国赛Python组
A带宽
考常识的，Mbps是兆比特每秒，MB是兆字节，1字节等于8比特，除以8就好
答案：25
print(200//8)
# 25B纯质数
模拟即可，注意细节，自己是质数并且每个数位上也是质数
答案：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)
# 1903C完全日期
模拟即可，注意闰年
答案：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)
# 977D最小权值
动态规划问题中有一种方法用于存储具有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])
# 2653631372E大写
没啥好说的
print(input().upper())F123
在最初阶段观察前缀和时发现其表现不佳，在数据规模扩大后同样无法承受压力。通过识别规律可知应该采用等差数列。
将整个数列分段：第一段为1；第二段为1，2；第n段为1到n
基于该数值的位置索引信息, 我们可以明确确定它处于哪一个区间内, 并进一步明确具体属于该区间内的第几位数值. 其作用等同于以下所述的定位函数.
若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冰山
只会模拟，也不知道能过多少
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和与乘积
长度为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二进制问题
暴力应该只能过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翻转括号序列
基于栈的概念，“将左括号依次压入栈中”，每当遇到右括号时依次弹出。”需要注意的是，“若当前栈为空”、“尽管尚未遍历完整个序列”、“可能存在后续的有效括号配对”、“可以通过递归来继续处理”。
以下代码不保证正确性：
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)