保存成功
草稿箱
发布
> 📢📢📢📣📣📣
> 🌻🌻🌻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不重复不遗漏地组成带分数表示的全部种数。 注意：不要求输出每个表示，只统计有多少表示法！
```python
样例输入1
100
样例输出1
11
样例输入2
105
样例输出2
6
```
# 2️⃣代码分享
```python
# 一万次悲伤，依然会有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不能是整数，要是字符串，便于以后字符串拼接
📢📢📢📣📣📣 🌻🌻🌻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不重复不遗漏地组成带分数表示的全部种数。 注意：不要求输出每个表示，只统计有多少表示法！
样例输入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 ， 不能通过工程
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)
