【蓝桥杯国赛真题笔记】Python
蓝桥杯22天 最近感觉刷题越刷越上头 AC率也越来越好了
emm下面的解释都挺详细的
有任何不懂的欢迎留言评论
1.天干地支（填空题）
题目描述
古代中国使用天干地支来记录当前的年份。
天干一共有十个，分别为：甲（jiǎ）、乙（yǐ）、丙（bǐng）、丁（dīng）、戊（wù）、己（jǐ）、庚（gēng）、辛（xīn）、壬（rén）、癸（guǐ）。
地支一共有十二个，分别为：子（zǐ）、丑（chǒu）、寅（yín）、卯（mǎo）、辰（chén）、巳（sì）、午（wǔ）、未（wèi）、申（shēn）、酉（yǒu）、戌（xū）、 亥（hài）。
将天干和地支连起来，就组成了一个天干地支的年份，例如：甲子。
20202020 年是庚子年。
每过一年，天干和地支都会移动到下一个。例如 20212021 年是辛丑年。
每过 6060 年，天干会循环 66 轮，地支会循环 55 轮，所以天干地支纪年每 6060 年轮回一次。例如 19001900 年，19601960 年，20202020 年都是庚子年。
给定一个公元纪年的年份，请输出这一年的天干地支年份。
问题分析：考察取余 将下标和天干（地支）对应起来
用一个列表存起来 由于数组的下标是从0开始，这里对应起来可能会卡住一下
解决办法：以天干（下标从0到9）为例子，比如输入n=2027,由于一开始2020对应的下标是6（gengzi），经过7年后，数一下，会发现，2027对应的下标应该是3，
如果直接(7)%9会发现等于2 不符合我们的预期。
想到了一个办法，把下标0—9看作1—10,因而只需要(#变化的年数)%10-1即可
细节的地方：
变化的年数是负数怎么办？即导致下标是负数怎么办？
emm可以找几个比2020小的试一下，能过就放上去。（因为数学规律通常是简洁的，不会想得那么复杂!!）
AC代码：
a=['jia', 'yi', 'bing', 'ding', 'wu', 'ji', 'geng', 'xin', 'ren', 'gui']b=['zi', 'chou', 'yin', 'mao', 'chen', 'si', 'wu', 'wei', 'shen', 'you', 'xu', 'hai']n=int(input())print(a[(7+n-2020)%10-1]+b[(1+n-2020)%12-1])2.求值（填空题）
这道题和【蓝桥杯国赛真题】备战24天 Python_Py小郑的博客-CSDN博客
我之前写的文章里面的：阶乘约数 道理差不多
对于这道题我的思考过程是，第一步肯定想到暴力枚举，但是由于暴力枚举的上限关系到数组m的大小，m[i]表示质数i出现的次数，（i如果是偶数，我们初始化为1了，至于为什么在上面那个博客里面那道题详细说了），当上限很大的时候,m往往过大，时间过长，方法不合适。 但是有了先前那道题的经验，已经有了100以内的任意数字其的约数个数，把他们打印出来，即执行下面这段语句，观察一下，发现如果取两个数字，他们互质的话，那么，
for i in range(1,101): print(i,find(i))#find(i)在下面有说他们的乘积对应的约数个数就是两个数字约数个数的乘积。
因而，有了1-100对应的约数，我们可以进行迭代，详细点说：
创建一个数组p=[] ,p的每个元素以列表出现,每个列表有两个数字，分别存特定数字和特定数字对应的约数个数,即比如p=[[2，2],[7,2]]，可以获知2的约数有两个，7的约数有两个，由于2和7互质，那么可以迭代生成[14,4]
由于迭代多次不大可能实现，观察经过第一次迭代，发现已经有符合条件的（刚好是答案45360），那么只需要在（1,45260)验证即可，这是我的思路:做题经验+观察+猜测验证
因为是填空题嘛hh，结果发现在（1，45360）只有45360这一个数，那么就是他了
AC代码
#把n分解为多个质数乘机(a1+1)(a2+1)..(an+1)==100退出def find(n): s=1 m=[1]*101#m[i]:质数i被分解的个数 j=2 while j<=n: if n%j==0: m[j]+=1 n//=j else: j+=1 for i in m: s*=i return s#返回约数个数p=[]for i in range(1,101): if find(i)%5==0 or find(i)%2==0: p.append([i,find(i)])def gcd(a,b): while b: a,b=b,a%b return afor i in range(1,len(p)): if gcd(p[i][0],p[i-1][0])==1: key=p[i][0]*p[i-1][0] val=p[i][1]*p[i-1][1] if [key,val] not in p: p.append([key,val]) St=float('inf')#Stfor i in range(len(p)): for j in range(i+1,len(p)): if gcd(p[i][0],p[j][0])==1: if p[i][1]*p[j][1]==100: St=min(St,p[i][0]*p[j][0]) print(p[i],p[j])3.包子凑数
问题描述：
小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有N种蒸笼，其中第i种蒸笼恰好能放Ai个包子。每种蒸笼都有非常多笼，可以认为是无限笼。
每当有顾客想买X个包子，卖包子的大叔就会迅速选出若干笼包子来，使得这若干笼中恰好一共有X个包子。比如一共有3种蒸笼，分别能放3、4和5个包子。当顾客想买11个包子时，大叔就会选2笼3个的再加1笼5个的（也可能选出1笼3个的再加2笼4个的）。
当然有时包子大叔无论如何也凑不出顾客想买的数量。比如一共有3种蒸笼，分别能放4、5和6个包子。而顾客想买7个包子时，大叔就凑不出来了。
小明想知道一共有多少种数目是包子大叔凑不出来的。
问题分析： 结合这道题的结论：
两个数p,q互质，那么p和q最大不能表示的数字为pq-(p+q）
我们大胆推论，如果给出的n种包子数目不互质，那么就有inf（无穷）多个不能表示
否则 即gcd(a,b,c,d..)=1，就有有限个数字不能表示
包子数目最大是100，那么与100互质的最大是99。
在这n种包子数目中，总能取出两个最大的，即为p,q，那么pq-(p+q）+1开始以后的数目一定都可以表示，所以我们只需要统计[1,pq-(p+q])之内有多少个不能表示的数字
不妨令p>q，那么pq-(p+q)<pq<=9900,所以无论给出多少种互质包子数目，我们至多需要在[1,9900]这个范围内去搜（这里需要好好理解一下，想象一下区间）
下面讨论如何去搜：由于有一种包子无限个，想到完全背包问题
二维完全背包和二维01背包的区别在于 动态规划-完全背包问题_WUST_XIAO的博客-CSDN博客
可以这样理解:01背包问题中dp[i][j]设为容量为i前j个物品的最大价值
完全背包问题dp[i][j]代表容量为i前j种物品的最大价值
所以在01背包dp[i][j]在递推关系中，可能转移到dp[i-weight[j]][j-1]+val[j]，j减掉了1，因为物品有限；
而在完全背包问题中，可能转移到dp[i-weight[j]][j]+val[j]，j不变，因为物品无限，理解为预留weight[j]的空间，用前j种物品能够凑出来的最大值，那么这样理解,第j个物品就不止用一次。然后本题就可以迎刃而解~
AC代码
n=int(input())a=[0]*nfor i in range(n): a[i]=int(input())def gcd(a,b): while b: a,b=b,a%b return adef l_gcd(nums): if len(nums)==1: return nums[0] elif len(nums)==2: return gcd(nums[0],nums[1]) else: return gcd(l_gcd(nums[:len(nums)//2]),l_gcd(nums[len(nums)//2:]))if l_gcd(a)!=1:#这n个数字的最大公约数不等于1 print('INF')else:#这n个数字的最大公约数等于1,有解 #区间确定，取n个数字里面最大的两个p,q #那么在正整数集合,pq-(p+q)+1开始之后均可以表示，所以[1,9900] ans,res=1,0 a.insert(0,0) top=10000 dp=[[0]*(n+1)for i in range(0,top+1)]#目标为i，前j种包子(每种包子数量无限)能不能凑出来 for i in a: dp[i]=[1]*(n+1) for i in range(1,top+1): for j in range(1,n+1): if a[j]>i: dp[i][j]=dp[i][j-1] else: dp[i][j]=max(dp[i][j-1],dp[i-a[j]][j]) v=0 for k in range(1,len(dp)): if 1 not in dp[k]: v+=1 print(v) 4.K倍区间（省赛题）
问题描述：给定一个长度为N的数列，A1, A2, ... AN，如果其中一段连续的子序列Ai, Ai+1, ... Aj(i <= j)之和是K的倍数，我们就称这个区间[i, j]是K倍区间。
你能求出数列中总共有多少个K倍区间吗？
问题分析：已知(a+b)%p=(a%p+b%p)%p
推导过程,设a=xp+y,b=mp+n,那么(a+b)%p=((x+m)p+y+n)%p=(y+n)%p
即(a%p+b%p)%p 得证
那么，对于本题而言，还需要用到前缀和 不妨令Si>Sj，那么Si-Sj代表的和为区间[j+1,i]
按照提议(Si-Sj）%k==0 那么(Si%k-Sj%k)%k==0
那么Si%k=Sj%k，所以利用这个条件：
根据样例输入，我们存入数组a=[1,2,3,4,5]
前缀和数组[1,3,6,10,15] ，前缀和取余数组z=[1,1,0,0,1]
我们发现z[0],z[1],z[4]=1，那么[1],[1,4],[2,4]这三个区间都符合，懂排列组合的应该明白了等于C（n,2），到这里有三种
然后我们发现z[2],z[3]=0 那么 [3]这个区间符合，到这里加上前面3种一共4种
还有两种去哪了？把区间都列一下，会发现，正是由于我们的下标从0开始，那么区间的左端点必定大于等于1，那么就无法取到下标0，所以我们在数组a最前面插入一个0，前缀和数组和前缀和取余数组相应变化。会发现，现在0正好有3个，C(3,2)=3
加起来一共6种 符合预期，所以利用好样例，根据自己程序的实际和真正的要求做对比，发现缺了什么，想一想，大胆补上去条件，问题往往都可以迎刃而解。
AC代码
n,k=map(int,input().split())a=[0]*nfor i in range(n): a[i]=int(input())a.insert(0,0)s=[0]*(n+1)#前缀和s[0]=a[0]for i in range(1,n+1): s[i]=s[i-1]+a[i]#对s[i] mod k，代表前i项和对k取余后的余数z=[0]*(n+1)for i in range(n+1): z[i]=s[i]%kans=0p=dict()for i in range(n+1): if z[i] not in p.keys(): p[z[i]]=1 else: p[z[i]]+=1for j in p.values(): ans+=int(j*(j-1)/2)print(ans)5.青蛙跳杯子
奈何小郑没有写出来，是一个BFS模板题，求最少次数。66分超时了
但还是总结一下吧：BFS需要队列queue,pre记录前驱结点，searched记录访问过的结点，judge函数判断是否合法，关键点就这么些。（代码可以看看，没AC）
st=input()end=input()queue=[st]step=0searched=[]pre={}dx=[-3,-2,-1,1,2,3]def judge(new): global searched,pre if new not in searched and new not in pre.keys(): return True return Falsedef change(tmp,now_index,new_index): y=list(tmp) y[now_index],y[new_index]=y[new_index],y[now_index] return ''.join(y)while queue: tmp=queue.pop(0) if tmp==end: step=1 while pre[tmp]!=st: step+=1 tmp=pre[tmp] print(step) break else: #BFS搜6个方向，索引*位置 now_index=tmp.index('*') for i in range(6): new_index=now_index+dx[i] if 0<=new_index<=len(tmp)-1: new=change(tmp,now_index,new_index) if judge(new): searched.append(new) queue.append(new) pre[new]=tmp
