2024年第15届蓝桥杯省赛Python研究生组部分题解分享

前排提醒：本人水平有限，仅供参考!!!

答案不一定正确，还请读者自行判断，有错的地方还请您指出~

A题劲舞团

简单题，log.txt共2000行，暴力即可。

参考答案:9

n=2000
res=[]
for _ in range(2000):
    c,in_,t=input().split()
    res.append([c,in_,int(t)])
print(res)  
ans=0
n=len(res)

for i in range(n):
    if res[i][0]!=res[i][1]:
        continue
    st=i
    while i+1<n and res[i+1][0]==res[i+1][1] and res[i+1][2]-res[i][2]<=1000:
        i+=1
    ans=max(ans,i-st+1)
print(ans)

P.S 本人喜提WA。当时脑子迷糊先把字符打错的data去掉，再判断时间的。

B题召唤数学精灵

思路：

1.范围过大，无法暴力；

2.注意到B(i)为阶乘，其数值在10之后将全是100的倍数。因为n>10时，n!=1*2*…*5*…*10*……已经有2*5*10存在。

3.由2，只需考虑A(i)是否为100的倍数。

$A(i)=\frac{n(n+1)}{2}$

因此只需 $[n(n+1)]mod(200)=0$

考虑如下事实：

若对于某个x有：

$x(x+1)mod(200)=0$

即A(x)能被100整除，则:

$(x+200)(x+201)=x^2+401x+200\times201=x(x+1)+400x+200 \times 201$

显然也是200的倍数，因此只需要找出200以内满足要求的数字个数即可。

4.符合3中条件的200以内的x为：

24,175,199,200

共4个。

因此，满足条件的数字个数为：

2024041331404202//200*4+2=40480826628086

最后的2是10以内满足要求的数，即1,3

参考答案：40480826628086

C题封闭图形个数

本题对于python来说直接秒杀，不多说。

from functools import  cmp_to_key
cnt=[1,0,0,0,1,0,1,0,2,1]
def get(num):
    res=0
    for w in str(num):
        res+=cnt[int(w)]
    return res
def f(a,b):
    if a==b:
        return 0
    x,y=get(a),get(b)
    if x==y:
        return -1 if a<b else 1
    elif x<y:
        return -1
    else:
        return 1

def solve():
    n=int(input())
    a=list(map(int,input().split()))
    a.sort(key=cmp_to_key(f))
    print(*a)
    
solve()

D题商品库存管理

方法1：暴力，不多说。显然不能拿到所有分数

方法2：对于区间修改与查询，应该想到：差分数组，树状数组，线段树…etc

由于本题只是对区间整体加上同一个数（1），考虑使用差分数组。

若没有最后撤销执行操作，则只需要O(n)遍历数组，对0计数即可。

然而存在m个撤销操作，由于m范围较大，我们需要O(1)的找到撤销操作对答案的影响。

显然，这只要找到该撤销区间内1的个数即可。

O(1)获得某个区间内1的个数，用简单的前缀和即可解决。

最终时间复杂度为O(n+m)

n,m=map(int,input().split())
t=[]
for i in range(m):
    L,R=map(int,input().split())
    t.append((L-1,R-1))
    
dif=[0]*(n+1)
for L,R in t:
    dif[L]+=1
    dif[R+1]-=1

f=[0]
for d in dif:
    f.append(f[-1]+d)
f=f[1:-1]
cnt1=[0]
# print('final:',f)
for x in f:
    cnt1.append(cnt1[-1]+int(x==1))
cnt1=cnt1[1:]
# print('cnt1=',cnt1)
cnt0=sum([x==0 for x in f])
# print(cnt0)
for L,R in t:
    new=cnt1[R]-cnt1[L-1] if L>0 else cnt1[R]
    print(cnt0+new)

E题砍柴

比赛喜提WA。

不太会。没找到规律。dfs不能获得所有结果，打表未遂。

DFS:定义dfs(x)为棍长为x时，当前砍柴方赢为True，否则为False。

对某个n，在1-n-1里面遍历所有的质数x(砍掉），如果存在dfs(n-x)为False（对方输），则return True，否则return False。

以下不是赛时使用的编译器。注意cache在赛时编译器用不了，不过这不是为了打表吗。

from functools import cache
import sys
sys.setrecursionlimit(10**6)
mx=10**3
f=[True for i in range(mx+1)]
for i in range(2,mx+1):
    if f[i]:
        for x in range(2*i,mx+1,i):
            f[x]=False
a=[i for i in range(2,mx+1) if f[i]]
d=set(sorted(a))
print(a)
@cache
def dfs(x):
    if x==0 or x==1:
        return False
    res=False
    if x in d:
        return True
    for i in range(1,x+1):
        if i in d:
            res|=not(dfs(x-i))
    return res

# print([dfs(i) for i in range(mx+1)])
print([i for i in range(mx+1) if not dfs(i)])

Update：

与其遍历各个质数，不如遍历各个能够让对方输掉的值，判断需要砍掉的值是否为质数，存在一种情况即可。这样做是因为暴力发现让当前方输掉的值要远少于小于该值的质数的个数。

打表代码：

from functools import cache
import sys
sys.setrecursionlimit(10**6)
mx=10**5
f=[True for i in range(mx+1)]
for i in range(2,mx+1):
    if f[i]:
        for x in range(2*i,mx+1,i):
            f[x]=False
f[0]=f[1]=False
# a=[i for i in range(2,mx+1) if f[i]]
# d=set(sorted(a))
lose=set()
lose.add(0)
lose.add(1)
@cache
def dfs(x):
    if x==0 or x==1:
        return False
    if f[x]:
        return True
    for y in lose:
        if f[x-y]:
            return True
    lose.add(x)
    return False

# print([dfs(i) for i in range(mx+1)])
print([i for i in range(mx+1) if not dfs(i)])

F题智力测试

智力不够，不会。奠。

G题最大异或节点

树并没有什么卵用。只是添加了一个限制条件而已。

前置题：

421. 数组中两个数的最大异或值

本题只要在更新答案判断x和y是否为树中相邻节点即可。

def solve():
    n=int(input())
    g=[set() for i in range(n)]
    nums=list(map(int,input().split()))
    root=list(map(int,input().split()))
    for pa,son in enumerate(root):
        if pa==-1:
            continue
        g[pa].add(son)
        g[son].add(pa)

    res=0
    mask=0
    for i in range(31,-1,-1):
        mask|=(1<<i)
        tmp=res|(1<<i)
        s=dict()
        ok=False
        for i,x in enumerate(nums):
            if ok:
                break
            t=mask&x
            if t^tmp in s:
                for node in s[t^tmp]:
                    if node not in g[i]:
                        res=tmp
                        ok=True
                        break
            
            if t in s:
                s[t].append(i)
            else:
                s[t]=[i]
    print(res)
    
solve()

H题植物生命力

dfs枚举所有节点，同时判断其子树中符合条件的节点数量，时间复杂度O(n^2)

比赛WA了倒是。

def solve():
    n,root=map(int,input().split())
    val=list(map(int,input().split()))
    root-=1
    g=[[] for _ in range(n)]
    for _ in range(n-1):
        x,y=map(int,input().split())
        x-=1
        y-=1
        g[x].append(y)
        g[y].append(x)
#     print(g)
    res=0
    def dfs(x,pa):
        s=[]
        for y in g[x]:
            if y!=pa:
                s+=dfs(y,x)
        nonlocal res
        for v in s:
            if v<val[x] and val[x]%v!=0:
                res+=1
        s.append(val[x])
        return s 
    dfs(root,-1)
    print(res)
solve()

O(nlogn)做法思路:

首先获得每个子树中小于该节点值的节点总个数（可以使用树状数组等动态query）

以某个节点为子节点，判断从根节点到其路径上有多少个节点是能整除他的。

显然，只有值为1的节点需要一个个遍历，对于val[x]，只需要遍历10^5//val[x]个数。

因此这一步大概只需要10^5*(1+1/2+1/3+1/4+….+1/10^5)~O(n)步。

用符合条件1的所有节点数减去不符合条件2的所有节点数即可。