[数据结构与算法]【思特奇杯·云上蓝桥-算法集训营】第1周----真题汇总+思路分析

📢📢📢📣📣📣
🌻🌻🌻Hello，大家好我叫是Dream呀，一个有趣的Python博主，多多关照😜😜😜
🏅🏅🏅CSDN Python领域优质创作者，大二在读，欢迎大家找我合作学习（文末有VX 想进学习交流群or学习资料 欢迎+++）
💕入门须知：这片乐园从不缺乏天才，努力才是你的最终入场券！🚀🚀🚀
💓最后，愿我们都能在看不到的地方闪闪发光，一起加油进步🍺🍺🍺
🍉🍉🍉“一万次悲伤，依然会有Dream，我一直在最温暖的地方等你”，唱的就是我！哈哈哈~🌈🌈🌈
🌟🌟🌟???

1??第一题 跑步训练

问题描述*
小明要做一个跑步训练，初始时，小明充满体力，体力值计为 10000。
如果小明跑步，每分钟损耗 600 的体力。
如果小明休息，每分钟增加 300 的体力。
体力的损耗和增加都是 均匀变化的。
小明打算跑一分钟、休息一分钟、再跑一分钟、再休息一分钟……如此循环。
如果某个时刻小明的体力到达 0，他就停止锻炼，请问小明在多久后停止锻炼。
为了使答案为整数，请以秒为单位输出答案，答案中只填写数，不填写单位。
答案提交：
这是一道结果填空题，你只需要算出结果后提交即可。
本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法
得分。

2??代码分享

# 一万次悲伤，依然会有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 的阶乘）有多少个约数。
答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。
本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无
法得分。

2??代码分享

# 一万次悲伤，依然会有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<i:
        if i %j==0:
            break
        j+=1
    else:
        p.append(i)
# 运用字典记录不同的质数
dic = {}  # 创建字典
for i in p:
    # 字典中的每个键对应的值都为1
    dic[i]=1
for i in range(2,n+1):
    for j in p:
        # 如果属于其中的素数，相应的字典中键对应的值的大小+1
        while i%j == 0:
            i /= j
            dic[j] += 1
# 100之内所有素数其出现的次数进行相乘。
numbers = 1
for i in dic.values():
    numbers *= i
print(numbers)

运行结果
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??思路解析

1. 首先这道题读来读去的意思就是，要找10000以内的两两一对的素数组合，然后取两两组合中的小的那一个，再将所有组合中的小的素数进行比较，取最大的那个，得到我们想要的答案。
2. 那就是首先写出一个函数来确定是否是素数，然后再写出一个函数，使其可以得到所有的素数组合，之后再取其较小者，然后所有较小者比较得到其中的最大者！

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<M,N<500）,分别表示A、B的人数，保证人数合理性。

要求输出一个整数，表示可以产生的花样种数。

例如： 用户输入： 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跨年表白神器–你值得拥有
🥉 圣诞节来了，怎能还没有圣诞树呢 快来为心爱的她送上专属的圣诞礼物叭~

💕💕💕 好啦，这就是今天要分享给大家的全部内容了，我们下期再见！? ? ?
🍻🍻🍻如果你喜欢的话，就不要吝惜你的一键三连了~