博主是刚接触算法不久，侥幸入围python国赛的一枚渣渣。最近在刷历年试题，先把会写的写了，其他的慢慢补，写文章算是见证自己的成长了~
PS:题目包括我觉得个人能力范围之内的A组试题
填空题 购物单题目：
小明刚刚找到工作，老板人很好，只是老板夫人很爱购物。 老板忙的时候经常让小明帮忙到商场代为购物。小明很厌烦，但又不好推辞。
这不，XX大促销又来了！老板夫人开出了长长的购物单，都是有打折优惠的。 小明也有个怪癖，不到万不得已，从不刷卡，直接现金搞定。
现在小明很心烦，请你帮他计算一下，需要从取款机上取多少现金，才能搞定这次购物。
取款机只能提供100元面额的纸币。小明想尽可能少取些现金，够用就行了。 你的任务是计算出，小明最少需要取多少现金。
以下是让人头疼的购物单，为了保护隐私，物品名称被隐藏了。
**** 180.90 88折
**** 10.25 65折
**** 56.14 9折
**** 104.65 9折
**** 100.30 88折
**** 297.15 半价
**** 26.75 65折
**** 130.62 半价
**** 240.28 58折
**** 270.62 8折
**** 115.87 88折
**** 247.34 95折
**** 73.21 9折
**** 101.00 半价
**** 79.54 半价
**** 278.44 7折
**** 199.26 半价
**** 12.97 9折
**** 166.30 78折
**** 125.50 58折
**** 84.98 9折
**** 113.35 68折
**** 166.57 半价
**** 42.56 9折
**** 81.90 95折
**** 131.78 8折
**** 255.89 78折
**** 109.17 9折
**** 146.69 68折
**** 139.33 65折
**** 141.16 78折
**** 154.74 8折
**** 59.42 8折
**** 85.44 68折
**** 293.70 88折
**** 261.79 65折
**** 11.30 88折
**** 268.27 58折
**** 128.29 88折
**** 251.03 8折
**** 208.39 75折
**** 128.88 75折
**** 62.06 9折
**** 225.87 75折
**** 12.89 75折
**** 34.28 75折
**** 62.16 58折
**** 129.12 半价
**** 218.37 半价
**** 289.69 8折
思路：
直接相乘完事，要注意最后必须是00结尾（银行取钱以100为单位
代码：
c=180.90*0.88+10.25*0.65+56.14*0.9+104.65*0.9+100.30*0.88+297.15*0.5+26.75*0.65+130.62*0.5+240.28*0.58+270.62*0.8+115.87*0.88+247.34*0.95+\
73.21*0.9+101.00*0.5+79.54*0.5+278.44*0.7+199.26*0.5+12.97*0.9+166.30*0.78+125.50*0.58+84.98*0.9+113.35*0.68+166.57*0.5+42.56*0.9+81.90*0.95+\
131.78*0.8+255.89*0.78+109.17*0.9+146.69*0.68+139.33*0.65+141.16*0.78+154.74*0.8+59.42*0.8+85.44*0.68+293.70*0.88+261.79*0.65+11.30*0.88+\
268.27*0.58+128.29*0.88+251.03*0.8+208.39*0.75+128.88*0.75+62.06*0.9+225.87*0.75+12.89*0.75+34.28*0.75+62.16*0.58+129.12*0.5+218.37*0.5+289.69*0.8
print(((c//100)+1)*100)答案：5200
迷宫题目
思路：
题目给10*10的迷宫，那就画一个12*12的全1格子，按照题目定义每种字母走法，遍历每个字母格子，最终能走出去的记下来
[[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 'U', 'D', 'D', 'L', 'U', 'U', 'L', 'R', 'U', 'L', 1],
[1, 'U', 'U', 'R', 'L', 'L', 'L', 'R', 'R', 'R', 'U', 1],
[1, 'R', 'R', 'U', 'U', 'R', 'L', 'D', 'L', 'R', 'D', 1],
[1, 'R', 'U', 'D', 'D', 'D', 'D', 'U', 'U', 'U', 'U', 1],
[1, 'U', 'R', 'U', 'D', 'L', 'L', 'R', 'R', 'U', 'U', 1],
[1, 'D', 'U', 'R', 'L', 'R', 'L', 'D', 'L', 'R', 'L', 1],
[1, 'U', 'L', 'L', 'U', 'R', 'L', 'L', 'R', 'D', 'U', 1],
[1, 'R', 'D', 'L', 'U', 'L', 'L', 'R', 'D', 'D', 'D', 1],
[1, 'U', 'U', 'D', 'D', 'U', 'D', 'U', 'D', 'L', 'L', 1],
[1, 'U', 'L', 'R', 'D', 'L', 'U', 'U', 'R', 'R', 'R', 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]代码：
#定义走法
def zou(nums,n,m):
a=0
while nums[n][m]!=1 and a<50:
if nums[n][m]=='L':
m-=1
elif nums[n][m]=='R':
m+=1
elif nums[n][m]=='U':
n-=1
elif nums[n][m]=='D':
n+=1
a += 1
if nums[n][m]==1:
return 1
return 0strings='UDDLUULRUL;UURLLLRRRU;RRUURLDLRD;RUDDDDUUUU;URUDLLRRUU;DURLRLDLRL;ULLURLLRDU;RDLULLRDDD;UUDDUDUDLL;ULRDLUURRR'
nums=[[1 for _ in range(12)] for _ in range(12)]
j=0
n,m=1,0
for i in strings:
if i==';':
n += 1
m=0
continue
else:
m += 1
nums[n][m]=i
res=0
for n in range(1,11):
for m in range(1,11):
if zou(nums,n,m)==1:
res += 1
print(res)答案：31
等差素数序列题目
思路：
暴力解决，先找到素数的序列，然后设置两层循环，第一层是素数序列的首元素，第二层是公差大小。遍历十个若都满足条件则将公差加入res数组，最后min（res）
代码：
## nums：素数集合
nums=[2,3]
for i in range(5,10000):
keys=1
for j in range(2,int(i/2)+2):
if i%j==0:
keys=0
break
if keys==1:
nums.append(i)
res=[]
for num in nums:
for d in range(2,1000):
t1=[]
for i in range(10):
if (num+d*i) in nums:
t1.append(num+d*i)
else:
break
if len(t1)==10:
res.append(d)
print(min(res))
答案：210
承压计算题目
X 星球的高科技实验室中整齐地堆放着某批珍贵金属原料。
每块金属原料的外形、尺寸完全一致，但重量不同，金属材料被严格地堆放成金字塔形。
其中的数字代表金属块的重量（计量单位较大），最下一层的 X 代表 30 台极高精度的电子秤。
假设每块原料的重量都十分精确地平均落在下方的两个金属块上，
最后，所有的金属块的重量都严格精确地平分落在最底层的电子秤上。
电子秤的计量单位很小，所以显示的数字很大，工作人员发现，其中读数最小的电子秤的示数为：2086458231
请你推算出：读数最大的电子秤的示数为多少？
7
5 8
7 8 8
9 2 7 2
8 1 4 9 1
8 1 8 8 4 1
7 9 6 1 4 5 4
5 6 5 5 6 9 5 6
5 5 4 7 9 3 5 5 1
7 5 7 9 7 4 7 3 3 1
4 6 4 5 5 8 8 3 2 4 3
1 1 3 3 1 6 6 5 5 4 4 2
9 9 9 2 1 9 1 9 2 9 5 7 9
4 3 3 7 7 9 3 6 1 3 8 8 3 7
3 6 8 1 5 3 9 5 8 3 8 1 8 3 3
8 3 2 3 3 5 5 8 5 4 2 8 6 7 6 9
8 1 8 1 8 4 6 2 2 1 7 9 4 2 3 3 4
2 8 4 2 2 9 9 2 8 3 4 9 6 3 9 4 6 9
7 9 7 4 9 7 6 6 2 8 9 4 1 8 1 7 2 1 6
9 2 8 6 4 2 7 9 5 4 1 2 5 1 7 3 9 8 3 3
5 2 1 6 7 9 3 2 8 9 5 5 6 6 6 2 1 8 7 9 9
6 7 1 8 8 7 5 3 6 5 4 7 3 4 6 7 8 1 3 2 7 4
2 2 6 3 5 3 4 9 2 4 5 7 6 6 3 2 7 2 4 8 5 5 4
7 4 4 5 8 3 3 8 1 8 6 3 2 1 6 2 6 4 6 3 8 2 9 6
1 2 4 1 3 3 5 3 4 9 6 3 8 6 5 9 1 5 3 2 6 8 8 5 3
2 2 7 9 3 3 2 8 6 9 8 4 4 9 5 8 2 6 3 4 8 4 9 3 8 8
7 7 7 9 7 5 2 7 9 2 5 1 9 2 6 5 3 9 3 5 7 3 5 4 2 8 9
7 7 6 6 8 7 5 5 8 2 4 7 7 4 7 2 6 9 2 1 8 2 9 8 5 7 3 6
5 9 4 5 5 7 5 5 6 3 5 3 9 5 8 9 5 4 1 2 6 1 4 3 5 3 2 4 1
X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X
思路：
不难发现，每个块承重等于自身重量加上面的块施加的重量，整一个30*30的全0数组，一般条件下：dp[i][j]=(dp[i-1][j]+dp[i-1][j-1])/2+nums[i][j]，每行第一个数时：dp[i][j]=(dp[i-1][j])/2+nums[i][j]，每行最后一个数时：dp[i][j]=(dp[i-1][j-1])/2+nums[i][j]
代码：
nums=[]
for i in range(30):
nums.append(list(map(int,input().split())))
dp=[[0 for _ in range(30)]for _ in range(30)]
dp[0][0]=7
for i in range(1,29):
for j in range(i+1):
if j==0:
dp[i][j]=(dp[i-1][j])/2+nums[i][j]
elif j==i:
dp[i][j]=(dp[i-1][j-1])/2+nums[i][j]
else:
dp[i][j]=(dp[i-1][j]+dp[i-1][j-1])/2+nums[i][j]
for i in range(29,30):
for j in range(30):
if j==0:
dp[i][j]=(dp[i-1][j])/2
elif j==i:
dp[i][j]=(dp[i-1][j-1])/2
else:
dp[i][j]=(dp[i-1][j]+dp[i-1][j-1])/2
a=min(dp[-1])
x=2086458231/a
b=max(dp[-1])
print(int(x*b))答案：72665192664
方格分裂题目：
6 x 6 的方格，沿着格子的边线剪开成两部分。
要求这两部分的形状完全相同。
如图就是可行的分割法。
试计算： 包括这 3 种分法在内，一共有多少种不同的分割方法。 注意：旋转对称的属于同一种分割法。
思路：
编程大题 包子凑数还不会深搜，插一个大佬的解析https://blog.csdn.net/qq_51118755/article/details/123121618
题目
思路：
首先要明白一个定理：互质的两个数，他们相乘得到的这个数之后的任何数，都能由这两个数凑出来，比如3和4，相乘之后是12，13开始的所有数字都能由3和4凑出来。如果是4和6这样的最小公倍数不等于1的一组数，他们有无限个数字无法凑出来
所以第一步：判断这组数的最小公倍数是不是1 和 这组数是否含有1，满足一项返回inf
第二步：定义一个初值为0的dp数组，设置这组数的位置为1，然后从1循环到由这组数任意两个互质的数得到的最小公倍数的最小值（因为在这个数之后，所有数字都能由这两个数得到）。
第三步：确定状态转移方程：dp[i]=max(dp[i-nums[1]],dp[i-nums[2]]...)，比如3，7，8，dp[16]=max（dp[13],dp[9],dp[8]），（这里要注意括号内数字得大于0
第四步：找出dp数组中等于0的个数即为答案
代码：
def zhishu(nums):
c=min(nums)
d=max(nums)
if c==1:
return 0
c=c//2+1
for i in range(2,c+1):
t1 =0
for j in nums:
if j/i==int(j/i):
t1 += 1
if t1==len(nums):
return 0
return 1
def gongbeishu(nums):
res=100000
for i in range(len(nums)-1):
for j in range(i+1,len(nums)):
if zhishu([nums[i],nums[j]])==1:
res=min(res,nums[i]*nums[j])
return resdef main(nums):
# 若存在公因数，返回inf
if zhishu(nums)==0:
return 'INF'
# 找出最小公倍数
gbs=gongbeishu(nums)
dp=[0 for _ in range(gbs)]
# 包子数刚好等于
for i in nums:
dp[i-1]=1
mins=min(nums)
for i in range(mins+1,gbs+1):
for j in nums:
if i-1-j>0 and dp[i-1-j]==1:
dp[i-1]=1
break
return len(dp)-sum(dp)题目
思路：
设输入三个数依次为a,b,c。则全输出的情况下有，a-b-c、c-a-b、c-b-a。依次判断每个情况是否合法，最后再将合法的情况查重再排序即可（一定要记得查重！弄了很久一直没A，看了别人才知道这里出问题
代码：
## key1=a-b-c
## key2=c-a-b
## key3=c-b-a
def run(y):
#是否闰年
if (y%4==0 and y%100!=0) or y%400==0:
return True
return False
def hefa(y,m,d):
if y>=60:
y=1900+y
else:
y=2000+y
#判断月合法
if m>12 or m==0:
return False
#判断日合法
if d==0:
return False
if run(y):
if d>d1[m-1]:
return False
else:
if d>d2[m-1]:
return False
return True
def strs(tt):
if tt<10:
return '0'+str(tt)
return str(tt)
def strs2(tt):
if tt>=60:
return str(1900+tt)
return str(2000+tt)
d1=[31,29,31,30,31,30,31,31,30,31,30,31]
d2=[31,28,31,30,31,30,31,31,30,31,30,31]
nums=list(map(int,input().split('/')))
a=nums[0]
b=nums[1]
c=nums[2]
res=[]
if hefa(a,b,c):
aa,bb,cc=strs2(a),strs(b),strs(c)
res.append(aa + '-' + bb + '-' +cc)
if hefa(c,a,b):
aa,bb,cc=strs(a),strs(b),strs2(c)
res.append(cc + '-' + aa + '-' +bb)
if hefa(c,b,a):
aa,bb,cc=strs(a),strs(b),strs2(c)
res.append(cc + '-' + bb + '-' +aa)
##排序+去重
res=list(set(res))
res.sort()
##去重
for i in range(len(res)):
print(res[i])题目
儿童节那天有K位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。
小明一共有N块巧克力，其中第i块是Hi x Wi的方格组成的长方形。
为了公平起见，小明需要从这 N 块巧克力中切出K块巧克力分给小朋友们。切出的巧克力需要满足：
1. 形状是正方形，边长是整数
2. 大小相同
例如一块6x5的巧克力可以切出6块2x2的巧克力或者2块3x3的巧克力。
当然小朋友们都希望得到的巧克力尽可能大，你能帮小Hi计算出最大的边长是多少么？
思路：
一开始先写了个枚举，从边长为1开始，能切出k块，那就试试2，以此类推。后面发现超时，改用了二分法，分数从44->78还是没A，so代码思路仅供参考
判断条件：确定边长后，遍历每一块巧克力能切出多少块，每块巧克力切出的块数=（长//size)*(宽//size)
代码：
def main(nums,k,size):
count=0
for i in nums:
a,b=i[0],i[1]
count += (a//size)*(b//size)
if count>=k:
return True
return False
n,k=map(int,input().split())
nums=[]
left,right=0,0
for i in range(n):
tem=list(map(int,input().split()))
nums.append(tem)
right=max(max(tem),right)
while left+1题目
思路：
第一反应肯定是前缀和了，两个for循环，判断(sum[:j]-sum[:i-1])%K=0，满足则区间[i,j]是k倍区间。然后就是思考如何实现，一开始写暴力，不出意料超时了。然后找到一个数学公式：
( sum[j]-sum[i-1] )%K= 0 -> sum[j]%K-sum[i-1]%K -> sum[j]%K=sum[i-1]%K
例如样例，sum = [1, 3, 6, 10, 15]。分别对K取余后的值为[1,1,0,0,1]，这时候定义一个K大小的数组cnt，cnt[0]=2（即整除）,cnt[1]=3（余1的个数），相同数之间是k倍区间，第一个k倍区间[1,1]即原数组[1,3]，然后j可以等于i，所以0也可以构成k倍区间，即结果+=cnt[0]
代码：
n,k = map(int,input().split())
res = 0
cnt = [0]*k
for i in range(n):
num = int(input())
res += num
cnt[res%k] += 1
res = cnt[0]
for i in range(0,k):
if cnt[i]
res += cnt[i]*(cnt[i]-1)/2
print(int(res))
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）