第十二届蓝桥杯大赛软件赛省赛（Python大学A组）_蓝桥杯本科a组python真题

2021年蓝桥杯  省赛真题
Python大学A组

        试题A：卡片
        试题B：直线
        试题C：货物摆放
        试题D：路径
        试题E：回路计数
        试题F：时间显示
        试题G：杨辉三角形
        试题H：左孩子右兄弟
        试题I：异或数列
        试题J：括号序列

---

试题A：卡片     （5分）

【问题描述】

        小蓝有很多数字卡片，每张卡片上都是数字0到9，小蓝准备用这些卡片来拼一些数，他想从 1开始拼出正整数，每拼一个，就保存起来，卡片就不能用来拼其它数了。
        小蓝想知道自己能从1拼到多少？
        例如，当小蓝有30 张卡片，其中0到9各3张，则小蓝可以拼出1到10，但是拼11时卡片1已经只有一张了，不够拼出 11。
        现在小蓝手里有0到9的卡片各 2021张，共20210张，请问小蓝可以从1拼到多少?
        提示:建议使用计算机编程解决问题。

【答案提交】

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

【解析与方法】

        模拟题意就好，直接从1开始遍历到卡片不足够用来拼出这个数字。

【Python程序代码】

ka = [2021]*10
for i in range(1,100000):
    tep = i
    flag = True
    while tep:
        ka[tep%10]-=1
        if ka[tep%10]<0:
            flag = False
            break
        tep //= 10
    if not flag:
        print(i-1)
        break

最终结果：3181

---

试题B：直线     （5分） 

【问题描述】
        在平面直角坐标系中，两点可以确定—条直线。如果有多点在—条直线上，那么这些点中任意两点确定的直线是同一条。给定平面上2×3个整点(x，y)| 0 ≤x<2，0≤y<3，c ∈ Z，y ∈ Z，即横坐标是0到1(包含0和1)之间的整数、纵坐标是0到2(包含0和2)之间的整数的点。这些点—共确定了11条不同的直线。
        给定平面上20 x 21个整点，(x，y)|0≤x<20，0≤y<21，x ∈ Z，y ∈ Z，即横坐标是0到19(包含0和19)之间的整数、纵坐标是0到20(包含0和20)之间的整数的点。
        请问这些点—共确定了多少条不同的直线。

【答案提交】

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

【解析与方法】

        简单的计算几何，两点确定一条直线，为避免精度问题，可以采用斜截式子：

        剩下的注意一下斜率为0的情况就行。

【Python程序代码】

point = []
for x in range(20):
    for y in range(21):
        point.append((x,y))
ans = set()
for p1 in point:
    for p2 in point:
        if p1==p2:continue
        x1,y1 = p1[0],p1[1]
        x2,y2 = p2[0],p2[1]
        if x1==x2:continue
        else:
            k = (y2-y1)/(x2-x1)
            b = (y1*x2-y2*x1)/(x2-x1)
        ans.add((k,b))
print(len(ans)+20)

最终结果：40257

---

试题C：货物摆放     （10分）

【问题描述】

        小蓝有一个超大的仓库，可以摆放很多货物。现在，小蓝有n箱货物要摆放在仓库，每箱货物都是规则的正方体。小蓝规定了长、宽、高三个互相垂直的方向，每箱货物的边都必须严格平行于长、宽高。小蓝希望所有的货物最终摆成一个大的长方体。即在长、宽、高的方向上分别堆L、W、H的货物满足n=L*W*H。
        给定n，请问有多少种堆放货物的方案满足要求？
        例如，当n=4时，有以下6种方案: 1x1x4、1x2x2、1x4x1、2x1X2、2x2x1、4x1x1.请问，当n=2021041820210418 (注意有16位数字)时，总共有多少种方案?
        提示:建议使用计算机编程解决问题

【答案提交】

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

【解析与方法】

        本质上就是找a*b*c=2021041820210418成立的正整数解。可以预处理出2021041820210418的因子。然后枚举全部的情况就可以，用Python的话可能超时，不过一个选择题也就罢了。

【Python程序代码】

num = []
ii = 1
n = 2021041820210418
while ii*ii<=n:
    if n%ii==0:
        num.append(ii)
        if n/ii!=ii:
            num.append(n/ii)
    ii += 1
res = 0
for i in num:
  for j in num:
    for k in num:
      if i*j*k==n:
        res += 1
print(res)
#print(2430)

最终结果：2430

---

 试题D：路径     （10分）

【问题描述】

        小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图 中的最短路径。小蓝的图由2021个结点组成，依次编号1至2021。对于两个不同的结点a,b，如果a和b的差的绝对值大于 21，则两个结点之间没有边相连:如果a和b的差的绝对值小于等于21，则两个点之间有一条长度为a和b的最小公倍数的无向边相连。
        例如: 结点1和结点23 之间没有边相连:结点3 和结点24 之间有一条无向边，长度为 24;结点15 和结点25 之间有一条无向边，长度为 75。
        请计算，结点1和结点2021 之间的最短路径长度是多少。
        提示:建议使用计算机编程解决问题。

【答案提交】

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

【解析与方法】

        本质上就是一个求最短路径的问题，不过本题比较容易，每次往前更新21次前面的路径就行，最后a[2021]就是ans.

【Python程序代码】

import math
a = [0]*2022
def lcm(i,j):
  return i*j/(math.gcd(i,j))
for i in range(1,2021):
  for j in range(i+1,i+22):
    if j>2021:
      break
    if a[j]==0:
      a[j]=a[i]+lcm(i,j)
    else:
      a[j]=min(a[j],a[i]+lcm(i,j))
print(int(a[2021]))

最终结果：10266837

---

试题E：回路计数     （15分）

【问题描述】

        蓝桥学院由21栋教学楼组成，教学楼编号1到21。对于两栋教学楼a和6当a和6互质时，a和6之间有一条走廊直接相连，两个方向皆可通行，否则没有直接连接的走廊。小蓝现在在第一栋教学楼，他想要访问每栋教学楼正好一次，最终回到第一栋教学楼(即走一条哈密尔顿回路)，请问他有多少种不同的访问方案?
        两个访问方案不同是指存在某个，小蓝在两个访问方法中访问完教学楼后访问了不同的教学楼。
        提示:建议使用计算机编程解决问题

【答案提交】

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

【解析与方法】

        状态DP问题。设dp[i][j]，表示路径状态i，最后到达第j栋楼的路径数量。所以最终ans应该为∑dp[(1<<21)-1][i]。枚举每种状态i，枚举i状态可以前往的第k栋楼。每次更新：dp[i+(1<<k)][k] += dp[i][j]。注意赋初值dp[1][0]=1.用Python可能超时，不过选择题也就算了，偏难。注意：如果用C++的得开LL，答案爆int。

【Python程序代码】

import math
n,m = 21,1<<21
dp = [[0]*n for _ in range((m))]
v = [[0]*n for _ in range(n)]
res = 0
for i in range(1,22):
    for j in range(1,22):
        if math.gcd(i,j)==1:
            v[i-1][j-1]=v[j-1][i-1]=1
dp[1][0]=1
for i in range(1,1<<21):
    for j in range(21):
        if ((i>>j)&1):
            for k in range(21):
                if (i>>k)&1 or (not v[j][k]):continue
                dp[i+(1<<k)][k] += dp[i][j]
 
for i in range(21):
    res += dp[(1<<21)-1][i]
print(res)
print("881012367360")

最终结果：881012367360

---

试题F：时间显示     （15分） 

【问题描述】

        小蓝要和朋友合作开发一个时间显示的网站在服务器上，朋友已经获取了当前的时间，用一个整数表示，值为从1970年1月1日00:00:00到当前时刻经过的毫秒数。
        现在，小蓝要在客户端显示出这个时间。小蓝不用显示出年月日，只需要显示出时分秒即可，毫秒也不用显示，直接舍去即可。
        给定一个用整数表示的时间，请将这个时间对应的时分秒输出。

【输入描述】

        输入一行包含一个整数，表示时间。

【输出描述】

        输出时分秒表示的当前时间，格式形如 HH:MM:SS，其中 HH 表示时，值为0到23，MM 表示分，值为0到59，ss 表示秒，值为0到59。时、分、秒不足两位时补前导0。

【样例输入】

46800999

【样例输出】

13:00:00

【评测用例规模与约定】

        对于所有评测用例，给定的时间为不超过的正整数。

【解析与方法】

        时间换算，挺简单的，直接看代码就行~

【Python程序代码】

n = int(input())//1000
ss = n%60
n//=60
mm = n%60
n//=60
hh = n%24
print("%02d:%02d:%02d"%(hh,mm,ss))

---

试题G： 杨辉三角形     （20分）

【问题描述】

        下面的图形是著名的杨辉三角形！

        如果我们按从上到下、从左到右的顺序把所有数排成一列，可以得到如下数列: 1,1,1,1,2,1,1,3,3,1,1,4,6,4,1,```.给定一个正整数N，请你输出数列中第一次出现是在第几个数? 

【输入描述】

        输入一个整数N。
【输出描述】

        输出一个整数代表答案。

【样例输入】

6

【样例输出】

13

【评测用例规模与约定】

        对于20的评测用例，1<N<10; 对于所有评测用例，1<N<1000000000。

【解析与方法】

        稍微看看杨辉三角形就知道不可能直接找到n是第几个数。通过预处理发现C(34)(17)已经是大于1000000000.同时Cij的位置数为：(i+1)*i/2+j+1。所以我们只需要从x=17开始枚举C(mid)(x)，mid是采用二分来快速得到大于等于N的mid值，如果C(mid)(x)等于N则可以找到相应的位置。否则x--，根据简单判断是一定可以得到答案的。过程中可以加一些优化如：计算Cij时，如果Cij已经大于N后不需要再判断了。

【Python程序代码】

def c(a,b,n):
    res = 1
    for i in range(1,b+1):
        res = res*(a-i+1)//i
        if res>n:
            return int(res)
    return int(res)
def ck(x):
    l = 2*x
    r = max(n,l)
    while l<r:
        mid = (l+r)>>1
        if c(mid,x,n)>=n:
            r=mid
        else:
            l = mid+1
    if c(r,x,n)!=n:return False
    print( (r+1)*r//2+x+1)
    return True
 
n = int(input())
for i in range(17,-1,-1):
    if ck(i):break

---

试题H：左孩子右兄弟     （20分）

【问题描述】

        对于一棵多叉树，我们可以通过“左孩子右兄弟”表示法，将其转化成一棵又树。如果我们认为每个结点的子结点是无序的，那么得到的二又树可能不唯一换句话说，每个结点可以选任意子结点作为左孩子，并按任意顺序连接右兄弟。
        给定一棵包含N个结点的多叉树，结点从1至N编号，其中1号结点是根，每个结点的父结点的编号比自己的编号小。
        请你计算其通过“左孩子右兄弟”表示法转化成的二叉树，高度最高是多少
        注:只有根结点这一个结点的树高度为0。

【输入描述】

        输入的第一行包含一个整数N。以下 N-1行，每行包含一个整数，依次示2至号结点的父结点编号。

【输出描述】

        输出一个整数表示答案。

【样例输入】

5
1
1
1
2

【样例输出】

4

【评测用例规模与约定】

        对于30%的评测用例，1≤N≤20;
        对于所有评测用例，1≤N≤100000。

【解析与方法】

        仔细看题目后可以发现你需要求的最大高度其实就是：第二层结点拥有的最大子孩子数+第二层结点数。可以直接开启爆索模式，不过这题得调整一下递归深度。

【Python程序代码】

import sys
sys.setrecursionlimit(100000)
n = int(input())
a = [[]for i in range(n+2)]
for i in range(2,n+1):
    x = int(input())
    a[x].append(i)
def dfs(x):
    if len(a[x])==0:
        return 0
    maxn = 0
    for i in a[x]:
        maxn = max(maxn,dfs(i))
    return len(a[x])+maxn
print(dfs(1))

---

试题I：异或数列     （25分）

【题目描述】

        Alice和 Bob 正在玩一个异或数列的游戏。初始时，Alice 和 Bob 分别有一个整数a和b，初始值均为0。有一个给定的长度为n的公共数列X1，X2，···，Xn。Alice和 Bob 轮流操作，Alice先手，每步可以在以下两种选项中选一种:
        选项1：从数列中选一个Xi；给Alice的数异或上，或者说令a变为a^Xi(其中表示按位异或)
        选项2：从数列中选一个Xi；给Bob的数异或上，或者说令b变为b^X
        每个数Xi，都只能用一次，当所有Xi，均被使用后 (n轮后)游戏结束。游戏结束时，拥有的数比较大的一方获胜，如果双方数值相同，即为平手。 现在双方都足够聪明，都采用最优策略，请问谁能获胜?

【输入描述】

        每个评测用例包含多组询问。询问之间彼此独立。
        输入的第一行包含一个整数 T，表示询问数
        接下来T行每行包含一组询问。其中第行的第一个整数n;表示数列长度，随后ni个整数 X1,X2，··，Xn;表示数列中的每个数。

【输出描述】

        输出T行，依次对应每组询问的答案。 每行包含一个整数1、0或-1分别表示 Alice 胜、平局或败。

【样例输入】

4
1 1
1 0
2 2 1
7 992438 1006399 781139 985280 4729 872779 563580

【样例输出】

1
0
1
1

【评测用例规模与约定】

        对于所有评测用例，1<T<200000，1<∑ni< 200000,0<Xi<20²⁰

【解析与方法】

        二进制类型的博弈问题，通过分析可以发现，如果二进制最高位的数量cnt为奇数时，是一定可以直接分出胜负的，当数的个数为偶数时先手必输，为奇数时先手必胜。特例cnt为1时先手必胜。如果当前最高位比较不出来，则看下一位。请看下面的代码~

【Python程序代码】

import sys
T = int(input())
def solve(a):
    for i in range(20,-1,-1):
        cnt = 0
        for j in range(1,len(a)):
            if (a[j]>>i)&1:
                cnt += 1
        if cnt%2==0:continue
        if cnt==1 or a[0]%2:
            print(1)
            return
        else:
            print(-1)
            return
    print(0)
    return
for _ in range(T):
    a = list(map(int,sys.stdin.readline().split()))
    solve(a)

---

试题J：括号序列     （25分）

【题目描述】

        给定一个括号序列，要求尽可能少地添加若干括号使得括号序列变得合法当添加完成后，会产生不同的添加结果，请问有多少种本质不同的添加结果。
        两个结果是本质不同的是指存在某个位置一个结果是左括号，而另一个是右括号。
例如，对于括号序列(()，只需要添加两个括号就能让其合法，有以下几种不同的添加结果:()()()、()(())、(())()、(())()和((()))。

【输入描述】

        输入一行包含一个字符串 s，表示给定的括号序列，序列中只有左括号和右括号。

【输出描述】

        输出一个整数表示答案，答案可能很大，请输出答案除以1000000007(即1e9+7)的余数.

【输入样例】

((()

【输出样例】

5

【评测用例规模与约定】

        对于40的评测用例，s<200.
        对于所有评测用例，1< s<5000.

【解析与方法】        

        几个需要清楚的问题：
        ①关于括号序列合法性：对于一段括号序列，从左往右起，一个字符一个字符的往前看，对于每一段小的括号序列 –‘(’– 数量 大于等于 –‘)’– 数量，那么整个括号序列就合法。

        ②关于 –‘(’– 和 –’)’– 的添加可以分开来讨论：括号是被添加到原序列的括号与括号之间的空隙里的，假如左括号和右括号加入的是不同的空隙，那么它们必然是互不影响的。如果加入的是同一个空隙，那么右括号的添加必然在左括号之前，否则括号配对，添加无意义，不存在顺序的影响，那么也是互不影响的，所以我们将其的添加分开讨论。

        ③上面第二点清楚了之后，如何利用其解决问题：可以分开讨论之后，我们可以判断在原括号序列添加左括号使之变得合法，然后变换原括号序列（先将括号序列逆序，再将左括号变成右括号，右括号变成左括号），这样调整之后我们在变换后的括号序列中添加左括号使之变得合法（相当于在原括号序列添加右括号）。
下面是举例解释：

        通常我们只需要添加一种括号就能使整个括号序列合法。
        例如：
        原括号序列：（（（） 左括号数量大于等于右括号数量，合法，不用添加
        变换后序列：（））） 左括号数量小于右括号数量，不合法，需要添加
        但也有特殊情况，需要两种括号都加
        原括号序列：) ) ( ( 乍一看好像相等，理解了第一点就知道此序列不合法，需要添加。
        变换后序列：) ) ( ( 和原括号序列一样，不合法，需要添加。
        这样一来我们的问题变成了在括号序列中添加左括号使合法的问题，所以每碰到一个右括号，我们就可以在其前边添加左括号，从刚好合法（左右括号相等）到更多的左括号（上限是括号序列长度）。

        ④dp数组的含义：之前看题解都写的一样，但是那样想我感觉始终有些问题想不明白。
自己想了一种含义（其实和原含义差不多，但是更好理解了）:
dp[i][j]是指前i个括号字符之前 添加不知道多少个(可以是0个) –’(’– 使这前i个括号字符合法（合法的含义又是 –’(’– 比 –’)’– 多或者相等，所以j从0开始) 的种数。
        可能有点拗口…去掉括号注释来看就是：前i个括号字符之前添加不知道多少个左括号使前i个括号字符合法的种数。
        也就是说加多少个我们是不管的，我们只考虑添加后的结果中左括号比右括号多多少个。而j是下标所以必定大于等于0，于是如果dp[i][j]这个状态是可以存在的那么这个值一定不是0，也就是不可能是0种。

        ⑤递推公式：
        遇到 –‘(’– :我们只考虑在 –‘)’– 前添加 –‘(’– 使这个右括号之前的括号序列合法。遇到左括号的时候，证明在这个左括号之前的括号序列已经被判断过如何使其合法了，那么加上这个左括号依然合法，所以我们不需要管这个左括号。也就是在他前面的括号序列添加左括号使其合法的种数等于加上这个左括号之后这个序列需要添加的左括号种数。
                                                                      dp[i][j]=dp[i-1][j-1]；

        遇到 –‘)’– ：如果这个加上这个右括号的序列本身合法，那么我们仅需添加0个左括号就能使其合法，如果不合法就需要添加刚好使得其合法的左括号甚至可以更多。
                                        dp[i][j] = dp[i-1][0] + dp[i-1][1] + … + dp[i-1][j] + dp[i-1][j+1]

【Python程序代码】

s = list(input())
ns = ['0'] + s
n = len(ns)-1
p = (int)(1e9 + 7)
def solve(s):
    f = [[0]*(n+5) for _ in range(n+5)]
    f[0][0]=1
    for i in range(1,n+1):
        if s[i]=='(':
            for j in range(1,n+1):
                f[i][j] = f[i-1][j-1]
        else:
            f[i][0] = (f[i-1][0]+f[i-1][1])%p
            for j in range(1,n+1):
                f[i][j] = (f[i][j-1] + f[i-1][j+1])%p
    for i in range(n+1):
        if f[n][i]:
            return f[n][i]
l = solve(ns)
s.reverse()
ns = ['0'] + s
for i in range(1,n+1):
    if ns[i]=='(':
        ns[i]=')'
    else:ns[i]='('
r = solve(ns)
print(l*r%p)