第十三届蓝桥杯大赛软件赛省赛（Python大学A组）
2022年蓝桥杯 省赛真题
Python大学A组
试题A：裁纸刀
试题B：寻找整数
试题C：质因数个数
试题D：矩形拼接
试题E：消除游戏
试题F：重新排序
试题G：全排列的价值
试题H：最长不下降子序列
试题I：最优清零方案
试题J：数的拆分
试题A：裁纸刀 （5分）
【问题描述】
小蓝有一个裁纸刀，每次可以将一张纸沿一条直线裁成两半，小蓝用一张纸打印出两行三列共6个二维码，至少使用九次裁出来，下图给出了一种裁法。
在上面的例子中，小蓝的打印机没办法打印到边缘，所以边缘至少要裁4次。另外，小蓝每次只能裁一张纸，不能重季或者拼起来裁。如果小蓝要用一张纸打印出20行22列共440个二维码，他至少需要裁多少次?
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只输出这个整数，输出多余的内容将无法得分。
【解析与方法】
一道简单的数学题 先看例子，边缘必须裁四次，然后得到两行三列共六张二维码。 横线5裁一次，竖线6 7 8 9各裁一次，加上裁边缘的四次，共九次。 也就是说，横向裁剪次数为【行数-1】次。 竖向裁剪次数为【(列数-1)*行数】次。 题目共20行22列，则次数为：4 + 19 + (21*20) = 443次。可以证明这种方法是裁剪次数最少的方法。所以当行数为20行、列数为22列的440个二维码最少需要：（20-1） + （22-1）*20 + 4 = 443
【Python程序代码】
print(20-1 + (22-1)*20 + 4)
最终结果：443
试题B：寻找整数 （5分）
【问题描述】
有一个不超过10的17次方的正整数n，知道这个数除以2至49后的余数如下表所示，求这个正整数最小是多少？
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只输出这个整数，输出多余的内容将无法得分。
【解析与方法】
首先比较明显可以看出这应该属于线性同余方程组求解的问题，题目已经表明有解，所以可以直接采用中国剩余定理来求解。
首先明确所以的质数2~49的质数ai，以及对于的余数mi.
可以等价于：
存在通解：
令通解最小且符合条件：
带入第一个式子得：
即可以令m1 = a1k1+m1，a1 = k(a1a2)/d，继续迭代得到最终结果。
【Python程序代码】
import math
a = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]
m = [1,2,4,4,0,10,0,18,15,16,27,22,1,11,5]
a1,m1 = a[0],m[0]
def extended_gcd(a, b):
if b == 0:
return a, 1, 0
else:
gcd, x, y = extended_gcd(b, a % b)
return gcd, y, x - (a // b) * y
def mod(a,b):
return ((a%b)+b)%b
for i in range(1,len(a)):
d,k1,k2 = extended_gcd(a1,a[i])
k1 = mod(k1*(m[i]-m1)//d,int(math.fabs(a[i]/d)))
m1 = k1*a1 + m1
a1 = int(math.fabs(a1//d*a[i]))
print(m1)
最终结果：2022040920220409
试题C：质因数个数 （10分）
【题目描述】
给定正整数n,请问有多少个质数是n的约数？
【输入格式】
输入的第一行包含一个整数n。
【输出格式】
输出一个整数,表示n的质数约数个数。
【样例输入】
396
【样例输出】
3
【测评用例与规模】
对于30%的评测用例,1
