第十五届蓝桥杯大赛软件赛国赛Python 研究生组 A～G

A

在中国传统文化中，汉字“田”具有非常重要的地位。其最初的象形意义展现了一块被四等分的农田，四个等分代表农田的不同区域，中间交叉点则代表了田间的道路或水渠。在古代，农田的划分与耕作是社会经济的根基，所以“田”字不仅代表农田，还象征着土地、财产和生产力。到了现代，虽“田”字的直接象形意义已经不再明显，但它仍是生活中不可或缺的一部分，在语言文字以及数学逻辑思维训练中都发挥着作用。比如在几何问题中，“田字格”常常被用来帮助理解空间问题。

现在，若将汉字“田”抽象为一个由 99 个点组成的图形，这些点分布在田字格的四个角、四条外边的中点以及田字格的中心。那么请问，一共有多少条直线恰好只经过这 99 个点中的任意两个点？

答案提交

这是一道结果填空题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

分析

最终答案

解析过程

这道几何组合题可以通过“计算总数再排除不符合条件的组合”来解答。

1. 计算所有可能的两点组合

“田”字图阵（一个 $3 \times 3$ 的点阵）中共有 9 个点。从这 9 个点中任意选出 2 个点构成一条直线的初始组合数为：

$\binom{9}{2} = \frac{9 \times 8}{2} = 36$ 对。

2. 找出经过 3 个点的直线

题目要求直线恰好只经过任意两个点，因此我们需要排除掉那些经过 3 个点的直线。在 $3 \times 3$ 的点阵中，经过 3 个点的直线有：

水平线：3 条（上、中、下三行）
垂直线：3 条（左、中、右三列）
对角线：2 条（主对角线、副对角线）

总计共有 $3 + 3 + 2 = 8$ 条直线是经过 3 个点的。

3. 计算需排除的点对数量

每一条经过 3 个点的直线，其内部包含了 $\binom{3}{2} = 3$ 对点。

因此，在这 8 条直线上，一共包含了 $8 \times 3 = 24$ 对点。

4. 得出最终结果

将所有的点对总数，减去那些共线（落在3点直线上）的点对数，剩下的每一对点都各自唯一确定了一条恰好只经过这两个点的直线。

计算结果为：$36 - 24 = 12$ 条。

补充验证：
这 12 条直线具体可以分为以下三类：
斜率等于 $\pm 1$ 的短对角线（如从上边中点到左边中点）：4 条
斜率等于 $\pm 2$ 的线（类似国际象棋中马的走法，如从左下角到上边中点）：4 条
斜率等于 $\pm \frac{1}{2}$ 的线（如从左下角到右边中点）：4 条
共计 $4 + 4 + 4 = 12$ 条。

B

最近，小蓝对拼单词的游戏特别着迷。他有一盒专门用于拼单词的字母卡片，其中每张卡片上分别印有 l、a、n、q、i、o 中的一个字母，并且每种字母对应的卡牌都有 5 张。

小蓝给自己设定了一个目标，即拼出单词 lanqiao。对此，他需要 2 张 a 以及 l、n、q、i、o 各 1 张。

然而，很不幸的是，小蓝在玩耍时不小心把卡片盒打翻了，所有的卡片一下子都掉进了床底下。因为床底下光线非常暗，小蓝根本无法看清卡片上的字母。

那么请问，要想凑齐 l、a、n、q、i、a、o 这 6 张卡牌，小蓝最少需要从床底下取出几张卡牌呢？

答案提交

这是一道结果填空题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

分析

1. 分析最差的抽卡情况

我们需要尽可能多地抽出卡片，但依然无法达成目标要求。无法达成目标有两种最极端的情况：

极端情况 A（一直抽不到某个只需要 1 张的字母）： 假设我们运气极差，一直抽不到字母 l。那么我们可以把剩下的 5 种卡片（a、n、q、i、o）全部抽完。此时抽出的数量为：5 × 5 = 25 张。（在这 25 张里，我们依然没有 l，无法拼出 lanqiao）
极端情况 B（一直抽不到第 2 张 a）： 因为拼写 lanqiao 需要 2 张 a，假设我们把其他所有字母（l、n、q、i、o）各 5 张全部抽光，并且只抽出了 1 张 a。此时抽出的数量为：5 × 5（其他字母） + 1（一张 a） = 26 张。（在这 26 张里，我们只有 1 张 a，依然无法拼出 lanqiao）

2. 得出结论

通过对比可以发现，极端情况 B 能够让我们在抽出最多卡片（26 张）的情况下，依然宣告失败。

既然抽出 26 张都可能凑不齐，那么在这最糟糕的 26 张基础上，再多抽 1 张（即第 27 张），就必然能打破这个僵局。因为此时剩余在床底下的卡片只剩下 4 张 a，无论怎么抽，这第 27 张必定是一张 a，从而完美满足 2 张 a 和其余各 1 张的条件。

因此，最少需要抽出 26 + 1 = 27 张卡牌。

C

问题描述

小蓝设计了一个管理系统，管理系统需要支持设置用户的密码，并给出密码的强度。合法密码要求如下：

只能包含大小写字母，数字和特殊字符 ~!@#$%^&*()_，以上字符的 ASCII 码依次为： 126,33,64,35,36,37,94,38,42,40,41,95 。

密码的强度按下列方式判断：

强密码：密码长度 ≥12 ，同时包含大写字母，小写字母，数字，特殊字符，或包含包括特殊字符在内的其中三种，且特殊字符的种类数 ≥3；

中密码：密码长度 ≥8 ，不属于强密码，至少有大写字母，小写字母，数字，特殊字符中的两种；

弱密码：密码长度 ≥6 ，不属于强密码或中密码。

三者都不是的密码同样视为不合法的密码。

给定若干个字符串（每行一个），判断其是否能作为密码，能作为密码时判断密码的强度。

对每个字符串输出 0,1,2,3 中的一个，分别对应不合法的密码，弱密码，中密码，强密码四种情况。

输入格式

输入的第一行包含一个整数 T ，表示需要判断的密码的个数。

接下来 T 行，每行包含一个字符串 Si ，表示一个需要判断的密码。保证每个字符串中仅包含 ASCII 码中的可打印字符（ASCII 码在 32 至 126 之间，包含 32 和 126）。

输出格式

输出 T 行，每行包含一个数字 Ai 表示第 i 个密码的强度。

样例输入

4
@Qaq1
123456
lanqiao2024
a1@R7c1h(GO*q3)

样例输出

评测用例规模与约定

对于 80% 的评测用例，T=1；

对于所有评测用例，1≤T≤10⁵，1≤∣Si∣≤32，其中 ∣Si∣ 表示 Si 的长度。

分析

事实上这道题也没什么好说的，就是一个点，对于一旦出现非法字符串，例如「」、{}这类的字符串一律判为非法的即可

import os
import sys

# 请在此输入您的代码
def isA(a):
  if(a>='a' and a<='z'):
    return 1
  else:
    return 0

def isa(a):
  if(a>='A' and a<='Z'):
    return 1
  else:
    return 0

def isnum(a):
  if(a>='0' and a<='9'):
    return 1
  else:
    return 0

def isf(a):
  if a in "~!@#$%^&*()_":
    return 1
  else:
    return 0

def istag(a):
  if(not isA(a) and not isa(a) and not isf(a) and not isnum(a)):
    return 0
  return 1

n=int(input())
for i in range(n):
    s=input()
    e=set()
    a=0
    b=0
    c=0
    d=0
    tag=1
    for j in s:
        a=a or isA(j)
        b=b or isa(j)
        c=c+isf(j)
        d=d or isnum(j)
        if isf(j):
            e.add(j)
        tag=istag(j)
        if(tag==0):
            break
    if len(s)<6 or tag==0:
        print(0)
    elif len(s)>=12 and ((a and b and c and d) or (len(e)>=3 and a+b+d>=2)):
        print(3)
    elif len(s)>=8 and (a+b+d+bool(c)>=2):
        print(2)
    elif len(s)>=6:
        print(1)

D

问题描述

小蓝最近为自己的服务开发了一套 OpenAPI ，为了防止接口被恶意盗刷，他需要搭建一套分布式限流组件。简而言之，我们想要限制在时间区间 [k⋅N,(k+1)⋅N) (k=0,1,2,…) 中，接口最多只允许成功访问 M 次，对于超出限制的访问则返回异常状态表示请求失败。现在给出某个客户端对 API 请求的时间戳，请你统计下其中有多少次的请求是成功的。

输入格式

输入的第一行包含三个整数 N,M,L，相邻整数之间使用一个空格分隔。第二行包含 L 个整数 t1,t2,…,tL，相邻整数之间使用一个空格分隔，表示 L 次 API 访问的时间戳。

输出格式

输出一行包含一个整数表示 API 请求成功的次数。

样例输入

60 5 10
0 60 15 60 0 50 60 1 1 61

样例输出

样例说明

[0,60) 内访问了 6 次，有 1 次会访问失败，5 次访问成功；[60,120) 内访问了 4 次，均成功；总计成功访问 5+4=9 次。

评测用例规模与约定

对于所有评测用例，1≤N,M,L≤1000，0≤ti≤1000。

分析

1. 确定时间窗口（分桶）

题目要求在时间区间 $[k \cdot N, (k+1) \cdot N)$ 中限制访问次数。这意味着时间线被切割成了长度为 $N$ 的连续段落（桶）。

对于任意给定的时间戳 $t$ ，我们可以通过简单的整数除法求出它属于哪一个窗口区间（即求 $k$ 的值）：

k = \lfloor \frac{t}{N} \rfloor

在 Python、C++ 等语言中，直接使用整除（如 Python 的 t // N）即可得到这个结果。

2. 统计每个窗口的请求数

我们只需要遍历所有的输入时间戳，计算出每个时间戳对应的窗口编号 $k$ ，然后将该窗口的请求计数加一。这一步可以使用哈希表（如 Python 的 dict 或 C++ 的 unordered_map）来实现。

3. 计算成功的总次数

对于每一个记录了请求的窗口，题目要求最多只允许成功 $M$ 次。因此，对于窗口 $k$ ，如果它总共收到了 $C$ 次请求，成功的次数就是 $C$ 和 $M$ 中的较小值：

\text{成功次数} = \min(C, M)

最后，把所有窗口的成功次数累加起来，就是总的成功请求次数。

N,M,L=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
tag=a[0]//N
sum1=0
sum=0
for i in a:
    if i//N!=tag:
        sum1=1
        sum+=1
        tag=i//N
    else:
        if sum1<M:
            sum1+=1
            sum+=1
print(sum)

E

问题描述

给定一个 $n$ 位的没有前导零的十进制数 $m$ ，你可以将其任意位 $a_i$ 改为任意其它数字 $b_i$ ，花费为 $|b_i - a_i|$ 。我们希望通过最少的花费使得修改后的数中存在连续的 10 位，包含了从 0 到 9 的所有数字，且每个数字恰好出现一次。请输出最少需要的花费是多少（修改后也要求没有前导零）。

输入格式

输入一行包含一个整数表示 $m$ 。

输出格式

输出一行包含一个整数表示答案。

样例输入

Plaintext

123456789301

样例输出

Plaintext

样例说明

将右边第 3 位改为 2 是一种方案，此时后 10 位恰好含有 0 到 9 各一个。

评测用例规模与约定

对于 40% 的评测用例， $1 \le n \le 500$
对于 60% 的评测用例， $1 \le n \le 5000$
对于所有评测用例， $1 \le n \le 10^6$

请注意： $n$ 表示数位个数。

分析

对于第一个窗口，我们把首个数字单独拎出来，强制它只能变成 1 到 9，然后把剩下的 9 个数字排序，去和剩下的 9 个目标数字做匹配

import sys

m = input().strip()
# 如果总长度不到10，直接输出0
if len(m) < 10:
    print(0)
    sys.exit()

minsum = 999999999999999

# ==========================================
# 第一部分：特殊处理 i == 0 的情况（杜绝前导零）
# ==========================================
# 提取原数字的第一个字符
first_digit = int(m[0])
# 提取剩下的 9 个字符并排序
rest_chars = list(m[1:10])
rest_chars.sort()

# 枚举首个数字被修改成了 k (k 只能是 1 到 9，不能是 0)
for k in range(1, 10):
    # 计算修改首位数字的花费
    suma = abs(first_digit - k)
    
    # 剩下的 9 个目标数字 (0~9 中剔除掉 k)
    targets = [t for t in range(10) if t != k]
    
    # 将剩下的 9 个字符与目标数字按顺序一一匹配求差
    for j in range(9):
        suma += abs(int(rest_chars[j]) - targets[j])
        
    minsum = min(minsum, suma)

# ==========================================
# 第二部分：常规处理 i > 0 的窗口（你的原版逻辑！）
# ==========================================
for i in range(1, len(m) - 9):
    a = list(m[i:i+10])
    a.sort()
    suma = 0
    for j in range(10):
        # abs() 直接求绝对值，等同于 max - min
        suma += abs(int(a[j]) - j) 
    minsum = min(minsum, suma)

print(minsum)

F

问题描述

小蓝在环游宇宙的过程中误入了一个数轴上的秘境，秘境的入口为 $1$ ，这是小蓝的初始位置，出口为 $L$ 。小蓝每次可以选取两个正整数 $x, y$ ，其中 $x, y \in \{a_1, a_2, \dots, a_n\}$ ，并向右瞬间移动 $x + y$ 的距离。然而，秘境有大小限制，如果小蓝当前位置为 $p$ ，则瞬移后的位置为 $(p + x + y - 1) \bmod L + 1$ 。当小蓝的位置在出口 $L$ 时即可离开秘境，请问小蓝最少瞬移多少次之后可以离开秘境？

输入格式

输入的第一行包含两个正整数 $n, L$ ，用一个空格分隔。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ，相邻整数之间使用一个空格分隔。

输出格式

输出一行包含一个整数表示答案，如果小蓝永远无法离开秘境，输出 $-1$ 。

样例输入

Plaintext

2 10
1 2

样例输出

Plaintext

样例说明

第一次选取 $x=1, y=1$ ，到达位置 $3$ 。
第二次选取 $x=1, y=2$ ，到达位置 $6$ 。
第三次选取 $x=2, y=2$ ，到达位置 $10$ 。

评测用例规模与约定

对于 20% 的评测用例， $1 \le n \le 200$ ， $1 \le L \le 200$ ；
对于所有评测用例， $1 \le n \le 2000$ ， $1 \le L \le 2000$ ， $0 \le a_i \le 10^8$ 。

分析

这道题的核心其实是一个最短路/BFS（广度优先搜索）问题。

虽然 $a_i$ 的值域很大（ $10^8$ ），但由于每次移动后的位置都会对 $L$ 取模（实际是映射到 $1 \dots L$ 的圆环上），且 $L \le 2000$ ，说明图中的节点最多只有 2000 个。

你可以先利用两层循环，把所有可能的步长 $(x + y) \bmod L$ 预处理出来并去重。因为 $L \le 2000$ ，去重后有效的步长种类绝对不超过 2000 种。接着从起点 $1$ 开始跑一个简单的 BFS 队列，最快到达 $L$ 时的层数就是最少的瞬移次数！时间复杂度完全可以控制在 $O(L^2)$ 级别以内。

from collections import deque

n, L = map(int, input().split())
a = list(map(int, input().split()))

# 构造可用步数集合 (两两相加)
se = set()
for i in range(n):
    for j in range(i + 1, n):
        se.add((a[i] + a[j])%L)

# 1. 使用双端队列，极大提升速度
que = deque()

# 2. 数组大小直接开 L 即可，因为取模 % L 的结果只有 0 到 L-1
tag = [-1] * L
tag[0] = 0
que.append(0)

# 标记是否已经找到答案，用于提前跳出
found = False 

while que and not found:
    t = que.popleft()
    for i in se:
        d = (i + t) % L
        if tag[d] == -1:
            tag[d] = tag[t] + 1
            
            # 3. 提前判定：如果到达目标点，直接结束
            if d == L - 1:
                found = True
                break
                
            que.append(d)

print(tag[L - 1])

G

没问题，这道题的格式也已经帮你清理并排版好了。你可以直接复制下面的 Markdown 源码到你的 Halo 博客中：

问题描述

给定一棵包含 $n$ 个结点的树，其树根编号为 $1$ 。我们规定其第 $i$ 个结点的值为其对应的子树内所有与 $i$ 奇偶性相同的结点数量。请按编号从小到大的顺序输出其每个结点的值。

输入格式

输入的第一行包含一个整数 $n$ 。

接下来 $n-1$ 行描述每个结点的父结点，其中第 $i$ 行包含一个整数 $F_{i+1}$ ，表示第 $i+1$ 个结点的父结点。

输出格式

输出 $n$ 行，每行包含一个整数表示编号为 $i$ 的结点的值。

样例输入

Plaintext

样例输出

Plaintext

评测用例规模与约定

对于 40% 的评测用例， $1 \le n \le 5000$ ；
对于所有评测用例， $1 \le n \le 2 \times 10^5$ ， $1 \le F_i < i$ 。

分析

这是一道非常典型的树形 DP（或者自底向上递推）题目。

from collections import deque
n=int(input())
mp = [[] for _ in range(n+1)]
ansmp=[ [0 for _ in range(2)] for _ in range(n+1)]
ans=[]
tag=[0]*(n+1)
que=deque()
for i in range(2,n+1):
    d=int(input())
    tag[i]=d
    mp[d].append(i)
que.append(1)
ans.append(1)
while(len(que)):
    d=que.popleft()
    for i in mp[d]:
        que.append(i)
        ans.append(i)
for i in range(n-1,-1,-1):
    d=ans[i]
    ansmp[d][d%2]+=1
    ansmp[tag[d]][0]+=ansmp[d][0]
    ansmp[tag[d]][1]+=ansmp[d][1]
for i in range(1,n+1):
    print(ansmp[i][i%2])

分享

第十五届蓝桥杯大赛软件赛国赛Python 研究生组 A～G

A

分析

最终答案

解析过程

B

分析

1. 分析最差的抽卡情况

2. 得出结论

C

问题描述

输入格式

输出格式

样例输入

样例输出

评测用例规模与约定

分析

D

问题描述

输入格式

输出格式

样例输入

样例输出

样例说明

评测用例规模与约定

分析

E

问题描述

输入格式

输出格式

样例输入

样例输出

样例说明

评测用例规模与约定

分析

F

问题描述

输入格式

输出格式

样例输入

样例输出

样例说明

评测用例规模与约定

分析

G

问题描述

输入格式

输出格式

样例输入

样例输出

评测用例规模与约定

分析

评论