营销推广型网站,专门做特产的网站,定制头像的网站,网站设计博客今日复习内容#xff1a;做题
例题1#xff1a;仙境诅咒
问题描述#xff1a;
在一片神秘的仙境中#xff0c;有N位修仙者#xff0c;他们各自在仙境中独立修炼#xff0c;拥有他们独特的修炼之地和修炼之道#xff0c;修炼者们彼此之间相互尊重#xff0c;和平相处…今日复习内容做题
例题1仙境诅咒
问题描述
在一片神秘的仙境中有N位修仙者他们各自在仙境中独立修炼拥有他们独特的修炼之地和修炼之道修炼者们彼此之间相互尊重和平相处。
然而有一天仙境的主宰者妮妮第一位修仙者收到了诅咒该诅咒会向距离妮妮不超过D的范围内范围内的修仙者传播。也就是说如果一个修仙者被诅咒那么在距他不超过D的范围内的修仙者都会收到诅咒。
现在你需要预测哪些修仙者最终会被诅咒以便及时采取措施保护仙境的和平与安宁。
输入格式
第一行输入一个正整数N(1 N 10^3)表示仙境中有N位修仙者。
接下来N行每行两个实数Xi和Yi(-10^3 Xi,Yi 10^3)表示第i位修仙者的坐标(Xi,Yi)第一位修仙者即仙境的主宰者妮妮。
最后一行输入一个整数D(1 D 10^3)表示诅咒传播的范围。
输出格式
输出N行每行一个整数第i行整数为1表示第i位修仙者最终被诅咒若为0则没有被诅咒。
参考答案
def dis(x1,y1,x2,y2):return (x1 - x2) ** 2 (y1 - y2) ** 2 D ** 2
def dfs(x,y):for i in range(n):if not vis[i] and dis(x,y,wh[i][0],wh[i][1]):vis[i] Truedfs(wh[i][0],wh[i][1])n int(input())
wh [list(map(int,input().split())) for i in range(n)]
D int(input())
vis [False] * n
vis[0] True
dfs(wh[0][0],wh[0][1])
for i in vis:print(int(i))
运行结果 以下是我对此题的理解
用深度优先搜索首先定义一个函数dis用来判断两个修仙者之间的距离是否超过D然后再定义一个函数dfs用来递归地搜索收到诅咒的修仙者。接着读取输入初始化修仙者的坐标和诅咒的范围。然后标记仙境的主宰者妮妮已经收到诅咒从主宰者的位置开始进行dfs搜索将与主宰者的距离小于等于D的修仙者标记为收到诅咒最后输出每个修仙者是否收到诅咒的标记。
整体思路就是从主宰者妮妮开始逐个遍历与其距离小于等于D的修仙者并将其标记为收到诅咒。
dfs(x1,y1,x2,y2):
return (x1 - x2) ** 2 (y1 - y2) ** 2 D ** 2
这是一个函数dis用于计算两个修仙者之间的距离是否小于等于给定范围D的平方。通过欧氏距离的平方来比较两个修仙者之间的距离与给定距离之间的大小关系以避免使用开方运算提高效率。
def dfs(x,y):
定义一个函数
for i in range(n):这个循环遍历所有的修仙者其中n是修仙者的总数
if not vis[i] and dis(x,y,wh[i][0],wh[i][1])这个条件判断语句检查当前遍历到的修仙者是否未被访问和且与当前正在搜索的点的距离小于等于D如果满足这两个条件
vis[i] True
将满足条件的修仙者标记为已收到诅咒。
dfs(wh[i][0],wh[i][1])递归地调用dfs函数以当前修仙者的坐标(wh[i][0],wh[i][1])为新的起点继续进行深度搜索寻找与该修仙者距离小于等于D的其他修仙者。
n int(input())
wh [list(map(int,input().split())) for i in range(n)]
D intinput()
vis [False] * n
vis[0] True
dfs(wh[i][0],wh[i][1])
这部分代码用于读入和初始化。首先读取输入的修仙者数量n然后依次读入每个修仙者的坐标和诅咒的范围然后初始化一个布尔数组vis用于标记修仙者是否收到诅咒。初始时仙境的主宰者妮妮被标记为已收到诅咒即vis[] True然后从主宰者妮妮的位置开始调用dfs函数进行DFS搜索。
for i in vis:
print(int(i))
输出每个修仙者是否收到诅咒的标记即输出布尔数组vis中的各个元素。 例题2小怂爱水洼
问题描述
小怂喜欢收集水洼里的水他每到一个水量不为0的水洼中就会收集里面所有的水。
小怂去到了一个大小为N * M的水洼水洼上的每一个小水洼水量为ai,j(i属于[1,n],j属于[1,m])假设小怂的起点是(1,1)他可以移动无数次每次移动只能移动到当前水洼上下左右四个方向的相邻小水洼上并且需要满足相邻小水洼的水量大于0即如果新的小水洼量为0小怂就不能走到这个小水洼上。特别地小怂可以重复走到某块小水洼但是小水洼中的水只能被收集一次如果起始点的水洼有水他会收集那些水。
值得注意的是每块上下左右相邻且水量不为0的小水洼可以汇集成一个大水洼小怂每到一个新的大水洼他之前收集到的水量会变为0。
求解小怂在大水洼中可以收集到的最大水量。
输入格式
第一行是两个整数N和M分别表示行数和列数。
接下来N行每行包括M个整数每个整数表示当前位置的小水洼的水量。
数据范围保证1 N,M 1001 ai,j 10^6数据不保证起始点不为0
输出格式
输出共一行一个整数表示小怂在水洼中可以收集到的最大水量。
参考答案
import sys
sys.setrecursionlimit(1000000)
inds [[1,0],[-1,0],[0,1],[0,-1]]
def dfs(x,y):vis[x][y] Trueans water[x][y]for ind in inds:cur_x x ind[0]cur_y y ind[1]if n cur_x 0 and m cur_y 0 and not vis[cur_x][cur_y] and water[cur_x][cur_y] ! 0:ans dfs(cur_x,cur_y)return ans
n,m map(int,input().split())
water [list(map(int,input().split())) for i in range(n)]
vis [[False] * m for i in range(n)]
ans 0
for i in range(n):for j in range(m):if not vis[i][j] and water[i][j] ! 0:ans max(ans,dfs(i,j))
print(ans)运行结果 以下是我对此题的理解
对于这道题我的思路是
1.导入模块和设置递归深度限制
导入sys 模块并设置递归深度限制
2.定义移动方向和dfs函数
定义了一个列表用来记录小怂可以走的4个方向上下左右
定义了深度优先搜索函数dfs用来从当前水洼的位置(x,y)开始递归地搜索可以收集水的水洼并返回小怂在该大水洼中能收集到的水量。
3.初始化水洼信息和访问标记
读取输入大小为N * M 的水洼其中每个小水洼的水量用二维列表water表示并初始化一个二维布尔数组vis用于标记该水洼是否被访问过。
4.dfs搜索和计算最大水量
使用两层循环来遍历所有水洼
对于某个未被访问且水量不为0的水洼调用dfs函数进行搜索并更新最大水量。
在dfs函数中首先标记当前水洼为已访问并初始化当前水洼的水量为最大水量。然后依次尝试向4个方向移动并递归地计算可以收集到的水量。最后返回当前水洼可以收集到的水量。
在移动过程中如果移动到一个新的大水洼则当前收集到的水量变为0因为小怂已经收集过当前水洼的水了。
5.输出结果 例题3串变换
问题描述
有两个长度为n的数字字符串S和T下标从0开始。
一共有k个操作操作只可能是一下两种类型
1 x y 表示将Sx变为(Sx v) mod 10;2 x y 表示交换Sx,Sy
你可以挑选出任意个操作以任意顺序执行但是每个操作只能最多执行一次 如果可以将S串变为T串则输出Yes,否则输出No。
输入格式
第一行输入一个正整数n用于表示S和T的长度
第二行输入一个只由数字组成长度为n的字符串S
第三行输入一个只由数字组成长度为n的字符串T
第四行输入一个正整数k表示操作次数。
接下来k行每行3个整数其中第i行表示第i种操作的3个参数opi,xi,yi。
输出格式
一行一个字符串
如果可以通过操作使得S串等于T串则输出Yes否则输出No。
参考答案
flag False
def check(path):global flagstr_ list(map(int,list(s)))for i in path:if ops[i][0] 1:str_[ops[i][1]] ops[i][2]str_[ops[i][1]] % 10else:str_[ops[i][1]],str_[ops[i][2]] str_[ops[i][2]],str_[ops[i][1]]if .join(list(map(str,str_))) t:flag Truedef dfs(depth):if flag:returnif depth k:check(path)returnfor i in range(k):if not vis[i]:vis[i] Truepath.append(i)dfs(depth 1)vis[i] Falsepath.pop()dfs(k)n int(input())
s input()
t input()
k int(input())
ops [list(map(int,input().split())) for i in range(k)]
path []
vis [False] * k
dfs(0)
if flag:print(Yes)
else:print(No)
运行结果 OK这几个题有点难所以我就只写这些下一篇继续
