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]*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
学习犹如逆水行舟，不进则退，希望大家都能在这次省赛中拿到理想成绩。
有任何不懂欢迎留言提问 ！
