【思特奇杯·云上蓝桥-算法集训营】第一周
Hello，大家好我叫是Dream呀，一个有趣的Python博主，多多关照
CSDN Python领域优质创作者，大二在读，欢迎大家找我合作学习（文末有VX 想进学习交流群or学习资料 欢迎+++）
入门须知：这片乐园从不缺乏天才，努力才是你的最终入场券！
最后，愿我们都能在看不到的地方闪闪发光，一起加油进步
“一万次悲伤，依然会有Dream，我一直在最温暖的地方等你”，唱的就是我！哈哈哈~
✨✨✨
1️⃣第一题 跑步训练2️⃣代码分享3️⃣思路解析1️⃣第二题 阶乘约数2️⃣代码分享3️⃣思路解析1️⃣第三题 出栈次序2️⃣代码分享3️⃣思路解析1️⃣第四题 哥德巴赫分解2️⃣代码分享3️⃣思路解析1️⃣第五题 图书排列2️⃣代码分享3️⃣思路解析1️⃣第六题 猴子分香蕉2️⃣代码分享3️⃣思路解析1️⃣第七题 稍小分数2️⃣代码分享3️⃣思路解析1️⃣第八题 excel 地址2️⃣代码分享3️⃣思路解析1️⃣第九题 日期问题2️⃣代码分享3️⃣思路解析1️⃣第十题 整数划分2️⃣代码分享3️⃣思路解析1️⃣第十一题 一步之遥2️⃣代码分享3️⃣思路解析1️⃣第十二题 机器人塔2️⃣代码分享3️⃣思路解析1️⃣第十三题2️⃣代码分享3️⃣思路解析写在最后----惊喜活动
磊福利1賂福利2是Dream呀博主正在参与2021年CSDN博客之星评选活动！希望你可以五星支持哟！感谢~往期文章----好文推荐
1️⃣第一题 跑步训练问题描述*
小明要做一个跑步训练，初始时，小明充满体力，体力值计为 10000。
如果小明跑步，每分钟损耗 600 的体力。
如果小明休息，每分钟增加 300 的体力。
体力的损耗和增加都是 均匀变化的。
小明打算跑一分钟、休息一分钟、再跑一分钟、再休息一分钟……如此循环。
如果某个时刻小明的体力到达 0，他就停止锻炼，请问小明在多久后停止锻炼。
为了使答案为整数，请以秒为单位输出答案，答案中只填写数，不填写单位。
答案提交：
这是一道结果填空题，你只需要算出结果后提交即可。
本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法
得分。
# 一万次悲伤，依然会有Dream，我一直在最温暖的地方等你！
# @Time : 2022/1/5 21:46
# @Author : 是Dream呀！
# @File : 打草.py
a = 10000
for i in range(10000):
if i%2==0:
if a<=600:
print(a/600)
# print(i * 60 + a / 10)
print(f'{i * 60 + a / 10:.0f}')
break
a-=600
else:
a+=300
3️⃣思路解析
遍历分钟数，偶数代表跑步（0也算）-600；奇数代表休息-300.用%来进行整除，余数为零跑步，余数为一代表休息，for循环遍历依次相加相减判断条件：当能量a为0时就停止，此时考虑两种情况，一是运动完刚好到0，二是还没运动完一分钟就已经到零了，又由题目中所说要均匀变化，故要等能量a<=600时就停止遍历，将最后一次的能量除每分钟运动消耗能量，得出最后的分钟数。本题答案为一个整数，但是依据我们的了解，1/3或者1/6无论如何都是除不开的，所以会有题目中的*60化为秒数。最后输出的时候我们可以借用Python3.5中自带的string—f格式字符串的方法，利于f'{i * 60 + a / 10:.0f}'中的取小数点方法:.0f来使其不保留小数。 1️⃣第二题 阶乘约数
问题描述
定义阶乘 n! = 1 × 2 × 3 × ··· × n。
请问 100! （100 的阶乘）有多少个约数。
答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。
本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无
法得分。
# 一万次悲伤，依然会有Dream，我一直在最温暖的地方等你！
# @Time : 2022/1/6 9:50
# @Author : 是Dream呀！
# @File : 第二题 阶乘约数.py
n = 100
p = [2] # 2是最小的质数
# 求一百之内的所有质数
for i in range(3,n+1):
j=2
while j
运行结果
39001250856960000
3️⃣思路解析
1.约数：约数又称因数，整数A除以整数B(B≠0) 除得的商正好是整数而没有余数，我们就说A能被B整除，或B能整除A。A称为B的倍数，B称为A的约数。
2.约数个数：
定理补充：
6=2乘3，由一个质数2和一个质数3的乘积组成。6的全部约数x（即因子）为x=（an1+1）（an2+1）其中an1和an2是不同质数的个数即代入得x=(1+1)(1+1),x=4.
3.求一百之内的所有质数，然后将其放到列表中
4.运用字典记录不同的质数，用键值对存储其出现的次数。
暴力解法：
使用Python math.factorial() 方法----返回数字的阶乘。
import math
def count(num: int):
k, ans = 2, 1
while k < (num // k):
p = 1
while num % k == 0:
num //= k
p += 1
ans *= p
k += 1
if num > 1:
ans *= 2
return ans
if __name__ == '__main__':
n = math.factorial(100)
print(f'100! = {n}')
print(f'约数个数 = {count(n)}')
1️⃣第三题 出栈次序
问题描述
X 星球特别讲究秩序，所有道路都是单行线。
一个甲壳虫车队，共 16 辆车，按照编号先后发车，夹在其它车流中，缓缓前行。
路边有个死胡同，只能容一辆车通过，是临时的检查站，如图所示。
X 星球太死板，要求每辆路过的车必须进入检查站，也可能不检查就放行，也可能仔细检查。
如果车辆进入检查站和离开的次序可以任意交错。那么，该车队再次上路后，可能的次序有多少种？
为了方便起见，假设检查站可容纳任意数量的汽车。
显然，如果车队只有 1 辆车，可能次序 1 种；2 辆车可能次序 2 种；3 辆车可能次序 5 种。
现在足足有 16 辆车啊，亲！需要你计算出可能次序的数目。
答案提交
这是一个整数，请通过浏览器提交答案，不要填写任何多余的内容（比如说明性文字）
2️⃣代码分享
# 一万次悲伤，依然会有Dream，我一直在最温暖的地方等你！
# @Time : 2022/1/6 15:50
# @Author : 是Dream呀！
# @File : 第三题 出栈次序.py
result=1
for x in range(1,17):
result=result*(4*x-2)/(x+1)
print(f'{result:.0f}')
答案分享：
35357670
3️⃣思路解析
卡特兰数又称卡塔兰数，卡特兰数是组合数学中一个常出现在各种计数问题中的数列。以比利时的数学家欧仁·查理·卡塔兰 (1814–1894)的名字来命名设h(n)为Catalan数的第n+1项，令h(0)=1,h(1)=1，Catalan数满足递推式：h(n)= h(0)h(n-1)+h(1)h(n-2) + … + h(n-1)h(0) (n>=2)出栈次序数目为卡特兰数，满足一个递推公式：h[1]=1;h[n]=h[n-1] (4n-2)/(n+1).其中n表示数的个数。
1️⃣第四题 哥德巴赫分解
哥德巴赫猜想认为：不小于4的偶数都可以表示为两个素数的和。
你不需要去证明这个定理，但可以通过计算机对有限数量的偶数进行分解，验证是否可行。
实际上，一般一个偶数会有多种不同的分解方案，我们关心包含较小素数的那个方案。
对于给定数值范围，我们想知道这些包含较小素数方案中最大的素数是多少。
比如，100以内，这个数是19，它由98的分解贡献。
你需要求的是10000以内，这个数是多少？
注意，需要提交的是一个整数，不要填写任何多余的内容（比如，说明性的文字）
2️⃣代码分享
# 一万次悲伤，依然会有Dream，我一直在最温暖的地方等你！
# @Time : 2022/1/6 17:04
# @Author : 是Dream呀！
# @File : 第四题 哥德巴赫分解.py
def sushu(num):
if num<2:
return False
elif num == 2:
return True
for i in range(2,num):
if num%i == 0:
return False
return True
def fenjie(n):
# 只需要取一半的大小就行，另一半表示为n-j
for j in range(2,n//2+1):
if sushu(j)and sushu(n-j)==True:
return [j,n-j]
a = []
for k in range(4,10001,2):
# 取返回值中最小的那个加入列表中
a.append(min(fenjie(k)))
# 输出列表中最大的数
print(max(a))
答案分享：
173
3️⃣思路解析
首先这道题读来读去的意思就是，要找10000以内的两两一对的素数组合，然后取两两组合中的小的那一个，再将所有组合中的小的素数进行比较，取最大的那个，得到我们想要的答案。那就是首先写出一个函数来确定是否是素数，然后再写出一个函数，使其可以得到所有的素数组合，之后再取其较小者，然后所有较小者比较得到其中的最大者！
1️⃣第五题 图书排列
题目描述：
将编号为 1~10 的 10 本书排放在书架上，要求编号相邻的书不能放在相邻的位置。
请计算一共有多少种不同的排列方案。
注意，需要提交的是一个整数，不要填写任何多余的内容
2️⃣代码分享
# 一万次悲伤，依然会有Dream，我一直在最温暖的地方等你！
# @Time : 2022/1/6 19:35
# @Author : 是Dream呀！
# @File : 第五题 图书排列.py
import itertools
res = 0
x = [i for i in range(10)]
def check(a):
for i in range(9):
if abs(a[i]-a[i+1]) == 1:
return False
return True
for i in itertools.permutations(x):
if check(i):
res += 1
print(res)
3️⃣思路解析
需要用到itertools模块中的排列函数：permutations()，简单一个例子：
import itertools
nums = [1,3,5]
for num in itertools.permutations(nums):
print(num)
输出：
(1, 3, 5)
(1, 5, 3)
(3, 1, 5)
(3, 5, 1)
(5, 1, 3)
(5, 3, 1)
itertools包中的permutations可以迭代出所有的排列可能，然后直接用check函数进行判断就可以了
1️⃣第六题 猴子分香蕉
题目如下
5只猴子是好朋友，在海边的椰子树上睡着了。这期间，有商船把一大堆香蕉忘记在沙滩上离去。
第1只猴子醒来，把香蕉均分成5堆，还剩下1个，就吃掉并把自己的一份藏起来继续睡觉。
第2只猴子醒来，重新把香蕉均分成5堆，还剩下2个，就吃掉并把自己的一份藏起来继续睡觉。
第3只猴子醒来，重新把香蕉均分成5堆，还剩下3个，就吃掉并把自己的一份藏起来继续睡觉。
第4只猴子醒来，重新把香蕉均分成5堆，还剩下4个，就吃掉并把自己的一份藏起来继续睡觉。
第5只猴子醒来，重新把香蕉均分成5堆，哈哈，正好不剩！
请计算一开始最少有多少个香蕉。
需要提交的是一个整数，不要填写任何多余的内容。
2️⃣代码分享
# 一万次悲伤，依然会有Dream，我一直在最温暖的地方等你！
# @Time : 2022/1/6 20:12
# @Author : 是Dream呀！
# @File : 第六题 猴子分香蕉.py
for i in range(1, 10000):
a = i
if (i-1)%5 == 0:
i = (i-1)/5
i = i*4
if (i-2)%5==0:
i = (i - 2) / 5
i = i * 4
if (i-3)%5 == 0:
i = (i - 3) / 5
i = i * 4
if (i-4)%5==0:
i = (i - 4) / 5
i = i * 4
if i and i%5 == 0:
print(a)
break
3️⃣思路解析
没有技巧，全是感情…慢慢写吧
1️⃣第七题 稍小分数
回到小学----
真分数：分子小于分母的分数
既约分数：分子分母互质，也就是说最大公约数是 1 x 星球数学城的入口验证方式是：
屏幕上显示一个真分数，需要你快速地找到一个比它小的既约分数，要求这个分数越大越好。
同时限定你的这个分数的分母不能超过 100
2️⃣代码分享
# 一万次悲伤，依然会有Dream，我一直在最温暖的地方等你！
# @Time : 2022/1/6 20:31
# @Author : 是Dream呀！
# @File : 第七题 稍小分数.py
from fractions import Fraction
a = int(input('请输入分子:'))
b = int(input('请输入分母:'))
def check(x):
if x == 2:
return True
for i in range(2, x):
if x%i==0:
return False
return True
m = []
ALL = []
for i in range(2,100):
if check(i):
m.append(i)
for i,j in enumerate(m):
for k in m[:i]:
a = Fraction(k,j)
if a not in ALL:
ALL.append(a)
ALL = sorted(ALL)
num = Fraction(a, b)
out = False
for i in range(len(ALL)):
if ALL[i] >= num:
print(ALL[i-1])
out = True
break
if not out:
print(ALL[-1])
3️⃣思路解析
暴力求解
1️⃣第八题 excel 地址
问题描述
Excel 单元格的地址表示很有趣，它使用字母来表示列号。 比如， A 表示第 1 列， B 表示第 2 列， Z 表示第 26
列， AA 表示第 27 列， AB 表示第 28 列， BA 表示第 53 列， … 当然
Excel的最大列号是有限度的，所以转换起来不难。 如果我们想把这种表示法一般化，可以把很大的数字转换为很长的字母序列呢？
本题目即是要求对输入的数字, 输出其对应的 Exce濿 地址表示方式。
样例输入
26
样例输出
Z
样例输入
2054
样例输出
BZZ
数据规模和约定
我们约定，输入的整数范围[1,2147483647]
峰值内存消耗（含虚拟机） < 256M
CPU 消耗 < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。
注意：
main 函数需要返回 0;
只使用 ANSI C/ANSI C++ 标准;
不要调用依赖于编译环境或 *** 作系统的特殊函数。
所有依赖的函数必须明确地在源文件中
不能通过工程设置而省略常用头文件。
提交程序时，注意选择所期望的语言类型和编译器类型
2️⃣代码分享
# 一万次悲伤，依然会有Dream，我一直在最温暖的地方等你！
# @Time : 2022/1/6 21:59
# @Author : 是Dream呀！
# @File : 第八题 excel地址.py
# 一万次悲伤，依然会有Dream，我一直在最温暖的地方等你！
# @Time : 2022/1/6 21:59
# @Author : 是Dream呀！
# @File : 第八题 excel地址.py
n = int(input())
a = []
while n != 0:
if n % 26 == 0:
a.append(26)
n = n / 26
if n==1:
n=0
else:
a.append(n % 26)
n //= 26
print(a)
l = len(a)
for i in range(l):
print(chr(a[l - i - 1] + 64), end='')
3️⃣思路解析
chr()函数返回值是当前整数对应的 ASCII 字符，利用其返回字母。这个相当于就是26进制，后面再再用chr（）函数将字母填充上就可以啦！
1️⃣第九题 日期问题
小明正在整理一批历史文献。这些历史文献中出现了很多日期。小明知道这些日期都在1960年1月1日至2059年12月31日。令小明头疼的是，这些日期采用的格式非常不统一，有采用年/月/日的，有采用月/日/年的，还有采用日/月/年的。更加麻烦的是，年份也都省略了前两位，使得文献上的一个日期，存在很多可能的日期与其对应。
比如02/03/04，可能是2002年03月04日、2004年02月03日或2004年03月02日。
给出一个文献上的日期，你能帮助小明判断有哪些可能的日期对其对应吗？
输入 一个日期，格式是"AA/BB/CC"。 (0 <= A, B, C <= 9)
输出 输出若干个不相同的日期，每个日期一行，格式是"yyyy-MM-dd"。多个日期按从早到晚排列。
样例输入 02/03/04
样例输出 2002-03-04 2004-02-03 2004-03-02
资源约定： 峰值内存消耗（含虚拟机） < 256M CPU消耗 < 1000ms
2️⃣代码分享
# 一万次悲伤，依然会有Dream，我一直在最温暖的地方等你！
# @Time : 2022/1/7 11:48
# @Author : 是Dream呀！
# @File : 第九题 日期问题.py
a = list(map(int,input().split('/')))
list = []
def runnian(year):
if year%4 == 0 and year %100 != 0:
return True
elif year % 400 == 0:
return True
return False
def fun(x,y,z): # x代表年，y代表月，z代表天数、
# 年份
if 0 <= x <= 59:
x += 2000
elif 60 <= x <=90:
x += 1900
# 考虑闰年二月份的具体情况
if runnian(x) and y==2 and z>29:
return False
if not runnian(x) and y==2 and z>28:
return False
# 月份
if (y==4 and z > 30) or (y == 6 and z > 30) or (y == 9 and z > 30) or (y == 11 and z > 30):
return False
if y > 12:
return False
# 判断日
if z>31:
return False
# 满足所有条件，输出日期格式
else:
if y < 10:
y ='0'+str(y)
if z <10:
z = '0'+str(z)
list.append(f'{x}-{y}-{z}')
# 三种情况
fun(a[0],a[1],a[2])
fun(a[2],a[1],a[0])
fun(a[2],a[0],a[1])
for i in sorted(list):
print(i)
3️⃣思路解析
分闰年按年、按月、按日
1️⃣第十题 整数划分
对于一个正整数n的划分，就是把n变成一系列正整数之和的表达式。注意，分划与顺序无关，例如6=5+1.跟6=1+5是同一种分划，另外，这个整数本身也是一种分划。
例如：对于正整数n=5，可以划分为：
1+1+1+1+1
1+1+1+2
1+1+3
1+2+2
2+3
1+4
5
输入描述 输入一个正整数n
输出描述 输出n整数划分的总数k
输入样例 5
输出样例 7
2️⃣代码分享
# 一万次悲伤，依然会有Dream，我一直在最温暖的地方等你！
# @Time : 2022/1/7 14:07
# @Author : 是Dream呀！
# @File : 第十题 整数划分.py
list = []
def fun(n,a,k):
if n <= 0:
for i in range(k):
continue
list.append(1)
for i in range(n,0,-1):
if k > 0 and i < a[k-1]:
continue
a[k] = i
fun(n-i,a,k+1)
a = [0]*10000
fun(5,a,0)
print(len(list))
3️⃣思路解析
递归方法
1️⃣第十一题 一步之遥
从昏迷中醒来，小明发现自己被关在X星球的废矿车里。
矿车停在平直的废弃的轨道上。
他的面前是两个按钮，分别写着“F”和“B”。
小明突然记起来，这两个按钮可以控制矿车在轨道上前进和后退。
按F，会前进97米。按B会后退127米。
透过昏暗的灯光，小明看到自己前方1米远正好有个监控探头。
他必须设法使得矿车正好停在摄像头的下方，才有机会争取同伴的援助。
或许，通过多次 *** 作F和B可以办到。
矿车上的动力已经不太足，黄色的警示灯在默默闪烁…每次进行 F 或 B *** 作都会消耗一定的能量。
小明飞快地计算，至少要多少次 *** 作，才能把矿车准确地停在前方1米远的地方。请填写为了达成目标，最少需要 *** 作的次数。
注意： 需要提交的是一个整数，不要填写任何无关内容（比如：解释说明等）
2️⃣代码分享
# 一万次悲伤，依然会有Dream，我一直在最温暖的地方等你！
# @Time : 2022/1/7 20:42
# @Author : 是Dream呀！
# @File : 第十一题 一步之遥.py
# 暴力方法
x = 97
y = 127
ans = 600
for i in range(300):
for j in range(300):
if i*x - j* y==1:
ans = min(ans, i+j)
print(ans)
3️⃣思路解析
暴力解法
1️⃣第十二题 机器人塔
X星球的机器人表演拉拉队有两种服装，A和B。
他们这次表演的是搭机器人塔。
类似：
A
B B
A B A
A A B B
B B B A B
A B A B B A
队内的组塔规则是：
A 只能站在 AA 或 BB 的肩上。
B 只能站在 AB 或 BA 的肩上。
你的任务是帮助拉拉队计算一下，在给定A与B的人数时，可以组成多少种花样的塔。
输入一行两个整数 M 和 N，空格分开（0
要求输出一个整数，表示可以产生的花样种数。
例如： 用户输入： 1 2
程序应该输出： 3
再例如： 用户输入： 3 3
程序应该输出： 4
资源约定： 峰值内存消耗 < 256M CPU消耗 < 1000ms
2️⃣代码分享
# 一万次悲伤，依然会有Dream，我一直在最温暖的地方等你！
# @Time : 2022/1/7 20:48
# @Author : 是Dream呀！
# @File : 第十二题 机器人塔.py
import math
def check():# 判断是否可以向上拓展
a = 0
b = 0
tmp = row
while tmp >0:
for i in range(1, tmp+1):
if cnt[i] == 1:
a +=1
else:
b += 1
for i in range(2, tmp+1):
if cnt[i-1]==cnt[i]:
cnt[i-1] = 1
else:
cnt[i-1] = 2
tmp -=1
if a == m and b == n:
return True
else:
return False
def dfs(k):# 遍历所有第一排
global res
if k > row:
if check():
res +=1
return
cnt[k] = 1
dfs(k+1)
cnt[k] = 2
dfs(k+1)
if __name__ == "__main__":
m = int(input())
n = int(input())
res = 0
cnt = [0 for _ in range(100010)]
row = int(math.sqrt(2*(m+n)))
dfs(1)
print(res)
3️⃣思路解析
太难了，我看不懂了，呜呜呜等会了一定回来补上…
1️⃣第十三题
如下图所示。在七角星的 14 个节点上填入 1 ~ 14的数字，不重复，不遗漏。 要求每条直线上的四个数字之和必须相等。
图中已经给出了 3 个数字。 请计算其它位置要填充的数字，答案唯一。
填好后，请输出绿色节点的 4 个数字（从左到右，用空格分开）。
2️⃣代码分享
# 一万次悲伤，依然会有Dream，我一直在最温暖的地方等你！
# @Time : 2022/1/7 20:49
# @Author : 是Dream呀！
# @File : 第十三题 七星填空.py
import itertools
x = [i for i in range(1, 15)]
x.remove(6)
x.remove(11)
x.remove(14)
def check(a):# 这道题对数字的排序完全是自定义，每次比较是为了减少所需要的时间
num1 = a[0] + a[1] + a[2] + a[3]
num2 = 6 + a[1] + a[4] + 14
if num1 != num2:
return False
num3 = 6 + a[2] + a[5] + 11
if num2 != num3:
return False
num4 = a[3] + a[5] + a[7] + a[10]
if (num3 != num4):
return False
num5 = a[8] + a[9] + a[7] + 11
if (num4 != num5):
return True
num6 = a[6] + a[10] + a[8] + 14
if (num5 != num6):
return False
num7 = a[0] + a[4] + a[6] + a[9]
if (num6 != num7):
return False
return True
for i in itertools.permutations(x):
if check(i):
print(i)
for j in range(4):
print(i[j])
break
3️⃣思路解析
全排列遍历所有可能的情况
写在最后----惊喜活动
磊福利1
如果对学习没有自制力或者没有一起学习交流的动力，欢迎私信或者在文末添加我的VX，我会拉你进学习交流群，我们一起交流学习，报团打卡，群内更有众多福利等你来解锁哟，赶快加入我们吧！
也欢迎大家加入企业微信，更有超多IT就业福利等你来领取嗷~
賂福利2
1️⃣课程配备PPT【原创版权，侵权必究】：如果想快速上手python的小伙伴们，这个详细整理PPT可以迅速帮助大家打牢python基础，需要的小伙伴们可以下载一下
Python入门基础教程全套+小白速成+学不会来找我！
2️⃣ 这是用Python做过的表白神器和表白圣诞树，需要的小伙伴自取：
Python表白神器，源码+解析+各种完美配置+浪漫新颖
3️⃣ 圣诞树表白源码+素材+拿去直接用
是Dream呀博主正在参与2021年CSDN博客之星评选活动！希望你可以五星支持哟！感谢~
期待你的五星好评----2021年「博客之星」参赛博主：是Dream呀
点击上方即可投票✌✌✌✌✌✌✌✌✌✌
往期文章----好文推荐
磊 我与CSDN的2021 --从路人到一名万粉博主的自述
賂 python跨年表白神器–你值得拥有
雷 圣诞节来了，怎能还没有圣诞树呢 快来为心爱的她送上专属的圣诞礼物叭~
好啦，这就是今天要分享给大家的全部内容了，我们下期再见！✨ ✨ ✨
如果你喜欢的话，就不要吝惜你的一键三连了~
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）