蓝桥杯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 a for 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')#St for 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背包问题中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]*n for i in range(n): a[i]=int(input()) def gcd(a,b): while b: a,b=b,a%b return a def 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]*n for 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]%k ans=0 p=dict() for i in range(n+1): if z[i] not in p.keys(): p[z[i]]=1 else: p[z[i]]+=1 for 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=0 searched=[] 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 False def 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
学习犹如逆水行舟，不进则退，希望大家都能在这次省赛中拿到理想成绩。
