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

【思特奇杯·云上蓝桥-算法集训营】第一周

1️⃣第一题 带分数

问题描述
100 可以表示为带分数的形式：100 = 3 + 69258 / 714。
还可以表示为：100 = 82 + 3546 / 197。
注意特征：带分数中，数字1~9分别出现且只出现一次（不包含0）。
类似这样的带分数，100 有 11 种表示法。

输入格式： 从标准输入读入一个正整数N (N<1000*1000)

输出格式： 程序输出该数字用数码1~9不重复不遗漏地组成带分数表示的全部种数。 注意：不要求输出每个表示，只统计有多少表示法！

样例输入1
100
样例输出1
11

样例输入2
105
样例输出2
6

2️⃣代码分享

# 一万次悲伤，依然会有Dream，我一直在最温暖的地方等你！
# @Time    : 2022/1/12 17:55
# @Author  : 是Dream呀！
# @File    : 第一题 带分数.py
# n = a + b/c
# b = c(n-a)
n = input('请输入你要求的n:')
count = 0
for a in range(1,int(n)):
    for c in range(int('9'*(5-len(n))),int('9'*(6-len(n)))):
        b = int(c)*(int(n)-a)
        list1 = list(str(a))+list(str(b))+list(str(c))
        if list1.count('1')==1 and list1.count('2')==1 and list1.count('3')==1 and list1.count('4')==1 and list1.count('5')==1 and list1.count('6')==1 and list1.count('7')==1 and list1.count('8')==1 and list1.count('9')==1 and list1.count('0')==0:
            count += 1
print(count)

3️⃣思路解析

哎，怎么说呢，那个正规解法中排列树的深度优先搜索方法我是真的看不懂，什么剪枝不剪枝的我是真的头大。于是乎我就看到了这个暴力解法，深得我心，得意：

• 这个就是把a,b,c放到一个列表里，用count函数确定是否1-9每一个元素都在其中，并且次数唯一
• 输入的n不能是整数，要是字符串，便于以后字符串拼接
• n = a + b/c， b = c(n-a)，先遍历a，然后再确定c，最后表达出b来，三个元素拼接成一个完整的字符串。
• 求c时，c是分母，要比分子b小，所以说看可以通过其位数确定其范围，进一步缩小遍历的范围，位数是6-len(n)，即在int('9'*(5-len(n))),int('9'*(6-len(n)))之间。

1️⃣第二题 李白打酒

题目描述
话说大诗人李白，一生好饮。幸好他从不开车。一天，他提着酒壶，从家里出来，酒壶中有酒2斗。他边走边唱：无事街上走，提壶去打酒。逢店加一倍，遇花喝一斗。

这一路上，他一共遇到店5次，遇到花10次，已知最后一次遇到的是花，他正好把酒喝光了。

请你计算李白遇到店和花的次序，可以把遇店记为a，遇花记为b。则：babaabbabbabbbb 就是合理的次序。像这样的答案一共有多少呢？请你计算出所有可能方案的个数（包含题目给出的）。

2️⃣代码分享

# 一万次悲伤，依然会有Dream，我一直在最温暖的地方等你！
# @Time    : 2022/1/13 21:19
# @Author  : 是Dream呀！
# @File    : 第二题 2.李白打酒.py
result = 0
def count(a,b,alcohol):
    # a表示遇到店家，b表示遇到叫花，alcohol便是酒的量
    global result
    if a>0:
        count(a-1,b,alcohol*2)
    if b>0:
        count(a,b-1,alcohol-1)
    if a==0 and b==0 and alcohol == 1:
        result +=1
    return result
print(count(5,9,2))

3️⃣思路解析

• 遇到店家每次*2，遇到乞丐每次-1，并且次数已知，我们可以采用递归的方法来做这道题
• 定义count(a,b,alcohol):函数，其中a表示遇到店家，b表示遇到叫花，alcohol便是酒的量
• 当满足if a==0 and b==0 and alcohol == 1:此条件时，结果+1，表示方法种类+1，因为每次遍历result要保持之前的数据，所以要提前global全局定义result

1️⃣第三题 第39级台阶

题目描述：
小明刚刚看完电影《第39级台阶》，离开电影院的时候，他数了数礼堂前的台阶数，恰好是39级!
站在台阶前，他突然又想着一个问题：
如果我每一步只能迈上1个或2个台阶。先迈左脚，然后左右交替，最后一步是迈右脚，也就是说一共要走偶数步。那么，上完39级台阶，有多少种不同的上法呢？
输出格式：
输出一个整数

2️⃣代码分享

def left(n):
    if n == 1:  # 第一次迈左脚
        return 1
    elif n == 2:
        return 1
    else:
        return right(n-1)+right(n-2)  # 大于等于三个台阶时，上一次右脚可能迈两个或者一个

def right(n):
    if n == 1:
        return 0
    elif n == 2:
        return 1
    else:
        return left(n-1)+left(n-2)  # 大于等于三个台阶时，上一次右脚可能迈两个或者一个

print(right(39))  # 最后一次39步是迈得右脚

3️⃣思路解析

• 设置左右脚两个函数
• 大于等于三个台阶时，上一次右脚可能迈两个或者一个
• print(right(39))最后一次迈右脚

1️⃣第四题 穿越雷区

题目描述
已知的地图是一个方阵，上面用字母标出了A，B区，其它区都标了正号或负号分别表示正负能量辐射区。
例如：

A + - + -
- + - - +
- + + + -
+ - + - +
B + - + -

坦克车只能水平或垂直方向上移动到相邻的区。

数据格式要求：
输入第一行是一个整数n，表示方阵的大小， 4<=n<100
接下来是n行，每行有n个数据，可能是A，B，+，-中的某一个，中间用空格分开。
A，B都只出现一次。
要求输出一个整数，表示坦克从A区到B区的最少移动步数。
如果没有方案，则输出-1

例如： 用户输入： 5 A + - + -

• • • • • B + - + -

则程序应该输出： 10 资源约定： 峰值内存消耗 < 512M CPU消耗 < 1000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。

所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。

注意: main函数需要返回0 注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。 注意:
所有依赖的函数必须明确地在源文件中 #include <xxx>， 不能通过工程

2️⃣代码分享

# 一万次悲伤，依然会有Dream，我一直在最温暖的地方等你！
# @Time    : 2022/1/15 14:31
# @Author  : 是Dream呀！
# @File    : 第四题 穿越雷区.py
n=int(input())
df=[[0 for i in range(n)] for j in range(n)]
for i in range(n):
    STR=input().split()
    for j in range(len(STR)):
        df[i][j]=STR[j]
        if STR[j]=="A":
            a,b=i,j
        elif STR[j]=="B":
            a1,b1=i,j
map1=[[1000000 for x in range(n+1)] for y in range(n+1)]
used=[[0 for x in range(n+1)] for y in range(n+1)]
map1[0][0]=0
dx=[1,-1,0,0]
dy=[0,0,-1,1]
tank=[]
tank.append([a,b])
while (tank):
    h=tank[0]
    del tank[0]
    if h[0]==a1 and h[1]==b1:
        break
    for i in range(4):
        nx=h[0]+dx[i]
        ny=h[1]+dy[i]
        if nx>=0 and nx<=n-1 and ny>=0 and ny<=n-1 and df[h[0]][h[1]]!=df[nx][ny] and used[nx][ny] == 0 and df[nx][ny]!="A":
            map1[nx][ny]=map1[h[0]][h[1]]+1
            used[nx][ny]=1
            tank.append([nx,ny])
if map1[a1][b1]!=1000000:
    print(map1[a1][b1])
else:
    print(-1)

1️⃣第五题 迷宫

题目描述
下图给出了一个迷宫的平面图，其中标记为 1 的为障碍，标记为 0 的为可 以通行的地方。

010000
000100
001001
110000

迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这 个它的上、下、左、右四个方向之一。 对于上面的迷宫，从入口开始，可以按DRRURRDDDR 的顺序通过迷宫， 一共 10 步。其中 D、U、L、R 分别表示向下、向上、向左、向右走。 对于下面这个更复杂的迷宫（30 行 50 列），请找出一种通过迷宫的方式， 其使用的步数最少，在步数最少的前提下，请找出字典序最小的一个作为答案。 请注意在字典序中D<L<R<U。（如果你把以下文字复制到文本文件中，请务 必检查复制的内容是否与文档中的一致。在试题目录下有一个文件 maze.txt， 内容与下面的文本相同）

答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一 个字符串，包含四种字母 D、U、L、R，在提交答案时只填写这个字符串，填 写多余的内容将无法得分

2️⃣代码分享

m = '''01010101001011001001010110010110100100001000101010
00001000100000101010010000100000001001100110100101
01111011010010001000001101001011100011000000010000
01000000001010100011010000101000001010101011001011
00011111000000101000010010100010100000101100000000
11001000110101000010101100011010011010101011110111
00011011010101001001001010000001000101001110000000
10100000101000100110101010111110011000010000111010
00111000001010100001100010000001000101001100001001
11000110100001110010001001010101010101010001101000
00010000100100000101001010101110100010101010000101
11100100101001001000010000010101010100100100010100
00000010000000101011001111010001100000101010100011
10101010011100001000011000010110011110110100001000
10101010100001101010100101000010100000111011101001
10000000101100010000101100101101001011100000000100
10101001000000010100100001000100000100011110101001
00101001010101101001010100011010101101110000110101
11001010000100001100000010100101000001000111000010
00001000110000110101101000000100101001001000011101
10100101000101000000001110110010110101101010100001
00101000010000110101010000100010001001000100010101
10100001000110010001000010101001010101011111010010
00000100101000000110010100101001000001000000000010
11010000001001110111001001000011101001011011101000
00000110100010001000100000001000011101000000110011
10101000101000100010001111100010101001010000001000
10000010100101001010110000000100101010001011101000
00111100001000010000000110111000000001000000001011
10000001100111010111010001000110111010101101111000'''

m = m.split('\n')

visit = [[False] * 50 for _ in range(30)]
visit[0][0] = True

step = [(1, 0, 'D'), (0, -1, 'L'), (0, 1, 'R'), (-1, 0, 'U')]


queue = [(0, 0, -1, 0)] # 坐标、父节点在path中的下标、走的方向对应的字母
path = []
while queue:
    y, x, _, _  = cur = queue.pop(0)
    path.append(cur)

    if cur[:2] == (29, 49):
        # 走到终点
        temp = []
        i = len(path) - 1
        while i > 0: # 沿着之前标记的父节点将路径取出
            temp.append(path[i][3])
            i = path[i][2]
        temp.reverse() # 反转，因为取出来的路径是反的
        print(''.join(temp))
        break

    for dy, dx, dir in step: # 往上下左右走一步
        ny, nx = y+dy, x+dx # 下一步到达的位置
        if -1 < nx < 50  and -1 < ny < 30 and m[ny][nx] == '0' and not visit[ny][nx]:
            # 判断是否越界、迷宫该位置是否能走、是否已经走过
            queue.append((ny, nx, len(path)-1, dir)) # 将下一步添加到队列中，len(path)-1 是添加到节点的父节点在path中的下标
            visit[ny][nx] = True # 标记已经访问过

1️⃣第六题 跳马

问题描述：
中国象棋半张棋盘如图1所示。马自左下角(0,0)向右上角（m，n）跳。规定只能往右跳，不准往左跳。比如图1中所示为一种跳行路线，并将路径总数打印出来。

输入格式：
只有一行：两个数n，m
输出格式：
只有一个数：总方案数total。

2️⃣代码分享

a, b, c, d = map(int, input().split(' '))

step = [(1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1)]

visit = [[False]*8 for _ in range(8)]


queue = [(a, b, 0)] # 坐标、步数

while queue:
    y, x, t = queue.pop(0)

    if y == c and x == d:
        print(t)
        break

    for dy, dx in step:
        ny = y + dy
        nx = x + dx
        if -1 < ny < 8 and -1 < nx < 8 and not visit[ny][nx]:
            queue.append((ny, nx, t+1))
            visit[ny][nx] = True
    
if not queue:
    print(-1)

3️⃣思路解析

• 使用广度搜索方法，记录步数，标记访问过的点。

1️⃣第七题 路径之谜

2️⃣代码分享

n = int(input())

nums = [list(map(int, input().split(' '))) for _ in range(2)] # 第一行是上面的，第二行是左面的

visit = [[False]*n for _ in range(n)]
visit[0][0] = True

ans = [0]

record = [[0]*n for _ in range(2)]
record[0][0] = record[1][0] = 1

step = [(0, -1), (0, 1), (-1, 0), (1, 0)]

def dfs(y, x):
    if y == n-1 and x == n-1 and record == nums:
        print(' '.join(map(str, ans)))
        return
    for dy, dx in step:
        ny = y + dy
        nx = x + dx
        if -1 < ny < n and -1 < nx < n and not visit[ny][nx]:
            ans.append(ny*n + nx)
            visit[ny][nx] = True
            record[0][nx] += 1
            record[1][ny] += 1

            dfs(ny, nx)

            ans.pop()
            visit[ny][nx] = False
            record[0][nx] -= 1
            record[1][ny] -= 1
            
dfs(0, 0)

1️⃣第八题 未名湖边的烦恼

2️⃣代码分享

m, n = map(int, input().split(' '))

record = [[-1]*(n+1) for _ in range(m+1)]

def dfs(a, b): # 还鞋、借鞋
    if a == b == 0:
        return 1
    
    if record[a][b] != -1:
        ans = record[a][b]
    else:
        ans = 0
        if a > 0:
            ans += dfs(a-1, b)
        if 0 < b <= a:
            ans += dfs(a, b-1)
        record[a][b] = ans
    
    return ans

print(dfs(m, n))

1️⃣第九题 大臣的旅费

2️⃣代码分享

n = int(input())
lis = [list(map(int, input().split(' '))) for _ in range(n-1)]
m = {i: [] for i in range(1, n+1)}
for i in lis:
    m[i[0]].append(i[1:])
    m[i[1]].append((i[0], i[2]))

visit = [False] * (n+1)

node = max_length = 0
def dfs(x, length):
    global max_length
    if length > max_length:
        global node
        max_length, node = length, x
    
    for nx, l in m[x]:
        if not visit[nx]:
            visit[nx] = True
            dfs(nx, length+l)
            visit[nx] = False

dfs(1, 0)

visit = [False] * (n+1)
visit[node] = True
dfs(node, 0)


print(max_length * 11 + max_length*(max_length-1)//2)

1️⃣第十题 2n皇后问题

2️⃣代码分享

def check(record, i, j):
    # 根据之前已有的，判断第i行第j列可不可以放
    for k in range(i): # 遍历前面所有的行，k:之前某一行
        if j == record[k] or abs(record[k] - j) == abs(i - k):
            return False
    return True
    

def dfs(record, i, color):
    if i == n: # 到达最后一行，也就是说所有皇后都可以摆上
        if color == 'black':
            dfs([0]*n, 0, 'white')
        else:
            global ans
            ans += 1
        return

    for j in range(n):
        # 检查当前第i行的皇后放在第j列是否合法
        if m[i][j] == '1':
            if check(record, i, j):
                m[i][j] = '2'
                record[i] = j
                dfs(record, i+1, color)
                m[i][j] = '1'
            

n = int(input())
m = [input().split(' ') for _ in range(n)]

ans = 0
dfs([0]*n, 0, 'black')

print(ans)

七----十题思路解析

第二周蓝桥训练营题解（python）

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