📢📢📢📣📣📣🌻🌻🌻Hello，大家好我叫是 Dream 呀，一个有趣的 Python 博主，多多关照😜😜😜🏅🏅🏅CSDN Python 领域优质创作者，大二在读，欢迎大家找我合作学习（文末有 VX 想进学习交流群 or 学习资料 欢迎+++）💕 入门须知：这片乐园从不缺乏天才，努力才是你的最终入场券！🚀🚀🚀💓最后，愿我们都能在看不到的地方闪闪发光，一起加油进步🍺🍺🍺🍉🍉🍉“一万次悲伤，依然会有 Dream，我一直在最温暖的地方等你”，唱的就是我！哈哈哈~🌈🌈🌈🌟🌟🌟✨✨✨
@TOC
1️⃣第一题 带分数
问题描述 100 可以表示为带分数的形式：100 = 3 + 69258 / 714。还可以表示为：100 = 82 + 3546 / 197。注意特征：带分数中，数字 1~9 分别出现且只出现一次（不包含 0）。类似这样的带分数，100 有 11 种表示法。
输入格式： 从标准输入读入一个正整数 N (N<1000*1000)
输出格式： 程序输出该数字用数码 1~9 不重复不遗漏地组成带分数表示的全部种数。 注意：不要求输出每个表示，只统计有多少表示法！
样例输入1100样例输出111
样例输入2105样例输出26
复制代码
2️⃣代码分享
# 一万次悲伤，依然会有Dream，我一直在最温暖的地方等你！# @Time : 2022/1/12 17:55# @Author : 是Dream呀！# @File : 第一题 带分数.py# n = a + b/c# b = c(n-a)n = input('请输入你要求的n:')count = 0for 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 += 1print(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.李白打酒.pyresult = 0def 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 resultprint(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 + - + -
则程序应该输出： 10 资源约定： 峰值内存消耗 < 512M CPU 消耗 < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意: main 函数需要返回 0 注意: 只使用 ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。 注意:所有依赖的函数必须明确地在源文件中 #include <xxx>， 不能通过工程
2️⃣代码分享
# 一万次悲伤，依然会有Dream，我一直在最温暖的地方等你！# @Time : 2022/1/15 14:31# @Author : 是Dream呀！# @File : 第四题 穿越雷区.pyn=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,jmap1=[[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]=0dx=[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 的为可 以通行的地方。
迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这 个它的上、下、左、右四个方向之一。 对于上面的迷宫，从入口开始，可以按 DRRURRDDDR 的顺序通过迷宫， 一共 10 步。其中 D、U、L、R 分别表示向下、向上、向左、向右走。 对于下面这个更复杂的迷宫（30 行 50 列），请找出一种通过迷宫的方式， 其使用的步数最少，在步数最少的前提下，请找出字典序最小的一个作为答案。 请注意在字典序中 D<L<R<U。（如果你把以下文字复制到文本文件中，请务 必检查复制的内容是否与文档中的一致。在试题目录下有一个文件 maze.txt， 内容与下面的文本相同）
答案提交这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一 个字符串，包含四种字母 D、U、L、R，在提交答案时只填写这个字符串，填 写多余的内容将无法得分
2️⃣代码分享
m = '''010101010010110010010101100101101001000010001010100000100010000010101001000010000000100110011010010101111011010010001000001101001011100011000000010000010000000010101000110100001010000010101010110010110001111100000010100001001010001010000010110000000011001000110101000010101100011010011010101011110111000110110101010010010010100000010001010011100000001010000010100010011010101011111001100001000011101000111000001010100001100010000001000101001100001001110001101000011100100010010101010101010100011010000001000010010000010100101010111010001010101000010111100100101001001000010000010101010100100100010100000000100000001010110011110100011000001010101000111010101001110000100001100001011001111011010000100010101010100001101010100101000010100000111011101001100000001011000100001011001011010010111000000001001010100100000001010010000100010000010001111010100100101001010101101001010100011010101101110000110101110010100001000011000000101001010000010001110000100000100011000011010110100000010010100100100001110110100101000101000000001110110010110101101010100001001010000100001101010100001000100010010001000101011010000100011001000100001010100101010101111101001000000100101000000110010100101001000001000000000010110100000010011101110010010000111010010110111010000000011010001000100010000000100001110100000011001110101000101000100010001111100010101001010000001000100000101001010010101100000001001010100010111010000011110000100001000000011011100000000100000000101110000001100111010111010001000110111010101101111000'''
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 = 0def 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] = Truedfs(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 = 0dfs([0]*n, 0, 'black')
print(ans)
复制代码
💕💕💕 好啦，这就是今天要分享给大家的全部内容了，我们下期再见！✨ ✨ ✨🍻🍻🍻如果你喜欢的话，就不要吝惜你的一键三连了~
评论