第十五届蓝桥杯大赛软件赛省赛Python 研究生组（正在更新）

一、劲舞团

题目

题目链接：0劲舞团 - 蓝桥云课

小蓝最近迷上了一款名为 “劲舞团” 的游戏，具体来说，只要按照游戏中给出的键位提示依次按出对应的键位，游戏人物便可以跟随节奏跳舞。对于连续的 K 次正确敲击，如果任意连续的两次敲击间间隔时间都小于等于 1s ，那么我们称这是一次 K 连击。现在给出一局小蓝的游戏 记录文件，log.txt 中记录了 N 条记录，每条记录有三个字段，依次为正确地敲击字符、小蓝打出的字符、 打出字符的时间对应的毫秒时间戳。现在请你计算下最长的 K 连击是多少，你只需要输出 K 的值。

解析

根据题目所述，记录有三个字段，为 “答案”，“小蓝打出的字符”，“打出字符的时间”

我们需要判断小蓝的答案是否正确，然后判断两次记录时间的时间间隔是否小于等于1s即可。定义一个指针指向前一个时间，然后一次遍历即可解决。

答案

import os
import sys

records = []
# 处理输入，将时间戳转换为整数
for _ in range(2000):
    parts = input().split()
    correct_char, entered_char, timestamp = parts[0], parts[1], int(parts[2])
    records.append((correct_char, entered_char, timestamp))

max_streak = 1  # 最大连击数
current_streak = 1  # 当前连续记数
prev_timestamp = records[0][2] # 上一条的记录的时间

for i in range(1, len(records)):
    # 当前记录的用户输入、答案和输入时间
    curr_correct, curr_entered, curr_ts = records[i]
    # 时间差
    time_diff = curr_ts - prev_timestamp

    # 用户答案是否正确，以及时间是否符合
    if curr_correct == curr_entered and time_diff <= 1000:
        # 更新记录
        current_streak += 1
        max_streak = max(max_streak, current_streak)
    else:
        # 连击中断
        current_streak = 1
    # 更新时间
    prev_timestamp = curr_ts

print(max_streak)

二、召唤数学精灵

题目

题目链接：0召唤数学精灵 - 蓝桥云课

数学家们发现了两种用于召唤强大的数学精灵的仪式，这两种仪式分别被称为累加法仪式 A(n) 和累乘法仪式 B(n) 。

累加法仪式 A(n) 是将从 1 到 n 的所有数字进行累加求和，即：A(n)=1+2+⋯+n

累乘法仪式 B(n) 则是将从 1 到 n 的所有数字进行累乘求积，即：B(n)=1×2×⋯×n

据说，当某个数字 i 满足 A(i)−B(i) 能被 100 整除时，数学精灵就会被召唤出来。

现在，请你寻找在 1 到 2024041331404202 之间有多少个数字 i，能够成功召唤出强大的数学精灵。

解析

由题可得

当 \forall n >= 10，B(n) \equiv 0 \ mod \ (100)

n = n + 200 \ mod \ (100)

n + 1 = n + 201 \ mod \ (100)

n(n+1) = (n+200)(n+201) \ mod \ (100)

\frac {n(n+1)} 2 = \frac {(n+200)(n+201)} 2 \ mod \ (100)

A(n) = A(n+200)

代表在 \forall n >= 10的情况下，A(n) \ mod \ (100)的值会每 200 重复一次，那么我们只需要计算 200 之内有那些符合条件，然后乘一下就行。

注意这里是在 n >= 10的前提条件下，还要加上个位数的情况。

答案

from math import factorial

count = 0
for i in range(10,211):
    if ( i * ( i + 1 ) // 2 - factorial(i) ) % 100 == 0:
        count += 1
# print(count) # 4

num = 0
for i in range(1,10):
    if ( i * ( i + 1 ) // 2 - factorial(i) ) % 100 == 0:
        num += 1
# print(num) # 2

print(2024041331404202 // 200 * count + num)

三、封闭图形个数

题目

题目链接：0封闭图形个数 - 蓝桥云课

在蓝桥王国，数字的大小不仅仅取决于它们的数值大小，还取决于它们所形成的“封闭图形”的个数。

封闭图形是指数字中完全封闭的空间，例如数字 1、2、3、5、7 都没有形成封闭图形，而数字 0、4、6、9 分别形成了 1 个封闭图形，数字 8 则形成了 2 个封闭图形。值得注意的是，封闭图形的个数是可以累加的。例如，对于数字 68，由于 6 形成了 1 个封闭图形，而 8 形成了 2 个，所以 68 形成的封闭图形的个数总共为 33。

在比较两个数的大小时，如果它们的封闭图形个数不同，那么封闭图形个数较多的数更大。例如，数字 41 和数字 18，它们对应的封闭图形的个数分别为 1 和 2，因此数字 41 小于数字 18。如果两个数的封闭图形个数相同，那么数值较大的数更大。例如，数字 14 和数字 41，它们的封闭图形的个数都是 1，但 14<41，所以数字 14 小于数字 41。 如果两个数字的封闭图形个数和数值都相同，那么这两个数字被认为是相等的。

小蓝对蓝桥王国的数字大小规则十分感兴趣。现在，他将给定你 n 个数 a1,a2,…,an​，请你按照蓝桥王国的数字大小规则，将这 n 数从小到大排序，并输出排序后结果。

解析

Python 很适合做这道题，可以使用 sorted 函数来进行自定义的排序

答案

# 封闭图形字典
d = {'0':1,'4':1,'6':1,'9':1,'8':2}

n = int(input())

nums = [*map(int,input().split(" "))]

# dict.get(x,y) 获取指定的元素 x ，如果不存在的话返回 y
# 指定排序的元素为 ( 封闭图形的个数 , 数值 ) 格式的元组，这样就能按照题目要求排序
res = sorted(nums,key=lambda num:(sum(d.get(c,0) for c in str(num)),num))
print(*res)

四、商品库存管理

题目

题目链接：0商品库存管理 - 蓝桥云课

在库存管理系统中，跟踪和调节商品库存量是关键任务之一。小蓝经营的仓库中存有多种商品，这些商品根据类别和规格被有序地分类并编号，编号范围从 1 至 n。初始时，每种商品的库存量均为 0。

为了高效地监控和调整库存量，小蓝的管理团队设计了 m 个操作，每个操作涉及到一个特定的商品区间，即一段连续的商品编号范围（例如区间 [L,R]）。执行这些操作时，区间内每种商品的库存量都将增加 1。然而，在某些情况下，管理团队可能会决定不执行某些操作，使得这些操作涉及的商品区间内的库存量不会发生改变，维持原有的状态。

现在，管理团队需要一个评估机制，来确定如果某个操作未被执行，那么最终会有多少种商品的库存量为 0。对此，请你为管理团队计算出，每个操作未执行时，库存量为 0 的商品的种类数。

解析

我一开始的思路是，先使用前缀和计算出在做完所有操作后的库存情况，然后再减去当前查询的操作，计算出有多少个 0 和 1 并输出。但是这样很容易超时。

于是就优化了一下，先统计好 0 的数量，这些无论是去掉什么操作，一直都是 0 。然后在做一个辅助数组来计算区间内 1 的数量，因为只有 1 有可能因为不做一次操作变成 0 。

答案

import sys
import os

def add_operator(left,right):
    # 更新差分数组
    global prefix,n
    prefix[left-1] += 1
    if right != n:
        prefix[right] -= 1

# 读取基础参数
n,m = list(map(int,input().split(" ")))
operators = []
prefix = [0] * n

# 构建差分数组
for _ in range(m):
    L,R = map(int,input().split())
    operators.append([L,R])
    add_operator(L,R)

# 计算前缀和并统计初始零库存的商品数量
count = 1 if prefix[0] == 0 else 0
for i in range(1,len(prefix)):
    prefix[i] += prefix[i-1]
    if prefix[i] == 0:
        count += 1

# 其实我们只需要找到 1 的数量即可，可以构建一个 1 的辅助数组来快速查询
ones = [0] * n
for i in range(n):
    ones[i] = 1 if prefix[i] == 1 else 0

pre_ones = [0] * (n+1)
for i in range(n):
    pre_ones[i+1] = pre_ones[i] + ones[i]

# 处理每个查询操作
for operator in operators:
    l,r = operator
    print(count + (pre_ones[r] - pre_ones[l-1]))

五、砍柴

题目

小蓝和小乔正在森林里砍柴，它们有 T 根长度分别为 n1,n2,⋯,nT的木头。对于每个初始长度为 n 的木头，小蓝和小乔准备进行交替砍柴，小蓝先出手。

每次砍柴时，若当前木头长度为 x，需要砍下一截长度为 p 的木头，然后换另一个人继续砍，其中 2≤p≤x 且 p 必须为质数。当轮到某一方时 x=1 或 x=0，它就没法继续砍柴，它就输了。它们会使用最优策略进行砍柴。请对每根木头判断是小蓝赢还是小乔赢，如果小蓝赢请输出 1（数字 1），如果小乔赢请输出 0（数字 0）。

解析

由于只能砍质数长度的木头，可以采用动态规划的方式。

当剩余长度为 0 和 1 的时候，是必输局面，即 dp[0] = dp[1] = 0，那么如果有 dp[ i - j ] = 0（ j 为质数 ），说明当前角色动手之后对方面临的是必输局面，那么当前必赢。那么我们可以得到如下方程，if dp[ i - j ] == 0 , dp[ i ] = 1 else dp[ i ] = 0。

代码中的推算过程是反过来的，因为要提高速度。

这道题 Python 代码很容易超时，需要优化之后才能过。

答案

def func(n):
    isprime = [True] * (n + 1)
    isprime[0] = isprime[1] = False
    result = []
    for i in range(2,n+1):
        if isprime[i]:
            result.append(i)
            for j in range(i*2,n,i):
                isprime[j] = False
    return result


t = int(input())
x = [int(input()) for _ in range(t)]
n = max(x) + 1

dp = [0] * n
prime_numbers = func(n)

for i in range(n):
    if dp[i] == 0:
        for p in prime_numbers:
            if i + p >= n:
                break
            dp[i+p] = 1

for xi in x:
    print(dp[xi])

六、智力测试（暂时还不会）

七、最大异或节点

题目

小蓝有一棵树,树中包含 N 个结点，编号为 0,1,2,⋯,N−1，其中每个结点上都有一个整数 Xi。他可以从树中任意选择两个不直接相连的结点 a、b 并获得分数 Xa⊕Xb​，其中 ⊕ 表示按位异或操作。

请问小蓝可以获得的最大分数是多少?

解析

这道题可以采用邻接表+Trie 树的方式来做。邻接表负责存储每个节点的邻居节点（父节点和子节点），Trie 树用于快速求取最大的异或值。关于 Trie 树的部分可以查看：Trie树（Prefix Tree）介绍-CSDN博客，这篇文章写的不错。

01 树在查询的过程中，应当尽量往相反的方向查询，考虑到异或的特性，只有相反的时候才能获取到更大的元素。可以把数字都补全到31位，这样就不用考虑这个节点是否是末尾节点的问题了。

但是这道题好像不满足“任意选择两个不直接相连的结点”这个条件也能过。

加上邻接表的话大概 6000ms 上下，不加的话 2000ms 上下，都能过。

答案

class TrieNode:
    def __init__(self):
        self.children = [None,None]
        # 统计经过的数量
        self.count = 0

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self,num:int):
        node = self.root
        # 题目里说，最大也就 2^31 - 1
        for i in range(31,-1,-1):
            bit = ( num >> i ) & 1
            if not node.children[bit]:
                node.children[bit] = TrieNode()
            node = node.children[bit]
            node.count += 1

    def remove(self,num:int):
        node = self.root
        for i in range(31,-1,-1):
            bit = ( num >> i ) & 1
            if not node.children[bit]:
                 return
            if node.children[bit].count == 1:
                node.children[bit] = None
                return
            node = node.children[bit]
            node.count -= 1


    def search(self,num):
        node = self.root
        # 确保树不为空
        if node.children[0] is None and node.children[1] is None:
            return 0

        result = 0
        for i in range(31,-1,-1):
            bit = ( num >> i ) & 1
            opposite_bit = bit ^ 1
            # 考虑到异或的特性，尽量取相反的元素，才能得到最大值
            if node.children[opposite_bit]:
                result |= ( 1 << i )
                node = node.children[opposite_bit]
            # 如果没有也没办法啦
            else:
                node = node.children[bit]

        return result

N = int(input())
X = list(map(int,input().split()))
F = list(map(int,input().split()))

# 这一块是邻接表，加上这一块的话最后几个测试需要 6000ms
# 不加上的话只需要 2000ms
# 不加上也能过

# adj = [[] for _ in range(N)]
# for i in range(N):
    # parent = F[i]
    # if parent != -1:
    #     adj[i].append(parent)
        # adj[parent].append(i)

# 创建 01 树
trie = Trie()
for x in X:
    trie.insert(x)

result = 0
for i in range(N):

    # 考虑不直接相连的话，应当先把所有相连的节点和当前节点都删除的
    # nodes = list(adj[i]) + [i]
    # for node in nodes:
    #     trie.remove(X[node])

    result = max(result,trie.search(X[i]))

    # 恢复前面删除的节点
    # for node in nodes:
    #     trie.insert(X[node])

print(result)

八、植物生命力（暂时还不会）